Massachusetts Institute of Technology Handout 6 6.042J/18.062J: Mathematics for Computer Science September 14, 2000 Professors Nancy Lynch and Shlomi Dolev

Problem Set 1 Solutions

Problem 1 Propositional logic

(a) Rosen §1.1, Exercise 24 (f).

Solution:

p q r p ∧ q ¬r (p ∧ q) ∨ ¬r)
t t t t  f  t
t t f  t  t  t
t f t  f  f  f
t f f  f  t  t
f t t  f  f  f
f t f  f  t  t
f f t  f  f  f
f f f  f  t  t

(b) Rosen §1.2, Exercise 8 (c),(d).

Solution: We construct a truth table for each implication and see that the relevant column contains only t’s

[p ∧ (p → q)] → q

p q (p → q) [p ∧ (p → q)] [p ∧ (p → q)] → q
t t  t  t  t
t f  f  f  t
f t  t  f  t
f f  t  f  t

[(p ∨ q) ∧ (p → r) ∧ (q → r)] → r

p q r (p ∨ q) (p → r) (q → r) [(p ∨ q) ∧ (p → r) ∧ (q → r)] [(p ∨ q) ∧ (p → r) ∧ (q → r)] → r
t t t  t  t  t  t  t
t t f  t  f  f  f  t
t f t  t  t  t  t  t
t f f  t  f  t  f  t
f t t  t  t  t  t  t
f t f  t  t  f  f  t
f f t  f  t  t  f  t
f f f  f  t  t  f  t

(c) Velleman §1.5, Exercise 6.

Solution: P → (Q → R) P → (¬Q ∨ R) [equivalence] ¬P ∨ (¬Q ∨ R) [equivalence] ¬P ∨ ¬Q ∨ R [associative and commutative laws]

Q → (P → R) Q → (¬P ∨ R) [equivalence] ¬Q ∨ (¬P ∨ R) [equivalence] ¬P ∨ ¬Q ∨ R [associative and commutative laws]

(P → Q) ∧ (P → R) (¬P ∨ Q) ∧ (¬P ∨ R) [equivalence]

(P ∧ Q) → R ¬(P ∧ Q) → R [equivalence] ¬P ∨ ¬Q ∨ R [De Morgan’s law]

P → (Q ∧ R) ¬P ∨ (Q ∧ R) [equivalence] (¬P ∨ Q) ∧ (¬P ∨ R) [distributive law]

For the values P = true, Q = false, R = false, ¬P ∨ ¬Q ∨ R evaluates to true (¬P ∨ Q) ∧ (¬P ∨ R) evaluates to false thus, these two expressions are not equivalent.

Thus, Parts (a), (b) and (d) are equivalent. Parts (c) and (e) are equivalent.

Problem 2 Set theory

(a) Rosen §1.4, Exercise 16 (a),(b),(c),(d).

Solution: ∅ No. The power set of every set includes at least the empty set, so the power set cannot be empty. Thus ∅ is not the power set of any set.

{∅, {a}} Yes. This is the power set of {a}.

{∅, {a}, {∅, a}} No. This set has three elements. Since 3 is not a power of 2, this set cannot be the power set of any set.

{∅, {a}, {b}, {a, b}} Yes. This is the power set of {a, b}.

(b) Rosen §1.5, Exercise 12(c).

Solution: Let x ∈ (A − B) − C. Then x is in A − B but not in C. Since x ∈ A − B, we know that x ∈ A (we also know that x ∉ B, but that won’t be used here). Since we have established that x ∈ A but x ∉ C, we have proved that x ∈ A − C. Thus, (A − B) − C ⊆ A − C.

(c) Rosen §1.5, Exercise 18 (a),(b),(c).

Solution:

(d) Rosen §1.5, Exercise 36.

Solution: ⋃_{i=1}^{n} A_{i} = {1, 2, 3, ...}

⋂_{i=1}^{n} A_{i} = {n, n + 1, n + 2, ...}

Problem 3 Proofs or fallacies?

Determine whether each of the following arguments is valid. If it is not valid, then explain what the error is. (You may want to use the rules of inference and fallacies from Rosen in your solutions.)

(a) Theorem: if n^{3} > 1, then n > 1. Proof: If n is a real number such that n > 1, then n^{3} > 1. Suppose that n^{3} > 1, then n > 1.

Solution: Not valid. Given the propositions p: n > 1 q: n^{3} > 1 the argument says that p → q, so if q then p. This is the fallacy of affirming the conclusion.

(b) Theorem: The number log_{2} 3 is irrational. Proof: A number is irrational if it is not the ratio of two integers. Therefore, since log_{2} 3 cannot be written in the form a/b where a and b are integers, it is irrational.

Solution: Not valid. Fallacy: Circular reasoning. The statement following the “therefore” is precisely the one we want to prove. And it doesn’t follow from anything before, so the therefore has no justification for being there.

(c) Theorem: If n^{2} > 9 then, n > 3. Proof: Because if n is a real number with n > 3, then n^{2} > 9.

Solution: Not valid. Given the propositions p: n > 3 q: n^{2} > 9 the argument says that p → q, so if q then p. Again, this is the fallacy of affirming the conclusion.

Problem 4 Proofs Velleman §3.1, Exercise 6.

We prove the contrapositive i.e. if x = 8, \frac{\sqrt[3]{x}+5}{x^{2}+6} ≠ \frac{1}{x}.

\frac{\sqrt[3]{8} + 5}{8^{2} + 6} = \frac{1}{10} ≠ \frac{1}{x} = \frac{1}{8}

As we have shown the contrapositive to be true, the original hypothesis, that if \frac{\sqrt[3]{x}+5}{x^{2}+6} = \frac{1}{x} then x ≠ 8, is true. This is an example of an indirect proof.

Problem 5 And more proofs Rosen §3.1, Exercise 46.

Solution: Proof by cases:

1. m = 1 As n is an integer, ⌊⌊x⌋ + n⌋ = ⌊⌊x⌋⌋ + n = ⌊x⌋ + n = ⌊x + n⌋ The hypothesis is proved to be true when m = 1.

2. m > 1 Proof by contradiction: Assume that the hypothesis is false, that is ⌊\frac{⌊x⌋+n}{m}⌋ ≠ ⌊\frac{x+n}{m}⌋. Let x = z + y, where z is an integer and 0 ⩽ y < 1. Also, let k = ⌊\frac{⌊x⌋+n}{m}⌋.

k = ⌊\frac{⌊x⌋ + n}{m}⌋ ≠ ⌊\frac{x + n}{m}⌋

k = ⌊\frac{z + n}{m}⌋ ≠ ⌊\frac{z + y + n}{m}⌋

As m is an integer and is greater than 1, it follows that

\frac{z + n}{m} ⩽ k + \frac{m − 1}{m}

Handout 6: Problem Set 1 Solutions 5

and

\frac{z + n + y}{m} ⩾ k + \frac{m}{m}

Thus,

\frac{y}{m} ⩾ \frac{1}{m}

y ⩾ 1

This is a contradiction, as we defined 0 ⩽ y < 1. Thus, our original hypothesis, ⌊\frac{⌊x⌋+n}{m}⌋ = ⌊\frac{x+n}{m}⌋, is true when m > 1.

As we have proved that the hypothesis is true in both cases, the hypothesis is always true.