From jacobson@math-cs.cns.uni.edu Mon Sep  8 15:01:15 2003
Date: Mon, 08 Sep 2003 14:59:33 -0500 (CDT)
From: Mark Jacobson <jacobson@math-cs.cns.uni.edu>
To: 810-080-01@uni.edu, 810-080-03@uni.edu
Subject: [810-080-01] My client is innocent proof...

Hi 080 students,

   We will get started on section 1.3 of the textbook on Wednesday.
Section 1.3 will NOT be on the quiz on Friday, but you will probably
find that section 1.3 is good review of material from 1.1 and 1.2,
as it builds on those.

   Section 1.3 switches from Propositional Logic to Predicate Logic.

   We will see statements that involve variables, like:

   For every x, E(x) v O(x)              Domain of x is Integers

   There exists n such that for every p, Z(n, p)  Domain of x is Integers

          E(x) means x is EVEN
          O(x) means x is ODD

   There does NOT exist an x such that E(x) ^ O(x) is true.

   For all x, ( E(x) and O(x) )'

   In the proof that my client is innocent from page 33 exercise #46,
   the question arose in the 1 p.m. class as to why you could
   not go directly from:

   4.  O ----> (K ^ H)     hyp
   5.  H'                  hyp

       to

   6.  O'                  5, 6, mt

   Modus tollens (mt) would require that you know (K ^ H)'

   Make the proof as follows would be okay to do.

   1.  G ---> K               hyp
   2.  K' v J                 hyp
   3.  O' ---> J'             hyp
   4.  O ----> (K ^ H)        hyp   #4 and #5 lead to #9, but NOT directly
   5.  H'                     hyp                     #9 is not O, i.e. O'

   6.  O' v (K ^ H)           4, imp
   7.  (O' v K) ^ (O' v H)    6, dist   (distributive law, dist v over ^)
   8.  O' v H                 7, sim
   9.  O'                     5, 8, ds  (disjunctive syllogism)

  10.  J'                     3, 9, mp
  11.  K'                     2, 10, ds    (remove 2 incorrect lifeline
                                            from I Wanna Be a Millionaire)
  12.  G'                     1, 11, mt  (modus tollens = mt = emp ty gas tank)
                                                                m  t
  Proven!

  We could make a new Theorem or Rule of Inference to shorten up the
  above proof:

  Whenever an antecendent implied a conjuction the rule of inference
  antcon1 or the equivalence antcon2 could be applied.
  -------                    -------

antcon2 equivalence:

  A ----> (B ^ C) is equivalent to (A ---> B) and (A ---> C)

  Proof part #1 for ----> :               The conjunction is the GOAL

  1. A --> (B ^ C)           hyp
  2. A' v (B ^ C)            1, imp
  3. (A' v B) ^ (A' v C)     2, dist
  4. (A --> B) ^ (A --> C)   3, imp            PROVEN!

  Proof part #2 for <---- :                A --> (B ^ C) is the GOAL

  1. (A --> B) ^ (A --> C)          hyp
  2. (A' v B)  ^ (A' v C)           1, imp
  3. A' v (B ^ C)                   2, dist
  4. A ---> (B ^ C)                 3, imp      PROVEN!

Proving the RULE OF INFERENCE antcon1:

  1. A ---> (B ^ C)          hyp
  2. (A --> B) ^ (A --> C)   1, antcon2
  3. A --> B                 2, sim
  4. A --> C                 2, sim

  Thus the rule of inference is:

  A ---> (B ^ C) can be used to derive A --> B, A --> C

                 now by just using antcon1 as the justification.


   1.  G ---> K               hyp
   2.  K' v J                 hyp
   3.  O' ---> J'             hyp
   4.  O ----> (K ^ H)        hyp   #4 and #5 lead to #9, but NOT directly
   5.  H'                     hyp                     #9 is not O, i.e. O'

   6.  O ---> H               4, antcon1
   7.  O'                     5, 6, mt
   8.  J'                     3, 7, mp
   9.  K'                     2, 8, ds
  10.  G'                     1, 9, mt

  Note that antcon1 THEOREM or rule of inference was used as a building
  block and as a new rule to make the proof shorter.

  Mark