Show that you can create a circuit for any Boolean function using only AND and N

Question

Show that you can create a circuit for any Boolean function using only AND and NOT gates. (That is: show that you do not need OR gates.) Explain your answer; particularly, explain why what you have written shows that you can represent any Boolean function using only AND and NOT gates. Hint: You should assume (and do not need to prove) that it is possible to construct a circuit for any Boolean function using all three. AND, OR, and NOT gates. (In class, we demonstrated that this is true by using the sum-of-products algorithm) Hint: Look into De Morgan's laws.

Explanation / Answer

Solution:

So, we know that any boolean circuit can be implemented using three basic gates named as NOT, AND, and OR gate. so let's take an example of a circuit and play with that to see if it is possible to draw using only NOT and AND gate.

Example:

A.(B + C')

We can say that the given circuit can be easily implemented using all three basic gates, but what about only AND and NOT.

So, we know the logic of AND gate and it's A . B

which means in order to implement any circuit it needs to be in dot form (or we can say no plus is there).

So by using DeMorgan's law we can write the circuit as

= (A.(B+C'))''-------------DeMorgan law A''= A

= (A' + (B+C')')'----------DeMorgan's law (A.B)' = A' + B'

= (A' + (B'.C''))'---------DeMorgan's law A' + B' = (A + B)'

= A''.(B'.C)

= A.(B'.C)

Now this circuit can be implemented using AND and NOT gates.

One more interpretation is there that AND and NOT gates combining together creates NAND gate which is a universal gate which means any circuit can be created using universal gates (another one is NOR).

I don't think it is covered in your syllabus yet that is why I didn't use that interpretation.

I hope this helps, please let me know in case of any doubt. Thumbs up if this helped.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.