Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search