Boolean Algebra & Logic Gates: Laws, Minimization, Gates & Latches

---

Boolean Algebra Fundamentals

1. Definitions and Basic Laws

Boolean algebra is a mathematical system for manipulating binary variables (0 and 1) using logical operations. It forms the foundation for designing digital circuits.

Key Laws (Visualized in Truth Tables)

Worked Example: Simplify $F=AB+A(B+C)+B(B+C)$. Solution:

1. Apply Distributive Law to $A(B+C)$: $F=AB+AB+AC+B(B+C)$.
2. Simplify using Idempotent Law ($AB+AB=AB$): $F=AB+AC+B(B+C)$.
3. Expand $B(B+C)$: $F=AB+AC+BB+BC$.
4. Apply Idempotent Law ($BB=B$): $F=AB+AC+B+BC$.
5. Factor $B$ from terms: $F=B(A+1+C)+AC$.
6. Since $A+1=1$, simplify to: $F=B+AC$.

---

In the Real World

1. eSewa (Nepal):

   • Boolean Logic in Payment Validation: When you pay via eSewa, the system checks multiple conditions (e.g., account_balance > amount, OTP_matched, network_available) using AND/OR gates in hardware to approve/reject transactions. Example: Transaction_Approved = (Balance_OK AND OTP_Valid) OR (Admin_Override).

2. Khalti’s Fraud Detection:

   • Uses Boolean expressions to flag suspicious transactions. For example: Fraud_Alert = (Amount > Threshold) AND (Location_Change) AND (Time_Window_Violation).

3. NTC’s Traffic Light Control:

   • Traffic lights use sequential logic (flip-flops) to cycle through states (Red → Green → Yellow). The timing is controlled by Boolean conditions like: Green_Light = NOT (Pedestrian_Button_Pressed) AND (Current_State = Green).

---

2. Logic Gates and Their Symbols

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

Basic Gates

Universal Gates (NAND and NOR)

• NAND Gate: Output is 0 only if all inputs are 1.
• NOR Gate: Output is 1 only if all inputs are 0.
• Why Universal? Any Boolean function can be implemented using only NAND or only NOR gates.

Example: Implement $F=AB+C$ using NAND gates only. Solution:

1. Rewrite $F$ using De Morgan’s Law: $F=(AB{)}^{\prime }+C^{\prime }$'.
2. Implement using NAND gates as shown below:

NAND Gate IC (7400 Series) (Image: Tosaka, CC BY 3.0, via Wikimedia Commons)

```mermaid
flowchart LR
  A["A"] --> N1["NAND"]
  B["B"] --> N1
  N1 --> N2["NAND"]
  C["C"] --> N2
  N2 --> F["F = AB + C"]

---

3. Boolean Function Minimization

A. Algebraic Minimization

Use Boolean laws to simplify expressions. Example: Simplify $F=A^{\prime }{B}^{\prime }C+A^{\prime }B{C}^{\prime }+A{B}^{\prime }C+AB{C}^{\prime }$. Solution:

1. Group terms with common literals: $F=C(A^{\prime }{B}^{\prime }+A{B}^{\prime })+C^{\prime }(A^{\prime }B{C}^{\prime }+AB{C}^{\prime })$.
2. Factor: $F=C(B^{\prime }+A{B}^{\prime })+C^{\prime }(A^{\prime }B{C}^{\prime }+AB{C}^{\prime })$.
3. Simplify $B^{\prime }+A{B}^{\prime }=B^{\prime }$: $F=C{B}^{\prime }+C^{\prime }(A^{\prime }B{C}^{\prime }+AB{C}^{\prime })$.
4. Factor $C^{\prime }$: $F=C{B}^{\prime }+C^{\prime }(B(A^{\prime }+A))$.
5. Since $A^{\prime }+A=1$: $F=C{B}^{\prime }+C^{\prime }B$.
6. Factor $B$: $F=B(C^{\prime }+C)=B$.

Result: $F=B$ (simplified to a single input!).

---

B. K-Map Minimization (Visual Grouping)

Karnaugh Maps (K-maps) provide a graphical method to minimize Boolean functions.

Example: 4-Variable K-Map

Minimize $F(A,B,C,D)=\Sigma (0,2,4,6,8,10,12,14)$ with don’t-cares $d(1,3,11)$.

Steps:

1. Group 8-cell blocks (powers of 2):
   • Group 1: Cells 0,2,8,10 → $\overline{B}\overline{D}$.
   • Group 2: Cells 4,6,12,14 → $BD$.
2. Don’t-cares can be used to complete groups (e.g., cell 1 is unused but adjacent to 0 and 2).
3. Final Expression: $F=\overline{B}\overline{D}+BD$.

Implementation with Universal Gates: Use NAND gates to implement $\overline{B}\overline{D}$ and $BD$, then combine with a NAND as OR.

---

4. Sequential Logic: Latches and Flip-Flops

Sequential circuits store state (memory) using latches or flip-flops.

A. SR Latch (Basic Memory Element)

Problem: Invalid state when $S=R=1$. Solution: Use JK or D flip-flops.

Real Picture:

---

B. Flip-Flops (Edge-Triggered)

Flip-flops are clocked versions of latches, avoiding invalid states.

Example: JK Flip-Flop as T Flip-Flop Connect $J=K=T$. On each clock pulse, the output toggles:

• $Q_{n+1}=Q_n\oplus 1$.

Application in Pathao’s Ride Allocation: Pathao uses flip-flops in counters to track ride requests in real-time. For example:

• A binary counter (made of T flip-flops) increments with each new request.
• When the counter reaches a threshold (e.g., 100), it triggers a load balancer to assign drivers.

---

Exam Tip

1. For Boolean Algebra:

   • Always show step-by-step simplification using laws (e.g., distributive, absorption).
   • Draw truth tables for functions with 3+ variables to verify correctness.

2. For K-Maps:

   • Group in powers of 2 (1, 2, 4, 8 cells).
   • Use don’t-cares to complete larger groups (e.g., a 4-cell group).
   • Label groups clearly (e.g., $\overline{A}B$).

3. For Gates/Latches:

   • Draw standard symbols (not text-based).
   • Compare SR latch vs. flip-flops in exams (e.g., "Why is a JK flip-flop better than an SR latch?").
   • Memorize universal gate implementations (NAND/NOR for any function).

4. Real-World Links:

   • eSewa/Khalti: Boolean conditions for transactions.
   • NTC Traffic Lights: Sequential logic for timing.
   • Pathao/Daraz: Counters for request tracking.

---

Final Note: Master K-maps and flip-flop behavior—these are high-weightage topics in TU/PU exams. Practice designing circuits from Boolean expressions and vice versa.