In logic, disjunction (also known as logical disjunction, logical or, logical addition, or inclusive disjunction) is a logical connective typically notated as ∨ and read aloud as "or". For instance, the English language sentence "it is sunny or it is warm" can be represented in logic using the disjunctive formula S ∨ W, assuming that S abbreviates "it is sunny" and W abbreviates "it is warm". In classical logic, disjunction is given a truth functional semantics according to which a formula ϕ ∨ ψ {\displaystyle \phi \lor \psi } is true unless both ϕ {\displaystyle \phi } and ψ {\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 as the numerous mismatches between classical disjunction and its nearest equivalents in natural languages. An operand of a disjunction is a disjunct.
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 is 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 use 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 ∨ (Unicode U+2228 ∨ LOGICAL OR). Alternative notations include +, used mainly in electronics, as well as | and || 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). In mathematics, the disjunction of an arbitrary number of elements a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} can be denoted as an iterated binary operation using a larger ⋁ (Unicode U+22C1 ⋁ N-ARY LOGICAL OR):
⋁ i = 1 n a i = a 1 ∨ a 2 ∨ … a n − 1 ∨ a n {\displaystyle \bigvee _{i=1}^{n}a_{i}=a_{1}\lor a_{2}\lor \ldots a_{n-1}\lor a_{n}}
Classical disjunction
Semantics In the semantics of logic, 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:
⊨ ϕ ∨ ψ {\displaystyle \models \phi \lor \psi } if ⊨ ϕ {\displaystyle \models \phi } or ⊨ ψ {\displaystyle \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 (∧) and not (¬) as:
A ∨ B = ¬((¬A) ∧ (¬B)). Alternatively, it may be defined in terms of implies ( → {\displaystyle \to } ) and not as:
A ∨ B = (¬A) → B. The latter can be checked by the following truth table:
It may also be defined solely in terms of → {\displaystyle \to } :
A ∨ B = ( A → B ) → B {\displaystyle A\lor B=(A\to B)\to B} . It can be checked by the following truth table:
Properties The following properties apply to disjunction:
Associativity: a ∨ (b ∨ c) ≡ (a ∨ b) ∨ c Commutativity: a ∨ b ≡ b ∨ a Distributivity: (a ∧ (b ∨ c)) ≡ ((a ∧ b) ∨ (a ∧ c)) (a ∨ (b ∧ c)) ≡ ((a ∨ b) ∧ (a ∨ c)) (a ∨ (b ∨ c)) ≡ ((a ∨ b) ∨ (a ∨ c)) (a ∨ (b ≡ c)) ≡ ((a ∨ b) ≡ (a ∨ c)) Idempotency: a ∨ a ≡ a Monotonicity: (a → b) → ((c ∨ a) → (c ∨ b)) (a → b) → ((a ∨ c) → (b ∨ 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
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.
… excerpt ends here. Continue reading the full article.
