in Digital Logic edited by
1,129 views
9 votes
9 votes
Show that {NOR} is a functionally complete set of Boolean operations.
in Digital Logic edited by
1.1k views

3 Answers

18 votes
18 votes
Best answer

The functionally complete set is by which you can perform all operations. So, if any logical set is able to implement the operation {And , NOT}  or {OR, NOT}; it is known as functionally complete.

Now come to NOR gate.

  • $A$(NOR)$B= (A+B)'$
  • $A$(NOR)$A =(A+A)' =(A)'$ , so we can perform the NOT operation .
  • $(A+B)'$ NOR $(A+B)' =((A+B)' + (A+B)')'=((A+B)')' =(A+B) $, so OR operation is also performed successfully .

So, NOR is functionally complete.

edited by

3 Comments

Yes, This is the definition for functionally completeness.
0
0
edited by
Theorem: A System of boolean functions is functionally complete iff this system doesn't entirely belong any of property listed:

1. F preserve 0.

2. F preserve 1

3. F is linear

4. F is monotone

5. F is self dual

 

For this question: 1. F doesn't preserve 0 i.e for i/p 0 it produces 1 similarly it doesn't preserve 1. F is not linear there is even and odd no. of 1's when o/p is 0. F is not monotone i.e for 00 it is 1 then it goes from 1 to 0. F is not self dual i.e  $\neg(A+B)$ != $\neg(A)+ \neg(B)$.  $\therefore$ F is Functionally complete.
1
1
1 vote
1 vote

WE Know that we can derive any GAte from NAND,NOR, so all boolean functions can be derived from NOR

so it is functionally complete

http://www.electrical4u.com/universal-gate-nand-nor-gate-as-universal-gate/

1 vote
1 vote

Preserves Zero : $\times$ Preserves One : $\times$ Linear : $\times$

Monotone : $\times$ Self-Dual : $\times$

 

 

 

 

NOR is functionally Complete.

Ref : https://victoramelkin.com/ta/cs40/posts-criterion.pdf

Related questions