Happenings – 2010 July 17

My mathematical life continues to be extremely narrowly focused; I’m doing logic.

I hope that the next post will summarize syllogistic reasoning… I think I can pretty clearly see the light at the end of the tunnel for this post. Of course, my favorite version of Murphy’s Law is: the light at the end of the tunnel is the headlight of an oncoming train.

Over lunch I mentioned the following puzzle to a friend, and he asked me to e-mail it to him so he could work on it. This comes from Brown’s “Boolean Reasoning”, p. 132 and pp. 134-135. I really like this puzzle.

1. if Alfred studies, then he gets good grades.
2. if Alfred doesn’t study, then he enjoys college.
3. if Alfred doesn’t receive good grades, then he doesn’t enjoy college.

What’s that all mean?

If we use the symbols

E: he enjoys college
S: he studies
G: he gets good grades.

then

1. S => G
2. S’ => E
3. G’ => E’

equivalently (recalling that S => G is equivalent to “we never have G false and S true”, and we use the symbol G’ for not-G, etc.)

SG’ = 0
S’E’ = 0
G’E = 0

and that set of equations is equivalent to the single equation (and use e because E is reserved):

e G’+S G’+ e’ S’== 0

(It is crucial that I have equations saying that some Boolean functions are equal to 0 (false).)

Now I find a minimal equivalent SOP (sum of products) formula for the left hand side…. To do this, I convert my plus and times to Or and And…

(e\land \neg G)\lor (S\land \neg G)\lor (\neg e\land \neg S)

and let Mathematica® find me a minimal form:

(\neg e\land \neg S)\lor \neg G

… and use that form to rewrite my single equation as:

G’+e’ S’==0

Whoa! That single equation is equivalent to the pair of equations

G’ = 0
e’S’ = 0.

The first equation says that it is false that he gets bad grades: hey, we know that Alfred gets good grades!

The second equation says that e’S’ (~e \land ~S) is false, i.e. that e + S (e \lor S\ ) is true: we conclude that either Alfred enjoys college or Alfred studies, and possibly both.

(Yes, I am gleefully switching among Mathematica’s…

(\neg e\land \neg S)

the arithmetic-looking e’S’…

and my typed logical form ~e \land\ ~S.)

To put that another way, there are 3 possibilities:

  1. he studies, but does not enjoy college, and gets good grades;
  2. he enjoys college, but does not study, and gets good grades;
  3. he studies, enjoys college, and gets good grades.

We cannot tell which of the three actually happens, but that he gets good grades is common to all three.

Once I even ask if he gets good grades, I can verify it easily enough. We have

1. S => G
2. S’ => E
3. G’ => E’

Assume for the moment that he gets bad grades (G’ is true); then (3) says G’ -> E’; the contrapositive, or transposition, of (2) says E’ -> S; and then (1) says S -> G. That is, we have

G’ => E’ => S => G

but G’ and G is a contradiction, so our provisional assumption (that G’ is true) must be false .

It is even easier to show that E’S’ is false. Suppose to the contrary that E’S’ is true… but then each of E’ and S’ is true, and (2) says that E is true — and we have both E’ and E true. Ding. We reject the provisional assumption (that E’S’ is true).

The advantage of the minimal sum-of-products form is that I know I don’t need to look for other possibilities. I haven’t omitted any information; the two equations

G’ = 0
e’S’ = 0

are equivalent to the original three:

SG’ = 0
S’E’ = 0
G’E = 0.

No, I haven’t shown you logical equations before; we’ll take them up down the road.

I really, really like having extracted the information that Alfred gets good grades.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: