Logical disjunction is a connective in logic that combines propositions to express that at least one of them holds. It is usually written , read “ or ,” and its constituent propositions are called disjuncts. In classical propositional logic, a disjunction is false only when both disjuncts are false. This is an inclusive interpretation: remains true when both and are true.
Definition and truth conditions
Classical disjunction is a binary, truth-functional connective: the truth value of the compound proposition depends only on the truth values of its two disjuncts. Its truth table is:
| True | True | True |
| True | False | True |
| False | True | True |
| False | False | False |
For example, let mean “the integer is divisible by 2” and mean “the integer is divisible by 3.” Then is true of 4, 9, and 6, but false of 5. The case of 6 illustrates that both disjuncts may hold.
If truth is represented by and falsity by , disjunction can be expressed as
The arithmetic expression on the right is an encoding of the truth table, not a replacement for the logical connective in ordinary formulas.
Inclusive and exclusive “or”
Inclusive disjunction differs from exclusive OR, which is true exactly when one disjunct is true and the other is false. Exclusive OR can be defined using inclusive disjunction:
Here denotes logical conjunction, and denotes logical negation.
In ordinary language, “or” can suggest either interpretation. “Tea or coffee” may imply a choice of one, whereas “applicants must know French or German” may allow applicants who know both. The exclusive suggestion often depends on context rather than on the word “or” alone. Formal logic specifies the interpretation explicitly.
Notation and scope
The standard logical symbol for disjunction is . In Boolean algebra, is also commonly used for OR, with multiplication or juxtaposition representing AND. Boolean addition must not be confused with ordinary arithmetic addition or addition modulo 2: in Boolean OR, , whereas addition modulo 2 represents exclusive OR.
Parentheses determine the scope of a connective. For example,
differs from
A common convention gives negation higher precedence than conjunction, and conjunction higher precedence than disjunction, but explicit parentheses avoid ambiguity.
Disjunction also occurs inside first-order logic, where its disjuncts may contain predicates, variables, and quantifiers. For example,
says that every object satisfies at least one of the two predicates. It does not generally imply
because different objects may satisfy different predicates.
Algebraic properties
Classical disjunction satisfies several fundamental equivalences. Here means that the formulas have the same truth value under every assignment.
| Property | Equivalence |
|---|---|
| Commutativity | |
| Associativity | |
| [[idempotence | Idempotence]] |
| Identity | |
| Domination | |
| Absorption |
The symbols and represent falsity and truth, respectively.
Associativity allows a finite disjunction to be written without specifying its grouping:
It is true exactly when at least one disjunct is true. The disjunction of no propositions—the empty disjunction—is conventionally false, consistently with being the identity for OR.
Disjunction and conjunction distribute over one another:
De Morgan’s laws connect these operations with negation:
Consequently, in classical logic disjunction can be defined from conjunction and negation:
is a classical tautology. Some of these equivalences and principles do not extend unchanged to nonclassical logics.
Rules of inference
Disjunction is governed by rules specifying how it may be introduced and used in a formal proof.
Disjunction introduction
From , one may infer ; from , one may infer :
These rules of inference require no evidence for the additional disjunct. If is already established, the inclusive claim that at least one of and holds is established as well.
Disjunction elimination
In natural deduction, disjunction elimination formalizes proof by cases. If is established, and the same conclusion follows both from assuming and from assuming , then follows:
The bracketed assumptions are discharged when the rule is applied. The two cases need not be mutually exclusive: the argument remains valid if both and hold.
A familiar related pattern is disjunctive syllogism:
It is valid in classical and standard intuitionistic logic. By contrast, together with does not justify , because inclusive disjunction permits both disjuncts to be true.
Set-theoretic and probabilistic interpretations
In set theory, disjunction corresponds to union:
Under this correspondence, conjunction becomes intersection and negation becomes complement relative to a specified universe. The algebraic laws for logical connectives therefore parallel laws for sets.
In a partial order derived from a Boolean algebra, disjunction is the join, or least upper bound. For propositions ordered by logical entailment, modulo logical equivalence, is the weakest common upper bound: both and entail it, and it entails every proposition entailed by both.
In probability theory, the occurrence of event or event is represented by . Its probability is
The subtraction prevents outcomes satisfying both events from being counted twice. For mutually exclusive events, the intersection has probability zero. Under statistical independence, the formula becomes
Independence and mutual exclusivity are distinct conditions.
Computation and applications
Disjunction is a basic operation in computer science. Digital circuits implement it using OR gates, whose output is 1 when at least one input is 1. Multi-input OR gates generalize the same rule.
Programming languages commonly distinguish:
- Logical OR, which combines Boolean conditions, although operand and return-value conventions vary by language.
- Bitwise OR, which applies the OR truth table independently to corresponding bits.
- Short-circuit OR, which evaluates the second operand only when the first operand does not already establish a true result.
Short-circuit evaluation matters when an operand has side effects, is computationally expensive, or would be invalid to evaluate in certain circumstances. Such evaluation behavior is not part of the abstract classical truth table.
Disjunction is also central to standard forms for propositional formulas. A disjunctive normal form is a disjunction of conjunctions of literals, where a literal is a proposition variable or its negation. A conjunctive normal form is a conjunction of clauses, each clause being a disjunction of literals. These representations support satisfiability testing, automated reasoning, and formal verification.
Nonclassical interpretations
Intuitionistic logic
In intuitionistic logic, disjunction retains its introduction and elimination rules, but its meaning is not exhausted by a classical two-valued truth table. Under the Brouwer–Heyting–Kolmogorov interpretation, evidence for identifies a disjunct and supplies evidence for that disjunct.
Accordingly, intuitionistic logic has the disjunction property: if a closed formula is provable in pure intuitionistic logic, then is provable or is provable. Classical logic lacks this property; it proves without generally proving either disjunct.
The classical equivalence
does not hold intuitionistically in general. The left side implies the right, but the converse is not generally derivable.
Through the Curry–Howard correspondence, constructive disjunction corresponds to a sum type: a value contains either an inhabitant of one type or an inhabitant of the other, together with an indication of which alternative it represents.
Other nonclassical systems
Many-valued logics may interpret disjunction as an operation on more than two truth values. The chosen operation and its interaction with negation depend on the system.
In paraconsistent logic, some familiar inference patterns require restriction. In particular, disjunctive syllogism may fail when a proposition and its negation can both hold without every proposition following.
Historical context
The distinction between different readings of “or” predates modern symbolic notation. The development of algebraic logic in the nineteenth century, particularly the work of George Boole, helped establish systematic algebraic methods for reasoning about propositions and classes. Later symbolic logic standardized disjunction as a basic connective, while the development of Boolean methods for switching circuits connected the same operation to digital computation.