EECS 203: Discrete Mathematics

Fall 2024

Homework 3

Legal Assumptions

• You may use closure properties of the integers without proof, such as: integer · integer = integer, integer + non-integer = non-integer, etc.

• You may use any facts about modular arithmetic/algebra without justification, such as the rules of modular addition and multiplication. This includes facts about algebra on even and odd numbers, such as even + dd = odd, even · dd = even, etc. (since these are equivalent to addition and multiplication mod 2).

• The following facts from Boolean logic may always be used without justification:

Definitions

• The logical operator ¬ means “not,” ∧ means “and,” ∨ means “or,” → means “if-then.”

• The set operator ∪ means “union,” ∩ means “intersection,” and ¯ (a line over a set, like S) means “complement”.

• An integer m divides an integer x, written m | x, if there exists an integer k with x = mk. We also say that x is a multiple of m. The greatest common divisor of two integers a, b, written gcd(a, b), is the largest integer that divides both a and b.

• The set Z = {. . . , −2, −1, 0, 1, 2, . . . } is the integers. The set Z+ = {1, 2, . . . } is the positive integers. The set Q is the rational numbers; that is, the numbers that can be written in the form. a/b for integers a and b. The set Q+ is the positive rational numbers. The set ∅ is the empty set.

• The cardinality of a set S, written |S|, its the number of elements in S.

Mechanical Problems

1. Majority Rules [6 points]

Let # be the majority operator, which takes three truth values on input and which returns a truth value indicating whether a majority (at least two) of them are True. Write a logical expression equivalent to #(p, q, r) using only the symbols p, q, r, ∨, ∧, and parentheses. Justify your expression in 1-2 sentences.

2. GCD Reloaded [8 points]

Write the proposition

“Every pair of integers x, y has a greatest common divisor.”

as a logical expression, and justify your expression in 1-2 sentences. The only symbols in your expression should be variable names, quantifiers (∀, ∃), logical operators (∧, ∨, ¬,→,↔), set notation (∈, Z), divides (|), comparisons (>, <, ≥, ≤, =, ≠), and grouping parentheses.

3. Get Taut Of Here [16 points]

A logical expression is a tautology if it is equivalent to True (in other words, it evaluates to True regardless of the truth values of its variables).

(a) Using sequences of logical equivalences, show that each of the following expressions is a tautology. Use only DeMorgan’s laws, distributive laws, implication breakout, and the rules listed in the “Legal Assumptions” section.

(i) (¬p → F) → p

(ii) (p → q) → (¬q → ¬p)

(iii) ((p ∨ q) ∧ (p → r) ∧ (q → r)) → r

(b) Using the fact that the three expressions above are tautologies, justify that the three proof styles we have learned (contrapositive, contradiction, and cases) are valid ways of reasoning.

4. Cheeky NANDos [15 points]

The logical operator nand, written ↑, is defined by the following truth table:

For each of the following expressions, write an equivalent logical expression using only the symbols a, b, ↑, and parentheses. You do not need to justify your expressions.

(a) ¬a

(b) a ∧ b

(c) a ∨ b

(d) a → b

(e) true

5. Spot the Difference [12 points]

The difference of two sets A and B, written A − B, is the set of all elements in A that are not also in B.

(a) Write a formal definition for A−B in terms of the set operations union (∪), intersection (∩), and complement.

(b) Write the negation of the proposition A ⊆ B using the variables A, B, set difference (−), and any other set symbols you like such as complement ∪, ∩, =, ≠, standard set names, etc.

You must use set difference in your answer. You may not use explicit or implicit logical symbols like ∨, ∧,→, ¬, ̸⊆.

(c) Prove that your negation in the previous part is correct, by using logical manipulations to show that it is equivalent to ¬(A ⊆ B).

Your answer should appeal to both your formal definition of set difference from the first part and the negation you wrote in the second part. You may either start with ¬(A ⊆ B) and turn it into your negation, or start with your negation and turn it into ¬(A ⊆ B). You may use any logical symbols you like.

Bad Proofs

Each of the following propositions may or may not be true, but we have given an incorrect “proof” that attempts to show that it is true. Identify the specific logical error made in each proof by citing a sentence, equation, step, or missing part of the argument, and briefly explain why it is wrong.

6. Decimal Deception [6 points]

Proposition. Let F be the set of positive real numbers that have a finite (non-repeating) decimal representation. Then F = Q+.

Incorrect Proof. Let f ∈ F. We can write f in the form. f = a.b where a and b are integers (for example, if f = 12.34, then a = 12 and b = 34). Let k be the number of digits in b (in the previous example, k = 2). We then have

Since 10k , a, b are all integers, both parts of this fraction are integers, meaning that f is rational. Since f is also positive, that means f ∈ Q+.

7. Hometown Hoax [6 points]

Proposition. All EECS 203 students are from Michigan.

Incorrect Proof. Let m be the proposition that all EECS 203 students are from Michigan, and let A(x) be the predicate that student x is from Ann Arbor. Notice that we have

that is, if all EECS 203 students are from Ann Arbor then they are all from Michigan. We next rearrange this expression using our logical equivalence laws:

The last line states that, if there exists an EECS 203 student from Ann Arbor, then m is true. We have checked the roster and there does indeed exist an EECS 203 student from Ann Arbor, so we conclude that m is true.

Discovery Problems

8. Into the Multiple-verse [15 points]

Given an integer x ∈ Z, let Mx = {z ∈ Z | z is a multiple of x} . Fill in the blank:

“For all positive integers a and b, we have Ma ∩ Mb = Mab if and only if                                .”

Then prove only the first direction of this proposition: if Ma ∩Mb = Mab, then [what you wrote in the blank]. For credit, you must fill in the blank with an easy-to-state property of a, b that makes the proposition true, and which is not just a straightforward restatement of Ma ∩ Mb = Mab.

9. Feeling Productive [16 points]

For a set of numbers S, its product set is defined as {s · t | s, t ∈ S} . For an arbitrary positive integer n, what is the smallest possible cardinality of the product set of an n-element set S ⊆ Z +? Prove your answer.

Notes:

• A complete proof must include both an example of an n-element set whose product set has your claimed number of elements, and also a proof that no other n-element set can have even fewer elements in its product set. For this second part, it may help to look for a smaller set of pairs of elements within S that are guaranteed to generate distinct products from each other.

• Both parts of your answer should leave n as a general variable, rather than assum-ing a specific value for n. For example, your n-element set might be something like “{1, 2, 3, . . . , n}”—that is, a set that depends in some way on the variable n. (That particular set is not the right answer to this problem.)

• Reminder: sets do not have a concept of repeat elements, and so your example set needs to include n distinct elements. In particular, the set is the same as the set {1}, and so it has cardinality 1, not n.