Mathematical LogicDate: 02/09/2001 at 21:48:25 From: ONG YEN CHIN Subject: Logic Given ~c <-> (a n b) and d <-> [(a n ~b) u (b n ~a)] where ~ = not <-> = if and only if n = and u = or how do I prove this? (c n ~d)<->(~a n ~b) I would appreciate your help very much. Thanks. Kind regards, Yen Chin Date: 02/13/2001 at 20:05:13 From: Doctor Achilles Subject: Re: Logic Hi Yen Chin, Thanks for writing Dr. Math. Mathematical logic is one of my specialties, so I'll give your problem a try. One thing I should say before I start: there is more than one set of rules for derivations in mathematical logic, so I will show you how to do your derivation using the rules I've learned. These are the rules I've learned (they're pretty standard, so you can probably skip to the derivation below): A (assumption): I will introduce assumptions with { and close them off with }. Once a { has been closed by a }, anything between the squiggly brackets is {off limits} for future steps. However, you can take things down from above a { as long as it hasn't been closed off. Note: Each operation (and, or, not, if-then, and if-and-only-if) has an "introduction" rule and an "elimination" rule. The first states that if you have proved certain facts about p and q, then you have shown that the operation holds for p and q (or just p, in the case of not). The second states that if you have proved the operation holds for p and q, then you can derive certain other facts about p and q. nI (n intro): p on one line and q on another gives (p n q). nE (n elim): (p n q) on one line gives p (or q if you want it instead). uI (u intro): p on one line gives (p u q) where q is anything. uE (u elim): Start with (p u q). Assume p, derive r. Assume q, derive r. This gives (p u q) -> r. ->I: Assume p, derive q. This gives (p -> q). ->E: (p -> q) on one line and p on another gives q. <->I: (p -> q) and (q -> p) gives (p <-> q). <->E: (p <-> q) and p gives q. (p <-> q) and q gives p. ~I: Assume p, derive a contradiction (e.g. (q n ~q)). This gives ~p. ~E: ~~p gives p. DeMorgan's rule: ~(p n q) <-> (~p u ~q) AND ~(p u q) <-> (~p n ~q) Disjunctive syllogism (DS): ((p u q) n ~p) -> q DeMorgan's rule and DS can be derived from the other rules, but they are useful shotcuts. One more note: the first two assumptions here are not going to be closed off since we're trying to show that (c n ~d)<->(~a n ~b) is true given those assumptions. { 1) ~c <-> (a n b) (A, given by the problem) { 2) d <-> [(a n ~b) u (b n ~a)] (A, given by the problem) { 3) (c n ~d) (A, for ->I) 4) c (nE on line 3) { 5) (a n b) (A, for ~I) 6) ~c (<->E on lines 1 and 5) 7) c (repetition of line 4) 8) (c n ~c) (nI on 6-7: contradiction) } (close off A at line 5) 9) ~(a n b) (~I on 5-8) 10) (~a u ~b) (DeMorgan's on 9) 11) ~d (nE on from line 3) { 12) [(a n ~b) u (b n ~a)] (A, for contradiciton) 13) d (<->E on lines 2 and 12) 14) ~d (repetition of line 11) 15) (d n ~d) (nI on 13-14: contradiction) } (closes off A at line 12) 16) ~[(a n ~b) u (b n ~a)] (~I on 12-15) 17) [~(a n ~b) n ~(b n ~a)] (DeMorgan's on 16) 18) ~(a n ~b) (nE on 17) 19) ~(b n ~a) (nE on 17) 20) (~a u b) (DeM on 18) 21) (~b u a) (DeM on 19) 22) (~a u ~b) (Rep of 10) { 23) a (A for ~I) 24) b (DS on 20) 25) ~b (DS on 22) 26) (b n ~b) (nI on 24-25: contradiction) } (closes off A on 23) 27) ~a (~I on 23-26) { 28) b (A for ~I) 29) a (DS on 21) 30) ~a (DS on 22) 31) (a n ~a) (nI on 29-30: contradiction) } (closes off A on 28) 32) ~b (~I on 28-31) 33) ~a (Rep of 27) 34) (~a n ~b) (nI on 32-33) } (closes off A on 3) 35) (c n ~d) -> (~a n ~b) (->I on 3-34) Phew! We're halfway there (the next half is much shorter). Here's a start for it: { 36) (~a n ~b) (A for ->) 37) ~c <-> (a n b) (Rep of 1) 38) d <-> [(a n ~b) u (b n ~a)] (Rep of 2) From here you want to derive c and ~d. Try assuming ~c and getting a contradiction. Once you do that, assume d and get a contradiction. Once you've done all that put c and ~d together and close off the assumption at 36. That should give you (~a n ~b) -> (c n ~d). Then you just have to put that together with line 35 using the rule <->I. Hope this helps. If you want to talk about this or other math problems some more, please write back. - Doctor Achilles, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/