DeMorgan's Laws and Distribution RulesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/