Unit 1: Computer Systems & Organisation
Chapter 3: Boolean Logic and Logic Gates
1. Introduction to Boolean Algebra
Formulated by English mathematician George Boole in 1854, Boolean Algebra is a mathematical system that operates on two binary values:
- True (or $1$, High voltage, Closed switch)
- False (or $0$, Low voltage, Open switch)
A statement or variable that can only evaluate to either True or False is called a Boolean Variable or Proposition.
2. Fundamental Logic Gates
A Logic Gate is an electronic circuit with one or more binary inputs and exactly one binary output.
AND Gate OR Gate NOT Gate
+--------------+ +--------------+ +------------+
A -| | A -\ \ A -| >o- A' (NOT)
| D |- Y ) ) |- Y +------------+
B -| | B -/ /
+--------------+ +--------------+
Y = A . B Y = A + B Y = A'
1. AND Gate (Conjunction $\cdot$)
Output is $1$ only if all inputs are $1$.
| $A$ | $B$ | $Y = A \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2. OR Gate (Disjunction $+$)
Output is $1$ if at least one input is $1$.
| $A$ | $B$ | $Y = A + B$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
3. NOT Gate (Inverter $\bar{A}$ or $A'$)
Inverts the incoming binary state. Single input, single output.
| $A$ | $Y = \bar{A}$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
3. Universal Logic Gates: NAND and NOR
Universal Gates can recreate the functional behavior of all other logic gates (AND, OR, NOT) using only combinations of themselves.
NAND Gate NOR Gate
+------------------+ +-------------------+
A -| | A -\ \
| D o-------|- Y ) ) o--------|- Y
B -| | B -/ /
+------------------+ +-------------------+
Y = (A . B)' Y = (A + B)'
Truth Tables for NAND and NOR
| $A$ | $B$ | $\text{NAND} = \overline{A \cdot B}$ | $\text{NOR} = \overline{A + B}$ |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
4. Special Purpose Gates: XOR and XNOR
XOR Gate (Exclusive-OR: $\oplus$)
- Output is $1$ when the number of $1$s in input is odd (i.e., inputs are different).
- Expression: $Y = A \oplus B = \bar{A}B + A\bar{B}$
XNOR Gate (Equivalence: $\odot$)
- Output is $1$ when inputs are identical ($0,0$ or $1,1$).
- Expression: $Y = A \odot B = AB + \bar{A}\bar{B} = \overline{A \oplus B}$
| $A$ | $B$ | $\text{XOR} (A \oplus B)$ | $\text{XNOR} (A \odot B)$ |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
5. Postulates and Laws of Boolean Algebra
| Law | OR Form ($+$) | AND Form ($\cdot$) |
|---|---|---|
| Identity Law | $A + 0 = A$ | $A \cdot 1 = A$ |
| Null / Annulment Law | $A + 1 = 1$ | $A \cdot 0 = 0$ |
| Idempotent Law | $A + A = A$ | $A \cdot A = A$ |
| Involution Law | $(A')' = A$ | $(A')' = A$ |
| Complementarity Law | $A + A' = 1$ | $A \cdot A' = 0$ |
| Commutative Law | $A + B = B + A$ | $A \cdot B = B \cdot A$ |
| Associative Law | $(A + B) + C = A + (B + C)$ | $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ |
| Distributive Law | $A + (B \cdot C) = (A + B)(A + C)$ | $A \cdot (B + C) = AB + AC$ |
| Absorption Law | $A + AB = A$ | $A(A + B) = A$ |
6. De Morgan's Theorems
De Morgan's Theorems are fundamental for simplifying complex Boolean expressions and designing digital circuits.
First Theorem:
The complement of a sum is equal to the product of individual complements: $$\overline{A + B} = \bar{A} \cdot \bar{B}$$
Second Theorem:
The complement of a product is equal to the sum of individual complements: $$\overline{A \cdot B} = \bar{A} + \bar{B}$$
Proof of First Theorem using Truth Table:
| $A$ | $B$ | $A + B$ | $\overline{A + B}$ | $\bar{A}$ | $\bar{B}$ | $\bar{A} \cdot \bar{B}$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Columns 4 and 7 are identical, proving $\overline{A + B} = \bar{A} \cdot \bar{B}$.
7. Board Exam Practice Questions & Solutions
Q1. Why are NAND and NOR gates called Universal Gates?
Answer:
NAND and NOR gates are termed Universal Gates because any basic logic function (AND, OR, NOT) or any complex Boolean circuit can be implemented entirely using only NAND gates or only NOR gates without requiring any other type of gate.
Q2. Simplify the Boolean expression: $F = AB + A\bar{B} + \bar{A}B$
Answer:
$$F = A(B + \bar{B}) + \bar{A}B$$
Since $B + \bar{B} = 1$:
$$F = A(1) + \bar{A}B = A + \bar{A}B$$
Using the Distributive Law $A + \bar{A}B = (A + \bar{A})(A + B)$:
$$F = (1)(A + B) = \mathbf{A + B}$$
Q3. Draw the truth table for the Boolean function $F(A, B, C) = A'B + C$.
Answer:
| $A$ | $B$ | $C$ | $A'$ | $A'B$ | $F = A'B + C$ |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |