8.2k views

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.2k views
0
u mean u want to chk linearity only

and based on that u want ans right?
0
Yes using linearity, if a bool function is not linear, will check for monotonicity to check for functional complete
0

From Wikipedia:-

A Boolean function is linear if one of the following holds for the function's truth table:

1. In every row in which the truth value of the function is T, there are an odd number of Ts assigned to the arguments, and in every row in which the function is F there is an even number of Ts assigned to arguments. Specifically, f(F, F, ..., F) = F, and these functions correspond to linear maps over the Boolean vector space.
2. In every row in which the value of the function is T, there is an even number of Ts assigned to the arguments of the function; and in every row in which the truth value of the function is F, there are an odd number of Ts assigned to arguments. In this case, f(F, F, ..., F) = T.

Can, we conclude that all the function which have, odd no of argument are always, linear?

+58

A function will be called functionally complete if either we can get {NOT, OR} or {NOT, AND}.

1. f(X,Y,Z) = X'YZ + XY' + Y'Z'
take all input as X=Y=Z=x
f(x,x,x) = x'xx + xx' + x'x' = x'  (NOT gate)
f(x,x,z) = x'xz + xx' + x'z' = x'z',  now if we take complement of x'z' as (x'z')' = x+z, (OR Gate)
Hence, f is functionally complete as we have got {NOT, OR}
.

2.
g(X,Y,Z) = X'YZ + X'YZ' + XY
g(x,x,x) = x'xx + x'xx' + xx = x ( not possible to get NOT gate)
or if further minimized the given expression,
X'YZ + X'YZ' + XY = X'Y( Z + Z') + XY = X'Y + XY = Y( X+X') = Y
Hence, g is not functionally complete.

+1

A function will be called functionally complete if either we can get {NOT, OR} or {NOT, AND}.

take all input as X=Y=Z=x

Sir , is this a trick  or definition?

+6
NAND and NOR are universal GATE.
+6

here

in f

f(X,X,X)=X'XX+XX'+X'X'= 0+0+X'=X'  <--- NOT

f(X,Y',Y)=X'Y'Y+XY+YY'= 0+XY+0=XY            <--- AND

and g is not functionally complete..

0
This makes sense . We can use NOT that we got in step 1.
0

@tusharp  Sir , Cant we use {1,0} to get Not gate in step. 1 of your solution in comment above?

$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 and hence B is the answer.

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

by Veteran (430k points)
edited
0
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?
+11

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.

+1
Thanks a lot!!!

The explanation as well as material!! Kudos
0
the link given is not working @arjun
+13
+1
Great (Ans+Link) .Thank U very Much.
+4
@ arjun sir, cant we just check whether the circuit derives and/or and not gate??
0
^ Yes. thats the simplest way.
0
Cool. But I think this method will work faster. Only thing is memorizing this method. ,
0
Superb solution and Material.Thank u Arjun sir.
0
@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?
0
@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.
0
@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.
0
Arjun sir thanks a lot  for this approach and link u provide
0
thanks sachin sir for updated link u provide
0

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

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

0

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

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)

by Boss (29k points)
0
you have interchanged 'linear' & 'monotone' in function g.
0

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

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

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

Please, correct me if i am wrong.

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.

by Active (4.8k points)
+7
@Jatin Saini

U are taking help from 0 or 1 in order to implement OR gate, i think it is called partially functionally complete.
+1
Ya nt a correct way of solving ....

If we able to derive

• ## <AND,NOT>

THEN function is functionally completed set.

Option b is right

by Boss (36.5k points)
+1
Should i check for all possible ways of XYZ to get  solution of function containing operations  NOT OR and AND
0
Yes we try to derive any one of the set
by Active (1.4k points)
+1 vote

A function will be called functionally complete if either we can get {NOT, OR} or {NOT, AND}.

1. f(X,Y,Z) = X'YZ + XY' + Y'Z'
take all input as X=Y=Z=x
f(x,x,x) = x'xx + xx' + x'x' = x'  (NOT gate)
f(x,x,z) = x'xz + xx' + x'z' = x'z',  now if we take complement of x'z' as (x'z')' = x+z, (OR Gate)
Hence, f is functionally complete as we have got {NOT, OR}

2.
g(X,Y,Z) = X'YZ + X'YZ' + XY
g(x,x,x) = x'xx + x'xx' + xx = x ( not possible to get NOT gate)
or if further minimized the given expression,
X'YZ + X'YZ' + XY = X'Y( Z + Z') + XY = X'Y + XY = Y( X+X') = Y
Hence, g is not functionally complete.

by Loyal (5.3k points)
by Active (1.4k points)
+1
how??

## So, (B) is correct answer

by Active (1.5k points)