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$ is preserving $0$ as when all inputs are zero, output is always $0$ and so $g$ cannot be functionally complete.

$f$ is not preserving $0.$
$f$ is not preserving $1.$ $($when all inputs are $1,$ output is $0).$
$f$ is not linear as in $XY'$ only one (odd) input $(X = 1, Y = Z = 0)$ needs to be $1$ and in $X'YZ$ two inputs (even) $(X = 0, Y = Z = 1)$ need to be $1.$ 
$f$ is not monotone as changing $Y$ from $0$ to $1,$ can take $f$ from $1$ to $0.$
$f$ is not self dual as $f(X, Y, Z) ≠ ⌐f(⌐X, ⌐Y, ⌐Z)$ 

So, $f$ satisfies all $5$ conditions required for functional completeness.

Hence, B is the answer. 

http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf

Comments

@khushitshah This q is absolutely correct. It asks which of the following functions f,g is functionally complete. This can be proved by Emil Post’s functional completeness theorem (the 5 steps mentioned by Arjun Sir).

---

For $f$:-

It’s given $\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$

If we take $\textit{f (X, X, Z) = X'XZ + XX' + X'Z' } = X’Z’$

Now $X’Z’ = X$ NOR $Z$ and since NOR gate is functionally complete, we can say $f$ is functionally complete.

 

For $g$:-

Using Post’s Functional Completeness Theorem 1 (Arjun Sir’s fist condition, i.e if $g(1,1,1) = 1$ then $g$ will not be functionally complete):-

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

Putting $X=Y=Z=1$ in $g(X,Y,Z)$

$\textit{g (1, 1, 1) = 1’.1.1 + 1’.1.1' + 1.1} = 1$ i.e. $g$ is preserving $1 \implies g$ is not functionally complete.

Answer : B. Only  {f}  is functionally complete

---

@Arjun is the topic functional completeness still important for gate 2024?

Answer 2

Following reference of what functionally complete functions are from below :

http://cs.ucsb.edu/~victor/ta/cs40/posts-criterion.pdf

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

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

1	0	1	0
1	1	0	0

Above is K map of f where row denotes variable X(row 1-0 and row 2-1)

Column denotes YZ with respective column values as 00 01 11 and 10.Usual 3 variable K-map implementation we have considered.

As we can see Function f now cannot be simplified further.

If we make truth table of the above function

X	Y	Z	f
0	0	0	1 (F does not preserve 0)
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0 (F does not preserve 1)

Consider the output of function at inputs (X,Y,Z) (0,1,1) and (1,0,0) which is 1, so for functional value of f to be 1 sometimes number of 1's input is even sometimes odd hence f(X,Y,Z) is not linear.

Consider when input (X,Y,Z) changes from (0,0,0) to (0,0,1) change in variable of Z from 0 to 1 results in changing of functional values from 1 to 0. Hence f(X,Y,Z) is not monotone.

f(X,Y,Z) is not self-dual as f(X,Y,Z) ≠ ⌐f(⌐X,⌐Y,⌐Z).

f(X,Y,Z) dis-satisfies all five properties talked about above. Hence, f(X,Y,Z) is functionally complete.

Now consider g (X, Y, Z) = X'YZ + X'YZ' + XY

0	0	1	1
0	0	1	1

Consider above K map for g (X, Y, Z) = X'YZ + X'YZ' + XY where row denotes variable X and column denotes variables YZ.

We can see now that g(x,y,z) can be reduced to Y.

Hence g(X,Y,Z) = Y

consider below truth table for g(X,Y,Z)

Y	F
0	0 (G preserves 0)
1	1 (G preserves 1)

G is linear as change in input of Y from 0 to 1 can only make output change from 0 to 1.

G is monotone as when output is 1 number if 1's in output is odd.

G(X,Y,Z)=Y=⌐(⌐Y)

Hence G(X,Y,Z) is self dual.

Hence g(X,Y,Z) is not functionally complete.

Ans- (b)

Comments

you have interchanged 'linear' & 'monotone' in function g.

---

Ayush Upadhyaya

Instead of dissatisfying all 5 properties, if 'f' dissatisfies only one, then also we can say that 'f' is functionally complete, right???

---

SIr, can we say it is not functionally complete if it dissatisfies any of the 1 property out of 5??

---

@Ayush Upadhyaya @akshayaK @MRINMOY_HALDER @Amit Tiwari 5 

Although, it won't affect the answer but i think g is not Linear. 

Please, correct me if i am wrong. 

Answer 3

If we able to derive 

• <OR,AND,NOT>

• <OR,NOT>

• <AND,NOT>

THEN function is functionally completed set.

Option b is right

Comments

Should i check for all possible ways of XYZ to get  solution of function containing operations  NOT OR and AND

---

Yes we try to derive any one of the set

Answer 4

F function--

 Given operaion is functionally complete ,if every boolean function can be generated from that operation only.

1.Not gate

2.OR

3.Nand

Given operation is =X'YZ + XY' + Y'Z' 

1.As NOT gate

F(X,1,1)=!X   

2.As And Gate

F(!X,1,Z)=XZ

3.As OR Gate

F(X,0,!Z)=X+Z

So f is functionally complete.

Function G---

Function g can be minimized to 

X'YZ + X'YZ' + XY=!XY+XY=Y

And this can only work as not gate.

so function g is not functionally complete.

Comments

@Jatin Saini

U are taking help from 0 or 1 in order to implement OR gate, i think it is called partially functionally complete.

---

Ya nt a correct way of solving ....