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

Logical Disjunction

Logical disjunction is the connective “or,” classically true when at least one of its constituent propositions is true, including when both are true.

25 keywords3 linked fromWritten by AI
LogicPropositional Lo…Truth TableExclusive ORLogical Conjunct…Logical NegationBoolean AlgebraFirst-Order Logi…Logical Di…

Logical disjunction is a connective in logic that combines propositions to express that at least one of them holds. It is usually written P∨QP\lor Q, read “PP or QQ,” 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: P∨QP\lor Q remains true when both PP and QQ 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:

PP QQ P∨QP\lor Q
True True True
True False True
False True True
False False False

For example, let PP mean “the integer is divisible by 2” and QQ mean “the integer is divisible by 3.” Then P∨QP\lor Q 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 11 and falsity by 00, disjunction can be expressed as

p∨q=max⁡(p,q)=p+q−pq,p,q∈{0,1}.p\lor q=\max(p,q)=p+q-pq, \qquad p,q\in\{0,1\}.

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:

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

Here ∧\land denotes logical conjunction, and ¬\neg 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 ∨\lor. 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, 1+1=11+1=1, whereas addition modulo 2 represents exclusive OR.

Parentheses determine the scope of a connective. For example,

P∨(Q∧R)P\lor(Q\land R)

differs from

(P∨Q)∧R.(P\lor Q)\land R.

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,

∀x(P(x)∨Q(x))\forall x\bigl(P(x)\lor Q(x)\bigr)

says that every object satisfies at least one of the two predicates. It does not generally imply

(∀x P(x))∨(∀x Q(x)),(\forall x\,P(x))\lor(\forall x\,Q(x)),

because different objects may satisfy different predicates.

Algebraic properties

Classical disjunction satisfies several fundamental equivalences. Here ≡\equiv means that the formulas have the same truth value under every assignment.

Property Equivalence
Commutativity P∨Q≡Q∨PP\lor Q\equiv Q\lor P
Associativity (P∨Q)∨R≡P∨(Q∨R)(P\lor Q)\lor R\equiv P\lor(Q\lor R)
[[idempotence Idempotence]]
Identity P∨⊥≡PP\lor\bot\equiv P
Domination P∨⊤≡⊤P\lor\top\equiv\top
Absorption P∨(P∧Q)≡PP\lor(P\land Q)\equiv P

The symbols ⊥\bot and ⊤\top represent falsity and truth, respectively.

Associativity allows a finite disjunction to be written without specifying its grouping:

P1∨P2∨⋯∨Pn.P_1\lor P_2\lor\cdots\lor P_n.

It is true exactly when at least one disjunct is true. The disjunction of no propositions—the empty disjunction—is conventionally false, consistently with ⊥\bot being the identity for OR.

Disjunction and conjunction distribute over one another:

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

De Morgan’s laws connect these operations with negation:

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

Consequently, in classical logic disjunction can be defined from conjunction and negation:

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

The law of excluded middle,

P∨¬P,P\lor\neg P,

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 PP, one may infer P∨QP\lor Q; from QQ, one may infer P∨QP\lor Q:

PP∨QQP∨Q.\frac{P}{P\lor Q} \qquad \frac{Q}{P\lor Q}.

These rules of inference require no evidence for the additional disjunct. If PP is already established, the inclusive claim that at least one of PP and QQ holds is established as well.

Disjunction elimination

In natural deduction, disjunction elimination formalizes proof by cases. If P∨QP\lor Q is established, and the same conclusion RR follows both from assuming PP and from assuming QQ, then RR follows:

P∨Q[P]⋮R[Q]⋮RR.\frac{ P\lor Q \qquad \begin{array}{c} [P]\\ \vdots\\ R \end{array} \qquad \begin{array}{c} [Q]\\ \vdots\\ R \end{array} }{R}.

The bracketed assumptions are discharged when the rule is applied. The two cases need not be mutually exclusive: the argument remains valid if both PP and QQ hold.

A familiar related pattern is disjunctive syllogism:

P∨Q,¬P⟹Q.P\lor Q,\quad \neg P \quad\Longrightarrow\quad Q.

It is valid in classical and standard intuitionistic logic. By contrast, P∨QP\lor Q together with PP does not justify ¬Q\neg Q, because inclusive disjunction permits both disjuncts to be true.

Set-theoretic and probabilistic interpretations

In set theory, disjunction corresponds to union:

x∈A∪B⟺(x∈A)∨(x∈B).x\in A\cup B \quad\Longleftrightarrow\quad (x\in A)\lor(x\in B).

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, P∨QP\lor Q is the weakest common upper bound: both PP and QQ entail it, and it entails every proposition entailed by both.

In probability theory, the occurrence of event AA or event BB is represented by A∪BA\cup B. Its probability is

Pr⁡(A∪B)=Pr⁡(A)+Pr⁡(B)−Pr⁡(A∩B).\Pr(A\cup B) = \Pr(A)+\Pr(B)-\Pr(A\cap B).

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

Pr⁡(A∪B)=Pr⁡(A)+Pr⁡(B)−Pr⁡(A)Pr⁡(B).\Pr(A\cup B) = \Pr(A)+\Pr(B)-\Pr(A)\Pr(B).

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 P∨QP\lor Q identifies a disjunct and supplies evidence for that disjunct.

Accordingly, intuitionistic logic has the disjunction property: if a closed formula P∨QP\lor Q is provable in pure intuitionistic logic, then PP is provable or QQ is provable. Classical logic lacks this property; it proves P∨¬PP\lor\neg P without generally proving either disjunct.

The classical equivalence

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

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.