Boolean Implication

I need some help with th开发者_开发问答is Boolean Implication.

Can someone explain how this works in simple terms:

A implies B = B + A' (if A then B). Also equivalent to A >= B

Boolean implication A implies B simply means "if A is true, then B must be true". This implies (pun intended) that if A isn't true, then B can be anything. Thus:

False implies False -> True
False implies True  -> True
True  implies False -> False
True  implies True  -> True

This can also be read as (not A) or B - i.e. "either A is false, or B must be true".

Here's how I think about it:

if(A)
  return B;
else
  return True;

if A is true, then b is relevant and should be checked, otherwise, ignore B and return true.

I think I see where Serge is coming from, and I'll try to explain the difference. This is too long for a comment, so I'll post it as an answer.

Serge seems to be approaching this from the perspective of questioning whether or not the implication applies. This is somewhat like a scientist trying to determine the relationship between two events. Consider the following story:

A scientist visits four different countries on four different days. In each country she wants to determine if rain implies that people will use umbrellas. She generates the following truth table:

Did it rain?  Did people      Does rain => umbrellas?  Comment
              use umbrellas?  
No            No              ??                       It didn't rain, so I didn't get to observe
No            Yes             ??                       People were shielding themselves from the hot sun; I don't know what they would do in the rain
Yes           No              No                       Perhaps the local government banned umbrellas and nobody can use them. There is definitely no implication here.
Yes           Yes             ??                       Perhaps these people use umbrellas no matter what weather it is

In the above, the scientist doesn't know the relationship between rain and umbrellas and she is trying to determine what it is. Only on one of the days in one of the countries can she definitively say that implies is not the correct relationship.

Similarly, it seems that Serge is trying to test whether A=>B, and is only able to determine it in one case.

However, when we are evaluating boolean logic we know the relationship ahead of time, and want to test whether the relationship was adhered to. Another story:

A mother tells her son, "If you get dirty, take a bath" (dirty=>bath). On four separate days, when the mother comes home from work, she checks to see if the rule was followed. She generates the following truth table:

Get dirty?   Take a bath?   Follow rule?   Comment
No           No             Yes            Son didn't get dirty, so didn't need to take a bath. Give him a cookie.
No           Yes            Yes            Son didn't need to take a bath, but wanted to anyway. Extra clean! Give him a cookie.
Yes          No             No             Son didn't follow the rule. No cookie and no TV tonight.
Yes          Yes            Yes            He took a bath to clean up after getting dirty. Give him a cookie.

The mother has set the rule ahead of time. She knows what the relationship between dirt and baths are, and she wants to make sure that the rule is followed.

When we work with boolean logic, we are like the mother: we know the operators ahead of time, and we want to work with the statement in that form. Perhaps we want to transform the statement into a different form (as was the original question, he or she wanted to know if two statements are equivalent). In computer programming we often want to plug a set of variables into the statement and see if the entire statement evaluates to true or false.

It's not a matter of knowing whether implies applies - it wouldn't have been written there if it shouldn't be. Truth tables are not about determining whether a rule applies, they are about determining whether a rule was adhered to.

I like to use the example: If it is raining, then it is cloudy.

Raining => Cloudy

Contrary to what many beginners might think, this in no way suggests that rain causes cloudiness, or that cloudiness causes rain. (EDIT: It means only that, at the moment, it is not both raining and not cloudy. See my recent blog posting on material implication here. There I develop, among other things, a rationale for the usual "definition" for material implication. The reader will require some familiarity with basic methods of proof, e.g. direct proof and proof by contradiction.)

~[Raining & ~Cloudy]

Judging from the truth tables, it is possible to infer the value of a=>b only for a=1 and b=0. In this case the value of a=>b is 0. For the rest of values (a,b), the value of a=>b is undefined: both (a=>b)=0 ("a doesn't imply b") and (a=>b)=1 ("a implies b") are possible:

a b a=>b comment
0 0  ?   it is not possible to infer whether a implies b because a=0
0 1  ?   --"--
1 0  0   b is 0 when a is 1, so it is possible to conclude
         that a does not imply b
1 1  ?   whether a implies b is undefined because it is not known
         whether b can be 0 when a=1 .

For a to imply b it is necessary and sufficient that b=1 always when a=1, so that there is no counterexample when a=1 and b=0. For the rows 1, 2 and 4 in the truth table it is not known whether there is counterexample: these rows do not contradict to (a=>b)=1, but they also do not prove (a=>b)=1 . In contrast, row 3 immediately disproves (a=>b)=1 because it provides a counterexample when a=1 and b=0. I guess I may shock some readers with these explanations, but it seems there are severe errors somewhere in the basics of the logic we are taught, and that is one of the reasons for such problems as Boolean Satisfiability being not solved yet.

The best contribution on this question is given by Serge Rogatch.

Boolean logic applies only where the result of quantifying(or evaluation) is either true or false and the relationship between boolean logic propositions is based on this fact.

So there must exist a relationship or connection between the propositions.

In higher order logic, the relationship is not just a case of on/off, 1/0 or +voltage/-voltage, the evaluation of a worded proposition is more complex. If no relationship exists between the worded propositions, then implication for worded propositions is not equivalent to boolean logic propositions.

While the implication truth table always yields correct results for binary propositions, this is not the case with worded propositions which may not be related in any way at all.

~A V B truth table:

A B Result/Evaluation

1 1 1

1 0 0

0 1 1

0 0 1

Worded proposition A: The moon is made of sour cream.
Worded proposition B: Tomorrow I will win the lotto.

A B Result/Evaluation

1 ? ?

As you can see, in this case, you can't even determine the state of B which will decide the result. Does this make sense now?

In this truth table, proposition ~A always evaluates to 1, therefore, the last two rows don't apply. However, the last two rows always apply in boolean logic.

http://thenewcalculus.weebly.com

Here's a compact statement:

Suppose we have two statements, A and B, each of which could either be true or false. Without any further information, there are 2 x 2 = 4 possibilities: "A and not B", "B and not A", "neither A nor B", and "both A and B".

Now impose the additional restriction that "if A, then also B". After imposing this restriction, the expression "x -> y", where -> is the "implication" operator, denotes whether it is still possible for A == x and B == y. The only outcome that is no longer possible after this additional restriction is A == 1 and B == 0, since that contradicts the restriction itself. Hence, we have 1 -> 0 is zero, and every other pair is 1.