Homework 2: Due, Tuesday, September 21, at the beginning of lecture.

Good Practice Problems
Chapter 1.3: 5, 13, 31, 39, 57
Chapter 1.4: 5, 6, 17, 39 

Problems to turn in:

1. Prove or disprove whether the following argument form is valid.
(to prove an argument valid, show how to use propositional
equivalences, and rules of inference to produce the conclusion given
the hypothesis.  To prove an argument invalid, find a way to make all
the hypothesis true, but the conclusion false.).  For this problem,
you must include EVERY step in the logical deduction.

(a) p v ~q
    ~q
    -------
     ~p


  ok.  Let's start. by writing out the hypotheses:
  
  (1) p v ~q
  (2) ~q

  let's see if we can prove this form of
  argument invalid.  To do that, we need to make sure that the
  hypotheses are true:
  "p v ~q" is true
  "~q"      is true  
    and the conclusion
  "~p" is false:

  if we set p = "true"
  and q = false, 
  then the three above conditions are true.


(b) p --> q
    ~q v r
    ~r
    -------
    ~p


(1) p --> q
(2) ~q v r
(3) ~r

(4) q --> r,    (2) implies rule
(5) p --> r,    (1,4) hypothetical syllogism
(6) ~p          (5,3) Modus Tollens  


(c) 1. p --> (q v ~r)
    2. s --> r
    3. p
    4. ~q
    -------
    ~s


(5) q v ~r,   1,3, Modus Ponens.
(6) ~r,       4,5  disjunctive syllogism.
(7) ~s        2,6, Modus Tolens



(d) 1. (exists y) ~q(y)
    2. (forall x) p(x) --> q(x)
    ---------------------------
    exists z, ~p(z)

(3) ~q(a),   for some a,  1, existential instantiation
(4) p(a) --> q(a),        2, universal generalization 
(5) ~p(a),                3,4, Modus Ponens
(6) exists x, ~p(x)       5, existential generalization



2. A real number x is an upper bound of a set S of real numbers if x
is greater than or equal to every number of S.

(a) Use quantifiers to express the fact that x is an upper bound of S.
That is, define the proposition UB(x) that is true when x is an upper
bound of S.


define s(x) to be true if x is an element of S.

UB(x):  forall y, ( (y in S) --> ( x >= y) )


A real number x is called the least upper bound of a set S of real
numbers if x is an upper bound of S, and x is less that or equal to
every upper bound of S

(b) Use quantifiers to express the fact that x is a least upper bound of S.


LUB(x):  forall y, ( UB(y) --> ( x <= y) )


(c) Define a set S of real numbers which has a least upper bound that
is not in the set S.


The set of real numbers between zero and one, but NOT including 1, 
often written as: [0,1) 
1 is the least upper bound, but is not in the set. 


4. Let P(x) denote that x is a politician, and Q(x, y) denote that x
quotes y where the universe of discourse for x and y are all
people. Express each of the below statements using these predicates,
quantifiers, and logical connectives.

(a). Every politician quotes someone, but no politician is quoted by
every one of the politicians that she quotes.


jeepers, this has many clauses.  lets' do it bit by bit:

Every politician quotes someone,

forall(x) (P(x) --> exists(y) Q(x,y))

but no politician is quoted by every one of the politicians that she
quotes.

  "every one of the politicians that she quotes."
  a statement true about politicians X that a politicial C quotes
    P(x) ^ Q(c,x)

  "no politician with some properties":
    ~(exists) c, P(c) ^ "some properties"

putting this together we get:

"but no politician is quoted by every one of the politicians that she
quotes."
~(exists) c, ((P(c) ^ Q(c,x)) --> (P(x) ^ Q(x,c))

and the whole shebang:

(forall(x) (P(x) --> exists(y) Q(x,y))) ^ 
           (~(exists) c, P(c) ^ Q(c,x) --> P(x) ^ Q(x,c))


(b). If a politician quotes any politician that does not quote him, he
quotes every politician that quotes no politician.


let's break this up again:

"a politician that quotes no politician":

P(x) ^ (forall)y (Q(x,y) -->  ~P(y))

"a politician who quotes every politician that quotes no politician."

P(z) ^ (forall x) ((P(x) ^ (forall)y (Q(x,y) -->  ~P(y))) --> Q(z,x))

"a politician that does not quite him":

P(a) ^ ~Q(a,him)

"a politician quotes any politician that does not quote him"

exists(a) Q(him,a) ^ P(a) ^ ~Q(a,him)

"If a politician quotes any politician that does not quote him, he
quotes every politician that quotes no politician."

P(him) ^ exists(a) (Q(him,a) ^ P(a) ^ ~Q(a,him)) -->
(forall x) ((P(x) ^ (forall)y (Q(x,y) -->  ~P(y))) --> Q(him,x)))

But this english statement is really talking about all politicians,
the "him" is a pronoun that means "all" (in this case), so:

(forall z) 
 P(z) ^ exists(a) Q(z,a) ^ P(a) ^ ~P(a,z) -->
(P(z) ^ (forall x) ((P(x) ^ (forall)y (Q(x,y) -->  ~P(y))) --> Q(z,x)))

 which we could factor, a little, if we want, to be:

(forall z) p(z) --> 
 [(exists)a  Q(him,a) ^ P(a) ^ ~Q(a,him) -->
  (forall)x ((P(x) ^ (forall)y (Q(x,y) -->  ~P(y))) --> Q(z,x)))]