Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

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

Status
Not open for further replies.

solvemydoubt

Newbie level 4
Newbie level 4
Joined
Feb 6, 2013
Messages
6
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,324
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. :)
 

zorro

Advanced Member level 4
Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,130
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,909
Plot Karnaugh maps for finding the most simple expressions for the two functions.
For example; Z = /C*X + C*Y
Regards

Z
 

solvemydoubt

Newbie level 4
Newbie level 4
Joined
Feb 6, 2013
Messages
6
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,324
Plot Karnaugh maps for finding the most simple expressions for the two functions.
For example; Z = /C*X + C*Y
Regards

Z
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 - - -

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

Z

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.
 

zorro

Advanced Member level 4
Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,130
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,909
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
 

solvemydoubt

Newbie level 4
Newbie level 4
Joined
Feb 6, 2013
Messages
6
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,324
so...functionally complete means being able to realize any given function in terms of AND OR and NOT. Am I right?
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
 

zorro

Advanced Member level 4
Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,130
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,909
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
 

solvemydoubt

Newbie level 4
Newbie level 4
Joined
Feb 6, 2013
Messages
6
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,324
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
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?
 

zorro

Advanced Member level 4
Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,130
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,909
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
 

solvemydoubt

Newbie level 4
Newbie level 4
Joined
Feb 6, 2013
Messages
6
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,324
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

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

zorro

Advanced Member level 4
Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,130
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,909
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
 

solvemydoubt

Newbie level 4
Newbie level 4
Joined
Feb 6, 2013
Messages
6
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,324
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 :)
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top