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

How did you check linearity by using single terms?

In your link it seems as if we need to construct truth tables and check for the whole function together if odd or even number of 1s can produce a 1 and same for 0.
Here you have checked with singular minterms instead of the full expression.Why?

---

We say that boolean function f is linear if one of the following two statements holds for f:

• For every 1-value of f, the number of 1’s in the corresponding input is odd, and for every 0-value of f, the number of 1’s in the corresponding input is even. or
• For every 1-value of f, the number of 1’s in the corresponding input is even, and for every 0-value of f, the number of 1’s in the corresponding input is odd.

So, for f, we can get a 1 output with X=1, Y=Z=0 or with X=0, Y=Z=1. Yes, we need to do for whole expression but since each term is added, when we get 1 for a term, we need not evaluate other terms. 

---

Thanks a lot!!!

The explanation as well as material!! Kudos

---

the link given is not working @arjun

---

Link is now dead, but I uploaded one copy here -http://docdro.id/zQj013C

---

Great (Ans+Link) .Thank U very Much.

---

@ arjun sir, cant we just check whether the circuit derives and/or and not gate??

---

^ Yes. thats the simplest way.

---

Cool. But I think this method will work faster. Only thing is memorizing this method. ,

---

Superb solution and Material.Thank u Arjun sir.

---

@Arjun, the pdf is awesome!!!
for 3 inputs / 4 inputs the Hasse Diagram becomes complex and time taking to check for monotonicity, is there a efficient/faster method, im thinking you used a diff method, just by observation, perhaps?

---

@arjun sir

sir how you will apply linearity property on the g(X,Y,Z)? it should follow linearity property but it is failing.for f=1 At (X=Y=Z=1) .num of ones are odd   and hare for f=1 at (X=Y=1,Z=0)  num. of ones are even. pls explain.

---

@arjun sir

I think that function f is monotone

X=0, Y=1, Z=0 gives f=0, if X=0, Y=1, Z=1(0 to 1) gives f=1

X=0, Y=0, Z=1 gives f=0, if X=0, Y=1(0 to 1), Z=1 gives f=1

X=0, Y=0, Z=1 gives f=0, if X=1(0 to 1), Y=0, Z=1 gives f=1

Therefore, function f is monotone and so not functionally complete.

Pls let me know if there is any mistake.

---

Arjun sir thanks a lot  for this approach and link u provide

---

thanks sachin sir for updated link u provide

---

 

correction : f is not self dual as f(X,Y,Z)≠ f( X, Y, Z)

in the answer please someone correct this to

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

---

please check if this is correct Hasse diagram of function 'f()' or not.

Hasse diagram of F()

 

---

just to help,.. page 4 on the mentioned pdf

---

def . A system S of boolean functions (or, alternatively, logical operators) is functionally complete
if every boolean function (or, alternatively, every compound proposition) can be expressed in terms
of the functions from S.

From the given link.

@Arjun sir, So this question makes no sense right? We can check if a system is functionally complete or not. 

but here only a boolean expression is given to check completeness..

 

---

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