| • Science | • People | • Locations | • Timeline |
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 gateA logic gate is an arrangement of electronically-controlled switches used to calculate operations in Boolean algebra. Logic gates can also be constructed from relays, diodes, fluidics and optical elements. Nikola Tesla first filed the patents on an electrs in digital circuitDigital circuits are electric circuits based on a number of discrete voltage levels. In most cases there are two voltage levels: one near to zero volts and one at a higher level depending on the supply voltage in use. These two levels are often representes. Practically all digital circuits (the major exception is DRAM) are built up from NAND, NOR, NOT, and transmission gateA transmission gate is a electronic element, representing an ideal non-mechanical relay, built with CMOS technology. Probably more usually known as an analog gate or electronic relay dependent on use. A current can flow through this element in either dires. 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.
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.