OR | |
---|---|
150px | |
Definition | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x+y} |
Truth table | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (0111)} |
Logic gate | 70px |
Normal forms | |
Disjunctive | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x+y} |
Conjunctive | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x+y} |
Zhegalkin polynomial | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x \oplus y \oplus xy} |
Post's lattices | |
0-preserving | yes |
1-preserving | yes |
Monotone | yes |
Affine | no |
In logic, disjunction is a logical connective typically notated Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lor } whose meaning either refines or corresponds to that of natural language expressions such as "or". In classical logic, it is given a truth functional semantics on which Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \phi \lor \psi} is true unless both Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \phi} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \psi} 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 theoretical treatments are often given in terms of rules such as disjunction introduction and disjunction elimination. Disjunction has also been given numerous non-classical treatments, motivated by problems including Aristotle's sea battle argument, Heisenberg's uncertainty principle, as well the numerous mismatches between classical disjunction and its nearest equivalents in natural language.^{[1]}^{[2]}^{[3]}
Notation
In logic and related fields, disjunction is customarily notated with an infix operator Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lor} .^{[1]}^{[2]} Alternative notations include Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle +} , used mainly in electronics, as well as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \vert} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \vert\!\vert} in many programming languages. The English word "or" is sometimes used as well, often in capital letters. In Jan Łukasiewicz's prefix notation for logic, the operator is A, short for Polish alternatywa (English: alternative).^{[4]}
Classical disjunction
Semantics
Classical disjunction is a truth functional operation which returns the truth value "true" unless both of its arguments are "false". Its semantic entry is standardly given as follows:^{[5]}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \models \phi \lor \psi} if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \models \phi} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \models \psi}
This semantics is corresponds to the following truth table:^{[2]}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \lor B} |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Defined by other operators
In systems where logical disjunction is not a primitive, it may be defined as^{[6]}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \lor B = \neg A \to B } .
This can be checked by the following truth table:
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B} | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \neg A } | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \neg A \to B } | Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \lor B} |
T | T | F | T | T |
T | F | F | T | T |
F | T | T | T | T |
F | F | T | F | F |
Properties
The following properties apply to disjunction:
- Associativity: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a \lor (b \lor c) \equiv (a \lor b) \lor c }
- Commutativity: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a \lor b \equiv b \lor a }
- Distributivity: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a \lor (b \land c)) \equiv ((a \lor b) \land (a \lor c))}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a \lor (b \lor c)) \equiv ((a \lor b) \lor (a \lor c))}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a \lor (b \equiv c)) \equiv ((a \lor b) \equiv (a \lor c))}
- Idempotency: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a \lor a \equiv a }
- Monotonicity: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a \rightarrow b) \rightarrow ((c \lor a) \rightarrow (c \lor b))}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a \rightarrow b) \rightarrow ((a \lor c) \rightarrow (b \lor c))}
- 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
20px | This section needs expansion. You can help by adding to it. (February 2021) |
Operators corresponding to logical disjunction exist in most programming languages.
Bitwise operation
Disjunction is often used for bitwise operations. Examples:
- 0 or 0 = 0
- 0 or 1 = 1
- 1 or 0 = 1
- 1 or 1 = 1
- 1010 or 1100 = 1110
The or
operator can be used to set bits in a bit field to 1, by or
-ing the field with a constant field with the relevant bits set to 1. For example, x = x | 0b00000001
will force the final bit to 1, while leaving other bits unchanged.^{[citation needed]}
Logical operation
Many languages distinguish between bitwise and logical disjunction by providing two distinct operators; in languages following C, bitwise disjunction is performed with the single pipe operator (|
), and logical disjunction with the double pipe (||
) operator.
Logical disjunction is usually short-circuited; that is, if the first (left) operand evaluates to true
, then the second (right) operand is not evaluated. The logical disjunction operator thus usually constitutes a sequence point.
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 true
or false
), in some languages (such as 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.^{[citation needed]}
Constructive disjunction
The Curry–Howard correspondence relates a constructivist form of disjunction to tagged union types.^{[citation needed]}
Set theory
20px | This section needs expansion. You can help by adding to it. (February 2021) |
The membership of an element of a union set in set theory is defined in terms of a logical disjunction: x ∈ A ∪ B if and only if (x ∈ A) ∨ (x ∈ B). 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.^{[citation needed]}
Natural language
The classical denotation for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lor} does not precisely match the denotation of disjunctive statements in natural languages such as English. Notably, classical disjunction is inclusive while natural language disjunction is often understood exclusively.^{[2]}
- 1. Mary is patriotic or quixotic.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \rightsquigarrow} Mary is not both patriotic and quixotic.
This inference has sometimes been understood as an entailment, for instance by Alfred Tarski, who suggested that natural language disjunction is 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 semantic denotation which behaves classically. However, disjunctive constructions including Hungarian vagy... vagy and French soit... soit have been argued to be inherently exclusive, rendering ungrammaticality in contexts where an inclusive reading would otherwise be forced.^{[2]}
Similar deviations from classical logic have been noted in cases such as free choice disjunction and simplification of disjunctive antecedents, where certain modal operators trigger a 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.^{[2]}
- 2. You can have an apple or a pear.
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \rightsquigarrow} You can have an apple and you can have a pear (but you can't have both)
In many languages, disjunctive expressions play a role in question formation. For instance, while the following 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 be analyzed using nonclassical logics such as alternative semantics and inquisitive semantics, which have also been adopted to explain the free choice and simplification inferences.^{[2]}
- 3. Is Mary a philosopher or a linguist?
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 and Maricopa, disjunction is marked using a verb suffix. For instance, in the Maricopa example below, disjunction is marked by the suffix šaa.^{[2]}
- 4.
Johnš
John-nom
Billš
Bill-nom
v?aawuumšaa
3-come-pl-fut-infer
'John or Bill will come'
See also
Notes
- George Boole, closely following analogy with ordinary mathematics, premised, as a necessary condition to the definition of "x + y", that x and y were mutually exclusive. Jevons, and practically all mathematical logicians after him, advocated, on various grounds, the definition of "logical addition" in a form which does not necessitate mutual exclusiveness.
References
- ^ ^{a} ^{b} "Comprehensive List of Logic Symbols". Math Vault. 2020-04-06. Retrieved 2020-09-03.
- ^ ^{a} ^{b} ^{c} ^{d} ^{e} ^{f} ^{g} ^{h} Aloni, Maria (2016), Zalta, Edward N. (ed.), "Disjunction", The Stanford Encyclopedia of Philosophy (Winter 2016 ed.), Metaphysics Research Lab, Stanford University, retrieved 2020-09-03
- ^ "Disjunction | logic". Encyclopedia Britannica. Retrieved 2020-09-03.
- ^ 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.
- ^ For the sake of generality across classical systems, this entry suppresses the parameters of evaluation.
- ^ Walicki, Michał (2016). Introduction to Mathematical Logic. WORLD SCIENTIFIC. p. 150. ISBN 9814343870.
External links
40x40px | Wikimedia Commons has media related to Logical disjunction. |
- "Disjunction", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- Aloni, Maria. "Disjunction". In Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy.
- Eric W. Weisstein. "Disjunction." From MathWorld—A Wolfram Web Resource