Massachusetts Institute of Technology Handout 6 6.042J/18.062J: Mathematics for Computer Science February 13, 1997 Professor David R. Karger

Problem Set 1 Solutions

Problem 1. Let p, q, and r be the following propositions:

p : You are a good water-polo player.
q :  You are a good swimmer.
r : You are in the water-polo team.

Write the propositions using p, q, and r and logical connectives (e.g. ∨, ∧, ¬, ⇒).

(a) To be in the water-polo team, it is sufficient for you to be a good water-polo player. We can rephrase this as “If you are a good water-polo player, you will be in the water-polo team.” p ⇒ r

(b) Being a good swimmer and a good water-polo player is necessary for getting into the water-polo team. r ⇒ p ∧ q

(c) You will get in the water polo team if and only if you are a good swimmer or you are a good water-polo player. r ⇔ p ∨ q

(d) You are neither a good swimmer nor a good water-polo player, yet you are in the water-polo team. ¬p ∧ ¬q ∧ r

Problem 2. Find a compound proposition involving the propositions p, q, and r that is false when exactly two of p, q, and r are false. The compound proposition is true otherwise.

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

which is equivalent to

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

which is also equivalent to

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

Problem 3. Let T (x, y) be the statement “x has proven y.” x ranges over the set of all mathematicians, and y over the set of all theorems.

a) There is a mathematician who has never proven a theorem.

∃x∀y(¬T (x, y))

b) Every mathematician has proven a theorem.

∀x∃yT (x, y)

c) Every theorem has been proven by a mathematician.

∀y∃xT (x, y)

d) There is a mathematician who has proven the Dominated Convergence Theorem and the Bounded Convergence Theorem.

∃x(T (x, Dominated Conv. T hm) ∧ T (x, Bounded Conv. T hm))

e) At least two mathematicians have proven the Hahn-Banach Theorem

∃x_{1}, x_{2}((x_{1} ≠ x_{2}) ∧ T (x_{1}, Hahn − Banach T hm) ∧ T (x_{2}, Hahn − Banach T hm))

Problem 4. Define predicates and formulas.

(a) Let x be in the domain of creatures. F (x): x is a frog D(x): x is a duck P (x): x is poetic

No frogs are poetical  ∀xF (x) → ¬P (x)
Some ducks are unpoetical  ∃xD(x) ∧ ¬P (x)
Thus, some ducks are not frogs ∃xD(x) ∧ ¬F (x)

The entire argument is stated by the formula

(∀xF (x) → ¬P (x)) ∧ (∃xD(x) ∧ ¬P (x)) ⇒ (∃xD(x) ∧ ¬F (x)).

(b) H(x): x is heavy (not light) S(x): x will silence him

Gold is heavy.  H(gold)
Nothing but gold will silence him. ∀x((x = gold) ↔ S(x))
Thus, nothing light will silence him. ∀x(¬H(x) → ¬S(x))

The entire argument is stated by the formula

H(gold) ∧ (∀x((x = gold) ↔ S(x))) ⇒ (∀x(¬H(x) → ¬S(x))).

(c) L(x): x is a lion F (x): x is fierce C(x): x drinks coffee

All lions are fierce.  ∀xL(x) → F (x)
Some lions do not drink coffee.  ∃xL(x) ∧ ¬C(x)
Thus, some creatures that drink coffee are not fierce. ∃xC(x) ∧ ¬F (x)

The entire argument is stated by the formula

(∀xL(x) → F (x)) ∧ (∃xL(x) ∧ ¬C(x)) ⇒ (∃xC(x) ∧ ¬F (x)).

(d) P (x): x is a pillow K(x): x is a poker S(x): x is soft

Some pillows are soft.  ∃xP (x) ∧ S(x)
No pokers are soft.  ∀xK(x) → ¬S(x)
Thus, some pokers are not pillows. ∃xK(x) ∧ ¬P (x)

The entire argument is stated by the formula

(∃xP (x) ∧ S(x)) ∧ (∀xK(x) → ¬S(x)) ⇒ (∃xK(x) ∧ ¬P (x))

Problem 5. Prove the correct arguments from the previous problem and show the incorrect ones are false.

(a) We prove that the argument

(∀xF (x) → ¬P (x)) ∧ (∃xD(x) ∧ ¬P (x)) ⇒ (∃xD(x) ∧ ¬F (x))

is wrong by exibiting a model in which the formula is false. The universe of discourse contains a single element dog which is both a duck and a frog and it is not poetical, i.e., D(dog), F (dog) and ¬P (dog). The formula ∀xF (x) → ¬P (x) is true because ¬P (dog). Also ∃xD(x) ∧ ¬P (x) is true because D(dog) and ¬P (dog). However the conclusion ∃xD(x) ∧ ¬F (x) is false because F (dog), so the argument is not valid.

(b) The argument

H(gold) ∧ (∀x((x = gold) ↔ S(x))) ⇒ (∀x(¬H(x) → ¬S(x)))

is correct. Assume H(gold) and ∀x((x = gold) ↔ S(x)) are true. We prove that ∀x(¬H(x) → ¬S(x)) is false by contradiction: Assume ¬(∀x(¬H(x) → ¬S(x)))

¬(∀x(¬H(x) → ¬S(x)))  assumption
¬(¬∃x¬(¬H(x) → ¬S(x))) ∀xQ(x) ↔ ¬∃x¬Q(x)
∃x¬(¬H(x) → ¬S(x))  Double negation law
∃x¬(H(x) ∨ ¬S(x))  Defintion of →
∃x¬H(x) ∧ S(x)  DeMorgan’s law
∃x¬H(x) ∧ (x = gold)  Logical equivalence

If we split this up into cases, x = gold and x ≠ gold, we find

• case 1: x = gold ¬H(x) ∧ (x = gold) = ¬H(gold) ∧ (gold = gold) = (¬T rue) ∧ T rue = F alse ∧ T rue = F alse

• case 2: x ≠ gold ¬H(x) ∧ (x = gold) = ¬H(x ≠ gold) ∧ (x = gold) =? ∧ F alse = F alse

Since neither case proves true, we know that our original assumption, ¬(∀x(¬H(x) → ¬S(x))), must be untrue, so ∀x(¬H(x) → ¬S(x))).

(c) We prove that the argument

(∀xL(x) → F (x)) ∧ (∃xL(x) ∧ ¬C(x)) ⇒ (∃xC(x) ∧ ¬F (x))

is wrong by exibiting a model in which the formula is false. The universe of discourse contains a single element loffy, which satisfies L(loffy), F (loffy) and ¬C(loffy). We have ∀xL(x) → F (x) and ∃xL(x) ∧ ¬C(x). However ∃xC(x) ∧ ¬F (x) is false, so the argument is not valid.

(d) We prove that the argument

(∃xP (x) ∧ S(x)) ∧ (∀xK(x) → ¬S(x)) ⇒ (∃xK(x) ∧ ¬P (x))

is wrong by exibiting a model in which the formula is false. The universe of discourse contains a single element poft such that P (poft), S(poft) and ¬K(poft). The formula ∃xP (x) ∧ S(x) is true. Also ∀xK(x) → ¬S(x) is true because there exists no x such that K(x). For the same reason the conclusion ∃xK(x) ∧ ¬P (x) is false, proving the the argument is not valid.

Problem 6. (a) Theorem: if n^{2} > 1, then n > 1. Proof: If n is a real number such that n > 1, then n^{2} > 1. Suppose that n^{2} > 1, then n > 1. Given the propositions p: n > 1 and q: n^{2} > 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. Fallacy: Circular reasoning (c) Theorem: If n^{2} ≤ 4 then, n ≤ 2. Proof: Because if n is a real number with

n > 2, then n^{2} > 4.

Given the propositions p: n^{2} ≤ 4 and q: n ≤ 2, the argument says ¬q → ¬p, so p → q. This is the correct argument of disjunctive syllogism.

(d) Theorem If n ≤ 3, then n^{2} ≤ 9. Proof: Because if n is a real number with n > 3, then n^{2} > 9. Given the propositions p: n ≤ 3 and q: n^{2} ≤ 9, the argument says ¬p → ¬q. This is the fallacy of denying the hypothesis.

Problem 7. Prove by contradiction: the square root of an irrational number is irrational.

Let x be an irrational number. Prove that \sqrt{x} is irrational.

Proof by contradiction:

Assume that \sqrt{x} is rational. Then we know that there exist integers p and q such that

\sqrt{x} = \frac{p}{q}.

Squaring both sides we get

x = \frac{p^{2}}{q^{2}}

Since the square of an integer is an integer, p^{2}/q^{2} is a ratio of integers, and therefore a rational number, making x a rational number. This, however, contradicts our original assertion that x is an irrational number, so the theorem must be true.

Problem 8. Prove that ^{3} \sqrt{5} is irrational.

Proof by contradiction:

Assume ^{3} \sqrt{5} is rational. It can then be represented as a fraction in lowest terms, p/q, where p and q are integers:

3 \sqrt{5} = \frac{p}{q}

Rearranging the equation we get

5 = \frac{p^{3}}{q^{3}}

and 5q^{3} = p^{3} Since 5 is prime (has no divisors other than 1 and 5) and p is an integer, we know that p = 5c where c is also an integer. However, using similar reasoning, we find that

5q^{3} = p^{3} = 5^{3}c^{3}

and therefore q^{3} = 5^{2}c^{3}, so q can also be represented as q = 5d where d is an integer. Since both p and q are multiples of 5, the fraction p/q is not in lowest terms, contradicting our hypothesis. Thus ^{3} \sqrt{5} is irrational.

Problem 9. Prove by cases that if x and y are real numbers, then

max(x, y) = \frac{x + y}{2} + \frac{|x − y|}{2}

Split the proof into two cases: x ≥ y where x is the maximum, and x < y where y is the maximum.

• Case 1: x ≥ y , x is the maximum Since x ≥ y, x − y ≥ 0, and |x − y| = x − y. So

\frac{x + y}{2} + \frac{|x − y|}{2} = \frac{x + y}{2} + \frac{x − y}{2} = \frac{2x}{2} = x = max(x, y).

• Case 2: x < y , y is the maximum Since x < y, x − y < 0, and |x − y| = −(x − y) = y − x. So

\frac{x + y}{2} + \frac{|x − y|}{2} = \frac{x + y}{2} + \frac{y − x}{2} = \frac{2y}{2} = y = max(x, y).

Therefore max(x, y) = \frac{x+y}{2} + \frac{|x−y|}{2} is true, because it is true in both cases.

Problem 10. Using the axioms and inference rules for equality given in class, prove that (∀xyz)((x = y) ∧ (y = z)) → (x = z)

Recall that the equality rules are E1 (∀x)(x = x) E2 For any formula F with free variable x,

(∀xyz …)(x = y ⇒ (F → F [x/y])

where F [x/y] denotes substituting y for some or all occurrences of x. Show that (∀xyz)((x = y) ∧ (y = z)) → (x = z). Let p ↔ ((x = y) ∧ (y = z)).

1. Let F = (x=z) in E2: ∀xyz.(x = y) → (x = z) → (y = z) in particular (b = a) → (b = c) → (a = c)

2. (y = x) → (x = y) [proved in class, see lecture notes 2] in particular (a = b) → (b = a)

3. by transitivity of →, from 1) and 2) we get (a = b) → (b = c) → (a = c)

4. (a = b) and (b = c) by hypothesis

5. modus ponens: (b = c) → (a = c)

6. modus ponens: (a = c)

We proved for fixed a,b,c, so by universal generalization holds for all.