Part 3: Boolean Algebra and Logic Gates

Source: Part-3-+Boolean+Algebra+and+Logic+Gates.pdf

1. Basic Logic Gates (AND, OR, NOT)
💡 Simple Explanation: Logic gates are tiny electronic switches that make decisions. AND = both inputs must be true. OR = at least one input must be true. NOT = flips the input. Everything in your computer is built from these three gates.

Formal Definition: A logic gate is a physical device implementing a Boolean function. It takes binary inputs and produces a single binary output based on a specific logical operation.

The three basic (fundamental) gates are:

AND gate: Output is 1 ONLY when ALL inputs are 1. Symbol: $F = A \cdot B$ or $F = AB$

OR gate: Output is 1 when ANY input is 1. Symbol: $F = A + B$

NOT gate (Inverter): Output is the opposite of input. Symbol: $F = \overline{A}$ or $A'$

These correspond to Boolean algebra operations: AND = multiplication, OR = addition, NOT = complement.

Key Points

  • AND: output 1 only if ALL inputs are 1. $F = A \cdot B$
  • OR: output 1 if ANY input is 1. $F = A + B$
  • NOT: inverts the input. $F = \overline{A}$
  • AND with 0 → always 0 (like multiplying by 0)
  • OR with 1 → always 1
  • These 3 gates can build ANY digital circuit
  • Truth table: lists all input combinations and their outputs

Formulas

$$F = A \cdot B$$
AND operation (also written as $AB$)
$$F = A + B$$
OR operation
$$F = \overline{A} = A'$$
NOT (complement) operation

Worked Examples

Example 1

Problem: Write the truth table for a 2-input AND gate.

  1. List all input combinations for A and B: (0,0), (0,1), (1,0), (1,1)
  2. A=0, B=0: $0 \cdot 0 = 0$
  3. A=0, B=1: $0 \cdot 1 = 0$
  4. A=1, B=0: $1 \cdot 0 = 0$
  5. A=1, B=1: $1 \cdot 1 = 1$

Answer: Truth table: output is 1 ONLY when A=1 AND B=1. All other combinations give 0.

⚠️ Common Traps

Don't confuse Boolean '+' (OR) with addition. In Boolean: $1 + 1 = 1$, NOT 2!
AND has higher precedence than OR (just like × before + in regular math). So $A + B \cdot C = A + (BC)$.

🧪 Quick Self-Test

What is the output of an AND gate when inputs are A=1, B=0?
AND requires ALL inputs to be 1. Since B=0, the output is 0.
In Boolean algebra, $1 + 1 = 2$.
In Boolean algebra, $+$ means OR. $1 + 1 = 1$ (1 OR 1 = 1). There is no '2' in binary Boolean algebra.
2. Derived Gates (NAND, NOR, XOR, XNOR)
💡 Simple Explanation: NAND and NOR are 'NOT-AND' and 'NOT-OR' — they give the opposite output. They're called 'universal gates' because you can build ANY other gate from just NANDs or just NORs. XOR outputs 1 when inputs are DIFFERENT. XNOR outputs 1 when inputs are the SAME.
NAND: AND followed by NOT. $F = \overline{AB}$. Output is 0 ONLY when all inputs are 1.

NOR: OR followed by NOT. $F = \overline{A+B}$. Output is 1 ONLY when all inputs are 0.

XOR (Exclusive OR): $F = A \oplus B$. Output is 1 when inputs are DIFFERENT.

XNOR (Exclusive NOR): $F = \overline{A \oplus B}$. Output is 1 when inputs are the SAME.

Universal gates: NAND and NOR are each individually capable of implementing ANY Boolean function. This makes them highly versatile in circuit design.

Key Points

  • NAND = NOT-AND: $F = \overline{AB}$ — universal gate
  • NOR = NOT-OR: $F = \overline{A+B}$ — universal gate
  • XOR: $F = A \oplus B = A\overline{B} + \overline{A}B$ — outputs 1 when inputs differ
  • XNOR: $F = \overline{A \oplus B} = AB + \overline{A}\overline{B}$ — outputs 1 when inputs are same
  • NAND and NOR are universal: can build AND, OR, NOT from either alone
  • NOT from NAND: connect both inputs together → $\overline{A \cdot A} = \overline{A}$
  • XOR is useful for parity checking and addition circuits

Formulas

$$\text{NAND: } F = \overline{AB} = \overline{A} + \overline{B}$$
NAND = complement of AND (by De Morgan's)
$$\text{NOR: } F = \overline{A+B} = \overline{A} \cdot \overline{B}$$
NOR = complement of OR (by De Morgan's)
$$A \oplus B = A\overline{B} + \overline{A}B$$
XOR expanded as sum-of-products
$$\overline{A \oplus B} = AB + \overline{A}\,\overline{B}$$
XNOR expanded as sum-of-products

Worked Examples

Example 1

Problem: Implement a NOT gate using only NAND gates.

  1. A NAND gate with both inputs connected to A: $\overline{A \cdot A} = \overline{A}$
  2. Since $A \cdot A = A$, we get $\overline{A}$

Answer: Connect both inputs of a NAND gate to the same signal A → output is $\overline{A}$.

Example 2

Problem: Write the truth table for XOR.

  1. A=0, B=0: same → $0 \oplus 0 = 0$
  2. A=0, B=1: different → $0 \oplus 1 = 1$
  3. A=1, B=0: different → $1 \oplus 0 = 1$
  4. A=1, B=1: same → $1 \oplus 1 = 0$

Answer: XOR outputs 1 when inputs are different, 0 when they're the same.

⚠️ Common Traps

NAND output is NOT the same as AND! NAND(1,1) = 0, but AND(1,1) = 1.
XOR(1,1) = 0, not 1! Many students forget this — XOR means 'exclusively one or the other, NOT both'.
Universal gate doesn't mean 'most used' — it means it CAN implement any function alone.

🧪 Quick Self-Test

What is the output of NAND when both inputs are 1?
NAND(1,1) = NOT(AND(1,1)) = NOT(1) = 0.
Which gates are called 'universal gates'?
NAND and NOR are universal — any Boolean function can be implemented using only NAND gates or only NOR gates.
$1 \oplus 1 = 1$
$1 \oplus 1 = 0$. XOR outputs 1 only when inputs are DIFFERENT. Both being 1 means they're the same → output 0.
3. Boolean Algebra Laws & Theorems
💡 Simple Explanation: Boolean algebra has a set of rules (like math rules) that let you simplify logic expressions. Some are obvious (like $A + 0 = A$) and some are tricky (like De Morgan's theorem that shows how to flip between AND and OR).
Boolean algebra follows specific axioms and theorems that let you simplify expressions and design more efficient circuits. The key laws are:

Key Points

  • Identity: $A + 0 = A$, $A \cdot 1 = A$
  • Null: $A + 1 = 1$, $A \cdot 0 = 0$
  • Complement: $A + \overline{A} = 1$, $A \cdot \overline{A} = 0$
  • Idempotent: $A + A = A$, $A \cdot A = A$
  • Involution: $\overline{\overline{A}} = A$ (double complement)
  • Commutative: $A + B = B + A$, $AB = BA$
  • Associative: $A + (B + C) = (A + B) + C$
  • Distributive: $A(B + C) = AB + AC$ and $A + BC = (A+B)(A+C)$
  • Absorption: $A + AB = A$, $A(A + B) = A$
  • De Morgan's: $\overline{AB} = \overline{A} + \overline{B}$, $\overline{A+B} = \overline{A} \cdot \overline{B}$
  • Consensus: $AB + \overline{A}C + BC = AB + \overline{A}C$

Formulas

$$\overline{A \cdot B} = \overline{A} + \overline{B}$$
De Morgan's Theorem (AND form)
$$\overline{A + B} = \overline{A} \cdot \overline{B}$$
De Morgan's Theorem (OR form)
$$A + AB = A$$
Absorption Law
$$A + BC = (A+B)(A+C)$$
Distributive Law (OR over AND) — unique to Boolean algebra!
$$AB + \overline{A}C + BC = AB + \overline{A}C$$
Consensus Theorem — the BC term is redundant

Worked Examples

Example 1

Problem: Simplify: $F = A\overline{B} + AB$

  1. Factor out $A$: $F = A(\overline{B} + B)$
  2. By complement law: $\overline{B} + B = 1$
  3. So $F = A \cdot 1 = A$

Answer: $F = A$

Example 2

Problem: Simplify: $F = \overline{\overline{A}\,\overline{B}}$

  1. Apply De Morgan's: $\overline{\overline{A} \cdot \overline{B}} = \overline{\overline{A}} + \overline{\overline{B}}$
  2. Apply involution: $= A + B$

Answer: $F = A + B$

Example 3

Problem: Simplify using absorption: $F = A + A \cdot B$

  1. By absorption law: $A + AB = A$

Answer: $F = A$

⚠️ Common Traps

The distributive law $A + BC = (A+B)(A+C)$ does NOT exist in regular algebra — it's unique to Boolean algebra! This is a favorite exam question.
De Morgan's: break the bar, change the operation. $\overline{A+B} = \overline{A} \cdot \overline{B}$ — break the OR bar, AND becomes the operation.
Don't forget involution: $\overline{\overline{A}} = A$. Double negation cancels out.
Absorption is very useful for simplification: $A + AB = A$. Intuition: if A is already true, whether AB is true doesn't matter.

🧪 Quick Self-Test

Simplify: $A + \overline{A}B$
By the absorption variant: $A + \overline{A}B = A + B$. (Can verify with truth table or by expanding: $A + \overline{A}B = A(1+B) + \overline{A}B = A + AB + \overline{A}B = A + B(A + \overline{A}) = A + B$).
What does De Morgan's theorem state about $\overline{A + B}$?
De Morgan's: $\overline{A + B} = \overline{A} \cdot \overline{B}$. Break the bar, change OR to AND.
In Boolean algebra: $A + BC = (A + B)(A + C)$
This is the distributive law of OR over AND, which is valid in Boolean algebra (but NOT in ordinary algebra).
4. Sum of Products (SOP) & Product of Sums (POS)
💡 Simple Explanation: SOP is writing a function as 'this combination OR that combination OR ...' — you list all the cases where output = 1. POS is the opposite: 'this factor AND that factor AND ...' — you list constraints that must all be satisfied. Both describe the same function, just differently.

Formal Definition: SOP (Sum of Products) is a Boolean expression written as an OR of AND terms (minterms). POS (Product of Sums) is written as an AND of OR terms (maxterms).

SOP: Each term is a product (AND) of literals. Terms are summed (OR'd) together. Example: $F = AB + \overline{A}C + BC$

POS: Each term is a sum (OR) of literals. Terms are multiplied (AND'd) together. Example: $F = (A+B)(\overline{A}+C)(B+C)$

To get SOP from truth table: find all rows where output = 1, write the corresponding minterms (AND terms), OR them together.
To get POS from truth table: find all rows where output = 0, write the corresponding maxterms (OR terms), AND them together.

Key Points

  • SOP = OR of AND terms (minterms) — from rows where F=1
  • POS = AND of OR terms (maxterms) — from rows where F=0
  • A minterm: product term where every variable appears exactly once (normal or complemented)
  • A maxterm: sum term where every variable appears exactly once
  • Canonical SOP: all terms are minterms (every variable present in every term)
  • Can convert between SOP and POS using De Morgan's or algebraically

Worked Examples

Example 1

Problem: Write the SOP expression from this truth table: A=0,B=0→0; A=0,B=1→1; A=1,B=0→1; A=1,B=1→0

  1. F=1 for rows: (A=0,B=1) and (A=1,B=0)
  2. Row (0,1): minterm = $\overline{A}B$
  3. Row (1,0): minterm = $A\overline{B}$
  4. SOP: $F = \overline{A}B + A\overline{B}$

Answer: $F = \overline{A}B + A\overline{B}$ (this is actually XOR!)

⚠️ Common Traps

SOP → look at 1s in truth table. POS → look at 0s. Don't mix them up!
In a maxterm (POS), a variable appears UNCOMPLEMENTED when the input is 0, and COMPLEMENTED when input is 1 — the OPPOSITE of minterms!
Canonical form means every variable appears in every term. Non-canonical (simplified) forms may have fewer variables per term.

🧪 Quick Self-Test

To write a SOP expression from a truth table, you look at rows where the output is:
SOP (Sum of Products): look at rows where F=1, write their minterms, OR them together.
In a canonical SOP form, every variable must appear in every minterm.
Canonical means 'standard form' — every product term must contain ALL variables (either normal or complemented).