GATE CSE 2015 Set 1 | Question: 39

Question

Consider the operations

$\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$

Which one of the following is correct?

• A. Both $\left\{\textit{f} \right\}$ and  $\left\{ \textit{g}\right\}$ are functionally complete
• B. Only  $\left\{ \textit{f} \right\}$  is functionally complete
• C. Only  $\left\{ \textit{g}\right\}$  is functionally complete 
• D. Neither $\left\{ \textit{f}\right\}$  nor  $\left\{\textit{g}\right\}$ is functionally complete

Comments

@Shivam Kasat  Whenever you take the help of constants (1 and 0) to make a function functionally complete then that function is called partially complete function.

Source: https://www.geeksforgeeks.org/functionally-complete-operations/

---

I think this is going to be a tedious task to convert into AND & OR .To minimize the complexity to convert into AND & OR are we using that 5 properties ?????

---

$\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{  , With Complete Analysis:}}$

https://youtu.be/qYZD8nmz0kQ

Answer 1

$g(X.Y,Z)=X'YZ+X'YZ'+XY$

 

Preserves Zero $:\checkmark$ 

Not functionally complete.

 

 

 

 

 

 

 

$f(X,Y,Z)=X'YZ+XY'+Y'Z'$

 

Preserves zero $\times$

Preserves one $\times$

Linear $\times$ (Observe $6^{th}$ line)

Monotone $\times$

Self-dual $\times$

Functionally complete $\checkmark$

Answer 2

- F produces both the operations, NOT(try f(X,X,X)) and OR.

- G cannot produce the Compliment i.e. NOT. Hence it can not be a functionally complete.

NOTE: A function is said to be functionally complete if it can produce any one among:

1. AND, OR, NOT
2. AND, NOT
3. OR,NOT

Answer 3

f(1,Y,1) = Y’ (not gate realisation)

f(f(1,x,1),1,z) = (x’)’z = xz (AND gate realization)

 Therefore from the given f(x,y,z) we can get AND+NOT = NAND gate so, Universal

any thing can be created .

g(x,y,z) = x’y(z+z’) + xy

         = x’y + xy

         = y

so, g(x,y,z) = y

we can’t create any thing from here

Answer 4

following the similar steps for function g(X,Y,Z) . the function g becomes functionally incomplete . Thus only function f is functionally complete and hence ,

ans ) B : Only  {f}  is functionally complete