Training Computer Engineering Boolean Algebra & Logic Gates
2 / 5

Boolean Algebra & Logic Gates

24 min Computer Engineering

Boolean Algebra & Logic Gates

Digital circuits are built from logic gates that implement Boolean functions. Simplifying Boolean expressions reduces circuit complexity.

Basic Operations

AND: $A \cdot B$ — output 1 only when both inputs are 1
OR: $A + B$ — output 1 when at least one input is 1
NOT: $\overline{A}$ — inverts the input

Boolean Algebra Laws
LawAND FormOR Form
Identity$A \cdot 1 = A$$A + 0 = A$
Null$A \cdot 0 = 0$$A + 1 = 1$
Complement$A \cdot \overline{A} = 0$$A + \overline{A} = 1$
Idempotent$A \cdot A = A$$A + A = A$
De Morgan's$\overline{A \cdot B} = \overline{A} + \overline{B}$$\overline{A + B} = \overline{A} \cdot \overline{B}$
Example 1

Simplify $F = A \cdot B + A \cdot \overline{B}$.

Factor out $A$: $F = A(B + \overline{B}) = A \cdot 1 = A$

Example 2

Simplify $F = \overline{\overline{A} + \overline{B}}$ using De Morgan's law.

$F = \overline{\overline{A}} \cdot \overline{\overline{B}} = A \cdot B$

Example 3

Write the truth table for $F = A \oplus B$ (XOR).

AB$A \oplus B$
000
011
101
110

XOR is 1 when inputs differ: $A \oplus B = A\overline{B} + \overline{A}B$

Practice Problems

1. Simplify: $F = A + A \cdot B$.
2. Simplify: $F = (A + B)(A + \overline{B})$.
3. Apply De Morgan's: $\overline{A \cdot B \cdot C}$.
4. Simplify: $\overline{\overline{A \cdot B} + C}$.
5. Write the Boolean expression for a 2-input NAND gate.
6. Complete the truth table for $F = A \cdot B + \overline{A} \cdot C$ with 3 inputs.
7. Express $F = \overline{A}B + AB$ in simplified form.
8. Prove that NAND is a universal gate by implementing NOT, AND, and OR using only NAND gates.
9. Simplify using a 2-variable Karnaugh map: $F = \overline{A}\overline{B} + \overline{A}B + A\overline{B}$.
10. How many rows does a truth table have for $n$ input variables?
11. Simplify: $F = ABC + AB\overline{C} + A\overline{B}C$.
12. Implement $F = A \oplus B$ using only AND, OR, and NOT gates.
Show Answer Key

1. $F = A$ (absorption law)

2. $F = A \cdot A + A\overline{B} + AB + B\overline{B} = A + A(\overline{B}+B) = A$

3. $\overline{A} + \overline{B} + \overline{C}$

4. $(A \cdot B) \cdot \overline{C}$ (De Morgan's then double negation)

5. $F = \overline{A \cdot B}$

6. 8-row truth table; $F = 1$ when ($A=1,B=1$) or ($A=0,C=1$)

7. $F = B(\overline{A}+A) = B$

8. NOT: $\overline{A} = \overline{A \cdot A}$. AND: $A \cdot B = \overline{\overline{A \cdot B}}$. OR: $A+B = \overline{\overline{A} \cdot \overline{B}}$.

9. K-map covers $\overline{A}$ row (2 cells) and $\overline{B}$ column; $F = \overline{A} + \overline{B}$

10. $2^n$ rows

11. $F = AB(C+\overline{C}) + A\overline{B}C = AB + A\overline{B}C = A(B + \overline{B}C) = A(B+C)$

12. $F = A\overline{B} + \overline{A}B$

Number Systems & Binary Arithmetic Algorithm Complexity — Big-O Notation