#+LINK w1 https://en.wikipedia.org/wiki/Logic_gate
#+LINK w1 https://en.wikipedia.org/wiki/Boolean_algebra
Boolean
Named after George Boole.
Boolean algebra properties
Associativity
- a + (b+c) = (a+b) + c
- a(bc) = (ab)c
Absorption
- a + ab = a
- a(a + b) = a
de Morgan's laws
- (ab)' = a' + b'
- (a+b)' = a'b'
Identity
- a + 0 = a
- a.1 = a
Commutativity
- a.b = b.a
- a + b = b + a
Distributivity
- a(b + c) = ab + ac
- a + bc = (a + b).(a + c)
Idempotency
- a.a = a
- a + a = a
Involution
aka 'double negation'.
- (a')' = a
Operations
- NOT: aka inverter
AND
| a | b | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR
| a | b | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
XOR
Exclusive OR.
True only when inputs doesn't have the same value.
| a | b | y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NAND
Inverted AND
| a | b | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR
Inverted OR
| a | b | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XNOR
Inverted XOR.
ie, True when both inputs are the same.
| a | b | y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Universal gates
- Can be used to realize any other gate.
- NAND, NOR
NAND
- NOT: (A.A)' → 1 NAND gate
- AND: (AB)'' → 2 NAND gates
- OR: (A+B)'' = (A'B')' → 3 NAND gates
NOR
- NOT: (A+A)' → 1 NOR gate
- AND: (AB)'' = (A'+B')' → 3 NOR gates
- OR: (A+B)'' → 2 NOR gates
References
- Switching Theory and Finite Automata (Third edition) by Zvi Kohavi, Niraj K. Jha
- [https://www.mi.mun.ca/users/cchaulk/misc/boolean.html](https://www.mi.mun.ca/users/cchaulk/misc/boolean.htm)