Please help me know how to show this function as functionally complete

I have, say a gate with 3 inputs C X Y and two outputs Z W , with the following truth table :

C X Y Z W
0 0 0 0 0
0 0 1 0 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 0
1 0 1 1 0
1 1 0 0 1
1 1 1 1 1

I am challenegd to prove it functionally complete by just showing that this gate can implement AND and NOT gate...I tried to figure out many boolean functions for Z and W but no luck. Some1 please kindly help me.

Plot Karnaugh maps for finding the most simple expressions for the two functions.
For example; Z = /C*X + C*Y
Regards

Z

zorro said:

Plot Karnaugh maps for finding the most simple expressions for the two functions.
For example; Z = /C*X + C*Y
Regards

Z

Click to expand...

Hi Zorro,

Thank you for the idea Now it turns out that W = /C*y + C*X and Z is as you said Z = /C*X + C*Y. And I understood that a boolean function is functionally complete if we can show AND in terms of OR and NOT and vice versa. So when I am asked to show the above boolean function as functionally complete how should I proceed beucase OR, AND, NOT all three of them are there in Z and W. I am a little confused. Should I just change the way Z and W are represnted like right now they are sum of prodcuts is it enough if I show them as product of sums ? Kindly clarify me in this regard.

Thank You.

- - - Updated - - -

zorro said:

Plot Karnaugh maps for finding the most simple expressions for the two functions.
For example; Z = /C*X + C*Y
Regards

Z

Click to expand...

Actually can you or anyone reading this post please tell me how to show any given boolean function(which might have XOR XNOR or any such functions (other than simple AND or OR or NOT) or gate as fucntionally complete ( can have any number of inputs and any number of outputs) .

Thank You.

Hi,

i see now that you must show that the two functions can be synthesized using the functionally complete set {AND, NOT}.
So, take the above expressions and transform them using De Morgan laws.

For example; Z = /C*X + C*Y = /(/(/C*X)*/(C*Y))

Analogously, you could obtain Z and W using the complete set {OR, NOT} or the complete set {NAND}, etc.
Regards

Z

so...functionally complete means being able to realize any given function in terms of AND OR and NOT. Am I right?

zorro said:

Hi,

i see now that you must show that the two functions can be synthesized using the functionally complete set {AND, NOT}.
So, take the above expressions and transform them using De Morgan laws.

For example; Z = /C*X + C*Y = /(/(/C*X)*/(C*Y))

Analogously, you could obtain Z and W using the complete set {OR, NOT} or the complete set {NAND}, etc.
Regards

Z

Click to expand...

Hi,

I wrote the my last post while you were updating your post #3...
It must be said that Functional Completeness is not a property of a boolean funcion but a property of a set of funcions.

For example, the set of elementary functions {AND, NOT} is functionally complete because using them you can generate any complex logical function of any number of variables. (N.B.: AND takes two arguments and NOT tekas only one.)
{NAND} is a functionally complete set. You can obtain any logical function using only NAND gates.
{AND} is not. For example you can not get Y=/X using only AND gates.

If I undesrstood toy problen, you must show how to obtain Z and W uing only AND and NOT gates. Is it right?

Regards

Z

zorro said:

Hi,

I wrote the my last post while you were updating your post #3...
It must be said that Functional Completeness is not a property of a boolean funcion but a property of a set of funcions.

For example, the set of elementary functions {AND, NOT} is functionally complete because using them you can generate any complex logical function of any number of variables. (N.B.: AND takes two arguments and NOT tekas only one.)
{NAND} is a functionally complete set. You can obtain any logical function using only NAND gates.
{AND} is not. For example you can not get Y=/X using only AND gates.

If I undesrstood toy problen, you must show how to obtain Z and W uing only AND and NOT gates. Is it right?

Regards

Z

Click to expand...

Yes, The hint given was to "implement AND and NOT gates using give gate/function". I thought functionally complete means to use that given function somehow manipulate and finally get a AND/NOT or OR/not but actually functionally complete means rewriting the given function in terms of AND, NOT or OR/NOT.. Did I understand correctly now?

Now I have a doubt.
Maybe what you are requested for is to show how to get NOT and AND operators using only Z and W functions.

In other words: suppose you have a logic "gate" (a logic block) with 3 inputs (named C, X, and Y) and 2 outputs (named Z and W).
Your task would be to find a combination of blocks of that type that implement the NOT function, and another that implement the AND function.
To obtain the NOT function is easy. This is one of the possible implementations:


..........------------
input-----|C.........|
..........|.........Z|----output
.......1--|X.........|
..........|.........W|--
.......0--|Y.........|
..........------------


Can this interpretation of your task be the correct one?

Note that if it were possible to obtain both NOT and AND using only block of this type, it would be functionally complete by itself because the set {NOT, AND} has that property.

Regards

Z

zorro said:

Now I have a doubt.
Maybe what you are requested for is to show how to get NOT and AND operators using only Z and W functions.

In other words: suppose you have a logic "gate" (a logic block) with 3 inputs (named C, X, and Y) and 2 outputs (named Z and W).
Your task would be to find a combination of blocks of that type that implement the NOT function, and another that implement the AND function.
To obtain the NOT function is easy. This is one of the possible implementations:


..........------------
input-----|C.........|
..........|.........Z|----output
.......1--|X.........|
..........|.........W|--
.......0--|Y.........|
..........------------


Can this interpretation of your task be the correct one?

Note that if it were possible to obtain both NOT and AND using only block of this type, it would be functionally complete by itself because the set {NOT, AND} has that property.

Regards

Z

Click to expand...

Hi Zorro... yes thats the question... I will try for various combinations firsto build AND and if I dont get it I will ask you here...thanks a lot for helping me

Hi again

I took this problem as a puzzle and I found a way to obtain the AND function.



..........------------
input1-+--|C.........|
.......|..|.........Z|----output
.......+--|X.........|
..........|.........W|--
input2----|Y.........|
..........------------


I don't know whether there is a systematic method to do that. My approach was just intuitive.
Regards

Z

Hi Zorro, We can show what you did from K-Maps. We can show the ouputs I mean AND and NOT also at W right.
Thank You