MATH 2601 - FoMP - Homework 3
Note: I will solve some of these problems in class during next week.
Several problems from Hammack’s book: 2.7: 4, 8, 9, 10 2.9: 6, 10, 13 2.10: 4, 6, 8 Ch. 4: 4, 20, 26, 28 Ch. 5: 6, 8, 12, 18, 20, 24, 28
Additional exercises
1. Describe the following sets using the set builder notation. (a) the set of odd integers (b) the set of rational numbers that may be written with denominator greater than 100 (c) the set of rational numbers that may be written with positive denominator less than 4
2. Using truth tables, prove that each of the following compound propositions is a tautology.
(a) [p ∧ (p ⇒ q)] ⇒ q
(b) [∼ q ∧ (p ⇒ q)] ⇒ ∼ p
(c) [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)
(d) [(p ∨ q) ∧ ∼ p] ⇒ q
These implications are four of the most important “rules of inference” in propositional logic. Each rule gives a conclusion which follows logically from a set of hypotheses. As such, these rules are the building blocks of a correct proof.
3. Prove that each of the following propositions is not a tautology, with or without using truth tables.
(a) [(p ⇒ q) ∧ q] ⇒ p
(b) [(p ⇒ q)∧ ∼ p] ⇒ ∼ q
These implications are common logical fallacies (errors in reasoning) since the conclusion does not follow logically from the set of hypotheses.
4. Let a ∈ Z. Prove that 3 | a 2 if and only if 3 | a. (You may use the fact that every integer can be written as exactly one of 3k, 3k + 1, or 3k + 2 for some integer k.)
5. Let a, b, c, d, x and y be integers with a 6= 0 and b 6= 0.
(a) If a | c, then a 2 | c 2 .
(b) If a | c and b | d, then ab | cd.
(c) If a | c and a | d, then a | cx + dy.
(d) If a | b and b | a, then a = b or a = −b.
(e) If a 6 |cd, then a 6 |c and a 6 |d.