Logic - 6
Boolean Functions
Below are two tables containing all the possible outputs and possible inputs of the two variables $P$ and $Q$. We should be able to deduce the function of $P$ and $Q$ that gives the results:
| $P$ | $Q$ | $\bot$ | $P\wedge Q$ | $\neg(P\Rightarrow Q)$ | $P$ | $\neg(Q\Rightarrow P)$ | $Q$ | $\neg(P\equiv Q)$ | $P\vee Q$ |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| $P$ | $Q$ | $\neg(P\vee Q)$ | $P\equiv Q$ | $\neg Q$ | $Q\Rightarrow P$ | $\neg P$ | $P\Rightarrow Q$ | $\neg(P\wedge Q)$ | $\top$ |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Logic Gates
-
AND, OR, NOT
-
XOR
This is the same as $\neg(\equiv)$
-
NAND, NOR, XNOR
XNOR is the same as $\equiv$.
Universality of NAND and NOR
Both the NAND and NOR gates can be used in place of any other gate. They also have their own symbols:
- NAND (Sheffer Stroke)
- $P\vert Q=\neg(P\wedge Q)$
- NOR (Pierce Arrow)
- $P\downarrow Q=\neg(P\vee Q)$
The universality means that they can be used as all gates:
-
$\neg P \equiv P\vert P$
-
$P\vee Q\equiv (P\vert P)\vert(Q\vert Q)$
-
$P\wedge Q\equiv (P\vert Q)\vert(P\vert Q)$
By using a single gate we can drive cost down through economy of scale.