Homework 2: Due, Tuesday, September 19, 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

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

(c) p --> (q v ~r)
    s --> r
    p
    ~q
    -------
    ~s

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

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.

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.

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

3. 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.

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