AND, OR and NOT operations — Huntington’s postulates, Boolean theorems including De Morgan’s, Duality principle, Venn diagrams, SOP and POS canonical forms, and realization using NAND/NOR universal gates.
⚡ Logic Operations — AND, OR, NOT
Every digital circuit is built from three primitive logic operations. A logic variable can only take two values — 0 (false/low) or 1 (true/high). The three operations combine these variables:
AND Gate
Y = A · B
Output HIGH only when ALL inputs are HIGH
OR Gate
Y = A + B
Output HIGH when ANY input is HIGH
NOT / Inverter
Y = Ā
Output is complement of input — unary operator
A
B
AND (A·B)
OR (A+B)
NOT (Ā)
0
0
0
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
0
AND vs OR memory aid. AND is both — student needs books AND ID card. OR is either — student needs books OR ID card. NOT is inverse — student without phone is allowed in.
📐 Huntington’s Postulates of Boolean Algebra
E.V. Huntington (1904) defined six postulates that form the axiomatic foundation of Boolean algebra. All theorems are derived from these — they are assumed true without proof.
#
Postulate
OR form
AND form (dual)
P1
Closure
A + B ∈ S
A · B ∈ S
P2
Commutative Law
A + B = B + A
A · B = B · A
P3
Identity Element
A + 0 = A (identity = 0)
A · 1 = A (identity = 1)
P4
Distributive Law
A + B·C = (A+B)·(A+C)
A·(B+C) = A·B + A·C
P5
Complement Law
A + Ā = 1
A · Ā = 0
P6
Non-triviality
At least two elements exist: A ≠ B
Key difference from ordinary algebra. Postulate P4 OR form — A + B·C = (A+B)·(A+C) — has no equivalent in ordinary algebra. This and the complement law (P5) make Boolean algebra fundamentally different from arithmetic.
🔢 Two-Valued Boolean Algebra (Switching Algebra)
When the set S = {0, 1}, the postulates reduce to the switching algebra rules used directly in digital circuits:
Figure 1 — Complete switching algebra rule set. Every rule on the left has a dual on the right — swap + with ·, and swap 0 with 1.
🔄 Duality Principle
The Duality Principle states that any theorem or identity in Boolean algebra remains valid if you simultaneously:
Swap every + (OR) with · (AND) and vice versa
Swap every 0 with 1 and vice versa
Leave all variables and their complements unchanged
This halves the proof work — prove one form, the dual is automatically valid.
📏 Boolean Theorems
#
Theorem
OR form
AND form (dual)
Name
1
Idempotent
A + A = A
A · A = A
—
2
Null element
A + 1 = 1
A · 0 = 0
—
3
Absorption
A + A·B = A
A·(A + B) = A
Absorption Law
4
Involution
Ā̄ = A (double complement = original)
—
5
Consensus / 2nd Absorption
A + Ā·B = A + B
A·(Ā + B) = A·B
Redundancy / Consensus
6
De Morgan’s
A·B̄ = Ā + B̄
A+B̄ = Ā·B̄
De Morgan’s Theorem
7
Associative
(A+B)+C = A+(B+C)
(A·B)·C = A·(B·C)
—
Proof — Absorption Theorem: A + A·B = A
StartA + A·B
Step 1= A·1 + A·B (since A·1 = A)
Step 2= A·(1 + B) (distributive law)
Step 3= A·1 (since 1 + B = 1)
= A ✓ Proved
Proof — Consensus Theorem: A + Ā·B = A + B
StartA + Ā·B
Step 1= (A + Ā)·(A + B) (distributive law P4-OR)
Step 2= 1·(A + B) (since A + Ā = 1)
= A + B ✓ Proved
🔀 De Morgan’s Theorems
De Morgan’s theorems are among the most useful in digital design — they allow any gate to be converted to its complement form:
Figure 2 — De Morgan’s theorems. These extend to n variables: the complement of any AND expression equals the OR of all complements, and vice versa.
Truth Table Verification (2 variables)
A
B
A·B
Ā·B̄ (=A·B)
Ā
B̄
Ā+B̄ (=A·B)
0
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
1
1
1
1
1
0
0
0
0
Columns 4 and 7 (A·B̄ and Ā+B̄) are identical — confirming Theorem 1.
📝 Canonical Forms — SOP and POS
Any Boolean function can be expressed in two standard canonical forms that are directly derivable from a truth table:
Figure 3 — Minterms and maxterms are opposite: a minterm uses complemented variables for 0-inputs; a maxterm uses complemented variables for 1-inputs.
📊 Minterms, Maxterms and Notation
For n variables there are 2ⁿ minterms (m₀–m₂ₙ₋₁) and 2ⁿ maxterms (M₀–M₂ₙ₋₁). The subscript is the decimal value of the input combination.
Row
A
B
C
Minterm (mᵢ)
Maxterm (Mᵢ)
0
0
0
0
m₀ = Ā·B̄·C̄
M₀ = A+B+C
1
0
0
1
m₁ = Ā·B̄·C
M₁ = A+B+C̄
2
0
1
0
m₂ = Ā·B·C̄
M₂ = A+B̄+C
3
0
1
1
m₃ = Ā·B·C
M₃ = A+B̄+C̄
4
1
0
0
m₄ = A·B̄·C̄
M₄ = Ā+B+C
5
1
0
1
m₅ = A·B̄·C
M₅ = Ā+B+C̄
6
1
1
0
m₆ = A·B·C̄
M₆ = Ā+B̄+C
7
1
1
1
m₇ = A·B·C
M₇ = Ā+B̄+C̄
Example 3.4 — Express F = A·B + B·C in canonical SOP and POS forms
F(POS) = Π(0, 1, 2, 4, 5) ← complement of SOP minterm set
SOP ↔ POS conversion shortcut. The minterm indices of SOP and the maxterm indices of POS for the same function are always complementary — they partition the full set {0…2ⁿ−1}. To convert: swap Σ ↔ Π and use the numbers missing from the original set.
🔌 Other Logic Gates — NAND, NOR, XOR, XNOR
NAND Gate
Y = A·B = Ā+B̄
LOW only when ALL inputs HIGH. Universal gate.
NOR Gate
Y = A+B = Ā·B̄
HIGH only when ALL inputs LOW. Universal gate.
XOR Gate
Y = A⊕B = Ā·B+A·B̄
HIGH when inputs differ (odd parity). Used in adders.
XNOR Gate
Y = A⊙B = A·B+Ā·B̄
HIGH when inputs are equal. Used in comparators.
A
B
NAND
NOR
XOR
XNOR
0
0
1
1
0
1
0
1
1
0
1
0
1
0
1
0
1
0
1
1
0
0
0
1
🌐 NAND and NOR as Universal Gates
A gate is universal if any Boolean function — and therefore any logic circuit — can be built using only that gate type. Both NAND and NOR are universal because AND, OR and NOT can each be constructed from them.
Figure 4 — Any Boolean function can be implemented using NAND gates alone (or NOR gates alone). This is why NAND and NOR are called universal gates.
⚙️ Realization of Boolean Functions
The design process: express the function in minimal SOP → draw the gate network. Minimization reduces gate count significantly.
Example 3.7 — Reduce F₁(A,B,C,D) = Σ(0,1,2,6,7,14,15) using Boolean algebra
F₁ = Ā·B̄ + B·C (reduced from 7 minterms to 2 terms, 6 gates → 2 gates)
Why minimize? The canonical SOP for example 3.7 requires 7 three-input AND gates + 1 seven-input OR gate + NOT gates = ~15 gates. The minimal expression Ā·B̄ + B·C needs just 2 AND gates + 1 OR gate + 2 NOT gates = 5 gates. That is a 3× reduction in silicon area and power.
📋 Quick Reference
Topic
Key Rule
AND
Y = A·B — HIGH only when all inputs HIGH
OR
Y = A+B — HIGH when any input HIGH
NOT
Y = Ā — unary complement
NAND
Y = A·B̄ = Ā+B̄ — universal gate (LOW only when all inputs HIGH)
NOR
Y = A+B̄ = Ā·B̄ — universal gate (HIGH only when all inputs LOW)
XOR
Y = A⊕B — HIGH when inputs differ
De Morgan 1
A·B̄ = Ā + B̄ (complement AND = OR of complements)
De Morgan 2
A+B̄ = Ā · B̄ (complement OR = AND of complements)
Absorption
A + A·B = A | A·(A+B) = A
Consensus
A + Ā·B = A + B | A·(Ā+B) = A·B
Minterm mᵢ
AND term — complement variable if column = 0; for rows where F = 1
Maxterm Mᵢ
OR term — complement variable if column = 1; for rows where F = 0
SOP → POS
Swap Σ↔Π and use the missing minterm numbers
Duality
Swap + ↔ · and 0 ↔ 1; every theorem has a dual that is automatically true
Coming next — DE-04: Simplification of Boolean Functions — Karnaugh maps from 2 to 6 variables, don’t-care conditions, NOR implementation with 0-grouping, and the Quine-McCluskey tabular method.