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 , it forms . Conjunction is binary: from and , it forms . Truth constants, usually written for truth and 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 is a formula, then is a formula.
- If and are formulas, then and are formulas.
- No other expressions are formulas unless generated by these rules.
Semantics assigns meanings to these expressions. In classical two-valued semantics, an -ary connective is interpreted as a function
where represents false and 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 | Not | True exactly when is false | |
| Conjunction | and | True exactly when both are true | |
| Inclusive disjunction | or | True when at least one is true | |
| Material implication | If , then | False exactly when is true and is false | |
| Biconditional | if and only if | True exactly when both have the same truth value | |
| Exclusive disjunction | Either or , but not both | True exactly when their truth values differ |
Their binary truth functions can be displayed in a truth table:
| 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 asserts neither a causal connection nor a relevant relationship between and . Its classical interpretation is simply equivalent to , so it is true whenever 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, and are logically equivalent exactly when 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:
denies that both and are true, whereas
asserts that is false and is true.
A common precedence convention places negation before conjunction, conjunction before disjunction, and implication and biconditional after them. Thus is normally read as . 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 without specifying a grouping. Implication is not associative:
and
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:
Here denotes logical equivalence rather than an additional connective in the language.
De Morgan’s laws relate negation to conjunction and disjunction:
Other important classical laws include double-negation elimination, , and the law of excluded middle, according to which 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 requires membership in both and .
Expressive power and functional completeness
There are
distinct classical truth functions of arity . There are 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 and are functionally complete. For example,
Two individual binary connectives are each sufficient on their own:
- NAND, or the Sheffer stroke, defined by .
- NOR, or the Peirce arrow, defined by .
Using NAND alone, negation and conjunction can be expressed as
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 is a formula, while modus ponens is the rule that permits the conclusion from premises and .
In natural deduction, connectives are characterized by introduction and elimination rules. Conjunction introduction permits to be inferred once both and have been established. Conjunction elimination permits either component to be inferred from their conjunction.
Implication introduction permits to be established by deriving under a temporary assumption , 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 supplies proofs of both components, while a proof of supplies a proof of one component together with an indication of which one. A proof of provides a construction transforming any proof of into a proof of . Excluded middle and double-negation elimination are not valid unrestricted principles in this setting.
In modal logic, operators such as , commonly read as “necessarily,” and , 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.