Logical disjunction
From Wikinfo
In logic and mathematics, logical disjunction (written or) is a logical operator that results in true just whenever some of its operands are true.
Contents |
Definition
Logical disjunction is an operation on two logical values, typically the values of two propositions, that produces a value of false if and only if both of its operands are false.
The truth table of p OR q (also written as p ∨ q) is as follows:
| p | q | p ∨ q |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
More generally a disjunction is a logical formula that can have one or more literals separated only by ORs. A single literal is often considered to be a degenerate disjunction.
Symbol
The mathematical symbol for logical disjunction varies in the literature. In addition to the word "or", the symbol "∨", deriving from the Latin word vel for "or", is commonly used for disjunction. For example: "A ∨ B " is read as "A or B ". Such a disjunction is false if both A and B are false. In all other cases it is true.
All of the following are disjunctions:
- A ∨ B
- ¬A ∨ B
- A ∨ ¬B ∨ ¬C ∨ D ∨ ¬E
The corresponding operation in set theory is the set-theoretic union.
Algebraic properties
For more than two inputs, OR can be applied to the first two inputs, and then the result can be OR'ed with each subsequent input:
- (A or (B or C)) ⇔ ((A or B) or C)
Because OR is associative, the order of the inputs does not matter: the same result will be obtained regardless of association.
The operator OR is also commutative and therefore the order of the operands is not important:
- A or B ⇔ B or A
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 1110 = 1110
Note that in computer science the OR operator can be used to set a bit to 1 by OR-ing the bit with 1.
Union
The union used 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.
Notes
- 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.
See also
Logical operators
|
Related topics
External links
- Stanford Encyclopedia of Philosophy entry
- Eric W. Weisstein. "Disjunction." From MathWorld--A Wolfram Web Resource
- Adapted from the Wikipedia article, "Logical_disjunction" http://en.wikipedia.org/wiki/Logical_disjunction, used under the GNU Free Documentation License.[[es:Disyunci�n l�gica]][[pt:Disjun��o l�gica]]
