Massachusetts Institute of Technology Handout 10 6.042J/18.062J: Mathematics for Computer Science September 17, 1998 Professors Nancy Lynch and Srinivas Devadas

Problem Set 1 Solutions

Problem 1. Let A, B, and C be sets. Assume that A ∩ B ∩ C = ∅. Prove that

A ∪ B ∪ C = (A \ B) ∪ (B \ C) ∪ (C \ A).

(Note: If X and Y are sets, then X \ Y is the set of elements in X that are not in Y.)

Proof. We prove the equality by showing that the left set contains the right set and vice versa. Let S be the set on the left, A ∪ B ∪ C, and let T be the set on the right, (A \ B) ∪ (B \ C) ∪ (C \ A). Our objective is to prove that S = T.

First, we show that S is contained in T. Let x be an element of S = A ∪ B ∪ C. There are then six cases:

• x ∈ A, x ∉ B, x ∉ C: Since x ∈ A and x ∉ B, we have x ∈ A \ B, and so x ∈ T.

• x ∉ A, x ∈ B, x ∉ C: Since x ∈ B and x ∉ C, we have x ∈ B \ C, and so x ∈ T.

• x ∉ A, x ∉ B, x ∈ C: Since x ∈ C and x ∉ A, we have x ∈ C \ A, and so x ∈ T.

• x ∈ A, x ∈ B, x ∉ C: Since x ∈ B and x ∉ C, we have x ∈ B \ C, and so x ∈ T.

• x ∈ A, x ∉ B, x ∈ C: Since x ∈ A and x ∉ B, we have x ∈ A \ B, and so x ∈ T.

• x ∉ A, x ∈ B, x ∈ C: Since x ∈ C and x ∉ A, we have x ∈ C \ A, and so x ∈ T.

In every case, x ∈ T as well; therefore, every element of S is also an element of T, and so S ⊆ T. (Note that the case x ∈ A, x ∈ B, x ∈ C does not exist, since A ∩ B ∩ C = ∅ by assumption.)

Now we show that T is contained in S. Let x be an element of T = (A\B)∪(B\C)∪(C\A). There are then three cases:

• x ∈ A \ B: This implies that x ∈ A, and so x ∈ S.

• x ∈ B \ C: This implies that x ∈ B, and so x ∈ S.

• x ∈ C \ A: This implies that x ∈ C, and so x ∈ S.

In every case, x ∈ S as well; therefore, every element of T is also an element of S, and so T ⊆ S. Since set S contains set T and vice versa, S and T must be the same set; that is, S = T.

The following alternative presentation of the proof may make the structure of the argument more clear.

Proof. Goal: show that if A ∩ B ∩ C = ∅, then A ∪ B ∪ C = (A \ B) ∪ (B \ C) ∪ (C \ A).

1. Let S = A ∪ B ∪ C.

2. Let T = (A \ B) ∪ (B \ C) ∪ (C \ A).

3. S ⊆ T (a) Let x be an element of S.

(b) If x ∈ A, x ∉ B, x ∉ C, then x ∈ A \ B ⊆ T by definition of \ and of T.

(c) If x ∉ A, x ∈ B, x ∉ C, then x ∈ B \ C ⊆ T by definition of \ and of T.

(d) If x ∉ A, x ∉ B, x ∈ C, then x ∈ C \ A ⊆ T by definition of \ and of T.

(e) If x ∈ A, x ∈ B, x ∉ C, then x ∈ B \ C ⊆ T by definition of \ and of T.

(f) If x ∈ A, x ∉ B, x ∈ C, then x ∈ A \ B ⊆ T by definition of \ and of T.

(g) If x ∉ A, x ∈ B, x ∈ C, then x ∈ C \ A ⊆ T by definition of \ and of T.

(h) Q. E. D. by exhaustive case analysis.

4. T ⊆ S (a) Let x be an element of T.

(b) If x ∈ A \ B, then x ∈ A ⊆ S by definition of \ and of S.

(c) If x ∈ B \ C, then x ∈ B ⊆ S. by definition of \ and of S.

(d) If x ∈ C \ A, then x ∈ C ⊆ S. by definition of \ and of S.

(e) Q. E. D. by exhaustive case analysis.

5. Q. E. D. since two-way set inclusion implies equality.

Problem 2. A real number r is called sensible if there exist positive integers a and b such that \sqrt{a/b} = r. For example, setting a = 2 and b = 1 shows that \sqrt{2} is sensible. Prove that 3 \sqrt{2} is not sensible. (Consider only positive real roots in this problem.)

Proof. The proof is by contradiction. Assume for the purpose of contradiction that ^{3} \sqrt{2} is sensible. Then there exist positive integers a and b such that \sqrt{a/b} = ^{3} \sqrt{2}. Squaring both sides of this equation gives a/b = ^{3} \sqrt{4}, which implies that ^{3} \sqrt{4} is rational.

Since ^{3} \sqrt{4} is rational, we can write it as a fraction x/y in lowest-terms, where x is an integer and y is a positive integer. Therefore, we have:

\sqrt[3]{4} = x/y
4 = x^{3}/y^{3}
4y^{3} = x^{3}

In the last equation, the left side is even, and so the right side must be even. Since x^{3} is even, x itself must be even. This implies that the right side is actually divisible by 8, and so the left side must also be divisible by 8. Therefore, y^{3} is even, and so y itself must be even.

The fact that both x and y are even contradicts the fact that x/y is a fraction in lowest terms. Therefore, ^{3} \sqrt{2} is not sensible.

Problem 3. Rewrite each of the following expressions using the symbols → and ¬, but not the symbols ∨ and ∧.

(a) p ∨ q ∨ ¬r

(b) p ∧ q ∧ ¬r

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

First, we will derive rules for translating and’s and or’s into implications. Then we will apply these rules to rewrite the given expressions.

Recall that the expression a → b is equivalent to ¬a ∨ b. Substituting a = ¬c and b = d, we find that c ∨ d can be rewritten as ¬c → d. Similarly, the expression ¬(a → b) is equivalent to ¬(¬a ∨ b). We can rewrite this last expression as (a ∧ ¬b) by using DeMorgan’s Law. Substituting a = c and b = ¬d, we find that c ∧ d can be rewritten as ¬(c → ¬d). In summary:

c ∨ d = ¬c → d
c ∧ d = ¬(c → ¬d)

The given expressions can now be translated using these two rules.

Part (a).

p ∨ q ∨ ¬r = (p ∨ q) ∨ ¬r
= (¬p → q) ∨ ¬r
= ¬(¬p → q) → ¬r

Part (b).

p ∧ q ∧ ¬r = (p ∧ q) ∧ ¬r
= (¬(p → ¬q)) ∧ ¬r
= ¬((¬(p → ¬q)) → r)

Part (c).

¬((p ∨ ¬q) ∧ ¬(¬r ∨ s)) = ¬((¬p → ¬q) ∧ ¬(r → s))
= (¬p → ¬q) → (r → s)))
= (q → p) → (r → s)

The very last step is a simplification using the fact that the implication q → p is equivalent to the contrapositive ¬p → ¬q.

Problem 4. A student is trying to prove that propositions p, q, and r are all true. She proceeds as follows. First, she proves three facts: p → q, q → r, and r → p. Then she concludes, “Thus obviously p, q, and r are all true.”

(a) Using logic notation and the symbols p, q, and r, write down the logical implication that she uses in her final step.

((p → q) ∧ (q → r) ∧ (r → p)) → (p ∧ q ∧ r)

(b) Use a truth table to determine whether this logical implication is a tautology.

p q r ((p → q) ∧ (q → r) ∧ (r → p)) (p ∧ q ∧ r) complete expression
T T T  T  T  T
T T F  F  F  T
T F T  F  F  T
T F F  F  F  T
F T T  F  F  T
F T F  F  F  T
F F T  F  F  T
F F F  T  F  → F ←

The truth table indicates that the implication that she uses is not a tautology.

(c) Is her proof that propositions p, q, and r are all true correct? Her proof is incorrect; she makes use of a false proposition. (However, the first part of her argument is sufficient to show that either all three statements are true or all three statements are false.)

Problem 5. Express each of the following statements in formal logic notation. In addition to the usual logic symbols and variables, you may build predicates using addition, multiplication, constants, and equality and inequality symbols. The domain of discourse is the non-negative integers. For example, the statement “n is an odd number” could be written “∃x(2 · x + 1 = n)”.

(a) n is the sum of three perfect squares.

∃x∃y∃z(x · x + y · y + z · z = n)

(b) n is a prime number.

(n > 1) ∧ ¬(∃x∃y((x > 1) ∧ (y > 1) ∧ (x · y = n))

(c) n is a product of exactly two primes.

∃x∃y ( (x > 1) ∧ ¬(∃a∃b((a > 1) ∧ (b > 1) ∧ (a · b = x))) ∧
(y > 1) ∧ ¬(∃c∃d((c > 1) ∧ (d > 1) ∧ (c · d = y))) ∧
(x · y = n))

Problem 6. A self-proclaimed “great logician” has invented a new quantifier, on par with ∃ (“there exists”) and ∀ (“for all”). The new quantifier is symbolized by ∃! and read “there exists a unique”. The proposition ∃!xP (x) is true if there is exactly one x in the domain of discourse for which P (x) is true. The logician has noted, “There used to be two quantifiers, but now there are three! I have extended the whole field of mathematics by 50%!”

(a) Rewrite the proposition ∃!xP (x) using only the ∃ quantifier.

∃x(P (x) ∧ ¬(∃y(x ≠ y ∧ P (y)))

(b) Rewrite the proposition ∃!xP (x) using only the ∀ quantifier.

¬∀x(¬P (x) ∨ ¬∀y(x = y ∨ ¬P (y))

Problem 7. A media tycoon has an idea for an all-news television network called LNN: The Logic News Network. Each segment will begin with a definition of the domain of discourse and a few predicates. The day’s happenings can then be communicated concisely in logic notation. For example, a broadcast might begin as follows:

“THIS IS LNN. The domain of discourse is {Bill, Monica, Ken, Linda, Betty}. Let D(x) be a predicate that is true if x is deceitful. Let L(x, y) be a predicate that is true if x likes y. Let G(x, y) be a predicate that is true if x turned over gifts to y.”

Complete the broadcast by translating the following statements into logic notation.

(a) If neither Monica nor Linda is deceitful, then Bill and Monica like each other.

(¬(D(Monica) ∨ D(Linda))) → (L(Bill, Monica) ∧ L(Monica, Bill))

(b) Everyone except for Ken likes Betty, and no one except Linda likes Ken.

∀x((x = Ken ∧ ¬L(x, Betty)) ∨ (x ≠ Ken ∧ L(x, Betty))) ∧
∀x((x = Linda ∧ L(x, Ken)) ∨ (x ≠ Linda ∧ ¬L(x, Ken)))

(c) If Ken is not deceitful, then Bill turned over gifts to Monica, and Monica turned gifts over to someone.

¬D(Ken) → (G(Bill, Monica) ∧ ∃xG(Monica, x))

(d) Everyone likes someone and dislikes someone else.

∀x∃y∃z(y ≠ z ∧ L(x, y) ∧ ¬L(x, z))

Problem 8. (The Mystery) The 6.042 mascot, Theory Pig, was recently found squished under a pile of course handouts. Fortunately, Theory Pig is okay and is getting his stuffing sorted out. However, he demands that the culprit or culprits be found. The only clue is a crumpled paper found nearby scrawled over with logic notation:

1. Domain of discourse = {Duran, Khurshid, Lehman, Gould, Sherman}.

2. G(x) = true if and only if x is guilty.

3. (∃xG(x)) ∧ (∃x(¬G(x)))

4. (G(Duran) ∨ G(Khurshid)) → ¬G(Sherman)

5. ¬(G(Khurshid) ∧ G(Lehman))

6. ¬G(Sherman) → (∃x∃y(x ≠ y ∧ G(x) ∧ G(y))

7. (G(Duran) → G(Sherman)) ∧ (G(Sherman) → G(Duran))

8. ¬(G(Lehman) ∧ G(Gould))

Who squished Theory Pig? State your answer and sketch your deductive process.

Theory Pig was squished by Khurshid and Gould. A straightforward, but laborious way to solve this problem is to write out a table with 2^{5} = 32 entries, one for each guilty/innocent combination. If we cross off each entry that is contradicted by a statement on the crumpled paper, then the single, remaining entry indicates the culprits.

Here is an alternative, ad hoc approach. Sherman appears often, so let’s first try to determine whether he is guilty. Suppose that Sherman is guilty. Then by statement 4, neither Duran nor Khurshid can be guilty. However, by statement 7, Duran must be guilty. This is a contradiction with respect to Duran, and so Sherman must be innocent. Since Sherman is innocent, statement 7 implies that Duran is also innocent, and statement 6 implies that there are at least two culprits among the remaining three suspects, Khurshid, Lehman, and Gould. Suppose that Lehman is guilty. Then Khurshid and Gould are both innocent by statements 5 and 8. This would imply only one cuprit, giving a contradiction. Therefore, Lehman must be innocent. Since there are at least two culprits, Khurshid and Gould must both be guilty.

(The simplest approach, of course, is a careful scrutiny of the moral fibre of your TAs.)