Logical connective
|
|
In formal logic, logical connectives, also known as logical connectors and sometimes logical constants, serve to connect statements into more complicated compound statements. In algebraic logic, the more refined term logical operator is preferred.
For example, considering the assertions "It's raining", and "I'm inside", we can form the compound assertions "it's raining, and I'm inside" or "it's not raining" or "if it's raining, then I'm inside."
A new statement or proposition combining two statements is called a compound statement or compound proposition.
The basic operators are "not" (¬, or ~), "and" (∧, <math>\land<math>, or &), "or" (∨), "conditional" (→), and "biconditional" (iff) (↔). "Not" is a unary operator--it takes a single term (¬ P). The rest are binary operators, taking two terms to make a compound statement (P ∧ Q, P ∨ Q, P → Q, P ↔ Q).
Note the similarity between the symbols for "and" (<math>\land<math>) and set-theoretic intersection (∩); likewise for "or" (∨) and set-theoretic union (∪). This is not a coincidence: the definition of the intersection uses "and" and the definition of union uses "or".
Truth tables for these connectives:
| P | Q | ¬P | P ∧ Q | P ∨ Q | P → Q | P ↔ Q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
In order to reduce the number of necessary parentheses, one introduces precedence rules: ¬ has higher precedence than ∧, ∧ higher than ∨, and ∨ higher than →. So for example, P ∨ Q ∧ ¬ R → S is short for (P ∨ (Q ∧ (¬ R))) → S.
Not all of these operators are necessary for a full-blooded logical calculus. Certain compound statements are logically equivalent. For example, ¬ P ∨ Q is logically equivalent to P → Q;. So the conditional operator "→" is not necessary if you have "¬" (not) and "∨" (or).
For the sake of convenience (and brevity), only the five most-commonly used operators (in math) are listed above. One can also consider other connectives, such as NAND ("not-and"), XOR ("not-biconditional"), and NOR ("not-or").
Logical operators are implemented as logic gates in digital circuits. Practically all digital circuits (the major exception is DRAM) are built up from NAND, NOR, NOT, and transmission gates. NAND and NOR gates with 3 or more inputs rather than the usual 2 inputs are fairly common, although they are logically equivalent to a cascade of 2-input gates. All other operators are implemented by breaking them down into a logically equivalent combination of 2 or more of the above logic gates.
If you throw away all the operators that are not necessary, what operators are you left with ? Which conditionals are the crucial must-have ones ? Surprisingly, there is more than one answer to that question.
- All connectives can be expressed with NAND alone.
- All connectives can be expressed with NOR alone, as demonstrated by the Apollo guidance computer.
- Since NAND can be built from NOT and AND, and we know that all connectives can be built from NAND alone, clearly all connectives can be built from combinations of NOT and AND.
- ... and several other answers.
The "logical equivalence" of "NAND alone", "NOR alone", and "NOT and AND" is similar to Turing equivalence.
Is some new technology (such as reversible computing, clockless logic, quantum dots computing, or Tinker Toys) is "logically complete", in that it can be used to build computers that can do all the sorts of computation that CMOS-based computers can do ? If it can implement the NAND operator, only then is it logically complete.
References
- Article on logical constants (http://plato.stanford.edu/entries/logical-constants/) at the Stanford Encyclopedia of Philosophy.
See also
- Truth values
- Laws of logic
- xor
- or
- and
- XNOR
- List of Boolean algebra topics
- Bitwise operation
- Sheffer's strokeda:Logisk operator
de:Boolescher Operator he:פעולה בוליאנית ja:論理演算 sv:Logisk operator th:ตัวดำเนินการทางตรรกศาสตร์ zh:逻辑运算符