8,271 views
27 votes
27 votes

A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?

  1. EX-NOR
  2. implication, negation
  3. OR, negation
  4. NAND

2 Answers

Best answer
47 votes
47 votes
EX-NOR is not functionally complete.

NOR and NAND are functionally complete logic gates, OR , AND, NOT any logic gate can be implemented using them.

And (Implication, Negation) is also functionally complete

First complement $q$ to get $q'$ then $p \rightarrow q' = p' + q'$

Now complement the result to get AND gate $(p' + q')' \rightarrow pq$
edited by
3 votes
3 votes
Option -A)

B) implication,negation is functionally complete because ,

                    f( p , q) = p-->q = !p OR q

                    f( !p , q) = p OR q (since we already have NOT we can use it straightaway) .

C) is functionally complete as it is the basic functionally complete set.

D) NAND is a universal gate which can implement NOT,AND,OR . (or even anyother gates,since it is a universal gate)
Answer:

Related questions

30 votes
30 votes
2 answers
2
Ishrat Jahan asked Oct 28, 2014
7,486 views
Match the following flag bits used in the context of virtual memory management on the left side with the different purposes on the right side of the table below.$$\small ...
26 votes
26 votes
4 answers
3