Chapter 1.5, Problem 50E

Put these statements in prenex normal form. [Hint:Use logical equivalence fromTables 6and7inSection 1.3,Table 2inSection 1.4,Example 19inSection 1.4, Exercises 47 and 48 in Section 1.4, and Exercises 48 and 49.)

a) $\exists xP\left(x\right)\wedge \exists xQ\left(x\right)\wedge A$, where A is a proposition not any quantifiers

b) $\neg \left(\forall xP\left(x\right)\wedge \forall xQ\left(x\right)\right)$

c)

   $\exists xP\left(x\right)\to \exists xQ\left(x\right)$

TABLE 6Logical Equivalences.
Equivalence	Name
$\begin{array}{l}p\wedge \text{T}\equiv p\\ p\vee \text{F}\equiv p\end{array}$	Identity laws

   $\begin{array}{l}p\vee \text{T}\equiv \text{T}\\ p\wedge \text{F}\equiv \text{F}\end{array}$ Domination laws

   $\begin{array}{l}p\vee p\equiv p\\ p\wedge p\equiv p\end{array}$ Idempotent laws

   $\neg \left(\neg p\right)\equiv p$ Double negation law

   $\begin{array}{l}p\vee q\equiv q\vee p\\ p\wedge q\equiv q\wedge p\end{array}$ Commutative laws

   $\begin{array}{l}\left(p\vee q\right)\vee r\equiv p\vee \left(q\vee r\right)\\ \left(p\wedge q\right)\wedge r\equiv p\wedge \left(q\wedge r\right)\end{array}$ Associative laws

   $\begin{array}{l}p\vee \left(q\wedge r\right)\equiv \left(p\vee q\right)\wedge \left(p\vee r\right)\\ p\wedge \left(q\vee r\right)\equiv \left(p\wedge q\right)\vee \left(p\wedge r\right)\end{array}$ Distributive laws

   $\begin{array}{l}\neg \left(p\wedge q\right)\equiv \neg p\vee \neg q\\ \neg \left(p\vee q\right)\equiv \neg p\wedge \neg q\end{array}$ De Morgan’s laws

   $\begin{array}{l}p\vee \left(p\wedge q\right)\equiv p\\ p\wedge \left(p\vee q\right)\equiv p\end{array}$ Absorption laws

   $\begin{array}{l}p\vee \neg p\equiv \text{T}\\ p\vee \neg p\equiv \text{F}\end{array}$ Negation laws

TABLE 2 De Morgan’s Laws for Quantifiers

Negation Equivalent Statement When Is Negation True? When False?
   $\begin{array}{l}\neg \exists xP\left(x\right)\\ \neg \forall xP\left(x\right)\end{array}$
   $\begin{array}{l}\forall x\neg P\left(x\right)\\ \exists x\neg P\left(x\right)\end{array}$ For everyx,P(x) is false.

There is anxfor whichP(x) is false.

There is anxfor whichP(x) is true.

P(x) is true for everyx.

47. Show that the two statements $\neg \exists x\forall yP\left(x,y\right)$and $\forall x\exists y\neg P\left(x,y\right)$, where both quantifiers over the first variable inP(x,y) have the same domain, and both quantifiers over the second variable inP(x,y) have the same domain, are logically equivalent.

*48. Show that $\forall xP\left(x\right)\vee \forall xQ\left(x\right)$and $\forall x\forall y\left(P\left(x\right)\vee Q\left(y\right)\right)$, where all quantifiers have the same non empty domain, are logically equivalent. (The new variableyis used to combine the quantifications correctly.)

*49

a) Show that $\forall xP\left(x\right)\wedge \exists xQ\left(x\right)$is logically equivalent to $\forall x\exists y\left(P\left(x\right)\wedge Q\left(y\right)\right)$, where all quantifiers have the same nonempty domain.

b) Show that $\forall xP\left(x\right)\wedge \exists xQ\left(x\right)$is equivalent to $\forall x\exists y\left(P\left(x\right)\vee Q\left(y\right)\right)$, where all quantifiers have the same nonempty domain.