Challenge Problems: Boolean Algebra
These challenge problems test deeper understanding. Only final answers are provided — work through each problem on your own.
Challenge 1: Multi-Step Boolean Simplification
Simplify the following expression using Boolean algebra laws (show only the final result):
Show Answer
\(F = \overline{C} \cdot (A + B) + BC = A\overline{C} + B\)
Simplified: \(F = A\overline{C} + B\)
Challenge 2: Prove a Boolean Identity
Prove algebraically that:
This is the Consensus Theorem. Your proof should use only the basic Boolean algebra axioms and theorems.
Show Answer
\(AB + \overline{A}C + BC\)
\(= AB + \overline{A}C + BC(A + \overline{A})\)
\(= AB + \overline{A}C + ABC + \overline{A}BC\)
\(= AB(1 + C) + \overline{A}C(1 + B)\)
\(= AB + \overline{A}C\) ∎
Challenge 3: Complement and De Morgan's Simplification
Find the complement of the expression below, then simplify the result to a minimum SOP form:
Show Answer
\(\overline{F} = \overline{A}\,\overline{B} + B\overline{C} + \overline{A}\,C\)
Challenge 4: Expression Equivalence
Determine whether the following two expressions are equivalent. If not, find an input combination where they differ.
Show Answer
They are equivalent.
\(F_1 = A\overline{B} + \overline{A}B + AB = A\overline{B} + B(\overline{A} + A) = A\overline{B} + B = A + B = F_2\)
Both functions equal 0 only when \(A = 0, B = 0\), and equal 1 for all other inputs.
Challenge 5: Simplify a 5-Term SOP Expression
Simplify the following 5-term SOP expression to a minimum form:
Show Answer
\(F = \overline{B}\,D + A\overline{C}\,D\)
This can also be written as: \(F = D(\overline{B} + A\overline{C})\)
Challenge 6: Dual of an Expression
Find the dual of the following expression, then simplify both the original and the dual to verify the duality principle:
Show Answer
Dual: Swap AND↔OR (keep complements unchanged):
\(F_D = (A+B)(A+\overline{C})(B+C)\)
Simplify original: By consensus theorem, \(BC\) is redundant: \(F = AB + A\overline{C}\)
Simplify dual: \(F_D = (A+B)(A+\overline{C})(B+C) = (A+B)(A+\overline{C})\) — the dual of the consensus theorem removes the redundant factor \((B+C)\).
Challenge 7: Universal Gate Implementation
Implement the function $F = A \oplus B$ (XOR) using only NAND gates. Show the expression in terms of NAND operations and count the total number of 2-input NAND gates required.
Show Answer
\(A \oplus B = A\overline{B} + \overline{A}B\)
Using NAND gates: Let \(W = \overline{A \cdot B}\) (NAND gate 1).
Then \(\overline{A \cdot W}\) = NAND gate 2, and \(\overline{B \cdot W}\) = NAND gate 3.
Finally, \(F = \overline{\overline{A \cdot W} \cdot \overline{B \cdot W}}\) = NAND gate 4. Total: 4 NAND gates.
Challenge 8: Absorption and Simplification Chain
Simplify the following expression step-by-step, citing the Boolean law used at each step:
Show Answer
\(= A\overline{B}(C + \overline{C}) + AB(C + \overline{C}) + \overline{A}BC\) (Factoring)
\(= A\overline{B} + AB + \overline{A}BC\) (Complement: \(X + \overline{X} = 1\))
\(= A(\overline{B} + B) + \overline{A}BC = A + \overline{A}BC\) (Complement)
\(= A + BC\) (Absorption: \(A + \overline{A}X = A + X\))
Challenge 9: Four-Variable De Morgan's Application
Apply De Morgan's theorem to complement the following 4-variable expression, then simplify the result:
Show Answer
Apply De Morgan's to the POS form (AND of ORs → OR of ANDs):
\(\overline{F} = \overline{A}\,\overline{B} + \overline{C}\,\overline{D} + AD\) (minimum SOP, 3 terms, 6 literals)