Chapter 3

Let \(p(x)\) stand for " \(x\) is a prime," \(q(x)\) for " \(x\) is even," and \(r(x, y)\) stand for " \(x=y . "\) Use these three symbolic statements and appropriate logical notation to write the statement "There is one and only one even prime." (Use the set \(Z^{+}\)of positive integers for your universe.)

Suppose that for each line of a two-variable truth table, you are told whether the final column in that line should evaluate to true or to false. (For example, you might be told that the final column should contain \(\mathrm{T}, \mathrm{F}, \mathrm{F}\), and \(\mathrm{T}\), in that order. Notice that Problem 12 can be interpreted as asking for this pattern.) Explain how to create a logical statement using the symbols \(s, t, \wedge, \vee\), and \(\neg\) that has that pattern as its final column. Can you extend this procedure to an arbitrary number of variables?

Prove or disprove the following statement: "For all integers \(b, c\), and \(d\), if \(x\) is a rational number such that \(x^{2}+b x+c=d\), then \(x\) is an integer." (Hints: Are all the quantifiers given explicitly? It is okay, but not necessary, to use the quadratic formula.)

Each of the following expressions represents a statement about the integers. Using \(p(x)\) for " \(x\) is prime," \(q(x, y)\) for " \(x=y^{2}, " r(x, y)\) for " \(x \leq y, " s(x, y, z)\) for " \(z=x y, "\) and \(t(x, y)\) for " \(x=y, "\) determine which expressions represent true statements and which represent false statements. a. \(\forall x \in Z(\exists y \in Z(q(x, y) \vee p(x)))\) b. \(\forall x \in Z(\forall y \in Z(s(x, x, y) \Leftrightarrow q(x, y)))\) c. \(\forall y \in Z(\exists x \in Z(q(y, x)))\) d. \(\exists z \in Z(\exists x \in Z(\exists y \in Z(p(x) \wedge p(y) \wedge \neg t(x, y))))\)

Why is \((\exists x \in U(p(x))) \wedge(\exists y \in U(q(y)))\) not equivalent to \(\exists z \in U(p(z) \wedge q(z)) ?\) Are the statements \((\exists x \in U(p(x))) \vee(\exists y\) \(\in U(q(y)))\) and \(\exists z \in U(p(z) \vee q(z))\) equivalent?

Prove that there is no largest prime number.

Prove that if \(f, g\), and \(h\) are functions from \(R^{+}\)to \(R^{+}\)such that \(f(x)=O(g(x))\) and \(g(x)=O(h(x))\), then \(f(x)=O(h(x))\).