retagged by
33,860 views

3 Answers

30 votes
30 votes
Step 1.

Check if the expression is minimized using K-Map. If it isn't minimized minimize it.(If we're trying to find minimum no. of NAND Gates obtain SOP form, else obtain POS form).

In this particular Example, the expression is already minimized.

Step 2.
We try to realize the expression using only AND and NOT by applying Demorgan's Law.

A'B+CD'+B'C

=C(B'+D')+A'B

=C(BD)'+A'B

=((C(BD)')'.(A'B)')'

So number of NAND Gates=1 [for (BD)'] + 1 [for (C(BD)')'] + 1 [for (A'B)'] + 1 [for ((C(BD)')'.(A'B)')'] + 1 [for A']=5

For number of NOR Gates the procedure is same, but instead of trying to realize the minimized expression (in case of NOR Gates which should be in POS form) using only AND and NOT we try to realize it only using OR and NOT.
edited by
0 votes
0 votes

No, there is not a systematic algorithm to approach this problem as it is

 

“NP-HARD”

So, there are only approximate methods, two of which I know are:

  1. SOP / POS one, followed by bubbling of gates concept.
  2. Apply double complement of given expression and try to proceed by de-morgan’s law.

 

Approach:   NOR

  1. Write minimized POS expression (see that there be only 2 literals in each SUM TERM!
  2. Now each SUM TERM is realized by OR GATE
  3. the product of each SUM TERM IS DONE by AND GATE
  4. CHANGE each OR to NOR and AND to BUBBLED AND (NOR)
  5. Change each GATE TO NOR GATE, you will see the functionality remains same!

NOW notice that : BUBBLED AND is NOR GATE.

OR followed by AND  IS exactly same as NOR followed by BUBBLED AND (NOR).

  1. As a safe -side relaize it by purely OR and NOT  (DEMORGAN’S )

 

 

Plus a tip: If you are getting answer, more than the no. of literals in POS or SOP, recheck. And 5 is mostly wrong option 😅

edited by
0 votes
0 votes
Firstly there is no systematic approach to find the minimum number of Gates required, you have to be efficient in utilising the boolean algebra laws.

And one thing you can observe that for SOP implementation AND-OR implementation is used which is same as NAND-NAND implementation.

Now in the given function, f=a'b+ b'c+ cd'.

You can take c common from 2nd, 3rd term to get c(b'+d').

Again notice that b'+d' =(bd)' [by de-Morgans law]

Thus your given expression becomes f=a'b+ c(bd)'.

Now,

a' will take 1 NAND Gate.

feed a'b into 1 NAND gate. ---(1)

(bd)' will take 1 NAND gate.

Feed c(bd)' into 1 NAND gate.-----(2)

Lastly, feed  (1),(2) into 1 more NAND gate to obtain f.

Finally the minimum number of NAND gates require: 5

Related questions

1 votes
1 votes
2 answers
1
sh!va asked Jan 26, 2017
8,393 views
F= PQ+ QR+ RS+ST.i) What is the minimum number of NAND gates required to implement F?ii) What is the minimum number of NOR gates required to implement F?
68 votes
68 votes
4 answers
2
bahirNaik asked Dec 17, 2015
82,247 views
Minimum No of Gates NAND/NOR Ex-OREx-NorHalf AdderHalf SubtractorFull AdderFull SubtractorNAND??????NOR??????
0 votes
0 votes
1 answer
3
smsubham asked Sep 8, 2018
4,281 views
What is the minimum number of NOR gates required to implement this boolean function?A'B + A'CDB + AC'B + ABCAlso how many NAND gates required?Confirm answer am getting ze...
6 votes
6 votes
3 answers
4
GateAspirant999 asked Oct 11, 2016
9,538 views
The truth table for the combinational circuit is shown below:What is the minimum number of two input NAND gates required to realize this logic circuit?