26,873 views
94 votes
94 votes

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?

  1. Both $\left\{\textit{f} \right\}$ and  $\left\{ \textit{g}\right\}$ are functionally complete
  2. Only  $\left\{ \textit{f} \right\}$  is functionally complete
  3. Only  $\left\{ \textit{g}\right\}$  is functionally complete 
  4. Neither $\left\{ \textit{f}\right\}$  nor  $\left\{\textit{g}\right\}$ is functionally complete

8 Answers

Best answer
119 votes
119 votes

$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

edited by
23 votes
23 votes

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)

22 votes
22 votes

If we able to derive 

  • <OR,AND,NOT>

  • <OR,NOT>

  • <AND,NOT>

THEN function is functionally completed set.

Option b is right

19 votes
19 votes

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.

Answer:

Related questions

12 votes
12 votes
3 answers
1
makhdoom ghaya asked Feb 11, 2015
4,989 views
Which one of the following combinations is incorrect?Acquiescence - SubmissionWheedle - RoundaboutFlippancy - LightnessProfligate - Extravagant
52 votes
52 votes
7 answers
3
makhdoom ghaya asked Feb 12, 2015
20,634 views
Consider a $4$-bit Johnson counter with an initial value of $0000.$ The counting sequence of this counter is $0, 1, 3, 7, 15, 14, 12, 8, 0$$0, 1, 3, 5, 7, 9, 11, 13, 15, ...
80 votes
80 votes
7 answers
4
makhdoom ghaya asked Feb 13, 2015
28,736 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...