Consider the Boolean function: F1= A+B′+C+D′+E′+F’+G+H’ Assume 2-input NAND…
Consider the Boolean function:
F1= A+B′+C+D′+E′+F’+G+H’
Assume 2-input NAND gates only are used to implement F1. Let the minimum number required = x.
Assume 2-input NOR gates only are used to implement F1. Let the minimum number required = y.
The value of x+y is ______.
Answer: 35 — Key insight: implement the OR of eight literals using only 2-input NAND or NOR gates by using De Morgan's laws and by building an 8-input NAND/NOR from…
Attempted by 20 students.
Show answer & explanation
Correct answer: 35
Key insight: implement the OR of eight literals using only 2-input NAND or NOR gates by using De Morgan's laws and by building an 8-input NAND/NOR from 2-input gates. An n-input NAND or NOR can be realized with 2n - 3 two-input gates (for n ≥ 2) using a balanced construction that uses intermediate inverters where needed.
NAND-only implementation (count x):
Given function: A + B' + C + D' + E' + F' + G + H'. To use NAND gates, write the OR as a NAND of complemented literals: F = NAND( (A)', (B')', (C)', (D')', (E')', (F')', (G)', (H')' ).
Compute which signals must be inverted before feeding the final multi-input NAND: the required inputs to the 8-input NAND are A', B, C', D, E, F, G', H (i.e., only A, C and G need inversion).
Number of 2-input NAND gates used as inverters: one per inversion → 3 gates (for A', C', G').
Build the 8-input NAND from 2-input NAND gates. Using the 2n - 3 formula gives 2·8 - 3 = 13 two-input NAND gates to realize the 8-input NAND.
Total NAND gates x = 3 (input inverters) + 13 (8-input NAND) = 16.
NOR-only implementation (count y):
With NOR gates, F = OR(literals) can be obtained as the inversion of a multi-input NOR: F = NOT( NOR( A, B', C, D', E', F', G, H' ) ).
Which signals must be generated first: the literals that are complements in the expression (B', D', E', F', H') must be produced from the primary inputs. That requires one 2-input NOR used as an inverter per complemented literal → 5 gates.
Realize the 8-input NOR with 2-input NOR gates: using the 2n - 3 formula gives 13 two-input NOR gates for the 8-input NOR.
Finally invert the 8-input NOR output to get the OR result (one 2-input NOR used as inverter) → +1 gate.
Total NOR gates y = 5 (input inverters) + 13 (8-input NOR) + 1 (final inverter) = 19.
Final answer: x = 16, y = 19, so x + y = 35.
Reason the 2n - 3 formula (short justification):
For n = 2, a single 2-input NAND/NOR suffices (2·2 - 3 = 1).
For n ≥ 3, form the n-input NAND/NOR by building a balanced binary tree of 2-input operations plus the required internal inversions; counting shows the construction uses 2n - 3 two-input gates.
A video solution is available for this question — log in and enroll to watch it.