Logical disjunction

Logical disjunction


In logic, logical disjunction is the join in the poset of truth values.

Assuming that (as in classical logic) the only truth values are true (TT) and false (FF), then the disjunction pqp \vee q of the truth values pp and qq may be defined by a truth table:

ppqqpqp \vee q

That is, pqp \vee q is true if and only if at least one of pp and qq is true. Disjunction also exists in nearly every non-classical logic.

More generally, if pp and qq are any two relations on the same domain, then we define their disjunction pointwise, thinking of a relation as a function to truth values. If instead we think of a relation as a subset of its domain, then disjunction becomes union.


Disjunction as defined above is sometimes called inclusive disjunction to distinguish it from exclusive disjunction, where exactly one of pp and qq must be true.

In the context of substructural logics such as linear logic, it is also called additive disjunction to disambiguate it from the multiplicative disjunction.

Disjunction is de Morgan dual to conjunction.

Like any join, disjunction is an associative operation, so we can take the disjunction of any finite positive whole number of truth values; the disjunction is true if and only if at least one of the various truth values is true. Disjunction also has an identity element, which is the false truth value. Some logics allow a notion of infinitary disjunction. Indexed disjunction is existential quantification.

In homotopy type theory, the disjunction of two mere propositions, PP and QQ, is the bracket type of their sum type, P+Q\| P + Q \|.

Rules of inference

The rules of inference for disjunction in sequent calculus are dual to those for conjunction:

Γ,p,ΔΣ;Γ,q,ΔΣΓ,pq,ΔΣleft additive ΓΔ,p,ΣΓΔ,pq,Σright additive 0 ΓΔ,q,ΣΓΔ,pq,Σright additive 1 \begin {gathered} \frac { \Gamma , p , \Delta \vdash \Sigma ; \; \Gamma , q , \Delta \vdash \Sigma } { \Gamma , p \vee q , \Delta \vdash \Sigma } \; \text {left additive} \\ \frac { \Gamma \vdash \Delta , p , \Sigma } { \Gamma \vdash \Delta , p \vee q , \Sigma } \; \text {right additive 0} \\ \frac { \Gamma \vdash \Delta , q , \Sigma } { \Gamma \vdash \Delta , p \vee q , \Sigma } \; \text {right additive 1} \\ \end {gathered}

Equivalently, we can use the following rules with weakened contexts:

Γ,pΔ;q,ΣΠΓ,pq,ΣΔ,Πleft multiplicative ΓΔ,p,q,ΣΓΔ,pq,Σright multiplicative \begin {gathered} \frac { \Gamma , p \vdash \Delta ; \; q , \Sigma \vdash \Pi } { \Gamma , p \vee q , \Sigma \vdash \Delta , \Pi } \; \text {left multiplicative} \\ \frac { \Gamma \vdash \Delta , p , q , \Sigma } { \Gamma \vdash \Delta , p \vee q , \Sigma } \text {right multiplicative} \\ \end {gathered}

The rules above are written so as to remain valid in logics without the exchange rule. In linear logic, the first batch of sequent rules apply to additive disjunction (interpret pqp \vee q in these rules as pqp \oplus q), while the second batch of rules apply to multiplicative disjunction (interpret pqp \vee q in those rules as pqp \parr q).

The natural deduction rules for disjunction are a little more complicated than those for conjunction:

Γ,pr;Γ,qrΓ,pqrelimination ΓpΓpqintroduction 0 ΓqΓpqintroduction 1 \begin {gathered} \frac { \Gamma , p \vdash r ; \; \Gamma , q \vdash r } { \Gamma , p \vee q \vdash r } \; \text {elimination} \\ \frac { \Gamma \vdash p } { \Gamma \vdash p \vee q } \; \text {introduction 0} \\ \frac { \Gamma \vdash q } { \Gamma \vdash p \vee q } \; \text {introduction 1} \\ \end {gathered}

basic symbols used in logic

A\phantom{A}\inA\phantom{A}element relation
A\phantom{A}:\,:A\phantom{A}typing relation
A\phantom{A}\vdashA\phantom{A}A\phantom{A}entailment / sequentA\phantom{A}
A\phantom{A}\topA\phantom{A}A\phantom{A}true / topA\phantom{A}
A\phantom{A}\botA\phantom{A}A\phantom{A}false / bottomA\phantom{A}
A\phantom{A}\LeftrightarrowA\phantom{A}logical equivalence
A\phantom{A}\neqA\phantom{A}negation of equality / apartnessA\phantom{A}
A\phantom{A}\notinA\phantom{A}negation of element relation A\phantom{A}
A\phantom{A}¬¬\not \notA\phantom{A}negation of negationA\phantom{A}
A\phantom{A}\existsA\phantom{A}existential quantificationA\phantom{A}
A\phantom{A}\forallA\phantom{A}universal quantificationA\phantom{A}
A\phantom{A}\wedgeA\phantom{A}logical conjunction
A\phantom{A}\veeA\phantom{A}logical disjunction
A\phantom{A}\otimesA\phantom{A}A\phantom{A}multiplicative conjunctionA\phantom{A}
A\phantom{A}\oplusA\phantom{A}A\phantom{A}multiplicative disjunctionA\phantom{A}

Last revised on February 20, 2020 at 10:22:48. See the history of this page for a list of all contributions to it.