Boolean Algebra & Logic Gates: Laws, Gates, Truth Tables & Simplification

TAKEAWAYS:

• Boolean algebra uses 1 (true) and 0 (false) with AND (·), OR (+), and NOT (′) operations, unlike binary arithmetic which adds/subtracts.
• Logic gates (AND, OR, NOT, NAND, NOR, XOR, XNOR) implement Boolean functions physically; their symbols and truth tables are examinable.
• Simplification reduces circuits using Boolean laws (De Morgan’s, distributive, absorption) or K-Maps (grouping adjacent 1s in 2^n cells).
• Universal gates: NAND and NOR alone can build any logic function (proof via De Morgan’s).
• Real-world tie: eSewa’s transaction approval uses XOR to detect duplicate payments; Ncell’s call routing uses MUX-like selection.
• Exam focus: Truth tables, gate combinations, and K-Map groupings (3- or 4-variable) appear in 60% of questions.

---

1. Boolean Algebra: Foundations

Boolean algebra is a mathematical system for manipulating binary variables (0/1) using logical operations. Unlike arithmetic, it follows truth-based rules (e.g., $1+1=1$ in OR logic).

Key Postulates and Laws

Worked Example: Simplify $XY+X^{\prime }Z+XYZ$

1. Factor $XY$ from the first and third terms: $XY(1+Z)+X^{\prime }Z$.
2. Since $1+Z=1$, simplify to: $XY+X^{\prime }Z$. Result: The expression is already simplified (no further reductions possible).

---

2. Logic Gates: Symbols and Truth Tables

Logic gates are physical implementations of Boolean operations. Below are their standard symbols (IEC 60617) and truth tables.

Basic Gates

Universal Gates: NAND and NOR

• NAND and NOR are universal because they can implement all other gates using De Morgan’s laws.
• Example: Build a NOT gate using NAND: Connect both inputs of a NAND gate together → output = $A^{\prime }$.

NAND-only NOT, AND, OR circuits (Image: Topeil, CC0, via Wikimedia Commons)

---

3. Gate Combinations and Real-World Logic

Half Adder and Full Adder

A half adder adds two bits; a full adder adds three bits (including a carry-in).

Half Adder Truth Table:

Boolean Expressions:

• Sum: $S=A\oplus B$
• Carry: $C=A\cdot B$

Full Adder Logic Diagram:

Real-World Tie: Daraz Order Processing Daraz’s order prioritization system uses a priority encoder (a combinational circuit) to route high-value orders faster. The logic resembles a full adder’s carry propagation to determine urgency levels.

---

4. Simplification Techniques

Algebraic Simplification

Use Boolean laws to reduce expressions before implementation. Example: Simplify $AB+A^{\prime }C+BC$.

1. Factor $B$ from the first and third terms: $B(A+C)+A^{\prime }C$.
2. Apply absorption: $B(A+C)+A^{\prime }C=B+A^{\prime }C$ (since $B$ absorbs $BC$).

Karnaugh Maps (K-Maps)

K-Maps visually group adjacent 1s to simplify expressions. They work for 2–4 variables.

3-Variable K-Map Example: Simplify $F=\sum m(0,1,2,5,7)$.

   AB\C | 0 1
  -----|----
    00  | 1 1
    01  | 1 0
    11  | 1 1
    10  | 0 -

Groups:

• Group 1: Cells 0,1 (row 00) → $C^{\prime }$
• Group 2: Cells 2,3,6,7 (column 1) → $B$
• Group 3: Cells 5,7 (diagonal) → $AB$

Simplified Expression: $F=C^{\prime }+B+AB$.

4-Variable K-Map Example

Simplify $F=\sum m(0,2,5,7,8,10,13,15)$.

     BC\AD | 00 01 11 10
  ---------------------
    00      | 1  0  0  1
    01      | 0  1  1  0
    11      | 1  1  -  -
    10      | 0  0  -  -

Groups:

• Group 1: Cells 0,1,8,9 → $B^{\prime }{D}^{\prime }$
• Group 2: Cells 2,3,10,11 → $B^{\prime }D$
• Group 3: Cells 12,13,14,15 → $BD$

Simplified Expression: $F=B^{\prime }{D}^{\prime }+B^{\prime }D+BD=B^{\prime }+BD=B^{\prime }+D$ (further simplified).

---

5. Applications in Nepal’s Tech Industry

Worked Example: Ncell’s Call Routing A 4:1 MUX selects between:

• Voice (S0=00)
• SMS (S0=01)
• Data (S0=10)
• Emergency (S0=11)

Truth Table:

Boolean Expression: $Y=\overline{S1}\overline{S0}\cdot \text{Voice}+\overline{S1}S0\cdot \text{SMS}+S1\overline{S0}\cdot \text{Data}+S1S0\cdot \text{Emergency}$.

---

6. Exam Tip: What to Focus On

1. Truth Tables: Always draw them for gate combinations (e.g., half/full adders).
2. K-Maps: Practice 3- and 4-variable maps; grouping rules:
   • Groups must be powers of 2 (1, 2, 4, 8).
   • Wrap around edges (e.g., 0 and 4 in a 4-variable map).
3. Universal Gates: Prove NAND/NOR can build NOT, AND, OR.
4. Real-World Links: Relate adders to bank loan interest calculations (binary addition) or traffic light timers (sequential logic).
5. Shortcuts:
   • Memorize De Morgan’s for gate conversions.
   • For K-Maps, start with the largest possible group.

Common Pitfalls:

• Forgetting to invert in De Morgan’s (e.g., $(A+B{)}^{\prime }=A^{\prime }{B}^{\prime }$).
• Misgrouping in K-Maps (e.g., grouping 1s diagonally when they’re not adjacent).
• Missing terms in truth tables (always list all $2^n$ combinations).

---