TheInfoList

OR: In logic, disjunction is a logical connective typically notated as $\lor$ and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula $R \lor S$, assuming that $R$ abbreviates "it is raining" and $S$ abbreviates "it is snowing". In classical logic, disjunction is given a truth functional semantics according to which a formula $\phi \lor \psi$ is true unless both $\phi$ and $\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 Disjunction introduction or addition (also called or introduction) is a rule of inference of propositional logic and almost every other deduction system. The rule makes it possible to introduce disjunctions to logical proofs. It is the infere ...
and
disjunction elimination In propositional logic, disjunction elimination (sometimes named proof by cases, case analysis, or or elimination), is the valid argument form and rule of inference that allows one to eliminate a disjunctive statement from a logical proof. I ...
. 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 languages.

# Inclusive and exclusive disjunction

Because the logical "or" means a formula is when either or both 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 And/or (sometimes written and or) is an English grammatical conjunction used to indicate that ''one or more'' (or even all) of the cases it connects may occur. It is used as an inclusive ''or'' (as in logic and mathematics), because saying "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 $\lor$. Alternative notations include $+$, used mainly in electronics, as well as $\vert$ and $\vert\!\vert$ in many programming languages. The English word "or" is sometimes used as well, often in capital letters. In
Jan Łukasiewicz Jan Łukasiewicz (; 21 December 1878 – 13 February 1956) was a Polish logician and philosopher who is best known for Polish notation and Łukasiewicz logic His work centred on philosophical logic, mathematical logic and history of logic. ...
's prefix notation for logic, the operator is A, short for Polish ''alternatywa'' (English: alternative).

# Classical disjunction

## Semantics

In the
semantics of logic In logic, the semantics of logic or formal semantics is the study of the semantics, or interpretations, of formal and (idealizations of) natural languages usually trying to capture the pre-theoretic notion of entailment. Overview The truth c ...
, 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: :: $\models \phi \lor \psi$     if     $\models \phi$     or     $\models \psi$     or     both This semantics corresponds to the following truth table:

## Defined by other operators

In classical logic systems where logical disjunction is not a primitive, it can be defined in terms of the primitive " and" ($\land$) and " not" ($\lnot$) as: :$A \lor B = \neg \left(\left(\neg A\right) \land \left(\neg B\right)\right)$. Alternatively, it may be defined in terms of " implies" ($\to$) and "not" as: :$A \lor B = \left(\lnot A\right) \to B$. The latter can be checked by the following truth table:

## Properties

The following properties apply to disjunction: *
Associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacemen ...
: $a \lor \left(b \lor c\right) \equiv \left(a \lor b\right) \lor c$ * Commutativity: $a \lor b \equiv b \lor a$ *
Distributivity In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmet ...
: $\left(a \land \left(b \lor c\right)\right) \equiv \left(\left(a \land b\right) \lor \left(a \land c\right)\right)$ :::$\left(a \lor \left(b \land c\right)\right) \equiv \left(\left(a \lor b\right) \land \left(a \lor c\right)\right)$ :::$\left(a \lor \left(b \lor c\right)\right) \equiv \left(\left(a \lor b\right) \lor \left(a \lor c\right)\right)$ :::$\left(a \lor \left(b \equiv c\right)\right) \equiv \left(\left(a \lor b\right) \equiv \left(a \lor c\right)\right)$ * Idempotency: $a \lor a \equiv a$ *
Monotonicity In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...
: $\left(a \rightarrow b\right) \rightarrow \left(\left(c \lor a\right) \rightarrow \left(c \lor b\right)\right)$ :::$\left(a \rightarrow b\right) \rightarrow \left(\left(a \lor c\right) \rightarrow \left(b \lor c\right)\right)$ *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 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 A bit field is a data structure that consists of one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to ...
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.

## 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 JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of websites use JavaScript on the client side for webpage behavior, ofte ...
), the logical disjunction operator returns one of its operands: the first operand if it evaluates to a true value, and the second operand otherwise.

## Constructive disjunction

The Curry–Howard correspondence relates a constructivist form of disjunction to
tagged union In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. ...
types.

# Set theory

The
membership Member may refer to: * Military jury, referred to as "Members" in military jargon * Element (mathematics), an object that belongs to a mathematical set * In object-oriented programming, a member of a class ** Field (computer science), entries ...
of an element of a union set in set theory is defined in terms of a logical disjunction: $x\in A\cup B\Leftrightarrow \left(x\in A\right)\vee\left(x\in B\right)$. Because of this, logical disjunction satisfies many of the same identities as set-theoretic union, such as
associativity In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacemen ...
, commutativity,
distributivity In mathematics, the distributive property of binary operations generalizes the distributive law, which asserts that the equality x \cdot (y + z) = x \cdot y + x \cdot z is always true in elementary algebra. For example, in elementary arithmet ...
, and de Morgan's laws, identifying logical conjunction with set intersection,
logical negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fal ...
with set complement.

# Natural language

Disjunction in natural languages does not precisely match the interpretation of $\lor$ in classical logic. Notably, classical disjunction is inclusive while natural language disjunction is often understood exclusively, as the following English typically would be. :1. Mary is eating an apple or a pear. This inference has sometimes been understood as an
entailment Logical consequence (also entailment) is a fundamental concept in logic, which describes the relationship between statements that hold true when one statement logically ''follows from'' one or more statements. A valid logical argument is on ...
, for instance by
Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...
, 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 French (french: français(e), link=no) may refer to: * Something of, from, or related to France ** French language, which originated in France, and its various dialects and accents ** French people, a nation and ethnic group identified with Franc ...
''soit... soit'' have been argued to be inherently exclusive, rendering un grammaticality in contexts where an inclusive reading would otherwise be forced. 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. You can have an apple or a pear. ::$\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 A question is an utterance which serves as a request for information. Questions are sometimes distinguished from interrogatives, which are the grammatical forms typically used to express them. Rhetorical questions, for instance, are interrogativ ...
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 Alternative semantics (or Hamblin semantics) is a framework in formal semantics and logic. In alternative semantics, expressions denote ''alternative sets'', understood as sets of objects of the same semantic type. For instance, while the word "L ...
and inquisitive semantics, which have also been adopted to explain the free choice and simplification inferences. :3. Is Mary a philosopher or a linguist? In English, as in many other languages, disjunction is expressed by a
coordinating conjunction In grammar, a conjunction (abbreviated or ) is a part of speech that connects words, phrases, or clauses that are called the conjuncts of the conjunctions. That definition may overlap with that of other parts of speech and so what constitutes a ...
. 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''.

* Affirming a disjunct *
Bitwise OR In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic oper ...
*
Boolean algebra (logic) In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...
* Boolean algebra topics *
Boolean domain In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written ...
* Boolean function *
Boolean-valued function A Boolean-valued function (sometimes called a predicate or a proposition) is a function of the type f : X → B, where X is an arbitrary set and where B is a Boolean domain, i.e. a generic two-element set, (for example B = ), whose elements ar ...
* Disjunctive syllogism *
Disjunction elimination In propositional logic, disjunction elimination (sometimes named proof by cases, case analysis, or or elimination), is the valid argument form and rule of inference that allows one to eliminate a disjunctive statement from a logical proof. I ...
*
Disjunction introduction Disjunction introduction or addition (also called or introduction) is a rule of inference of propositional logic and almost every other deduction system. The rule makes it possible to introduce disjunctions to logical proofs. It is the infere ...
* First-order logic *
Fréchet inequalities In probabilistic logic, the Fréchet inequalities, also known as the Boole–Fréchet inequalities, are rules implicit in the work of George BooleBoole, G. (1854). ''An Investigation of the Laws of Thought, On Which Are Founded the Mathematical The ...
*
Free choice inference Free choice is a phenomenon in natural language where a linguistic disjunction appears to receive a logical conjunctive interpretation when it interacts with a modal operator. For example, the following English sentences can be interpreted to mean ...
*
Hurford disjunction In formal semantics, a Hurford disjunction is a disjunction in which one of the disjuncts entails the other. The concept was first identified by British linguist James Hurford. The sentence "Mary is in the Netherlands or she is in Amsterdam" is a ...
* Logical graph * Logical value * Operation * Operator (programming) *
OR gate The OR gate is a digital logic gate that implements logical disjunction. The OR gate returns true if either or both of its inputs are true; otherwise it returns false. The input and output states are normally represented by different voltage lev ...
*
Propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...
* Simplification of disjunctive antecedents

# Notes

*
George Boole George Boole (; 2 November 1815 – 8 December 1864) was a largely self-taught English mathematician, philosopher, and logician, most of whose short career was spent as the first professor of mathematics at Queen's College, Cork in ...
, 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.