3.6: Exercises

EXERCISE 3.1. Prove de Morgan’s laws, (3.3) and (3.4). (Hint: There are four possible assignments of truth values 0 and 1 to the two statements \(P\) and \(Q\). For each such assignment, evaluate the truth values of the left-hand and right-hand sides of (3.3) and show they are always the same.)

EXERCISE 3.2. Prove that compound statements \(P\) and \(Q\) are propositionally equivalent iff \(P \Longleftrightarrow Q\).

EXERCISE 3.3. Give an example of a true conditional statement in which the consequence is false. ExERCISE 3.4. If \(P, Q\) and \(R\) are statements, prove that the following are true:
a) \(P \wedge \neg P \Rightarrow Q\)
b) \([(P \Rightarrow Q) \wedge(Q \Rightarrow R)] \Rightarrow(P \Rightarrow R)\)
c) \([P \Rightarrow(Q \wedge \neg Q)] \Rightarrow \neg P\)
d) \([P \wedge(P \Rightarrow Q)] \Rightarrow Q\)
e) \(P \Rightarrow(Q \vee \neg Q)\).

EXERCISE 3.5. Let \(P\) and \(Q\) be statements. Prove that there are statements using only \(P, Q, \neg\) and \(\wedge\) that are propositionally equivalent to
a) \(P \wedge Q\)
b) \(P \vee Q\)
c) \(P \Rightarrow Q\).

Prove that there are statements using only \(P, Q, \neg\) and \(\vee\) that are equivalent to the above.

EXERCISE 3.6. Prove the distributive laws for propositional logic: If \(P, Q\) and \(R\) are statements, then
a) \(P \vee(Q \wedge R) \equiv(P \vee Q) \wedge(P \vee R)\)
b) \(P \wedge(Q \vee R) \equiv(P \wedge Q) \vee(P \wedge R)\).

EXERCISE 3.7. Prove the distributive law for sets: If \(X, Y\) and \(Z\) are sets, then
a) \(X \cup(Y \cap Z)=(X \cup Y) \cap(X \cup Z)\)
b) \(X \cap(Y \cup Z)=(X \cap Y) \cup(X \cap Z)\).

EXERCISE 3.8. Let sets \(X, Y\) and \(Z\) be characteristic sets of formulas \(P(x), Q(x)\) and \(R(x)\) respectively. For each possible region of the Venn diagram of \(X, Y\) and \(Z\) give a compound formula (with atomic formulas \(P, Q\) and \(R\) ) that has that region as its characteristic set.

EXERCISE 3.9. Write a formula in one variable that defines the even integers.

EXERCISE 3.10. Write a formula that defines perfect squares. EXERCISE 3.11. Write a formula in two variables that defines the points in \(\mathbb{R}^{2}\) that have distance 1 from the point \((\pi, e)\).

EXERCISE 3.12. Can you write a formula in one variable using only addition, multiplication, exponentiation, integers and equality, to define the set of all roots of a given polynomial with integer coefficients? How about the set of roots of all polynomials with integer coefficients?

EXERCISE 3.13. Which of the following statements are true?
a) \((\forall x \in \mathbb{R}) x+1>x\)
b) \((\forall x \in \mathbb{Z}) x^{2}>x\)
c) \((\exists x \in \mathbb{Z})(\forall y \in \mathbb{Z}) x \leq y\)
d) \((\forall y \in \mathbb{Z})(\exists x \in \mathbb{Z}) x \leq y\)
e) \((\forall \varepsilon>0)(\exists \delta>0)(\forall x \in \mathbb{R})[0<|x-1|<\delta] \Rightarrow\left[\left|x^{2}-1\right|<\varepsilon\right]\).

EXERCISE 3.14. What is the negation of each statement in Exercise 3.13? Which of the negations are true?

EXERCISE 3.15. Let \(a, L \in \mathbb{R}\) and \(f\) be a real function. Prove that the statements \[(\forall \varepsilon>0)(\exists \delta>0)(\forall x \in \operatorname{Dom}(f))[0<|x-a|<\delta] \Rightarrow[|f(x)-L|<\varepsilon]\] and \[(\exists \delta>0)(\forall \varepsilon>0)(\forall x \in \operatorname{Dom}(f))[0<|x-a|<\delta] \Rightarrow[|f(x)-L|<\varepsilon]\] are not equivalent. Which statement is a consequence of the other?

EXERCISE 3.16. Let \(P(x, y)\) be a formula in two variables. Show that in general \((\forall x)(\exists y) P(x, y)\) need not be equivalent to \((\exists y)(\forall x) P(x, y)\). Show that \((\forall x)(\forall y) P(x, y)\) is equivalent to \((\forall y)(\forall x) P(x, y)\). What about \((\exists x)(\exists y) P(x, y)\) and \((\exists y)(\exists x) P(x, y)\) ?

EXERCISE 3.17. Consider the following statements. Write down the contrapositive and the converse to each one.

(i) All men are mortal.

(ii) I mean what I say. (iii) Every continuous function on the interval \([0,1]\) attains its maximum

(iv) The sum of the angles of a triangle is \(180^{\circ}\).

EXERCISE 3.18. Prove that a number is divisible by 4 if and only if its last two digits are.

EXERCISE 3.19. Prove that a number is divisible by 8 iff its last three digits are.

EXERCISE 3.20. Prove that a number is divisible by \(2^{n}\) iff its last \(n\) digits are.

EXERCISE 3.21. Suppose \(m\) is a number with the property that any natural number is divisible by \(m\) iff its last three digits are. What does this say about \(m\) ? Prove your assertion.

ExERCISE 3.22. Prove that an integer is divisible by 11 iff the sum of the oddly placed digits minus the sum of the evenly placed digits is divisible by 11. (So \(11 \mid 823493\) iff 11 divides \((2+4+3)-(8+3+9)\).)

EXERCISE 3.23. Show that every interval contains rational and irrational numbers.

EXERCISE 3.24. Prove that \(\sqrt{3}\) is irrational.

EXERCISE 3.25. Prove that \(\sqrt{10}\) is irrational.

EXERCISE 3.26. Prove that the square root of any natural number is either an integer or irrational.

EXERCISE 3.27. Prove that there exist irrational numbers \(x\) and \(y\) so that \(x^{y}\) is rational. (Hint: consider \(\sqrt{2}^{\sqrt{2}}\) and \(\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}\).)

EXERCISE 3.28. Prove or disprove the following assertion: Any 4 points in the plane, no three of which are collinear, lie on a circle.

EXERCISE 3.29. Prove that there are an infinite number of primes. ExERCISE 3.30. For \(k=0,1,2\), let \(P_{k}\) be the set of prime numbers that are congruent to \(k \bmod 3\). By Exercise 3.29, \(P_{0} \cup P_{1} \cup P_{2}\) is infinite. Can you say which of the sets \(P_{0}, P_{1}\) and \(P_{2}\) are infinite?

(Remark: For two of the three sets, this problem is not too difficult. For the third one, it is extremely difficult, and is a special case of a celebrated theorem of Dirichlet. See \(e . g\). [8] for a treatment of Dirichlet’s theorem.)

EXERCISE 3.31. Let the points in \(\mathbb{R}^{2}\) be colored red, green and blue. Prove that either there are two points of the same color a distance 1 apart, or there is an equilateral triangle of side length \(\sqrt{3}\) all of whose vertices are the same color.

EXERCISE 3.32. Prove that \[e=\sum_{n=0}^{\infty} \frac{1}{n !}\] is irrational. (Hint: Argue by contradiction. Assume \(e=\frac{p}{q}\), and multiply both sides by \(q !\) Rearrange the equation to get an integer equal to an infinite sum of rational numbers that converges to a number in \((0,1)\). )