The Gateway to Computer Science Excellence
+58 votes
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
in Set Theory & Algebra by Boss (30.7k points) | 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.

So, (B) is correct answer!

+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  @Manu Thakur Sir , Cant we use {1,0} to get Not gate in step. 1 of your solution in comment above?

10 Answers

+81 votes
Best answer

$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 by
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
Link is now dead, but I uploaded one copy here -http://docdro.id/zQj013C
+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)

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

0

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

Hasse diagram of F()

 

+16 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)

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

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

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

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 ....
+8 votes

If we able to derive 

  • <OR,AND,NOT>

  • <OR,NOT>

  • <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
+2 votes
answer is b
by Active (1.4k points)
+1 vote

copying manu thakur's answer

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.

So, (B) is correct answer!

by Loyal (5.3k points)
0 votes
answer is b
by Active (1.4k points)
+1
how??
0 votes

 Nov 25, 2017 by  Boss (43.7k points)
moved Nov 25, 2017 by 

 

+46

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.

So, (B) is correct answer

by Active (1.5k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
198,061 comments
104,696 users