DeMorgan's Laws and Distribution Rules

Date: 05/06/2003 at 11:27:06
From: Rosa
Subject: Logic

How can I show the reduction of the following problem without using
tables? 

The > sign stands for "then." 

   (p>q)>(r>(p>q))
   (p then q) then (r then (p then q))

   p>(p>(p>p>p))

I have always seen problems using p>q  or q>p or p>r....but never
all p...p..p..p...

Is this problem the same as [p > p^2 > p3 >p4 >p^5] > c  ?

Date: 05/07/2003 at 09:39:37
From: Doctor Luis
Subject: Re: Logic

Hi Rosa,

p>q means "if p then q," right?

Then, you have

  ~(p>q) = p ^ ~q

That is, ~(p>q) is only true when you have p but not q (i.e. 
hypothetical is true, but conclusion is false).

You can verify this via the following truth table (0 false, 1 true).
__________________________________________
| p | q | p>q | ~(p>q) || p | ~q | p ^ ~q |
|---|---|-----|--------||---|----|--------|
| 0 | 0 |  1  |    0   || 0 |  1 |    0   |
| 0 | 1 |  1  |    0   || 0 |  0 |    0   |
| 1 | 0 |  0  |    1   || 1 |  1 |    1   |
| 1 | 1 |  1  |    0   || 1 |  0 |    0   |
|---|---|-----|--------||---|----|--------|

So,

  ~(p>q) = p ^ ~q

    p>q  = ~(p ^ ~q) = ~p v q

Thus, repeated applications of p>q are merely repeated applications 
of ~p v q. Just use DeMorgan's laws and the distribution rules for 
^ and v.

For example,

  p>(p>p) = ~p v (p>p) = ~p v (~p v p) = ~p v 1 = 1

See? No truth tables here. :)

For p>(p>(p>p>p)), use the logical equivalence that we established:

   p>q  = ~p v q

In this case, p>(p>(p>(p>p))) is equivalent to:

   p>(p>(p>(p>p))) = ~p v (~p v (~p v (~p v p)))

You should be able to simplify this rather easily.

Let us know if you have any more questions.

- Doctor Luis, The Math Forum
  http://mathforum.org/dr.math/