Boolean Algebra; Standard Forms: SOP and POS; Karnaugh Maps

Boolean Algebra

Boolean algebra operates on variables that take only 0 and 1.

9.1 Basic Operations

Operation	Symbol	Meaning
AND	A·B or AB	1 only if both 1
OR	A+B	1 if any input 1
NOT	Ā or A'	Complement
XOR	A⊕B	1 if inputs differ
XNOR	A⊙B	1 if inputs same

9.2 Laws and Postulates

Commutative:

A·B = B·A
A + B = B + A

Associative:

(A·B)·C = A·(B·C)
(A+B)+C = A+(B+C)

Distributive:

A·(B+C) = A·B + A·C
A + (B·C) = (A+B)·(A+C) ← unique to Boolean

Identity:

A + 0 = A
A · 1 = A

Null:

A + 1 = 1
A · 0 = 0

Idempotent:

A + A = A
A · A = A

Complement:

A + Ā = 1
A · Ā = 0

Involution:

(Ā)̄ = A

Absorption:

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

9.3 De Morgan's Theorems

[ \overline{A + B} = \bar{A} \cdot \bar{B} ]

[ \overline{A \cdot B} = \bar{A} + \bar{B} ]

NAND/NOR universality: Any Boolean function can be built using only NAND or only NOR gates.

9.4 Proved Identities ()

Proof: x + x·y = x

x + x·y = x·1 + x·y = x·(1 + y) = x·1 = x

Proof: x·y + x·z + y·z = x·y + x·z

x·y + x·z + y·z = x·y + x·z + (x+x̄)·y·z
 = x·y + x·y·z + x·z + x·y·z
 = x·y(1+z) + x·z(1+y) = x·y + x·z

9.5 Complement of a Function

To find F̄: interchange AND↔OR and complement each literal.

Example: F = x'y'z + x'yz + xy' F̄ = (x+y+z̄)·(x+y+z̄)·(x̄+y+z)

Standard Forms: SOP and POS

10.1 Minterm and Maxterm

For n variables:

Minterm (mᵢ): Product term where each variable appears once (true form or complemented)
Maxterm (Mᵢ): Sum term where each variable appears once
Total: 2ⁿ minterms and 2ⁿ maxterms

10.2 Sum of Products (SOP)

OR of AND terms (minterms)
Implementation: AND gates → OR gate
Example: F = AB + BC + ĀC

10.3 Product of Sums (POS)

AND of OR terms (maxterms)
Implementation: OR gates → AND gate
Example: F = (A+B)(A+B+C)(C+D)

10.4 Converting to Standard SOP

Example: X(A,B,C) = A + BC

Expand to include all variables:

A = A·(B+B̄)·(C+C̄) = AB̄C̄ + AB̄C + ABC̄ + ABC + AB̄C̄ + ...
Standard SOP: sum of all minterms where F=1

Karnaugh Maps

The K-map (Karnaugh map) is a graphical method to minimize Boolean functions without complex algebra.

11.1 Structure

2ⁿ cells for n variables
Adjacent cells differ in exactly one bit (Gray code ordering)
2-variable: 2×2 grid
3-variable: 2×4 grid
4-variable: 4×4 grid

11.2 Simplification Rules

Group 1s with 1s OR 0s with 0s — never mix
Groups may overlap
Group size must be power of 2 (1, 2, 4, 8, 16...)
Groups must be rectangles — horizontal or vertical only (wrap-around allowed)
Make groups as large as possible

Use fewest groups possible 7. Opposite edges and corners can group together

11.3 Don't Care Conditions (X)

Used when output is irrelevant for certain input combinations
X can be treated as 0 or 1 to maximize group size
Common in: BCD circuits (invalid codes 10–15)

11.4 Solved Examples ()

Example 1: F = x'y'z + x'yz + xy'

| --- | | C' | C | | --- | --- | --- | | x'y' | 1 | 0 | | x'y | 0 | 1 | | xy' | 1 | 0 | | xy | 0 | 0 |

Group → F = x'z + xy' (after minimization)

Example 2: F(A,B,C) = Σ(1,5,6,7) Minterms 1,5,6,7 → group → F = A + BC

Example 3: F(A,B,C) = Σ(0,1,3,4,5) with don't cares d(2,6)

Use X for 2,6 to form larger groups.

Example 4: F(A,B,C,D) = Σ(0,2,4,6,8,9,10)

4-variable K-map — group adjacent 1s → minimal SOP expression.