How to Design a Boolean Function for a Full Adder?

[peripatein]

Hi,

Homework Statement

I'd like to find B_θ:{0,1}³→{0,1}² which is defined as follows:
Input: x,y,z\in{0,1},
Output: s,c\in{0,1},
Functionality:2c+s=x+y+z

Homework Equations

The Attempt at a Solution

I first tried listing all the possible combinations of x,y,z, and there are obviously 8. I noted that x+y+z would yield 1 only if at least one of the three were one. I then tried to find a Boolean formula for s and one for c, so I could use the relation given in the "functionality" above, but I truly got lost. How may I possibly assign a function to s and c? There certainly could be more than one such function satisfying that equation, couldn't there? In any case, I'd sincerely be thankful for some guidance/advice.

 

[jedishrfu]

I'd start by building a truth table with five columns x,y,z,s,c

then construct your equation for s using only the rows where s has a one value.

As an example for row x=1, y=0, z=0 then s=1 ===> we'd construct a term x . y' . z' where y' means "not y"

s = x . y' . z' + x' . y . z' ... where + means OR and . means AND

he eqn says that s will be true when the first erm is true or the second term is true or ... or the last term is true.

Use boolean algebra to simplify the s equation.

Do the same the construct the c equation,

 

[peripatein]

How can you tell, in your example, that x,y,z being 1,0,0 respectively, s would have to be 1? What if c were 1? In the latter case (c=1), s could surely also be zero and 2*1+0=1=x+y+z.

 

[jedishrfu]

okay look at the first term it will be true if x=1, y=0 and z=0 because its x and not-y and not-z which is 1 . 1 . 1 right?

 

[peripatein]

I agree that 1+0+0=1, or, alternatively, that 1 AND 1 AND 1=1, but how does that restrict s to be 1 as you first wrote?

 

[jedishrfu]

the first term represents the a row in your truth table where the inputs make s a 1 so when x=1 and y=0 (ie not-y=1) and z=0 (not-z=1) then this term will evaluate to 1.1.1 = 1 and so s will be a one. Remember the operators + and . are boolean operators Or and AND respectively.

 

[peripatein]

I am well aware of the truth tables of both AND and OR. However, x+y+z=1 still doesn't necessarily restrict s to be 1! That's all I am saying. Do you agree that x,y,z being 1,0,0 still doesn't necessarily entail s=1? As I wrote earlier, if c were 1 then s has two possible values still satisfying the desired functionality: s could be either 1 or 0, hence not just 1. Do you agree? If you do agree, then what made you write that s had to be 1 in that case?

 

[jedishrfu]

Okay I see where your're going and yes you need to factor carry in as well so you need a column for possible carry inputs
making the s terms be x.y.z.c so the first term might be x.y'.z'.c' which will be one if x=1,y=0,z=0 and c=0

So one question I have are you trying to make a standard 2 input full-adder with the z being the input carry then my original terms of x.y.z without the c would be the correct way to go.

so the s = xy'z' + x'yz' + x'y'z... ie a series of terms and if one or more of these terms evaluates to 1 then s will be a 1. The + symbols don't mean add they mean OR the terms together.

 

[peripatein]

I am not really sure how to go about this, I am afraid. Despite your explanation. For instance, how did you derive
s = xy'z' + x'yz' + x'y'z...? As far as I am concerned, s=1 iff x+y+z=1 and s=0 iff x+y+z=0.

 

[jedishrfu]

I am not really sure how to go about this, I am afraid. Despite your explanation. For instance, how did you derive
s = xy'z' + x'yz' + x'y'z...? As far as I am concerned, s=1 iff x+y+z=1 and s=0 iff x+y+z=0.

You are confusing the ordinary addition operator with the boolean + operator which means OR. I derived it from the truth table using every row where s=1 and there are more terms needed to complete the s equation which I didn't write because we aren't supposed to give you the answer here.

In essence my equation is codifying the truth table into a single equation each term represents a single row where s=1 (we ignore the rows where s=0). I used primes to mean NOT so the row where x,y,z are 1,0,0 is written as xy'z'. Why? because that term will be true if x,y,z are set to 1,0,0 respectively and the other s terms will be false.

so I expanded to more terms using more rows and wrote xy'z' + x'yz' + ... that means:

s = ( x AND (NOT y) AND (NOT z) ) OR ( (NOT x) AND y AND (NOT z) ) OR ...

from this equation s can only have two values 0 or 1

If you are treating the + as a boolean OR then the flaw in your equation is that it will set s true when x=1 and y=1 and z=0 which is wrong because in binary 1+1+0= 10 meaning s=0 and c=1

Try rereading your book maybe after having this discussion it will make more sense and try not to over think it. I first learned this stuff when I was in 9th grade by accident while I was studying for algebra and learning about computers more than 50 years ago.

 

[peripatein]

This is what I don't quite get. C is either 0 or 1, right? Hence, 2c would always be equal to c, wouldn't it?

 

[jedishrfu]

You have to look at the bigger picture. This problem describes a single stage full adder. Combine 32 stages together to get a register adder that can add two 32 bit numbers to produce a 32 bit answer. The z input is the carry bit from the previous stage.

The xyz input can sum at most to 11 binary which means the s is one and the carry is one to be passed into the next stage.