CPSC210Foundations of Computer Science

Fall 2010

Homework 1

Due: Start of the class, Friday, October 8th, 2010

It is required that you show your work. When doing proofs, each step must use only one law, rule of inference, or equivalence. The law, rule, or equivalence used on each step must be stated.

1. (24 points, 8 points each) Prove that each of the statements is a tautology using a series of logical equivalences. You cannot use a truth table. Use Example 7 on page 26 as a model. In addition, you may only use the equivalences listed on page 6 of the lecture notes. You may not use the additional equivalences listed in Tables 7 and 8 on page 25 of the textbook.

a. [p  (q q)] p

b. [(p  q)  (p  r)  (q  r)]  r

c. [p (rq)]  [(pr) q]

2. (10 points, 2 points each) Textbook(p. 59): Exercise 8 in section 1.4

3. (18 points) For this propositional function:

C(x, y): Person x called person y.

The domain is a set of people. Translate the following English statements into predicates and translate predicates into English.

  1. Every person called at least one other person (4 points).
  2. There is exactly one person who called everyone else(4 points).
  3. xy(xy C(x, y)  C(y, x)) (5 points).
  4. xy(C(x, y)  ((w(C(x, w) w = y)  (z(C(z, y) z = x)) (5 points).

4. (8 points) Prove this is a valid argument using rules of inference and logical equivalences.

(p  q)

z s

z  r

(p q)  s

 r

5. (30 points, 10 points each) Textbook (p.73): Exercise 14 (parts a, b, and c only) in section 1.5. For each part, define propositional functions. Then, write the premises and conclusion using the propositional functions you defined. Finally, write a proof illustrating how the premises imply the conclusion.

6. (10 points) Show, by giving a proof by contradiction, that if 40 coins are distributed among nine bags such that each bag contains at least one coin, at least two bags contain the same number of coins.

1