Mathematical Logic

Date: 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/