|
In logical calculus, logical operators or logical connectors serve to connect statements into more complicated compound statements. 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" (∧, , 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" () and "set theoretic intersection" (∩); likewise for "or" (∨) and "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 precendence 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 nessessary 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.
- 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.
See also
| 
Feeds |
Contact