Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to make a truth table from an SOP boolean algebra expression. I understand AND, OR, NOT truth tables. I just dont understand these types of tables and their outputs.

This is the expression: $$A'BD' + BCD + ABC' + AB'D = A'BD' + BCD + ABC' + AB'D + BC'D' + A'BC + ABD.$$

I can use either side whichever is easier. Just let me know which side. Would $A'$ be a $1$ and the others be a zero? I am also not sure how they get the output? I understand the outputs of a AND, OR truth tables.

But I can't figure out these outputs. Would this be considered an OR table since the expression is $+$?

Would I just construct $A$, $B$, and $D$ with nots = 1 or zero? Then, how do I determine the output?

 -----------------------
 A  | B  | D  |  output
-----------------------
| 1 | 0  | 1  |   1?    |  A'BD'
------------------------
| 0 | 0  | 0  |   0?    |  BCD
------------------------
| 0 | 0  | 1  |   1?    |  ABC'
-------------------------

something like that.

What I am trying to achieve is how the below expression is true using theorems.

$$A'BD' + BCD + ABC' + AB'D = A'BD' + BCD + ABC' + AB'D + BC'D' + A'BC + ABD$$

share|improve this question
add comment

4 Answers 4

A, B, C, and D are boolean variables, meaning that each takes the value "true" or "false". More complex expressions have value "true" or "false" depending on the values of these variables, so for example A'BD' is true if A is false, B is true, and D is false, and C is either true or false.

To say that F = G, where F and G are complex expressions, means that, no matter what values the boolean variables have, the value of F is the same as the value of G (that is, F and G are either both true or both false). So, for example, we have

     AB + AC = A(B+C)

because if A is true and either B or C is true, then both sides are true, and in any other case both sides are false---there's no way to assign values to A, B, C such that the two side come out differently.

As previous posters have mentioned, you can always prove (or disprove!) an equality by going through all possible assignments of "true" and "false" to the variables. The goal seems to be to prove "by theorems", that is, using operations previously proven true. As you say, we can either manipulate one side of the equation until it has the form of the other side, or we could manipulate both sides and get them into a common form.

In this case, the first thing to notice is that the right-hand side (RHS) is a copy of the LHS with some extra stuff tacked onto the end. For this reason it's simplest to manipulate just the RHS to get rid of the surplussage! We can start with this basic theorem:

  if Q is true whenever P is true, then Q = Q + P

We can prove this theorem by systematically considering all possibilities for P and Q. Or look at it this way: If Q is true, then both sides of the equation are true. And if Q is false, then P must be false (since, by assumption, if P were true Q would be true) hence both sides are false.

Given this theorem we prove:

  XY + X'Z = XY + X'Z + YZ     

Proof: Let P be YZ and let Q be XY+X'Z. Suppose P is true, that is, Y and Z are both true. But if Y and Z are both true, then XY+X'Z must be true. (Reason: If X is true then, since Y is true, XY is true. And if X is false then, since Z is true, X'Z is true. So in either case XY+X'Z is true.) So we've shown that Q is true whenever P is true, hence by the previous theorem Q = Q + P, which in this case is what we wanted to prove.

Now we can prove

 A'D' + AC' = A'D' + AC' + C'D'

This is just the same as the previous theorem, putting A for X, D' for Y, and C' for Z.

This last theorem implies

 B(A'D' + AC') = B(A'D' + AC' + C'D')

which is the same as

 A'BD' + ABC' = A'BD' + ABC' + BC'D'

Given this, we can take the RHS of the original and substitute A'BD' + ABC' for A'BD' + ABC' + BC'D', which is to say, we can drop the term BC'D'.

With steps similar to the above we can prove these two theorems:

 A'BD' + BCD = A'BD' + BCD + A'BC
 BCD + ABC' = BCD + ABC' + ABD

which permit us to drop the final two terms of the RHS of the original, completing the proof.

share|improve this answer
    
Thank you so much, things make more sense. Looking at my original uquation everything is the same except the last 3 peices. Should those cancel out? without those they equal exactly! –  Corey J Mattis Oct 22 '10 at 19:22
    
So, what your telling me is since the left hand side equals the right hand side except the last 3 i can just drop the last 3?A'BD' + BCD + ABC' + AB'D = A'BD' + BCD + ABC' + AB'D + //BC'D' + A'BC + ABD // all variables are the same except these –  Corey J Mattis Oct 22 '10 at 19:28
add comment

Your truth table will have 2^4=16 lines. Start with four columns labeled A,B,C,D. On each line put a different combination of truth values for A,B,C, and D. Then add more columns for the pieces of your expression. So to build up the left hand side, make a column A'B and put in the truth values of that combination. The prime on A is not and the multiply is AND. So this column would show (NOT A) AND B for the values of A and B on that line. Continue adding columns for other terms until you have built up the entire left hand side. Then start on the terms that make up right hand side. When you have built up the right hand side, compare the left hand side column and the right hand side column. If they agree on all 16 lines, your equation is correct. For a simple example, say we want to prove (A+B)'=A'B' The table would look like this

alt text

As the (A+B)' column and the A'B' column agree everywhere, the equation is correct.

share|improve this answer
    
How are we to do an output? like a function –  Corey J Mattis Oct 22 '10 at 10:28
add comment

This is more of an extended remark out of academic curiosity. I thought I would try to use Prover9 to prove the given identity. [here v denotes "or" and ^ denotes "and"]

To test this, I inputted the assumptions into Prover9 (this is the OP's list of axioms from here):

x v x' = y v y'.  % false
x ^ x' = y ^ y'.  % true

y v (x ^ x') = y.
y v (x v x') = y.
x v x = x.
x v y = y v x.
(x v y) v z = x v (y v z).
x ^ (x v y) = x.
(x ^ y) v (x ^ y') = x.

from which it proved the OP's identity (and if I understand correctly, it was by contradiction):

((((w' ^ x) ^ z') v ((x ^ y) ^ z)) v ((w ^ x) ^ y')) v ((w ^ x') ^ z) = (((((((w' ^ x) ^ z') v ((x ^ y) ^ z)) v ((w ^ x) ^ y')) v ((w ^ x') ^ z)) v ((x ^ y') ^ z')) v ((w' ^ x) ^ y)) v ((w ^ x) ^ z).
share|improve this answer
    
That is an interesting piece of software... just for that link, +1. –  J. M. Oct 23 '10 at 3:28
add comment

I think the "using theorems" part of the question is intended to prevent you from using the exhaustive "try every possibility" technique (so don't use this technique if it's a homework question).

However, this technique will work fine, you can just run through the $2^4=16$ possible values of (A,B,C,D) and check that both sides of the equation match. This will be a rigorous proof of the identity -- just not a particularly intelligent one.

Assuming I understand the notation correctly:

  • concatenation (i.e. writing the letters next to each other) is short for "and", for example ABC is "A and B and C",
  • addition (i.e. +) is short for "or", for example AB+CD is "(A and B) or (C and D)"
  • adding a dash ' is the notation for negation, i.e. "not", for example AB' is "A and (not B)".

So A'BD' is the same as (not A) and B and (not D). In your table, the first row is wrong since (not A) is false (because A is true=1). The second row is correct since B is false=0 (regardless of what value C has). The third row is wrong since A is false=0 (again, regardless of what values C has).

share|improve this answer
    
This is a homework question. We are to use theorems to Show the above expression is true using theorems. Not sure how to tackle this problem? –  Corey J Mattis Oct 22 '10 at 4:13
    
I admit it is tricky, my first instinct would be to prove a smaller identity, such as ABC'+A'BD'=ABC'+A'BD'+BC'D', then use it to eliminate the BC'D' from the right-hand-side of the equation. Then repeat with similar identities. –  Douglas S. Stones Oct 22 '10 at 4:28
    
im going to give up because i dont even know what the = means? does the left side equal the right side? or are they two different equations? does the lfet side when worked out equal the right side? im lost.. –  Corey J Mattis Oct 22 '10 at 5:37
    
The = implies that the left-hand side is true whenever the right-hand side is true (and the left-hand side is false whenever the right-hand side is false) [so yes, when worked out]. It is just one equation, your goal is to prove that it's always correct. –  Douglas S. Stones Oct 22 '10 at 5:44
    
what does true mean? do i have to work both sides? Why is this so hard? The book gives us some theorems with two variables and he gives us this monster to work on. So, in other words i have to work both sides of the = ? "your goal is to prove that it's always correct" what does correct mean? i dont mean to sound stupid but i am brand new to this stuff. I am a Software engineering student! –  Corey J Mattis Oct 22 '10 at 10:33
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.