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

Problem Set 1

Due: Start of class on September 15, 1998.

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.)

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.)

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))

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.

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

(c) Is her proof that propositions p, q, and r are all true correct?

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.

(b) n is a prime number.

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

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.

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

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.

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

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

(d) Everyone likes someone and dislikes someone else.

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.