Editing Logical disjunction

{{Short description|Logical connective OR}}
{{Redirect|Disjunction|the logic gate|OR gate|separation of chromosomes|Meiosis|disjunctions in distribution|Disjunct distribution}}
{{Redirect|Logical OR|the operator ''‖''|Vertical bars (disambiguation)}}
{{Infobox logical connective
| title        = Logical disjunction
| other titles = OR
| wikifunction = Z10184
| Venn diagram = Venn0111.svg
| definition   = <math>x+y</math>
| truth table  = <math>(1110)</math>
| logic gate   = OR_ANSI.svg
| DNF          = <math>x+y</math>
| CNF          = <math>x+y</math>
| Zhegalkin    = <math>x \oplus y \oplus xy</math>
| 0-preserving = yes
| 1-preserving = yes
| monotone     = yes
| affine       = no
| self-dual    = no
}}
{{Logical connectives sidebar}}
[[File:Venn 0111 1111.svg|thumb|220px|[[Venn diagram]] of <math>\scriptstyle A \lor B \lor C</math>]]

In [[logic]], '''disjunction''' (also known as '''logical disjunction''', '''logical or''', '''logical addition''', or '''inclusive disjunction''') is a [[logical connective]] typically notated as <math> \lor </math> and read aloud as "or". For instance, the [[English language|English]] language sentence "it is sunny or it is warm" can be represented in logic using the disjunctive formula <math> S \lor W </math>, assuming that <math>S</math> abbreviates "it is sunny" and <math>W</math> abbreviates "it is warm".

In [[classical logic]], disjunction is given a [[truth function]]al semantics according to which a formula <math>\phi \lor \psi</math> is true unless both <math>\phi</math> and <math>\psi</math> are false. Because this semantics allows a disjunctive formula to be true when both of its disjuncts are true, it is an ''inclusive'' interpretation of disjunction, in contrast with [[exclusive disjunction]]. Classical [[proof theory|proof theoretical]] treatments are often given in terms of rules such as [[disjunction introduction]] and [[disjunction elimination]]. Disjunction has also been given numerous [[nonclassical logic|non-classical]] treatments, motivated by problems including [[Aristotle's sea battle argument]], [[Heisenberg]]'s [[uncertainty principle]], as well as the numerous mismatches between classical disjunction and its nearest equivalents in [[natural language]]s.<ref name=":1">{{Citation|last=Aloni|first=Maria|author-link=Maria Aloni|title=Disjunction|date=2016|url=https://plato.stanford.edu/archives/win2016/entries/disjunction/|encyclopedia=The Stanford Encyclopedia of Philosophy|editor-last=Zalta|editor-first=Edward N.|edition=Winter 2016|publisher=Metaphysics Research Lab, Stanford University|access-date=2020-09-03}}</ref><ref>{{Cite web|title=Disjunction {{!}} logic|url=https://www.britannica.com/topic/disjunction-logic|access-date=2020-09-03|website=Encyclopedia Britannica|language=en}}</ref>

An [[operand]] of a disjunction is a '''disjunct'''.<ref name=":21">{{Cite book |last=Beall |first=Jeffrey C. |title=Logic: the basics |date=2010 |publisher=Routledge |isbn=978-0-203-85155-5 |edition=1. publ |location=London |pages=57 |language=en}}</ref>

==Inclusive and exclusive disjunction==

Because the logical ''or'' means a disjunction formula is true when either one or both of its parts are true, it is referred to as an ''inclusive'' disjunction.  This is in contrast with an [[exclusive disjunction]], which is true when one or the other of the arguments are true, but not both (referred to as ''exclusive or'', or ''XOR'').

When it is necessary to clarify whether inclusive or exclusive ''or'' is intended, English speakers sometimes uses the phrase ''[[and/or]]''. In terms of logic, this phrase is identical to ''or'', but makes the inclusion of both being true explicit.

==Notation==
In logic and related fields, disjunction is customarily notated with an infix operator <math>\lor</math> (Unicode {{unichar|2228|Logical Or}}).<ref name=":1"/> Alternative notations include <math>+</math>, used mainly in [[electronics]], as well as <math>\vert</math> and <math>\vert\!\vert</math> in many [[programming language]]s. The English word ''or'' is sometimes used as well, often in capital letters. In [[Jan Łukasiewicz]]'s [[Polish notation#Polish notation for logic|prefix notation for logic]], the operator is <math>A</math>, short for Polish ''alternatywa'' (English: alternative).<ref>[[Józef Maria Bocheński]] (1959), ''A Précis of Mathematical Logic'', translated by Otto Bird from the French and German editions, Dordrecht, North Holland:  D. Reidel, passim.</ref>

In mathematics, the disjunction of an arbitrary number of elements <math>a_1, \ldots, a_n</math> can be denoted as an [[iterated binary operation]] using a larger ⋁ (Unicode {{unichar|22C1|N-Ary Logical Or}}):<ref>{{cite web |last1=Weisstein |first1=Eric W. |title=OR |url=https://mathworld.wolfram.com/OR.html |website=MathWorld--A Wolfram Web Resource |access-date=24 September 2024 |language=en}}</ref>

<math>
\bigvee_{i=1}^{n} a_i = a_1 \lor a_2 \lor \ldots a_{n-1} \lor a_{n}
</math>

==Classical disjunction==

=== Semantics ===

In the [[semantics of logic]], classical disjunction is a [[truth function]]al [[logical operation|operation]] which returns the [[truth value]] ''true'' unless both of its arguments are ''false''. Its semantic entry is standardly given as follows:{{efn|For the sake of generality across classical systems, this entry suppresses the parameters of evaluation. The [[double turnstile]] [[List of logic symbols|symbol]] <math> \models </math> here is intended to mean "semantically entails".<!--this is hardly readable without context, it means  "(X ⊨  phi ∨ psi) if [(X  ⊨  phi) or (X  ⊨  psi)], for any X", in other words, " '∨' means 'or' ".-->}}

:: <math> \models \phi \lor \psi</math> &nbsp; &nbsp; if &nbsp; &nbsp; <math> \models \phi</math> &nbsp; &nbsp; or &nbsp; &nbsp; <math>\models \psi</math> &nbsp; &nbsp; or &nbsp; &nbsp; both

This semantics corresponds to the following [[truth table]]:<ref name=":1" />

{{2-ary truth table|0|1|1|1|<math>A \lor B</math>}}

===Defined by other operators===
In [[classical logic]] systems where logical disjunction is not a primitive, it can be defined in terms of the primitive ''[[logical conjunction|and]]'' (<math>\land</math>) and ''[[logical negation|not]]'' (<math>\lnot</math>) as:

:<math>A \lor B =  \neg ((\neg A) \land (\neg B))</math>.

Alternatively, it may be defined in terms of ''[[material conditional|implies]]'' (<math>\to</math>) and ''not'' as:<ref>{{cite book
 |last=Walicki
 |first=Michał
 |author-link=
 |date=2016
 |title=Introduction to Mathematical Logic
 |url=https://www.worldscientific.com/doi/abs/10.1142/9783
 |publisher=WORLD SCIENTIFIC
 |page=150
 |doi=10.1142/9783
 |isbn=978-9814343879
}}</ref>
:<math>A \lor B = (\lnot A) \to B</math>.
The latter can be checked by the following truth table:

{{2-ary truth table
|1|1|0|0|<math>\neg A</math>
|thick
|0|1|1|1|<math>\neg A \rightarrow B</math>
|
|0|1|1|1|<math>A \or B</math>
}}

It may also be defined solely in terms of <math>\to</math>:
:<math>A \lor B = (A \to B) \to B</math>.
It can be checked by the following truth table:

{{2-ary truth table
|1|1|0|1|<math>A \rightarrow B</math>
|thick
|0|1|1|1|<math>(A \rightarrow B) \rightarrow B</math>
|
|0|1|1|1|<math>A \or B</math>
}}

<!-- === Proof theory === -->

===Properties===

The following properties apply to disjunction:

*[[Associativity]]: <math>a \lor (b \lor c) \equiv (a \lor b) \lor c </math>'''<ref name=":13">{{Cite book |last=Howson |first=Colin |title=Logic with trees: an introduction to symbolic logic |date=1997 |publisher=Routledge |isbn=978-0-415-13342-5 |location=London; New York |pages=38}}</ref>'''
*[[Commutativity]]: <math>a \lor  b \equiv b \lor a </math>
*[[Distributivity]]: <math>(a \land (b \lor c)) \equiv ((a \land b) \lor (a \land c))</math>
:::<math>(a \lor (b \land c)) \equiv ((a \lor b) \land (a \lor c))</math>
:::<math>(a \lor (b \lor c)) \equiv ((a \lor b) \lor (a \lor c))</math>
:::<math>(a \lor (b \equiv c)) \equiv ((a \lor b) \equiv (a \lor c))</math>

*[[Idempotency]]: <math>a \lor a \equiv a </math>
*[[Monotonicity]]: <math>(a \rightarrow b) \rightarrow ((c \lor a) \rightarrow (c \lor b))</math>
:::<math>(a \rightarrow b) \rightarrow ((a \lor c) \rightarrow (b \lor c))</math>

*''Truth-preserving'': The interpretation under which all variables are assigned a [[truth value]] of 'true', produces a truth value of 'true' as a result of disjunction.
*''Falsehood-preserving'': The interpretation under which all variables are assigned a [[truth value]] of 'false', produces a truth value of 'false' as a result of disjunction.

==Applications in computer science==
{{Expand section|date=February 2021}}
[[File:Or-gate-en.svg|thumb|150px|OR [[logic gate]]]]
[[Operator (programming)|Operators]] corresponding to logical disjunction exist in most [[programming language]]s.

===Bitwise operation===
Disjunction is often used for [[bitwise operation]]s. Examples:
* 0 or 0 = 0
* 0 or 1 = 1
* 1 or 0 = 1
* 1 or 1 = 1
* 1010 or 1100 = 1110

The <code>or</code> operator can be used to set bits in a [[bit field]] to 1, by <code>or</code>-ing the field with a constant field with the relevant bits set to 1. For example, <code>x = x | 0b00000001</code> will force the final bit to 1, while leaving other bits unchanged.{{citation needed|date=February 2021}}

===Logical operation===
Many languages distinguish between bitwise and logical disjunction by providing two distinct operators; in languages following [[C (programming language)|C]], [[bitwise disjunction]] is performed with the single pipe operator (<code>|</code>), and logical disjunction with the double pipe (<code>||</code>) operator.

Logical disjunction is usually [[Short-circuit evaluation|short-circuited]]; that is, if the first (left) operand evaluates to <code>true</code>, then the second (right) operand is not evaluated. The logical disjunction operator thus usually constitutes a [[sequence point]].

{{anchor|parallel-or}}In a parallel (concurrent) language, it is possible to short-circuit both sides: they are evaluated in parallel, and if one terminates with value true, the other is interrupted. This operator is thus called the ''parallel or''.

Although the type of a logical disjunction expression is Boolean in most languages (and thus can only have the value <code>true</code> or <code>false</code>), in some languages (such as [[Python programming language|Python]] and [[JavaScript]]), the logical disjunction operator returns one of its operands: the first operand if it evaluates to a true value, and the second operand otherwise.<ref>{{cite web |title=Python 3.12.1 Documentation - The Python Language Reference - 6.11 Boolean operations |url=https://docs.python.org/3/reference/expressions.html#boolean-operations |access-date=25 Dec 2023}}</ref><ref>{{cite web |title=JavaScript References - Expressions & Operators - Logical AND (&&) |date=25 September 2023 |url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Logical_AND |access-date=25 Dec 2023}}</ref> This allows it to fulfill the role of the [[Elvis operator]].

===Constructive disjunction===
The [[Curry–Howard correspondence]] relates a [[constructivism (mathematics)|constructivist]] form of disjunction to [[tagged union]] types.{{citation needed|date=February 2021}}<ref>{{Cite journal |title=Context-Free Language Theory Formalization |journal=Universidade Federal de Pernambuco |pages=6|arxiv=1505.00061 |author1=Marcus Vinícius Midena Ramos |last2=de Queiroz |first2=Ruy J. G. B. |year=2015 }}</ref>

==Set theory==
{{Expand section|date=February 2021}}
The [[Element (mathematics)|membership]] of an element of a [[union (set theory)|union set]] in [[set theory]] is defined in terms of a logical disjunction: <math>x\in A\cup B\Leftrightarrow (x\in A)\vee(x\in B)</math>. Because of this, logical disjunction satisfies many of the same identities as set-theoretic union, such as [[associativity]], [[commutativity]], [[distributivity]], and [[de Morgan's laws]], identifying [[logical conjunction]] with [[set intersection]], [[logical negation]] with [[set complement]].<ref>{{cite book |last1=Ebbinghaus |first1=Heinz-Dieter |title=Einführung in die Mengenlehre |date=2021 |publisher=Springer |isbn=978-3-662-63865-1 |page=32 |edition=5 |language=German}}</ref>

== Natural language ==

Disjunction in [[natural language]]s does not precisely match the interpretation of <math>\lor</math> in classical logic. Notably, classical disjunction is inclusive while natural language disjunction is often understood exclusively, as the following English example typically would be.<ref name=":1" />

:* Mary is eating an apple or a pear.

This inference has sometimes been understood as an [[entailment]], for instance by [[Alfred Tarski]], who suggested that natural language disjunction is [[lexical ambiguity|ambiguous]] between a classical and a nonclassical interpretation. More recent work in [[pragmatics]] has shown that this inference can be derived as a [[conversational implicature]] on the basis of a [[formal semantics (natural language)|semantic]] denotation which behaves classically. However, disjunctive constructions including [[Hungarian language|Hungarian]] ''vagy... vagy'' and [[French language|French]] ''soit... soit'' have been argued to be inherently exclusive, rendering un[[grammaticality]] in contexts where an inclusive reading would otherwise be forced.<ref name=":1" />

Similar deviations from classical logic have been noted in cases such as [[free choice inference|free choice disjunction]] and [[simplification of disjunctive antecedents]], where certain [[linguistic modality|modal operators]] trigger a [[logical conjunction|conjunction]]-like interpretation of disjunction. As with exclusivity, these inferences have been analyzed both as implicatures and as entailments arising from a nonclassical interpretation of disjunction.<ref name=":1" />

:* You can have an apple or a pear.
::<math>\rightsquigarrow</math> You can have an apple and you can have a pear (but you cannot have both)

In many languages, disjunctive expressions play a role in question formation.
:* Is Mary a philosopher or a linguist?
For instance, while the above English example can be interpreted as a [[polar question]] asking whether it's true that Mary is either a philosopher or a linguist, it can also be interpreted as an [[alternative question]] asking which of the two professions is hers. The role of disjunction in these cases has been analyzed using nonclassical logics such as [[alternative semantics]] and [[inquisitive semantics]], which have also been adopted to explain the free choice and simplification inferences.<ref name=":1" />

In English, as in many other languages, disjunction is expressed by a [[coordinating conjunction]]. Other languages express disjunctive meanings in a variety of ways, though it is unknown whether disjunction itself is a [[linguistic universal]]. In many languages such as [[Dyirbal language|Dyirbal]] and [[Maricopa language|Maricopa]], disjunction is marked using a verb [[suffix]]. For instance, in the Maricopa example below, disjunction is marked by the suffix ''šaa''.<ref name=":1" />

{{interlinear|| lang=mrc|indent=3|ablist=INFER:inferential
|Johnš Billš vʔaawuumšaa |
|John-NOM Bill-NOM 3-come-PL-FUT-INFER
|'John or Bill will come.'}}

==See also==
{{div col|colwidth=28em}}
* [[Affirming a disjunct]]
* [[Boolean algebra (logic)]]
* [[Boolean algebra topics]]
* [[Boolean domain]]
* [[Boolean function]]
* [[Boolean-valued function]]
* [[Conjunction/disjunction duality]]
* [[Disjunctive syllogism]]
* [[Fréchet inequalities]]
* [[Free choice inference]]
* [[Hurford disjunction]]
* [[Logical graph]]
* [[Simplification of disjunctive antecedents]]
{{div col end}}

==Notes==
{{Notelist}}
* [[George Boole]], closely following analogy with ordinary mathematics, premised, as a necessary condition to the definition of x&nbsp;+ y, that x and y were mutually exclusive. [[William Stanley Jevons|Jevons]], and practically all mathematical logicians after him, advocated, on various grounds, the definition of ''logical addition'' in a form that does not necessitate mutual exclusiveness.

==References==
{{Reflist}}

==External links==
*{{springer|title=Disjunction|id=p/d033260}}
*{{cite SEP |url-id=disjunction |title=Disjunction |last=Aloni |first=Maria|author-link=Maria Aloni}}
*Eric W. Weisstein. [http://mathworld.wolfram.com/Disjunction.html  "Disjunction."] From MathWorld—A Wolfram Web Resource

{{Logical connectives}}
{{Mathematical logic}}
{{Common logical symbols}}
{{Formal semantics}}
{{Authority control}}

[[Category:Logical connectives|Disjunction]]
[[Category:Semantics]]
[[Category:Formal semantics (natural language)]]