Chapter 1

The exclusive disjunction of two propositions \(p\) and \(q\) is denoted by \(p\) XOR \(q .\) Construct a truth table for \(p\) XOR \(q\).

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$p \vee \sim p \equiv t$$

Write each sentence in \(i f-t h e n\) form. An equiangular triangle is isosceles.

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$p \wedge \sim p \equiv f$$

Write each sentence in \(i f\) -then form. Lines perpendicular to the same line are parallel.

Write each sentence in \(i f-t h e n\) form. Lines perpendicular to the same line are parallel.

Every inhabitant on a mysterious planet is either red or green. In addition, each inhabitant is either male or female. Every red man always tells the truth, whereas every green man always lies. The women, on the other hand, are opposite: every green woman tells the truth and every red woman lies. since the natives always disguise their voices, and wear masks and gloves, it is impossible to identify their sex or color. But a clever anthropologist from Mathland met a native who made a statement from which he was able to deduce that the native was a green woman. (R. Smullyan, Discover, 1993? The second native the anthropologist interviewed also made a statement from which he was able to conclude that the native was a man (but not his color). Give a statement that would work. Again, justify your answer.

Four women, one of whom was known to have committed a serious crime, made the following statements when questioned by the police: (B. Bissinger, Parade Magazine, 1993 ) $$\begin{array}{ll}{\text { Fawn: }} & {\text { "Kitty did it" }} \\ {\text { Kitty: }} & {\text { "Robin did it." }} \\ {\text { Bunny: }} & {\text { "I didn't do it" }} \\ {\text { Robin: }} & {\text { "Kitty lied." }}\end{array}$$ If exactly one of these statements is true, identify the guilty woman.

Give a counterexample to disprove each statement, where \(P(x)\) denotes an arbitrary predicate. The square of every real number is positive.

Rewrite each in words, where UD = set of integers. $$(\forall x)(\forall y)(x+y=y+x)$$

Four women, one of whom was known to have committed a serious crime, made the following statements when questioned by the police: (B. Bissinger, Parade Magazine, 1993 ) $$\begin{array}{ll}{\text { Fawn: }} & {\text { "Kitty did it" }} \\ {\text { Kitty: }} & {\text { "Robin did it." }} \\ {\text { Bunny: }} & {\text { "I didn't do it" }} \\ {\text { Robin: }} & {\text { "Kitty lied." }}\end{array}$$ If exactly one of these statements is false, identify the guilty woman.

Give a counterexample to disprove each statement, where \(P(x)\) denotes an arbitrary predicate. Every prime number is odd.

Write each sentence in \(i f\) -then form. \(x=1\) is sufficient for \(x^{2}=1\)

Write each sentence in \(i f-t h e n\) form. \(x=1\) is sufficient for \(x^{2}=1\).

"How is it, Professor Whipple," asked a curious student, "that someone as notoriously absentminded as you are manages to remember his telephone number?" "Quite simple, young man" replied the professor. "I simply keep in mind that it is the only seven-digit number such that the number obtained by reversing its digits is a factor of the number." What is Professor Whipple's telephone number? (A. J. Friedland, 1970 )

Write the converse, inverse, and contrapositive of each implication. If the calculator is working, then the battery is good.

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$p \rightarrow q \equiv q \rightarrow p$$

Give a counterexample to disprove each statement, where \(P(x)\) denotes an arbitrary predicate. Every month has exactly 30 days.

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$p \equiv p$$

Write the converse, inverse, and contrapositive of each implication. If London is in France, then Paris is in England.

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$\text { If } p \equiv q, \text { then } q \equiv p$$

Let \(x, y,\) and \(z\) be any real numbers. Represent each sentence symbolically, where \(p: x

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. If \(p \equiv q\) and \(q \equiv r,\) then \(p \equiv r\).

Find the flaw in the following "proof": Let \(a\) and \(b\) be real numbers such that \(a=b .\) Then \(a b=b^{2}\) Therefore, \(a^{2}-a b=a^{2}-b^{2}\) Factoring, \(a(a-b)=(a+b)(a-b)\) Cancel \(a-b\) from both sides: $$a=a+b$$ since \(a=b,\) this yields \(a=2 a\) Cancel a from both sides. Then we get \(1=2\) . Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Let \(x, y,\) and \(z\) be any real numbers. Represent each sentence symbolically, where \(p: xx\).

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$\text { If } p \wedge q \equiv p \wedge r, \text { then } q \equiv r$$.

Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Let \(x, y,\) and \(z\) be any real numbers. Represent each sentence symbolically, where \(p: x

Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Let UD \(=\) set of integers, \(\mathrm{P}(x, y) : x\) is a multiple of \(y,\) and \(Q(x, y) : x \geq y\) Determine the truth value of each proposition. $$(\exists x) \mathrm{P}(15, x)$$

Mark each sentence as true or false, where \(p, q,\) and \(r\) are arbitrary statements, \(t\) a tautology, and \(f\) a contradiction. $$\text { If } p \vee q \equiv p \vee r, \text { then } q \equiv r$$.

Let UD = set of integers, \(P(x, y): x\) is a multiple of \(y,\) and \(Q(x, y): x \geq y\) Determine the truth value of each proposition. $$(\exists x) \mathrm{P}(15, x)$$

Let \(x, y,\) and \(z\) be any real numbers. Represent each sentence symbolically, where \(p: x

Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Determine whether or not the assignment statement \(x \leftarrow x+1\) will be executed in each sequence of statements, where \(i \leftarrow 2, j \leftarrow 3, k \leftarrow 6,\) and \(x \leftarrow 0\). $$ \begin{array}{l} \text { If }(i<3) \wedge(j<4) \text { then } \\ \qquad x \leftarrow x+1 \end{array} $$ else $$ y

Use De Morgan's laws to verify each. (Hint: \(p \rightarrow q \equiv \sim p \vee q\) ). $$\sim(\sim p \wedge \sim q) \equiv p \vee q$$

Use De Morgan's laws to verify each. (Hint: \(p \rightarrow q \equiv \sim p \vee q\) ). $$\sim(\sim p \vee q) \equiv p \wedge \sim q$$

Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Determine whether or not the assignment statement \(x \leftarrow x+1\) will be executed in each sequence of statements, where \(i \leftarrow 2, j \leftarrow 3, k \leftarrow 6,\) and \(x \leftarrow 0\). $$ \begin{array}{l} \text { If }(i4) \text { then } \\ x \leftarrow x-1 \end{array} $$ else $$ x

Use De Morgan's laws to verify each. (Hint: \(p \rightarrow q \equiv \sim p \vee q\) ). $$\sim(\sim p \vee \sim q) \equiv p \wedge q$$

Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Determine whether or not the assignment statement \(x \leftarrow x+1\) will be executed in each sequence of statements, where \(i \leftarrow 2, j \leftarrow 3, k \leftarrow 6,\) and \(x \leftarrow 0\). While \(\sim(i \leq j)\) do begin \(x \leftarrow x+1\) \(i \leftarrow i+1\) endwhile

Use De Morgan's laws to verify each. (Hint: \(p \rightarrow q \equiv \sim p \vee q\) ). $$\sim(p \wedge \sim q) \equiv \sim p \vee q$$

Let \(a, b,\) and \(c\) be any real numbers. Then \(a

Determine whether or not the assignment statement \(x \leftarrow x+1\) will be executed in each sequence of statements, where \(i \leftarrow 2, j \leftarrow 3, k \leftarrow 6,\) and \(x \leftarrow 0\). While \(\sim(i+j \geq k)\) do $$ x \leftarrow x+1 $$

Let UD \(=\) set of integers, \(\mathrm{P}(x, y) : x\) is a multiple of \(y,\) and \(Q(x, y) : x \geq y\) Determine the truth value of each proposition. $$(\exists x)[\mathrm{P}(x, 2) \vee \mathrm{Q}(x, 6)]$$

Prime numbers of the form \(f(n)=2^{n}-1,\) where \(n\) is a positive integer, are called Mersenne primes, after the Franciscan monk Marin Mersenne \((1588-1648) .\) For example, \(f(2)=3, f(3)=7,\) and \(f(5)=31\) are Mersenne primes. Give a counterexample to disprove the claim that if \(n\) is a prime, then \(2^{n}-1\) is a prime.

Let UD = set of integers, \(P(x, y): x\) is a multiple of \(y,\) and \(Q(x, y): x \geq y\) Determine the truth value of each proposition. $$(\exists x)[\mathrm{P}(x, 2) \vee \mathrm{Q}(x, 6)]$$

Use De Morgan's laws to verify each. (Hint: \(p \rightarrow q \equiv \sim p \vee q\) ). $$\sim(p \rightarrow q) \equiv p \wedge \sim q$$

Let \(t\) be a tautology and \(p\) an arbitrary proposition. Find the truth value of each. $$(\sim t) \rightarrow p$$