6 votes

Provide short answers to the following questions:

Show that {NOR} is a functionally complete set of Boolean operations.

Show that {NOR} is a functionally complete set of Boolean operations.

14 votes

Best answer

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 the 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 the functionally complete .

0

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