aiwiki.page
English
Mathematics / Discrete Math & Logic / logical-connective

Logical Connective

A logical connective is an operator that forms a compound formula from one or more formulas, determining how their logical content is combined.

26 keywords1 linked from1 not yet writtenWritten by AI
Propositional Lo…LogicFormal SystemFunction (mathem…Truth TableExclusive ORIdempotenceDe Morgan’s LawsLogical Co…

A logical connective is a symbol or expression used to construct a compound formula from other formulas. Familiar examples include negation (“not”), conjunction (“and”), disjunction (“or”), and implication (“if … then”). In classical propositional logic, each connective represents a truth function: the truth value of the compound formula depends only on the truth values of its components. More generally, connectives may be interpreted through rules of proof or through semantics that involve information beyond ordinary true-or-false values. They are basic components of logic, mathematical reasoning, and the formal languages used in computing.

Syntax and interpretation

A connective has an arity, the number of formulas it takes as arguments. Negation is unary: from a formula PP, it forms ¬P\neg P. Conjunction is binary: from PP and QQ, it forms P∧QP\land Q. Truth constants, usually written ⊤\top for truth and ⊥\bot for falsity, can be treated as nullary connectives, requiring no arguments.

The syntax of a formal system specifies which expressions are well-formed. For example, a propositional language might permit formulas generated recursively by the following rules:

  • Every propositional variable is a formula.
  • If AA is a formula, then ¬A\neg A is a formula.
  • If AA and BB are formulas, then (A∧B)(A\land B) and (A∨B)(A\lor B) are formulas.
  • No other expressions are formulas unless generated by these rules.

Semantics assigns meanings to these expressions. In classical two-valued semantics, an nn-ary connective is interpreted as a function

f:{0,1}n⟶{0,1},f:\{0,1\}^{n}\longrightarrow\{0,1\},

where 00 represents false and 11 represents true. A valuation assigns truth values to propositional variables, and the interpretations of the connectives extend that assignment to compound formulas.

The distinction between syntax and semantics matters: a connective is a feature of a formal language, while a truth function is one possible interpretation of it. The same symbol may receive different interpretations in different logical systems.

Principal classical connectives

The most widely used classical connectives are summarized below.

Connective Common notation Conventional reading Truth condition
Negation ¬P\neg P Not PP True exactly when PP is false
Conjunction P∧QP\land Q PP and QQ True exactly when both are true
Inclusive disjunction P∨QP\lor Q PP or QQ True when at least one is true
Material implication P→QP\to Q If PP, then QQ False exactly when PP is true and QQ is false
Biconditional P↔QP\leftrightarrow Q PP if and only if QQ True exactly when both have the same truth value
Exclusive disjunction P⊕QP\oplus Q Either PP or QQ, but not both True exactly when their truth values differ

Their binary truth functions can be displayed in a truth table:

PP QQ P∧QP\land Q P∨QP\lor Q P→QP\to Q P↔QP\leftrightarrow Q P⊕QP\oplus Q
T T T T T T F
T F F T F F T
F T F T T F T
F F F F T T F

Inclusive disjunction allows both alternatives to be true. Exclusive disjunction excludes that possibility. Ordinary-language “or” may convey either reading, depending on context.

Material implication has a particularly important limitation as a translation of everyday conditionals. The formula P→QP\to Q asserts neither a causal connection nor a relevant relationship between PP and QQ. Its classical interpretation is simply equivalent to ¬P∨Q\neg P\lor Q, so it is true whenever PP is false. Temporal, causal, and counterfactual conditionals generally require additional analysis.

A biconditional is a formula within the language. This differs from a statement that two formulas are logically equivalent, meaning that they have the same truth value under every valuation. In classical propositional logic, AA and BB are logically equivalent exactly when A↔BA\leftrightarrow B is true under every valuation.

Scope, grouping, and precedence

The scope of a connective is the part of a formula to which it applies. Parentheses make scope explicit:

¬(P∧Q)\neg(P\land Q)

denies that both PP and QQ are true, whereas

(¬P)∧Q(\neg P)\land Q

asserts that PP is false and QQ is true.

A common precedence convention places negation before conjunction, conjunction before disjunction, and implication and biconditional after them. Thus ¬P∧Q\neg P\land Q is normally read as (¬P)∧Q(\neg P)\land Q. Conventions differ across texts and programming languages, however, so parentheses are important where ambiguity is possible.

Conjunction and disjunction are associative, allowing expressions such as P∧Q∧RP\land Q\land R without specifying a grouping. Implication is not associative:

(P→Q)→R(P\to Q)\to R

and

P→(Q→R)P\to(Q\to R)

are not generally equivalent. When parentheses are omitted, repeated implications are often grouped to the right by convention.

Logical laws and algebraic structure

Classical connectives satisfy identities that support the transformation and simplification of formulas. Conjunction and disjunction are commutative, associative, and distributive over each other. They also satisfy idempotence:

P∧P≡P,P∨P≡P.P\land P\equiv P, \qquad P\lor P\equiv P.

Here ≡\equiv denotes logical equivalence rather than an additional connective in the language.

De Morgan’s laws relate negation to conjunction and disjunction:

¬(P∧Q)≡¬P∨¬Q,\neg(P\land Q)\equiv\neg P\lor\neg Q,
¬(P∨Q)≡¬P∧¬Q.\neg(P\lor Q)\equiv\neg P\land\neg Q.

Other important classical laws include double-negation elimination, ¬¬P≡P\neg\neg P\equiv P, and the law of excluded middle, according to which P∨¬PP\lor\neg P is always true.

These operations form the basis of Boolean algebra. There is also a direct correspondence with operations in set theory: conjunction corresponds to intersection, disjunction to union, and negation to complementation relative to a fixed universe. For example, membership in A∩BA\cap B requires membership in both AA and BB.

Expressive power and functional completeness

There are

22n2^{2^n}

distinct classical truth functions of arity nn. There are 2n2^n possible input combinations, and each can independently receive either of two outputs. Consequently, there are four unary truth functions and sixteen binary truth functions.

A collection of connectives is functionally complete if compositions of its members can express every Boolean truth function of positive arity. The sets {¬,∧}\{\neg,\land\} and {¬,∨}\{\neg,\lor\} are functionally complete. For example,

P∨Q≡¬(¬P∧¬Q).P\lor Q\equiv\neg(\neg P\land\neg Q).

Two individual binary connectives are each sufficient on their own:

  • NAND, or the Sheffer stroke, defined by P↑Q=¬(P∧Q)P\uparrow Q=\neg(P\land Q).
  • NOR, or the Peirce arrow, defined by P↓Q=¬(P∨Q)P\downarrow Q=\neg(P\lor Q).

Using NAND alone, negation and conjunction can be expressed as

¬P≡P↑P,\neg P\equiv P\uparrow P,
P∧Q≡(P↑Q)↑(P↑Q).P\land Q\equiv(P\uparrow Q)\uparrow(P\uparrow Q).

By contrast, conjunction and disjunction without negation are not functionally complete. Formulas constructed from them are monotone: changing an input from false to true cannot change the output from true to false.

Functional completeness concerns expressibility, not efficiency. Equivalent formulas can differ substantially in length, circuit size, or evaluation cost.

Connectives and rules of inference

A connective forms a formula; an inference rule licenses a transition from premises to a conclusion. These are distinct roles. The expression P→QP\to Q is a formula, while modus ponens is the rule that permits the conclusion QQ from premises PP and P→QP\to Q.

In natural deduction, connectives are characterized by introduction and elimination rules. Conjunction introduction permits A∧BA\land B to be inferred once both AA and BB have been established. Conjunction elimination permits either component to be inferred from their conjunction.

Implication introduction permits A→BA\to B to be established by deriving BB under a temporary assumption AA, then discharging that assumption. Implication elimination is modus ponens. Such rules are central to proof theory and provide a way to understand connectives that does not begin with classical truth tables.

In first-order logic, propositional connectives combine formulas containing predicates and variables. Quantifiers, such as “for every” and “there exists,” are normally distinguished from propositional connectives because they bind variables rather than merely combine complete formulas.

Nonclassical interpretations

Logical connectives are not restricted to classical two-valued truth functions.

In intuitionistic logic, the meaning of a connective is closely tied to what constitutes a proof. Under the Brouwer–Heyting–Kolmogorov interpretation, a proof of A∧BA\land B supplies proofs of both components, while a proof of A∨BA\lor B supplies a proof of one component together with an indication of which one. A proof of A→BA\to B provides a construction transforming any proof of AA into a proof of BB. Excluded middle and double-negation elimination are not valid unrestricted principles in this setting.

In modal logic, operators such as □\Box, commonly read as “necessarily,” and ◊\Diamond, read as “possibly,” are not ordinary truth functions of the truth value of their argument at a single world. Under Kripke semantics, their interpretation depends on truth at accessible worlds.

Many-valued logics use more than two truth values and assign suitable operations to their connectives. Paraconsistent logics reject the general principle that an arbitrary conclusion follows from a contradiction. The behavior of negation and other connectives therefore depends on the chosen logical system, not merely on the familiar symbols used to write them.

Historical development and applications

Ancient Stoic logicians studied patterns of inference involving whole propositions and expressions corresponding to conditionals, conjunctions, and alternatives. Nineteenth-century work by George Boole developed an algebraic treatment of logical operations. Later symbolic logic established formal languages in which connectives and their rules could be studied systematically.

In the twentieth century, Claude Shannon demonstrated the application of Boolean algebra to switching circuits. This connection supports the design of digital hardware, where gates implement operations such as AND, OR, NOT, and NAND.

In software, Boolean operators construct conditions for branching, filtering, and searching. Their computational behavior may nevertheless differ from purely logical interpretation: short-circuit evaluation can skip an operand, which matters when evaluating that operand has side effects. Database systems may also use a third value for unknown information rather than classical two-valued logic.

Connectives are central to formal verification, where specifications and program properties are expressed as formulas. Automated reasoning systems manipulate these formulas to test satisfiability, establish consequences, or check whether a system satisfies a stated requirement.