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

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/MJgwNj8y3tw?t=34&feature=shared 

---

To be functionally complete, all of these properties needs to be followed, if any one property fails then not functionally complete.

1)  must not preserve 0's

2) must not preserve 1's

3) must not be linear

4) must not be monotone

5) must not be self dual

 

a) must not preserve 0's  means if we put give the input  0 then the output should not be 0

b) must no preserve 1' s means  if we put give the input  1 then the output should not be 1

now for the remaining checks we need to know the complete truth table.

c) linear means that where the output are 1 then in all the inputs the no of 1's should either be all odd or all even, similar for the places where the output is 0. (it cannot be the case that where the output is 1 some inputs have odd no of 1's while some have even). Also the other point is that where the output was 1 if the inputs(no of 1's) were even then it is necessary for where the output is 0 the inputs (no of 0's) must be odd.

d) monotone means that if for any input (x,y,z) we change a single input to (x,y,~z) then the output should not change from 1 to 0 or from 0 to 1. ( Remember for functional completeness we need it to non monotone ie, it should change)

e) must not be self dual;

Two ways in which self dual exists:-

i) no of minterms = no of maxterms(neutral function)

ii) should not contain mutually exclusive terms i,e from (0,7),(1,6) and (2,5) and (3,4), exactly one element has to be present from each pair otherwise not m.e.

IF ALL THESE PROPERTIES ARE SATISFIED THEN WE SAY FUNCTIONALLY COMPLETE.

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

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?

---

@rexritz, Yes, "Functional Completenss" is important for GATE CSE. 

Complete Functional Completeness Playlist: Functional Completeness - Complete Playlist

Answer 2

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

---

Simple, easy and best solution ever.

Answer 3

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

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. 

---

@ayushsomani, $g$ is Linear. 

NOTE that to check if a function is Linear or Not, first we need to remove all useless(dummy) variables from it. Explained HERE.

After removing all useless variables, we get $g(y) = y$ which is Linear. 

---

Linear Functions Explained Here: Linear Boolean Function (Post Theorem Concept)

POST's Theorem Explained Here: Post's Completeness Theorem 

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

---

@akash.dinkar12, There is NO concept called "Partially Functionally Complete". It is a Misconception. 

See Here: Partially Functionally Complete - A Major Misconception

Answer 5

$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 6

- 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