This is one thing that is rarely asked directly in GATE exam but there are other exams (specially PSUs) where there can be a direct question from this topic.
Problems can be asked like this:
How many NAND/NOR are required to realize the following Boolean expression?
Z = A.B + B.D
Before proceeding with this make sure to make the Boolean expression as minimal as you can to reduce the complexities
This is quite a simple example but even for problems with many terms the method provided below will always work.
Using NAND gates only
Perform the following steps to obtain the minimum number of gates required:
- All the ANDed literals can be realized directly using a NAND gate each.
- The outputs of all ANDed literals are then fed into one NAND gate to realize SOP (sum of product expression) as a whole.
- If there is any single literal in the expression fed it directly to second level NAND gate.
So the answer for the above problem is simple. Two NAND gates to realize 2 ANDed terms and one NAND gate the sum of product. Total comes out to be 3.
Remember SOP expression can be simply realized using two level NAND gates. However if we have POS (Product of Sums) expression in the problem it can go upto three levels of NAND gate.
e.g Z = (A+B) . (B+D)
so for the above problem the changes in the above technique would be as follows:
- All literals in the first step would be fed in their complemented forms
- After the third step an extra NAND gate is added to get the resultant output.
So for the problem Z = (A+B) . (B+D) we would be having 4 NAND gates.
Using NOR gates only
With NOR gate also one can proceed with the same assumptions as above just by interchanging NAND with NOR and SOP with POS.
Note: Here I have considered all inputs to be provided in both complemented and uncomplemented form but to get an actual number of Gates we have to consider NAND as an inverter to get every input in complemented form which will add to the total count of the gates required. It is usually preferred to go with assumption when asked for minimum number.