Chapter 1

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. $$(\forall x)(\exists y) P(x, y)$$

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

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

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. $$(\forall x)(\exists y) P(x, y)$$

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. $$(\forall x)(\exists y) Q(x, y)$$

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

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. $$(\forall x) | P(x, 3) \rightarrow Q(x, 3) ]$$

Show that the connectives \(\wedge, \rightarrow,\) and \(\leftrightarrow\) can be expressed in terms of v and \(\sim .\) (Hint: Use Exercise 44, law 18, and Tables 1.6 and 1.7.)

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. $$(\forall x)[\mathrm{P}(x, 3) \rightarrow \mathrm{Q}(x, 3)]$$

Simplify each boolean expression. $$p \wedge(p \wedge q)$$

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) | Q(x, 3) \rightarrow \mathrm{P}(x, 3) ]$$

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)[\mathbf{Q}(x, 3) \rightarrow \mathbf{P}(x, 3)]$$

Simplify each boolean expression. $$p \vee(p \vee q)$$

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

Simplify each boolean expression. $$p \vee(\sim p \wedge q)$$

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

Let UD \(=\) set of real numbers and \(\mathrm{P}(x, y) : y^{2} < x .\) Determine the truth value of each proposition. $$(\exists x)(\exists y) P(x, y)$$

Let UD = set of real numbers and \(P(x, y): y^{2} < x .\) Determine the truth value of each proposition. $$(\exists x)(\exists y) P(x, y)$$

Simplify each boolean expression. $$(p \wedge \sim q) \vee(p \wedge q) \vee r$$

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

Let UD \(=\) set of real numbers and \(\mathrm{P}(x, y) : y^{2} < x .\) Determine the truth value of each proposition. $$(\forall x)(\exists y) \mathrm{P}(x, y)$$

Let UD = set of real numbers and \(P(x, y): y^{2} < x .\) Determine the truth value of each proposition. $$(\forall x)(\exists y) \mathrm{P}(x, y)$$

Simplify each boolean expression. $$p \wedge(p \vee \sim q) \wedge(\sim p \vee \sim q)$$

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

Let UD \(=\) set of real numbers and \(\mathrm{P}(x, y) : y^{2} < x .\) Determine the truth value of each proposition. $$(\forall y)(\exists x) \mathrm{P}(x, y)$$

Let UD = set of real numbers and \(P(x, y): y^{2} < x .\) Determine the truth value of each proposition. $$(\forall y)(\exists x) \mathrm{P}(x, y)$$

Construct a truth table for each proposition. $$p \rightarrow(p \vee q)$$

Simplify each boolean expression. $$(p \wedge \sim q) \vee(\sim p \wedge q) \vee(\sim p \wedge \sim q)$$

Let UD = set of real numbers and \(P(x, y): y^{2} < x .\) Determine the truth value of each proposition. $$(\exists x)(\forall y) P(x, y)$$

Construct a truth table for each proposition. $$(p \wedge q) \rightarrow \sim p$$

Construct a truth table for each proposition. $$(p \wedge q) \rightarrow(p \vee q)$$

A third useful quantifier is the uniqueness quantifier \(\exists ! .\) The proposition \(\left(\exists^{\prime} x\right) P(x)\) means There exists a unique (meaning exactly one) \(x\) such that \(P(x) .\) Determine the truth value of each proposition, where UD \(=\) set of integers. $$\left(\exists^{\prime} x\right)(x+3=3)$$

Construct a truth table for each proposition. $$(p \vee q) \leftrightarrow(p \wedge q)$$

The Sheffer stroke / is a binary operator" defined by the following truth table.(Note: On page 25 we used the vertical bar \(|\) to mean is a factor of. The actual meaning should be clear from the context. So be careful.) Verify each. (Note: Exercise 58 shows that the logical operators \(|\) and \(\mathrm{NAND}\) are the same. (TABLE CAN'T COPY) $$p | q \equiv \sim(p \wedge q)$$

Determine whether or not each is a tautology. $$p \vee(\sim p)$$

Determine whether or not each is a tautology. $$[p \wedge(p \rightarrow q)] \rightarrow q$$

The Sheffer stroke / is a binary operator" defined by the following truth table.(Note: On page 25 we used the vertical bar \(|\) to mean is a factor of. The actual meaning should be clear from the context. So be careful.) Verify each. (Note: Exercise 58 shows that the logical operators \(|\) and \(\mathrm{NAND}\) are the same. (TABLE CAN'T COPY) $$p \wedge q \equiv(p | q)|(p | q)$$

Determine whether or not each is a tautology. $$[(p \rightarrow q) \wedge(\sim q)] \rightarrow \sim p$$

The Sheffer stroke / is a binary operator" defined by the following truth table.(Note: On page 25 we used the vertical bar \(|\) to mean is a factor of. The actual meaning should be clear from the context. So be careful.) Verify each. (Note: Exercise 58 shows that the logical operators \(|\) and \(\mathrm{NAND}\) are the same. (TABLE CAN'T COPY) $$p \rightarrow q \equiv((p | p)|(p | p))|(q | q)$$

Determine whether or not each is a tautology. $$[(p \vee q) \wedge(\sim q)] \rightarrow p$$

A third useful quantifier is the uniqueness quantifier \(\exists ! .\) The proposition \(\left(\exists^{\prime} x\right) P(x)\) means There exists a unique (meaning exactly one) \(x\) such that \(P(x) .\) Determine the truth value of each proposition, where UD \(=\) set of integers. $$(\forall x)(\exists ! y)(x+y=4)$$

The Sheffer stroke / is a binary operator" defined by the following truth table.(Note: On page 25 we used the vertical bar \(|\) to mean is a factor of. The actual meaning should be clear from the context. So be careful.) Verify each. (Note: Exercise 58 shows that the logical operators \(|\) and \(\mathrm{NAND}\) are the same. (TABLE CAN'T COPY) $$\sim(p \vee q) \equiv((p | p)|(q | q))|((p | p)|(q | q))$$

Determine whether or not each is a contradiction. $$p \wedge(\sim p)$$

Express \(p\) XOR \(q\) in terms of the Sheffer stroke. (Hint: \(\mathrm{XOR} q=[(p \vee q) \wedge \sim(p \wedge q)] .\)

Determine the truth value of each, where \(\mathrm{P}(\mathrm{s})\) denotes an arbitrary predicate. $$(\exists x) P(x) \rightarrow(\exists x) P(x)$$

The Sheffer stroke / is a binary operator" defined by the following truth table.(Note: On page 25 we used the vertical bar \(|\) to mean is a factor of. The actual meaning should be clear from the context. So be careful.) Verify each. (Note: Exercise 58 shows that the logical operators \(|\) and \(\mathrm{NAND}\) are the same. (TABLE CAN'T COPY) Express \(p\) XOR \(q\) in terms of the Sheffer stroke. (Hint: \(p\) XOR \(q \equiv[(p \vee q) \wedge \sim(p \wedge q)] .\) )

Determine the truth value of each, where \(P(s)\) denotes an arbitrary predicate. $$\left(\exists^{\prime} x\right) P(x) \rightarrow(\exists x) P(x)$$

Express \(p \leftrightarrow q\) in terms of the Sheffer stroke. (Hint: \(p \leftrightarrow q \equiv\) \((p \rightarrow q) \wedge(q \rightarrow p) . )\) INote: Exercises \(57-64\) indicate that all boolean operators can be expressed in terms of the Sheffer strokell

Determine whether or not each is a contradiction. $$\sim(p \vee \sim p)$$

The Sheffer stroke / is a binary operator" defined by the following truth table.(Note: On page 25 we used the vertical bar \(|\) to mean is a factor of. The actual meaning should be clear from the context. So be careful.) Verify each. (Note: Exercise 58 shows that the logical operators \(|\) and \(\mathrm{NAND}\) are the same. (TABLE CAN'T COPY) Express \(p \leftrightarrow q\) in terms of the Sheffer stroke. (Hint: \(p \leftrightarrow q \equiv\) \((p \rightarrow q) \wedge(q \rightarrow p) .)[\text {Note}: \text { Exercises } 57-64\) indicate that all boolean operators can be expressed in terms of the Sheffer stroke!]