Logical connective
From Wikipedia, the free encyclopedia
In logic, a logical connective or propositional operator is a syntactic operation on sentences, or the symbol for such an operation, that corresponds to a logical operation on the logical values of those sentences.
For example, the two sentences, "It's raining" and "I'm indoors", can be combined by means of various connectives to form the following compound sentences:
-
- It's not raining so I'm indoors.
- It's raining and I'm indoors.
- If it's raining then I'm indoors.
The basic operators are "not" (¬ or ~), "and" (∧ or &), "or" (∨), "conditional" (→ or ⊃), 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" (∧) 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 |
Here is a table that shows the precedence of logical operators.
| Operator | Precedence |
|---|---|
| ¬ | 1 |
| ∧ | 2 |
| ∨ | 3 |
| → | 4 |
| ↔ | 5 |
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) "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.
