Logical conjunction is a logical operation that combines statements and asserts that they hold together. In classical propositional logic, the conjunction of two statements and , written and read “ and ,” is true exactly when both statements are true. The statements being combined are called conjuncts. Conjunction is fundamental to logic, mathematical reasoning, and computing: it expresses simultaneous conditions, combines assumptions, and underlies Boolean AND operations.
Notation and truth conditions
The standard symbol for conjunction is . Other notations include , , and, in algebraic contexts, juxtaposition . Programming languages commonly use &&, and, or AND, though their operational behavior varies.
In classical two-valued logic, conjunction has the following truth table:
| True | True | True |
| True | False | False |
| False | True | False |
| False | False | False |
Conjunction is therefore truth-functional: its truth value depends only on the truth values of its conjuncts, not on their subject matter or any causal relationship between them.
For example, let be “12 is even” and be “12 is divisible by 3.” Their conjunction is true because both statements are true. By contrast, “12 is even and 12 is prime” is false because its second conjunct is false.
With truth represented by and falsity by , conjunction can be represented by multiplication:
Here multiplication operates on the numerical encodings of truth values, rather than on the statements themselves.
Logical “and” and ordinary language
Logical conjunction captures an important use of the English word “and,” but not all of its meanings.
In classical logic, and have the same truth value. Ordinary language may convey additional information through word order. “She unlocked the door and entered” normally suggests a temporal sequence, whereas reversing the clauses suggests a different sequence. Conjunction alone does not express that ordering.
Likewise, “He pressed the switch and the light came on” can suggest causation, but its logical conjunction asserts only that both events occurred. Any causal connection requires additional representation.
Not every grammatical use of “and” combines complete propositions. “Ada and Ben lifted the piano” can describe a joint action without asserting that Ada lifted it alone and Ben lifted it alone. Translating natural language into conjunction therefore requires identifying the propositions actually being asserted.
Conjunction in formal reasoning
In natural deduction, conjunction is characterized by an introduction rule and two elimination rules. These rules of inference explain how a conjunction is established and what follows from it.
Conjunction introduction
If and have each been established under compatible assumptions, their conjunction may be inferred:
More explicitly, if a collection of assumptions permits the derivation of both statements, then
The symbol indicates derivability in a formal proof system.
Conjunction elimination
Either conjunct may be inferred from a conjunction:
Thus a proof of “ is positive and even” supplies a proof that is positive and a proof that is even. Conversely, proving those two claims establishes the conjunction. These rules are used throughout mathematical proof, including proofs of definitions that impose several requirements.
A conjunction must not be confused with a conditional. asserts both statements; “if , then ” does not generally assert either statement on its own.
Algebraic laws
In classical logic, conjunction satisfies the following laws. Here means logical equivalence, denotes truth, and denotes falsity.
| Law | Equivalence |
|---|---|
| Commutativity | |
| Associativity | |
| Idempotence | |
| Identity | |
| Annihilation | |
| Noncontradiction |
Associativity allows to be written without parentheses. Idempotence means that repeating a conjunct does not change the resulting truth conditions.
Conjunction interacts with disjunction, written , through distributive and absorption laws:
Its relationship with negation is expressed by De Morgan’s laws:
In particular, denying a conjunction means that at least one conjunct is false; it does not mean that both are false. These equivalences are classical laws; some require qualification in nonclassical systems.
Boolean algebra, sets, and order
Conjunction is one of the basic operations of Boolean algebra. In an abstract Boolean algebra, it is called the meet operation.
Its order-theoretic meaning is especially useful. Order propositions, considered up to logical equivalence, by entailment: when logically entails . Then is their greatest lower bound:
- entails and entails .
- Any statement that entails both and also entails .
Thus conjunction combines requirements into a statement at least as strong as either requirement separately. This interpretation connects logic with partially ordered sets.
In set theory, conjunction corresponds to intersection:
The sets and represent two conditions on an element, and their intersection contains exactly the elements satisfying both.
This correspondence also explains conjunction in probability. For events and , their joint occurrence is the event . When ,
Only under independence may the conditional probability be replaced by . The multiplication rule for independent events is therefore not a general rule for assigning probabilities to conjunctions.
Multiple and quantified conjunctions
A finite family of propositions can be combined using indexed notation:
This expression is true exactly when every is true. The conjunction of an empty family is conventionally . This preserves truth as the identity element and agrees with the principle that no requirement is violated when there are no requirements.
Ordinary first-order logic uses finite formulas. A universal statement such as
requires to hold for every object in the domain, but it is syntactically a quantified formula, not an infinite string of conjunctions. Over a fixed finite domain with a name for each element, it can be expanded into a finite conjunction. Some infinitary logical languages explicitly permit infinite conjunctions.
Conjunctions also occur within conjunctive normal form, in which a formula is expressed as a conjunction of clauses, each clause being a disjunction of literals. For example,
is in conjunctive normal form. This representation is central to many automated methods for testing whether propositional conditions can all be satisfied.
Computing and digital circuits
A digital AND gate implements conjunction on Boolean inputs: its output is exactly when every input is . Networks of such gates, together with other logical gates, implement digital computations.
In programming, conjunction commonly combines tests, such as checking that a number lies within an interval:
x >= 0 and x <= 10
Many languages use short-circuit evaluation: if the first operand is false, the second is not evaluated. This matters when the second expression performs an action, raises an error, or does not terminate. Although conjunction is commutative as a Boolean operation, reversing two program expressions can therefore change program behavior.
Bitwise AND applies the same truth table separately to corresponding bits. For example,
1100 AND 1010 = 1000
Bitwise and logical operators are distinct in many languages and need not have the same operand types, return types, or evaluation rules.
Database systems provide another qualification. SQL uses a three-valued logic for many expressions involving NULL. For example, true AND unknown is unknown, while false AND unknown is false. Such behavior is not fully described by the classical two-valued truth table.
Constructive and nonclassical interpretations
In intuitionistic logic, conjunction retains its standard introduction and elimination rules. Under the Brouwer–Heyting–Kolmogorov interpretation, a proof of consists of a proof of together with a proof of . This is stronger than merely failing to refute either statement.
Through the Curry–Howard correspondence, conjunction corresponds to a product type: a value witnessing contains a component witnessing and another witnessing . Forming the pair corresponds to conjunction introduction; extracting its components corresponds to conjunction elimination.
Other nonclassical logics may change conjunction’s semantics or distinguish multiple conjunction-like operations. Many-valued logics allow more than two truth values. Resource-sensitive logics can distinguish combining resources from offering alternative ways to use them. Consequently, notation such as does not by itself establish that every classical Boolean law applies.
Historical development
Reasoning about combined assertions predates modern symbolic notation. The algebraic treatment of conjunction became central in the nineteenth century through the work of George Boole, whose logical algebra represented combinations of conditions using multiplication-like operations.
Later developments in propositional logic, proof systems, and Boolean algebra established conjunction as both a connective governed by inference rules and an algebraic operation. In the twentieth century, Claude Shannon connected Boolean algebra with switching circuits, making conjunction a basic operation in the mathematical description and design of digital hardware.