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$

edited | 5.8k views

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
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.

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

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

thanks for the explanations!

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

Almost same solution,

by Boss (10.8k points)

Option : B

Solution:

by (67 points)

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)