Boolean Logic

Every decision a computer makes — every "if this, then that" — comes down to two values: TRUE or FALSE. Boolean Logic is the algebra of these two values. This chapter covers truth tables, the basic and derived logic gates, the postulates and theorems of Boolean algebra, DeMorgan's Theorems, and how to draw logic circuits for Boolean expressions.

3.1 📜 Development of Boolean Logic

Boolean Logic (also called Boolean Algebra) was developed by the mathematician George Boole in the 1850s — a system of logic using only TWO values: TRUE (1) and FALSE (0).

graph LR
    BOOLE["👨‍🔬 George Boole\n(1854)\n'An Investigation of\nthe Laws of Thought'"]
    ALGEBRA["🧮 Boolean Algebra\n(Mathematical logic\nsystem)"]
    COMPUTERS["💻 Modern Computers\n(Built on TRUE/FALSE\ncircuit logic!)"]

    BOOLE --> ALGEBRA --> COMPUTERS

    style BOOLE fill:#9C27B0,color:#fff
    style COMPUTERS fill:#4CAF50,color:#fff

Why does this matter for computers? Remember from Chapter 1 — computers are just millions of switches, each either ON or OFF. Boolean Logic gives us the MATHEMATICAL RULES to combine and simplify these ON/OFF (TRUE/FALSE) values — this is literally how ALL digital circuits and computer decision-making work!

3.2 🔢 Binary Valued Quantities

A Binary Valued Quantity is any variable that can hold ONLY ONE of TWO possible values.

graph LR
    T["✅ TRUE\n1\nHIGH\nYES\nON"]
    F["❌ FALSE\n0\nLOW\nNO\nOFF"]

    style T fill:#4CAF50,color:#fff
    style F fill:#F44336,color:#fff

Real-World Examples of Binary Values:

3.3 🔧 Logical Operations

3.3.1 Logical Function or Compound Statement 📝

A Logical Function (or Compound Statement) is an expression formed by combining ONE OR MORE Boolean variables using logical operators, producing a TRUE or FALSE result.

Example: Y = A AND B
Here, Y is the logical function, A and B are Boolean variables,
and AND is the logical operator combining them.

Analogy: Think of a logical function like a RECIPE. The ingredients (A, B) go IN, an operation (AND/OR/NOT) is applied, and a single RESULT (TRUE or FALSE) comes OUT!

3.3.2 Logical Operators 🔧

The THREE fundamental logical operators form the foundation of ALL Boolean logic:

graph TD
    OPS["🔧 LOGICAL OPERATORS"]
    NOT["🚫 NOT\n(Inverts the value)"]
    AND["✖️ AND\n(TRUE only if BOTH true)"]
    OR["➕ OR\n(TRUE if AT LEAST ONE true)"]

    OPS --> NOT
    OPS --> AND
    OPS --> OR

    style NOT fill:#F44336,color:#fff
    style AND fill:#2196F3,color:#fff
    style OR fill:#4CAF50,color:#fff

Symbols Used in Boolean Expressions:

3.3.3 Evaluation of Boolean Expressions using Truth Table 📊

A Truth Table lists ALL possible combinations of input values and the corresponding output result — the ultimate "cheat sheet" for any Boolean expression!

Truth Table for AND:

Truth Table for OR:

Truth Table for NOT:

Memory Trick! 🎵 AND = Strict Boss — needs EVERYONE to say yes. OR = Easy-going friend — just needs ONE yes. NOT = The Opposite Person — always disagrees!

Evaluating a Compound Expression: Y = A·B + C

3.4 🚪 Basic Logic Gates

A Logic Gate is a physical electronic circuit that implements a Boolean/logical operation — taking one or more inputs and producing ONE output.

3.4.1 Inverter (NOT Gate) 🚫

graph LR
    IN["A"] -->|"NOT Gate\n—▷o—"| OUT["Ā (NOT A)"]

    style IN fill:#2196F3,color:#fff
    style OUT fill:#F44336,color:#fff

Truth Table:

The NOT gate has only ONE input and simply FLIPS/inverts it.

3.4.2 OR Gate ➕

graph LR
    A["A"] --> GATE["OR Gate"]
    B["B"] --> GATE
    GATE --> OUT["A + B"]

    style GATE fill:#4CAF50,color:#fff

Truth Table:

OR Gate Rule: Output is TRUE if AT LEAST ONE input is TRUE. Only FALSE when BOTH inputs are FALSE.

3.4.3 AND Gate ✖️

graph LR
    A["A"] --> GATE["AND Gate"]
    B["B"] --> GATE
    GATE --> OUT["A · B"]

    style GATE fill:#2196F3,color:#fff

Truth Table:

AND Gate Rule: Output is TRUE ONLY when BOTH inputs are TRUE. Any single FALSE input makes the whole output FALSE.

3.5 📐 Basic Postulates of Boolean Logic

Postulates are the fundamental, self-evident RULES that form the foundation of Boolean Algebra — accepted as true without needing proof.

3.6 🔄 Principle of Duality

The Principle of Duality states that EVERY valid Boolean expression remains valid if you SWAP:

• AND ↔ OR
• 0 ↔ 1

graph LR
    ORIG["Original Expression\nA + 0 = A"]
    SWAP["Swap AND↔OR, 0↔1"]
    DUAL["Dual Expression\nA · 1 = A"]

    ORIG --> SWAP --> DUAL

    style ORIG fill:#2196F3,color:#fff
    style DUAL fill:#4CAF50,color:#fff

More Duality Examples:

Analogy: Duality is like a MIRROR IMAGE — every rule has a "twin" rule where AND and OR simply swap places, and 0/1 swap places too. If one is TRUE, the mirrored version is AUTOMATICALLY true as well!

3.7 📜 Basic Theorems of Boolean Algebra/Logic

These are the LAWS you'll use CONSTANTLY to simplify Boolean expressions — memorise them well!

3.7.1 Properties of 0 and 1

3.7.2 Indempotence Law

"Combining a variable with ITSELF changes nothing."

3.7.3 Involution (Double Negation)

"NOT-NOT A equals A" — flipping twice returns the original!

(A')' = A

Analogy: Like saying "It's NOT that I DON'T like pizza" — the double negative means you DO like pizza! Two NOTs cancel out.

3.7.4 Complementarity Law

A value combined with its OPPOSITE via OR is ALWAYS true; combined via AND is ALWAYS false.

3.7.5 Commutative Law

"Order doesn't matter" — just like in regular math!

3.7.6 Associative Law

"Grouping doesn't matter" — how you bracket the terms doesn't change the result.

3.7.7 Distributive Law

"AND/OR distribute over each other" — similar to multiplication distributing over addition in regular math.

3.7.8 Absorption Law

"A larger expression gets 'absorbed' into a simpler one."

Analogy: If you already own a "car" (A), owning "a car AND a specific model of that car" (A·B) doesn't add anything NEW — it's absorbed into just owning "a car" (A)!

3.7.9 Some Other Rules of Boolean Logic Algebra

Complete Boolean Laws — Master Summary Table:

3.8 🔄 DeMorgan's Theorems

DeMorgan's Theorems are central to this chapter — they explain how NOT interacts with AND/OR!

3.8.1 DeMorgan's First Theorem

(A · B)' = A' + B'

"The complement of an AND expression equals
 the OR of the individual complements"

Verification via Truth Table:

Both (A·B)' and A'+B' produce IDENTICAL results in every row — proving the theorem!

3.8.2 DeMorgan's Second Theorem

(A + B)' = A' · B'

"The complement of an OR expression equals
 the AND of the individual complements"

Verification via Truth Table:

Memory Trick! 🎵 "Break the bar, change the operator!" When you push a NOT bar INSIDE brackets, it BREAKS apart onto each variable, AND the operator FLIPS (AND↔OR)!

graph TD
    A["(A·B)'"]
    B["Break the bar,\nFlip AND to OR"]
    C["A' + B'"]

    A --> B --> C

    style A fill:#F44336,color:#fff
    style C fill:#4CAF50,color:#fff

3.9 🚪 More about Logic Gates

Beyond the basic 3 gates, these DERIVED gates are built by COMBINING basic gates — and are extremely important in circuit design!

graph TD
    MORE["🚪 MORE LOGIC GATES"]
    NOR["NOR = NOT(OR)"]
    NAND["NAND = NOT(AND)"]
    XOR["XOR = Exclusive OR"]
    XNOR["XNOR = Exclusive NOR"]

    MORE --> NOR
    MORE --> NAND
    MORE --> XOR
    MORE --> XNOR

    style NOR fill:#FF9800,color:#fff
    style NAND fill:#9C27B0,color:#fff
    style XOR fill:#F44336,color:#fff
    style XNOR fill:#2196F3,color:#fff

3.9.1 NOR Gate (NOT + OR)

Truth Table:

NOR = OR gate followed by a NOT — output is the exact OPPOSITE of a regular OR gate!

3.9.2 NAND Gate (NOT + AND)

Truth Table:

NAND = AND gate followed by a NOT — output is the exact OPPOSITE of a regular AND gate!

3.9.3 XOR Gate (Exclusive OR)

Truth Table:

XOR Rule: Output is TRUE only when inputs are DIFFERENT from each other. If BOTH are the same (both 0 or both 1), output is FALSE.

Analogy: XOR is like an "Either-Or, but NOT Both" situation — "You can have cake OR ice cream" (not both, and not neither)!

3.9.4 XNOR Gate (Exclusive NOR)

Truth Table:

XNOR Rule: Output is TRUE when inputs are the SAME (both 0 or both 1) — exactly the OPPOSITE of XOR!

All 7 Logic Gates — Complete Summary Table:

3.10 🔌 Logic Circuits

A Logic Circuit combines MULTIPLE logic gates together to implement a COMPLEX Boolean expression.

Example: Building the circuit for Y = A·B + C

graph LR
    A["A"] --> AND["AND Gate"]
    B["B"] --> AND
    AND --> OR["OR Gate"]
    C["C"] --> OR
    OR --> Y["Y = A·B + C"]

    style AND fill:#2196F3,color:#fff
    style OR fill:#4CAF50,color:#fff

Steps to Draw a Logic Circuit from a Boolean Expression:

1. Identify all the input variables
2. Identify the operators used (AND/OR/NOT) and their ORDER
3. Draw gates matching each operator, connecting inputs correctly
4. Follow operator precedence: NOT is applied FIRST, then AND, then OR (just like math's BODMAS!)

⚠️ Common Errors and Misconceptions

AND (·) → TRUE only if BOTH true
OR (+)  → TRUE if AT LEAST ONE true
NOT (') → Inverts the value

(A·B)' = A' + B'   (First Theorem)
(A+B)' = A' · B'   (Second Theorem)
"Break the bar, flip the operator!"

🎯 Sample Exam Questions

Q1: Very Short Answer [1 mark each]

a) Who developed Boolean Logic? → George Boole

b) What are the two values used in Boolean Algebra? → TRUE (1) and FALSE (0)

c) Write the dual of A + 0 = A. → A · 1 = A

d) State DeMorgan's First Theorem. → (A·B)' = A' + B'

e) Which gate gives TRUE output only when both inputs differ? → XOR Gate

Q2: Short Answer [2 marks]

Q: Simplify the Boolean expression: Y = A + A'B

Using the Redundancy Law: A + A'B = A + B Answer: Y = A + B

Q3: Short Answer [3 marks]

Q: State and verify DeMorgan's Second Theorem using a truth table.

Statement: (A+B)' = A' · B'

Both columns (A+B)' and A'·B' match exactly, verifying the theorem.

Q4: Truth Table [2 marks]

Q: Draw the truth table for Y = AB' + A'B

(Notice: this is exactly the XOR truth table!)

Q5: Circuit Drawing [3 marks]

Q: Draw the logic circuit for Y = (A + B)·C

Steps: (1) Feed A and B into an OR gate. (2) Take the OR gate's output and C into an AND gate. (3) The AND gate's output is Y.

✏️ Practice Problems

1. Construct the truth table for the expression Y = (A+B)·(A+C).

2. Simplify: Y = A·(A+B) using the Absorption Law.

3. State DeMorgan's First Theorem and apply it to simplify (A'+B')'.

4. Differentiate between NAND and NOR gates with truth tables.

5. Write the dual of the expression: A·(B+C) = A·B + A·C

6. Draw the logic circuit for Y = A'·B + A·B'

7. Explain why NAND and NOR gates are called "Universal Gates."

8. Simplify the expression Y = AB + A'C + BC using the Consensus Theorem.

9. Construct a truth table comparing XOR and XNOR gates for the same two inputs A and B.

10. A circuit has inputs A, B, C, and the Boolean expression Y = A·B + A·C. Simplify this expression using the Distributive Law and draw the simplified logic circuit.