The Gateway to Computer Science Excellence
+30 votes
5.8k views

What is the minimum number of gates required to implement the Boolean function $\text{(AB+C)}$ if we have to use only $2\text{-input NOR}$ gates?

  1. $2$
  2. $3$
  3. $4$
  4. $5$
in Digital Logic by Veteran (52.2k points)
edited by | 5.8k views

6 Answers

+65 votes
Best answer

Given boolean function is 

 f$ = AB + C$

   $= (A+C) . (B +C)$ 

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

Therefore, $3$ NOR gate required .

Correct Answer: $B$

by Active (5.2k points)
edited by
0
Silly question but
Where is this rule written AB+C = (A+c)(B+C)

I just can figure out by looking at the question also never found this rule before anywhere.
0

It is a rule you can check it by using truth table or look into morris mano postulate 4, distributive (b)

0
beautiful explanation.
+9 votes

Here is a simple approach to these kinds of questions.

 

This can be applied to any questions and you'll get min number of gates always.

by Junior (823 points)
+1
Good answer.

Post more answers now in your stronger subjects like TOC.
0

Akash Papnai

thanks a lot man, but does this method works for implementing XOR gate using NAND gates only.

I got the answer as 5, but the valid answer is 4.

0
Yeah, this doesn't work for that things.
0

@`JEET and @neeraj2681 Implementing XOR using NAND or any other possible combination could be done using above method. I'm sure you are making a mistake while implementing it. This is how it's done:

Also, note that I was able to combine because I know that A XOR A is 0 and B XOR B is also 0.

0
Yeah, that what exactly I did.

But I still believe it can't be used at many other places, though I feel fundamental gates can be implemented.

I mean most of the cases its applicable but it doesn't seem to be an universal approach for a tricky or maybe a little big cases.
0

@Akash Papnai

You could combine them in the step $\mathbf 1$ itself.

Like taking $\mathbf{B}$ at both the places and same for $\mathbf A$ as well. You just need to add Not which can be converted to AND later.

Don't you think this can be done?

0

@Akash Papnai

The question might seem silly, but Is there an algorithm or something to check that the design can further be minimised after step 3rd or Is it just intuition?

I mean how one can be sure to go ahead after step 3rd? Also, Is there a way to check that its final and no further steps needed now?

 

+1

@`JEET I have done a lot question on NAND NOR implementation and I haven't encountered such a case in which I follow the above steps and got drowned even in many complex questions. 

Also, what you said about combining them in step 1 could surely be done but for the sake of understandability, I did it at last. This was done to understand the general idea of the question but not just the answer to the above question. It's better to understand the answer intricately.

0
No actually there isn't any feasible algorithm.
If I remember correctly, its time complexity is something exponential like.
0

@Akash Papnai

Yeah, right!

Let me see if I get any such question in the future, then will respond.

0

@Akash Papnai and @`JEET

thanks for the explanations!

+6 votes
Answer should be 3 nor gates...A.B + C can be written as (A+C).(B+C) which is a OR-AND realization and can be made with 3 NOR gates as OR- AND is similar to a NOR-NOR realization...
by (81 points)
edited by
+4 votes

Almost same solution,

by Boss (10.8k points)
+3 votes

Option : B 

Solution: 

by (67 points)
0 votes
answer - D

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

two NOR gates for complementing A and B

one for computing (A' + B')'

one to compute ((A' + B')' + C)'

one to negate the last result
by Loyal (8.6k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,228 comments
104,909 users