Logic Gates, Truth Tables, Boolean Algebra & Simplification

What is Logic?

Logic is the study of reasoning. In computers, we use logic gates to perform basic operations like AND, OR, and NOT. These gates are the building blocks of all digital circuits, including CPUs.

Why is Logic Important?

• Computers process data using binary numbers (0s and 1s).
• Logic gates help computers make decisions (e.g., "If input A is 1 AND input B is 1, then output is 1").
• Used in circuit design, programming conditions, and digital electronics.

---

Logic Gates: The Basic Building Blocks

Logic gates take input signals (0 or 1) and produce an output signal (0 or 1) based on a specific rule.

Common Logic Gates

Here are the 7 basic logic gates with their symbols, truth tables, and functions:

---

Example: AND Gate Truth Table

Explanation:

• The AND gate outputs 1 only when both A and B are 1.
• Used in password checks (e.g., "If username AND password match, grant access").

---

Combining Logic Gates: Circuits

Logic gates can be combined to create complex circuits. For example:

Example: Half-Adder Circuit

A half-adder adds two binary digits (bits) and gives a sum and a carry.

Truth Table for Half-Adder:

Explanation:

• If A = 1 and B = 1, the sum is 0 and carry is 1 (like in decimal: 1 + 1 = 10).
• Used in binary addition in CPUs.

---

Boolean Algebra: Rules for Simplifying Logic

Boolean algebra is a math system for simplifying logic expressions using variables (A, B, C) and operators (AND, OR, NOT).

Basic Boolean Laws

---

Example: Simplifying a Boolean Expression

Problem: Simplify F = A'BC' + AB'C + ABC' + ABC

Step-by-Step Solution:

1. Factor out common terms:

   • F = C'(A'B + AB') + C(AB' + AB)
   • F = C'(A'B + AB') + C(A(B' + B))
   • Since B' + B = 1, then A(B' + B) = A · 1 = A
   • So, F = C'(A'B + AB') + AC

2. Apply De Morgan’s Law to A'B + AB':

   • A'B + AB' = (A' + A)(A' + B') (Wait, this is incorrect. Let’s try another approach.)
   • Instead, recognize that A'B + AB' = (A XNOR B) but let’s use the consensus theorem:
     • A'B + AB' = (A XOR B) but we can also write it as (A + B)(A' + B') (but this complicates things).
   • A better approach is to expand and simplify:
     • F = A'BC' + AB'C + ABC' + ABC
     • Group terms with C and C':
       • F = C'(A'B + AB) + C(AB' + AB)
       • F = C'(A'B + AB) + C(A(B' + B))
       • Since B' + B = 1, then A(B' + B) = A
       • So, F = C'(A'B + AB) + AC
     • Now, A'B + AB = B(A' + A) = B(1) = B (since A' + A = 1)
     • Therefore, F = C'B + AC

Final Simplified Form: F = AC + BC'

Verification: Let’s check if F = AC + BC' works for all inputs:

✅ Both expressions give the same output!

---

Karnaugh Maps (K-Maps): Simplifying Logic Further

A Karnaugh Map (K-Map) is a graphical method to simplify Boolean expressions.

Example: 3-Variable K-Map

For F = A'B'C + A'BC' + AB'C + ABC'

1. Draw the K-Map:

2. Group the 1s:

   • Group A'B'C and A'BC' (they differ only in B).
   • Group AB'C and ABC' (they differ only in B).
   • Group A'B'C and AB'C (they differ only in A).
   • Group A'BC' and ABC' (they differ only in A).

3. Simplify:

   • A'B'C + A'BC' = A'C(B' + B) = A'C(1) = A'C
   • AB'C + ABC' = AC(B' + B) = AC(1) = AC
   • Final simplified form: F = A'C + AC = C(A' + A) = C(1) = C

✅ The expression simplifies to just C!

---

Applications of Logic Gates and Boolean Algebra

1. Digital Circuits: Used in CPUs, memory chips, and microcontrollers.
2. Programming Conditions: if statements in C/Java use AND (&&), OR (||), and NOT (!).
3. Combinational Logic: Used in adders, multiplexers, and decoders.
4. Sequential Logic: Used in flip-flops and registers (for memory).
5. Error Detection: Parity bits (XOR gates) detect errors in data transmission.

---

NEB Exam-Style Questions

Short Answer Questions (SAQ)

1. Define a logic gate. Name any two logic gates and draw their symbols.

   • Answer: A logic gate is an electronic circuit that performs a logical operation on one or more binary inputs to produce a single binary output. Two gates:
     • AND Gate: A AND B

       -----
       |   |
       |---A
       |   |
       |---B
       |   |
       -----
       

     • OR Gate: A OR B

       -----
       |   |
       |---A
       |   |
       |---B
       |   |
       -----
       

2. Write the truth table for a NOR gate.

   • Answer:

     A	B	A NOR B
     0	0	1
     0	1	0
     1	0	0
     1	1	0

3. State De Morgan’s Laws.

   • Answer:
     • (A + B)' = A' · B'
     • (A · B)' = A' + B'

---

Long Answer Questions (LAQ)

4. Explain the working of a half-adder circuit with a truth table and circuit diagram.

   • Answer:
     • A half-adder adds two binary digits and produces a sum and a carry.
     • Circuit:
     • Truth Table:

       A	B	Sum (A XOR B)	Carry (A AND B)
       0	0	0	0
       0	1	1	0
       1	0	1	0
       1	1	0	1

5. Simplify the following Boolean expression using Boolean algebra laws: F = A'B'C + A'BC' + AB'C + ABC'

   • Answer:
     • Group terms: F = C'(A'B' + AB) + C(AB' + AB)
     • Simplify: F = C'(A'B' + AB) + C(A)
     • Since A'B' + AB = B(A' + A) = B(1) = B
     • Final: F = BC' + AC

6. Draw a K-Map for F = Σ(0, 2, 5, 7) and simplify it.

   • Answer:
     • K-Map (3 variables: A, B, C):

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

     • Grouping:
       • Group F(0) and F(2) (differ in B).
       • Group F(5) and F(7) (differ in B).
     • Simplified: F = B'C' + AC

---

Exam Tips for NEB Computer Science (Unit 3)

✅ Memorize Truth Tables: Know the truth tables for AND, OR, NOT, NAND, NOR, XOR, XNOR by heart. ✅ Draw Logic Gate Symbols: Be able to draw and label all 7 gates correctly. ✅ Practice Simplification: Use Boolean laws and K-Maps to simplify expressions. ✅ Understand Applications: Know how logic gates are used in adders, multiplexers, and programming conditions. ✅ K-Map Practice: Always group 1s in powers of 2 (1, 2, 4, 8) for simplification. ✅ De Morgan’s Laws: These are frequently tested—practice converting between AND/OR and NAND/NOR. ✅ Circuit Diagrams: For LAQs, always draw a neat circuit with proper labels.

---

Good luck with your NEB exam preparation! 🚀