Boolean Axioms, De Morgan's, Canonical SOP/POS & Dual Functions
“Hunting algebraic redundancies, Shannon's expansion theorem, duality rules, and self-dual function counts.”
1.The Axiomatic Foundation of Boolean Algebra
§ 1.1.Boolean algebra is an algebraic structure defined over a set B = {0, 1} equipped with two binary operations: logical addition (+ or OR), logical multiplication (* or AND), and a unary operation: complementation (' or NOT).
Fundamental Theorems:
1. Idempotence: A + A = A and A \cdot A = A.
2. Involution: (A')' = A.
3. Absorption: A + AB = A and A(A + B) = A.
4. Consensus Theorem: AB + A'C + BC = AB + A'C. To apply consensus: (a) Three terms, each with 2 variables; (b) One variable appears complemented in one term and uncomplemented in another (A and A'); (c) The third term consists of the remaining variables (BC), which is redundant and can be deleted.
Shannon's Expansion Theorem: Any Boolean function f(x_1, x_2, ..., x_n) can be expanded about variable x_1 as: f(x_1, x_2, ..., x_n) = x_1 \cdot f(1, x_2, ..., x_n) + x_1' \cdot f(0, x_2, ..., x_n). This theorem forms the mathematical bedrock for multiplexer-based synthesis.
Self-Dual Functions: In a truth table of n variables with 2^n rows, minterm m_k and minterm m_{2^n - 1 - k} are bitwise complements. For f to equal its dual f_D, the output for row k must be the complement of row 2^n - 1 - k. Thus, there are 2^{n-1} complementary pairs, and choosing the value for one half fixes the other. Number of self-dual functions = 2^{2^{n-1}}.
2. Worked Analysis: Minimization via Consensus & Duality
Watch for hidden consensus terms disguised by distributing or grouping with a third variable.
Problem Statement (Modeled on GATE Pattern):
Simplify the following Boolean function into minimal sum-of-products (SOP) form:
f(A, B, C, D) = A'B'C' + A'C'D + B'CD + A'BD + A'C'D'
Step 1: Combine terms using basic absorption / idempotence:
Look at terms: A'C'D + A'C'D'
A'C'D + A'C'D' = A'C'(D + D') = A'C' * 1 = A'C'.
Now expression is: f = A'B'C' + A'C' + B'CD + A'BD.
Step 2: Apply absorption between A'B'C' and A'C':
A'C' + A'B'C' = A'C'(1 + B') = A'C'.
Now expression is: f = A'C' + B'CD + A'BD.
Step 3: Check for Consensus Theorem:
Let Term 1 = A'C', Term 2 = B'CD.
Variable C appears uncomplemented in Term 2 (C) and complemented in Term 1 (C').
The consensus between A'C' and B'CD is: A' * (B'D) = A'B'D.
Does A'B'D help? Let's check Term 3: A'BD.
Combine A'BD with A'C' and B'CD:
Notice between A'BD and B'CD: variable B appears as B and B'.
Consensus of A'BD and B'CD is: (A'D) * (CD) = A'CD.
Is A'CD present? Notice A'C' + A'CD = A'(C' + CD) = A'(C' + D) = A'C' + A'D.
Alternatively, factor A' from first and third terms:
A'C' + A'BD = A'(C' + BD).
Can we simplify B'CD? Notice B'CD + A'BD: (B'C + A'B)D.
In fact, K-map plotting confirms: minterms covered are A'C' (all D), B'CD (when A=0 or A=1), and A'BD.
Minimal SOP: A'C' + A'D + B'CD = A'C' + D(A' + B'C) = A'C' + A'D + B'CD.
Since A'D + B'CD = (A' + B'C)D = (A' + B')(A' + C)D, minimal SOP is: f = A'C' + A'BD + B'CD.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
The most thorough digital logic series — textbook quality at no cost.
GATE-focused digital logic with exam-style numericals.