Homework 3: Due, Tuesday, September 27, at the beginning of lecture.

1) Consider the following english arguments.  Define
   propositions/predicates and translate these arguments into logic,
   then prove or disprove whether the form of the argument is valid.

   a) All Computer Science majors are people.
      Some computer science majors are logical thinkers
      -------------------------------------------------
      Some people are logical thinkers.

      (You can assume that you are quantifying over "people").
 
Let's define:  C(x) = x is a computer science major,
               P(x) = x is a person,
               L(x) = x is a logical thinker,

then our argument can be written as:

(forall x) C(x) --> P(x)
(exists x) C(x) ^ L(x)
---------------------
(exists y) P(y) ^ L(y)


1. (forall x) C(x) --> P(x)   premise
2. (exists x) C(x) ^ L(x)     premise

3. C(a) ^ L(a)                2, existential instantiation
4. C(a) --> P(a)              1, universal instantiation
5. C(a)                       3, simplification
6. P(a)                       4,5, Modus Ponens
7. L(a)                       3, simplification
8. P(a) ^ L(a)                6,7 addition
9. (exists y) P(y) ^ L(y)     8 existential generalization
 


   b) If I like mathematics then I will study.
      Either i don't study or I pass mathematics
      If I don't pass mathematics, then I don't graduate.
      --------------------------------------------------
      If I graduate, then I like mathamatics.
 
Let L = I like mathematics
    S = I will study
    P = I pass mathematics
    G = I will graduate

Then the argument can be written:

 L --> S
~S  v  P
~P --> ~G
----------
G --> L 

If we set:
  L = F,
  S = T
  P = T
  G = T

then we get that all the premises are true:
 
L --> S   is  F --> T, which is true
~S v P    is  F  v T, which is true
~P --> ~G is  F --> F, which is true,

but the conclusion
G --> L   is T --> F, which is false.

So this argument is not valid.
 

2) prove the following form of argument is valid
1.   a v b
2.   a --> p
3.   b --> p
 ---------
   p
 
4. ~a v p               2. implies rule
5. (a v b) ^ (~a v p)   4,1. addition
6. b v p                5. resolution
7. ~b v p               3. implies rule
8. (b v p) ^ (~b v p)   7,6, addition
8. p ^ (b v ~b)         7,6, distributive
9. p ^ (T)              8. idempotent?
10. p                   9. identity                
 

3) Prove (for all integers) a,b,c,   (a | b  and b | c ) --> a | (b+c)
 
  b = ak,   for some integer k
  c = bj,   for some integer j
  c = akj,  
  b + c = ak + akj = a(k + kj)
  b + c = a(integer)
  a | b+c.
 

4) Prove (for all integers) n, n mod 3 == 2 --> n is not a perfect square
 
indirect proof.
Suppose n is a perfect square, prove the ~(n mod 3 == 2).
 n  = j^2,  for some integer j.
 Try 3 cases, 
   Case 1: j = 3k
           n = j^2 = (3k)^2 = 9k^2 = 3(3k^2), so n mod 3 = 0
   Case 2: j = 3k+1
           n = j^2 = (3k+1)^2 = 9k^2+6k+1 = 3(3k^2+2k)+1, so n mod 3 = 1
   Case 3: j = 3k+2
           n = j^2 = (3k+2)^2 = 9k^2+12k+4 = 3(3k^2 + 4k + 1)+ 1, so n mod 3 = 1
 In all three cases, n mod 3 is never 2.