Computer Science A67

Homework Assignment # 3

Handing in and marking

For this exercise, you need to submit your solutions on crowdmark. Your solutions will be marked with respect to correctness, clarity, brevity, and readability. This assignment counts for 6% of the course grade. Only a subset of questions will be selected for grading.

Please, note that the course Silent Running Policy, Special Consideration and Accommodations Policy, and Academic Integrity apply to this assignment. These policies are explained on the course website.

In all questions in this assignment, if you prove a result (say, in Part (a)), then you can use it in your subsequent proofs (say, in Parts (b) and (c)).

Question 1.                      [20 marks]

Prove each of the following statements, using the proof techniques we studied in class (including all equivalence laws and inference rules):

(a) There are no integer solutions for 2x2 + 5y2 = 14.

(b) If n = abc where a, b, and c are positive integers, then a ≤ 3√n, b ≤ 3√n, or c ≤ 3√n.

(c) At least one of the real numbers a1, a2, . . . , an is greater than or equal to the average of these numbers.

(d) The statements “x is irrational”, “3x+ 2 is irrational”, and “x/2 is irrational”are equivalent for any real number x.

Question 2.                       [30 marks]

Use Simple Induction and other proof techniques we studied in class (including all equivalence laws and inference rules), to prove each of the following statements:

(a) 2 − 2 · 7 + 2 · 7 2 − · · · + 2 · (−7)n = (1 − (−7)n+1)/4 for positive integers n.

(b) 1 · 2 + 2 · 3 + · · · + n(n + 1) = n(n + 1)(n + 2)/3 for positive integers n.

(c) n 2 − 7n + 12 is non-negative whenever n is an integer and n ≥ 3.

(d) For any integer n, if 10n! > nn, then n < 5.

(e) For any positive integer n, if A1, A2, . . . An and B1, B2, . . . Bn are sets such that Aj ⊆ Bj for j = 1, 2, . . . , n, then (A1 ∪ A2 ∪ · · · ∪ An) ⊆ (B1 ∪ B2 ∪ · · · ∪ Bn).

Question 3.                       [30 marks]

For each of the following pairs of expressions, either prove they are equivalent by using any of the proof techniques we studied in class (including all equivalence laws and inference rules), or prove they are not equivalent by providing a counterexample world.

(a) (∃x, P(x)) → (∃x, Q(x)) and ∃x, P(x) → Q(x)

(b) ∀x,(P(x) ∨ Q(y)) and (∀x, P(x)) ∨ Q(y) (note that y is a free variable here)

(c) ∀x,(P(x) ∧ Q(y)) and (∀x, P(x)) ∧ Q(y) (note that y is a free variable here)

(d) ∀x,(∃y, P(x, y)) → Q(x) and ∀x∀y, P(x, y) → Q(x)

(e) ∀x, Q(x) → ∃y, P(x, y) and ∀x∀y, Q(x) → P(x, y)

(f) ∀x, P(x) → (∀y, Q(x, y) → ∀z, R(x, y, z)) and ∀x, y, z,(P(x) ∧ Q(x, y)) → R(x, y, z)

(g) ∃x∀y,(P(y) ↔ (x = y)) and ∃x,(P(x) ∧ ∀y, P(y) → (x = y))

(h) ∃x∀y,(P(y) ↔ (x = y)) and (∃x, P(x)) ∧ (∀x∀y,(P(x) ∧ P(y)) → (x = y)).

Question 4.                         [20 marks]

Let A and B be sets in the universe U.

1. Let A denote the set complement of A, i.e., A = {x | x /∈ A}.

2. Let ∅ denote the empty set, i.e., A = ∅ if and only if ¬∃x, x ∈ A.

3. Recall that we say that A is a subset of B, denoted A ⊆ B, if and only if ∀x, x ∈ A → x ∈ B.

4. You can use the fact that any set A is a subset of U, i.e., A ⊆ U.

5. You can use the fact that A = B if and only if (A ⊆ B) ∧ (B ⊆ A).

Prove or disprove each of the following statements, using only the definitions of set operations and the proof techniques we studied in class (including all equivalence laws and inference rules).

(a) (A ∪ B = U) → (∀x ∈ U, x ∈ A ∨ x ∈ B)

(b) (A ⊆ B) ↔ (A ∪ B = U)

(c) (A ⊆ B) ↔ (B ⊆ A)

(d) ((A ∪ B = U) ∧ (A ∩ B = ∅)) → (∀x ∈ U,(x ∈ A) ↔ (x /∈ B))