2,722 views
4 votes
4 votes
Consider the operations defined as  f(X, Y, Z) = X'YZ + XY' + Y'Z'  and  g(X′, Y, Z) = X′YZ + X′YZ′ + XY .

Iam following this method,

 A function is said to be complete if it can implement Complementation and OR logic / Complementation and AND logic.

 

For function f(X,Y,Z) = X'YZ + XY' + Y'Z'

 f(X,X,X) = X'XX + XX' + X'X' = X' ( Complement logic)

Now if i can implement either OR / AND logic  , then can i say function is complete??

But for g(X′, Y, Z) = X′YZ + X′YZ′ + XY

g(X',X',X') = XX'X'  + XX'X' + X'X' = X' (Expected ans is X as X is complement of X', hence this is functionally incomplete).

 

How to prove OR / AND logic is possible for f(X,Y,Z)?

2 Answers

1 votes
1 votes
f(x,y,z)= x'yz+xy'+y'z'

f(x,1,1)= x' --> F(x) can implement NOT gate.

 

to get AND gate put x = x'  y=1 z=z we will get xz as outoput

f(f(x,1,1), 1, z)=>     f(x', 1, z)=>  xz

 

hence it is functionally complete.
0 votes
0 votes
A functionally complete function can realize any function, just like a universal function. So if you prove that it realizes NOT and AND (or Nand) or NOT and OR (or Nor) then it is functionally complete. Here if in the first function we put X equal to Y then it looks like this:
f(X,X,Z) = X'XZ + XY' + Y'Z' = (Y+ Z)'
This function becomes a NOR function which is functionally complete. Therefore, f is also functionally complete.

However, you can't implement any universal function mentioned above by using function g. Eg:

putting X=Y=Z gives X as output, putting X=Y gives X again..... similarly we can try. In your  eg, X' is output which means NOT gate is realized but then you need to realize AND/OR too along with NOT for it to be functionally complete.
Since we don't get any universal function from function g. Therefore it is functionally incomplete.

Related questions

2 votes
2 votes
1 answer
3
just_bhavana asked Oct 4, 2017
4,419 views
Which of the following set is not functionally complete?a) {XOR,1,NOT}b) {XOR,1,OR}c) {OR, NOT}d) {XOR,1, AND}
2 votes
2 votes
1 answer
4