To design circuits that perform complex operations on binary signals:
- Define primitive operators.
- Compose these primitive operators to perform more complex operations.
Primitive operators for combinational logic are called logic gates. The simplest logic gates are unary/binary operators that take as input one/two binary variables and output one binary value.
AND, OR, NOT gate: Perform the operation on the binary one bit at a time
-
Ex. 0b1001 0b0111 = 0b1111 - Ex. 0b1001 & 0b0111 = 0b0001
- Ex. ~0b1001 = 0b0110
NAND(a, b) = 1 IFF AND(a, b) = 0
NOR(a, b) = 1 IFF OR(a, b) = 0
XOR(a, b) = 1 IFF a ≠ b
\[\overline{a} b+a\overline{b}\]XNOR
\[\overline{a} \overline {b}+ab\]The symbol for common gates
NOT AND OR XOR NAND NOR XNOR
To compose the gates:
- Construct the truth table for the function definition by enumerating all input/output pairs.
- Use the truth table to write the canonical form, like $y = abc + ab\bar c$ .
- Use the laws of Boolean algebra to simplify the expressions.
- Construct the gate diagram.
The laws of Boolean algebra
| Name | AND Form | OR form |
|---|---|---|
| Commutative | AB = BA | A + B = B + A |
| Associative | AB(C) = A(BC) | A + (B + C) = (A + B) + C |
| Identity | 1A = A | 0 + A = A |
| Null | 0A = 0 | 1 + A = 1 |
| Absorption | A(A + B) = A | A + AB = A |
| Distributive | (A + B)(A + C) = A + BC | A(B + C) = AB + AC |
| Idempotent | A(A) = A | A + A = A |
| Inverse | $A(\bar{A}) = 0$ | $A + \bar{A} = 1$ |
| De Morgan’s law | $\overline{AB} = \bar{A} + \bar{B}$ | $\overline{A+B} = \bar{A}\bar{(B)}$ |