Truth Table

[webmasts]

Hi,

I'm taking my first course in CS. I am confused as to how to make the truth table. I know that FF = F or TF = F for an AND operator. How would I make a table for the following with 0s and 1s:

Q. What are the truth tables for the following Boolean expresssions:

1.

NOT ((a OR b) AND (NOT b)

2.

(a AND b) OR (NOT a AND NOT b)

I really appreciate your help! :confused:

[Dani]

True is 1 and False is 0. So all you have to do is first figure out all the Ts and Fs, and then convert it to 1 and 0. For example, if F and F = F, then 0 and 0 = 0.

Okay ... so here goes:

When we use AND we mean "both" and when we use OR we mean "either".

Here's an example:

Some statement A is false.
Some other statement, say statement B, is also false.
So now what is statement A and statement B?
Since we used "and", we mean "both". Both have to be true for the entire thing to be true. But neither is true. So the whole thing is false.

For example, we know statement A is false, so lets think of a false statement to use to represent statement A: The sky is green. We also know statement B is false, so let's think of a false statement to represent statement B: The grass is blue. So now we want to evaluate statement A AND statement B, together. In other words, let's evaluate "Both the sky is green AND the grass is blue." Well if the sky isn't green, and the grass isn't blue, it is definitely not true that both are true. Therefore, that evaluates to false. We just proved that FALSE AND FALSE = FALSE ... or 0 and 0 = 0.

Now let's use the OR operator, with the same two statements. Let's evaluate "Either the sky is green OR the grass is blue." Well that certainly isn't true. Neither the sky is green nor is the grass blue. Therefore, we just proved that FALSE OR FALSE = FALSE.

Now let's try evaluating when one statement is true and the other is false. Let's make statement A be that the grass is green (which is true) but we'll make statement B be that the sky is also green (which is false). Now let's use the AND operator: "The grass is green AND the sky is green." Well that's not true! It's not true that both the grass and sky are green. Therefore, when one statement is true and the other is false, using the AND operator on them results in a false statement. Therefore, T AND F = F.

Now let's use OR: "Either the grass is green or the sky is green." Well that actually IS true! Since it's true that the grass is green, and the OR statement only needs AT LEAST ONE truth in the statement to evaluate to true, we can say it's true. Therefore, T OR F = T.

Now let's have two true statements. The sky is blue can be statement A and the grass is green can be statement B. Let's use the AND operator: "Both the sky is blue AND the grass is green." Yup, true! How about OR: "Either the sky is blue OR the grass is green." Well, both halves of that statement are true. For an OR, remember, we need AT LEAST ONE to be true. It's just a bonus that both are. Therefore, we can say that T OR T = T as well.

There is something else called an exclusive OR, or XOR, which means "one but not both." Remember when we say: "Either the sky is blue OR the grass is green." we are saying T OR T = T. But if we were to say: "Either the sky is blue OR the grass is green but not both." we are saying T XOR T = F.

When we use NOT, we mean just the opposite. For example, NOT True is False. NOT False is True. When evaluating statements with NOT, just reverse the T or F value, and then plug it into a statement to evaluate it. For example, "The sky is blue." can be statement A, and it is TRUE. Therefore, NOT A would represent the statement "The sky isn't blue" OR "It is not true that the sky is blue." and would evaluate to FALSE. It's not true that the sky isn't blue ... the sky IS blue!

Now let's mix it up a bit: Let's make A be true, and B be false. We learned already that when that is the case, A AND B = False, because True AND False = False. But now what about NOT A AND B? Well, since A is true, then not A is false. Therefore, we're now evaluating the statement False AND False, which also happens to be False.

When dealing with parentheses, just work from inside out. For example, suppose a is TRUE and b is FALSE. We want to evaluate (a AND b) OR NOT b.

Well, let's work on the (a AND b) part first. That is T AND F which we know is F. So far we have FALSE OR NOT b. Well, if b is false, then not b is true. So now we have FALSE OR TRUE. Well, if we have an OR where one half of the statement is false and the other half is true, remember we only need part of an OR statement to be true for the entire thing to be true. So the entire thing evaluates to true.

Good luck!

[Rashakil Fol]

You know how to make a simple truth table, right? For example,

a | b | a AND b
---+---+---------
 F | F |    F
 T | F |    F
 T | T |    T
 F | T |    F

If you want to make a truth table for compound statements, just use parts of statements you've made before.

a | b | a AND b | NOT b | (a AND b) OR (NOT b) | ...
---+---+---------+-------+----------------------+------
 F | F |    F    |   T   |          T           | ...
 T | F |    F    |   T   |          T           | ...
 T | T |    T    |   F   |          T           | ...
 F | T |    F    |   F   |          F           | ...

Here, the column (a AND b) OR (NOT b) is derived from the truth and false values from the column a AND b and the column NOT b.

If you want to use 0's and 1's in place of F and T, that's fine.

[Dani]

Okay ... now we're bordering on just giving away too much of the answer without letting him or her give it a go on his/her own! ;) (I'm one to talk, I know, but I have insomnia.)

[Rashakil Fol]

Huh? Answer to what? (a AND b) OR (NOT b) is not in any of the problems...

[Dani]

(a AND b) OR (NOT a AND NOT b) ... Just throw a "not a" in there :) My statement was made with a somewhat sarcastic tone though. You just can't tell because it's 4 am and I can't get to sleep :(

[webmasts]

(a AND b) OR (NOT a AND NOT b) ... Just throw a "not a" in there :) My statement was made with a somewhat sarcastic tone though. You just can't tell because it's 4 am and I can't get to sleep :(

Thank you both for assistance! I understand the true false concept. What I'm confused is how to work on the parenthesis part. The too many NOTs makes me confused. I can make indvidual truth table, but mixing them makes me confused. That is what I wanted...I read every line of both of your suggestions! Can you tell me how to work the mixing problems...this is where i'm stuck! I'm not looking for the free answer...but so that I can understand...I understand better from example!--it always takes me long time to get any new concept!

[webmasts]

This is what I have..not sure if it is right for:

NOT(a OR b) AND (NOT b)

a b NOT a OR b NOT b
--------------------------
0 0 1 1
1 0 0 1
0 1 0 0
1 1 0 0

Please tell me what i'm doing wrong.

This is what I have..not sure if it is right for:

NOT(a OR b) AND (NOT b)

a b NOT a OR b NOT b
--------------------------
0 0 1 1
1 0 0 1
0 1 0 0
1 1 0 0

Please tell me what i'm doing wrong.

I believe there is a sense of ambiguity in the expression you gave. I assume you missed out a set of parenthesis looking at your initial question.

Should it be this:

NOT ((a OR b) AND (NOT b))

This makes it clearer. All you have to do is tackle the problem from the inner most parenthesis and work outwards:

A B | A or B | not B | A or B and not B | not(A or B and not B) |
----+--------+-------+------------------+-----------------------+
0 0 |    0   |   1   |        0         |           1           |
1 0 |    1   |   1   |        1         |           0           |
0 1 |    1   |   0   |        0         |           1           |
1 1 |    1   |   0   |        0         |           0           |

And just so no one can accuse me of doing your homework(dani) there is a deliberate mistake in there somewhere.

[webmasts]

Thanks! So to test my understanding, can you give me a similiar problem so that I can show you if I learned it?

[Lord Soth]

Hi,

Here are two simplifications for you which might save you some time :

(NOT A) or (NOT B) = NOT(A and B)
(NOT A) and (NOT B) = NOT(A or B)

Think those equalities in both directions, if we simplify 1 and 2 using these :

1. NOT ((a OR b) AND (NOT b)) = (NOT (a OR b)) OR NOT(NOT(b)) = NOT(A OR B) OR B

2. (a AND b) OR (NOT a AND NOT b) = (a AND b) OR NOT(a OR b)

Use as much as paranthesis and spaces to see the hierarchy as you need to not get lost on equations.

Loren Soth