*/Richard-David Simmons
CS241 Assignment 2 - Questions 1,3,4*/


1.a) Given P(x) => x/2 is odd and Q(x) => 4 divides x, for
 (∀x)[P(x) -> Q(x)] on DOI = {2,4,6,8,10,12,14,16,18,20}
  P(x) = {2,6,10,14,18}
  Q(x) = {2,4}

Truth set:
  {2,4,6,10,14,18}

Falsity set:
  {0}

b) If G(x, y) => x < y, for
                    (∀x)(∃y)[G(x,y) v G(y,x)]
  on DOI = Dx x Dy = {{1, 3, 5} x {2, 4, 6}}

Truth set:
  {(1,2), (1,4), (1, 6), (3,2), (3,4), (3,6), (5,2), (5,4), (5,6)}

Falsity set:
  {0}

3. Translate the English statements into a predicate w. Indicate what each predicate stands for.
  a) Everyone laughs, but no one knows why.
  b) Rational numbers are fractions. Some fractions are integers. Therefore, some rational numbers are integers.

a.
  P(x) => x to Laughs
  Q(x) => x Knows Why

  (∀x)[P(x) -> Q(x)']

b.
  R(x) => x Rational numbers
  F(x) => x Fractions
  I(x) => x Integers

  (∀x)[R(x) -> F(x)] ^ (∃x)[F(x) ^ I(x)] -> (∃x)[R(x) ^ I(x)]

4. Prove that the following predicate arguments are valid.
  a.(∃x)[A(x) ^ B(x)] v (∀x)A(x) ^ (∀x)[A(x) -> B(x)] -> (∃x)B(x)
  b.(∀x)[(∃y)P(x,y)]' -> (∀y)(∀x)P(x,y)'

  A.
    1. (∃x)[A(x) ^ B(x)] v (∀x)A(x) ^ (∀x)[A(x) -> B(x)]    Hypo
    2. [A(d) ^ B(d)] v (∀x)A(x) ^ (∀x)[A(x) -> B(x)]        Exist Inst 1
    3. B(d) v (∀x)A(x) ^ (∀x)[A(x) -> B(x)]                 Simp on 2
    4. B(d) v A(d) ^ [A(d) -> B(d)]                         Univ Inst on 3
    5. B(d) v B(d)                                          MP on 4
    6. B(d)                                                 Idemp- Self on 5
    7. (∃x)B(x)                                             Exist Gen on 6


  B.
    1. (∀x)[(∃y)P(x,y)]'                                    Hypo
    2. (∀x)(∀y)P(x,y)'                                      De Morgan's on 1
    3. (∀y)(∀x)P(x,y)'                                      Reordering on 2