Logical disjunction
From Free net encyclopedia
Image:ORGate.png In mathematics, logical disjunction (usual symbol or) is a logical operator that results in true if either of the operands is true.
Contents |
Definition
In logic and mathematics, a disjunction is an "or statement". For example "John skis or Sally swims" is a disjunction.
Note that in everyday language, use of the word "or" can sometimes mean "either, but not both" (e.g., "would you like tea or coffee?"). In logic, this is called an "exclusive disjunction" or "exclusive or" (xor). When used formally, "or" allows for both parts of the or statement (its disjuncts) to be true ("and/or"), therefore "or" is also called inclusive disjunction.Template:Rf
For two inputs A and B, the truth table of the function is as follows.
| A | B | A or B |
|---|---|---|
| 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.
Associativity and Commutativity
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 xor 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.
Note
Template:Ent 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
External links
- Stanford Encyclopedia of Philosophy entry
- Eric W. Weisstein. "Disjunction." From MathWorld--A Wolfram Web Resourcebg:Дизюнкция
cs:Disjunkce de:Disjunktion et:Disjunktsioon es:Disyunción lógica fr:Disjonction logique id:Logika disjungsi he:או (לוגיקה) mk:Логичка дисјункција nl:Logische disjunctie ja:論理和 no:Inklusiv disjunksjon pl:Alternatywa pt:Disjunção lógica sk:Disjunkcia (logika) sr:Дисјункција sv:Logisk disjunktion th:การเลือกเชิงตรรกศาสตร์ uk:Диз'юнкція (логічна)