Boolean Algebra & Logic Simplification: Laws, Theorems & Techniques

---

Core Concepts: Boolean Algebra Fundamentals

Boolean algebra is the mathematical foundation of digital logic design, manipulating binary variables (0/1) using logical operators (AND, OR, NOT). Unlike arithmetic, it follows truth-based laws rather than numerical operations.

1. Basic Laws of Boolean Algebra

These are universal rules that hold for all binary variables. Memorize them—they’re used in every simplification.

Visual Proof of Distributive Law:

A   B   C   A+B   A•C   B•C   (A+B)•(A+C)   A•(B+C)
0   0   0     0     0     0             0             0
0   0   1     0     0     0             0             0
0   1   0     1     0     0             0             0
0   1   1     1     0     1             0             0
1   0   0     1     1     0             1             0
1   0   1     1     1     0             1             1
1   1   0     1     0     0             0             1
1   1   1     1     1     1             1             1

The last two columns match: distributive law verified!

---

2. Boolean Theorems: De Morgan’s and Absorption

These transform NOT operations and reduce complexity in expressions.

De Morgan’s Theorems

Example: Simplify (X + Y)' • Z using De Morgan’s.

1. Apply De Morgan’s to (X + Y)' → X' • Y'.
2. Final expression: (X' • Y') • Z = X' • Y' • Z.

Absorption Laws

Real-World Tie-In:

• Khalti’s Payment Gateway: Uses absorption to simplify fraud-detection logic. If TransactionValid = (UserVerified + (UserVerified • OTPMatched)), absorption reduces it to just UserVerified (since OTP is already implied).

---

3. Simplification Techniques

A. Algebraic Simplification

Use laws/theorems to reduce terms. Goal: Fewer gates → cheaper hardware.

Worked Example: Simplify F = A'B'C + A'B'D + A'CD + ABC + ABD.

1. Factor A'B' from first two terms: A'B'(C + D) + A'CD + ABC + ABD.
2. Factor A' from next two: A'B'(C + D) + A'(C(D + D')) + AB(C + D).
3. Simplify D + D' to 1: A'B'(C + D) + A'C + AB(C + D).
4. Factor (C + D): (A'B' + AB)(C + D) + A'C.
5. Simplify A'B' + AB to A' + AB (consensus theorem).
6. Final: (A' + AB)(C + D) + A'C.

Visual Check:

A   B   C   D   F_original   F_simplified
0   0   0   0       0               0
0   0   0   1       0               0
0   0   1   0       1               1
0   0   1   1       1               1
0   1   0   0       0               0
0   1   0   1       0               0
0   1   1   0       1               1
0   1   1   1       1               1
1   0   0   0       0               0
1   0   0   1       0               0
1   0   1   0       1               1
1   0   1   1       1               1
1   1   0   0       0               0
1   1   0   1       0               0
1   1   1   0       1               1
1   1   1   1       1               1

Both columns match: simplification correct!

B. Consensus Theorem

XY + X'Z + YZ = XY + X'Z (removes redundant term). Example: Simplify AB + A'C + BC.

• Here, BC is the consensus term → remove it.
• Final: AB + A'C.

Real-World Use:

• NTC’s Traffic Light Controller: Uses consensus to eliminate redundant sensor checks when multiple inputs (e.g., CarDetected_A + CarDetected_B + CarDetected_A•CarDetected_B) can trigger the same output.

---

4. Practical Applications in Digital Circuits

A. Gate Reduction

Simplified Boolean expressions → fewer gates → lower power consumption and faster circuits.

Example: Design a circuit for F = A'B'C + A'B'D + A'CD + ABC + ABD.

1. Simplified to (A' + AB)(C + D) + A'C.
2. Implement using 2 AND gates, 1 OR gate, and 1 NOT gate (vs. 5 gates for original).

Circuit Diagram:

A ---[NOT]---> A' ---[AND]---> (A' + AB) B ---[AND]---> AB ---[OR]---> (A' + AB) C ---[OR]---> (C + D) D (A' + AB) ---[AND]---> (A' + AB)(C + D) A' ---[AND]---> A'C (C + D) ---[OR]---> Final Output F

#### **B. Real Chips Using Simplified Logic**
```figure
{"type":"layers","layers":["74LS86 (XOR)","74LS08 (AND)","74LS32 (OR)"],"right":["Parity Checkers","Multipliers","Decoders"],"highlight":["74LS86 (XOR)"],"caption":"Real-world ICs using simplified Boolean logic (highlighted: 74LS86 for parity)"}

---

In the Real World

1. Khalti’s Fraud Detection:

   • Uses Boolean simplification to merge multiple fraud-check conditions (e.g., TransactionValid = (UserVerified • OTPMatched) + (UserVerified • BiometricMatch)) into a single optimized gate.
   • Why? Reduces latency in transaction processing.

2. NTC’s Smart Traffic Lights:

   • Simplifies sensor inputs (e.g., GreenLight = (CarDetected_A + CarDetected_B) • !EmergencyVehicle) using absorption laws to avoid redundant checks.
   • Impact: Saves energy and reduces hardware costs.

3. Daraz’s Order Fulfillment Queue:

   • Uses priority encoders (based on Boolean logic) to assign delivery routes. Simplified logic ensures faster order processing.
   • Example: HighPriority = (OrderValue > 1000) • (CustomerTier = Gold).

---

5. Common Pitfalls & Exam Tips

Mistakes to Avoid

• Forgetting to apply laws systematically: Always start with factoring or grouping.
• Ignoring consensus terms: Leads to incomplete simplification.
• Misapplying De Morgan’s: Remember (A + B)' = A' • B' (NOT A' + B').

Exam Strategy

1. Show all steps: Examiners reward methodical simplification.
2. Verify with truth tables: Always cross-check simplified vs. original expressions.
3. Recognize patterns:
   • XY + X'Z → Consensus term.
   • A + AB → Absorption → A.
4. Practice with real scenarios:
   • "Design a circuit for a bank’s loan approval system where LoanApproved = (CreditScore > 700) • (Income > 50k) + (CollateralAvailable • Income > 30k)."

---

Exam Tip

• Unit 8 is 10% of your total marks. Expect:
  • 3–4 questions on simplification (algebraic + consensus).
  • 1 question on applying laws to real circuits (e.g., "Simplify the logic for a traffic light controller").
  • 1 short answer on De Morgan’s or absorption laws.
• Pro Tip: Memorize the consensus theorem—it’s a favorite exam question. Always check if XY + X'Z + YZ appears in your expression!

---

Summary Table: Simplification Techniques