Question

33. Rewrite each of these statements so that negations appear only within predicates (that is, so that no negationis outside a quantifier or an expression involving logical connectives).

a) \( \sim \forall \user1{x}\forall \user1{yP}\left( {\user1{x,y}} \right)\)

b)\( \sim \forall \user1{y}\exists \user1{xP}\left( {\user1{x,y}} \right)\)

c) \( \sim \forall \user1{x}\forall \user1{y}\left( {\user1{P}\left( {\user1{x,y}} \right) \vee \user1{Q}\left( {\user1{x,y}} \right)} \right)\)

d)\( \sim \left( {\exists \user1{x}\exists \user1{y} \sim \user1{P}\left( {\user1{x,y}} \right) \wedge \forall \user1{x}\forall \user1{yQ}\left( {\user1{x,y}} \right)} \right)\)

e) \( \sim \forall \user1{x}\left( {\exists \user1{y}\forall \user1{zP}\left( {\user1{x,y,z}} \right) \wedge \exists \user1{z}\forall \user1{yP}\left( {\user1{x,y,z}} \right)} \right)\)

Short answer

The negations of the statements are as follows,

1. \( \sim \forall x\forall \user2{yP}\left( {\user2{x,y}} \right)\) is \(\exists \user1{x}\exists \user1{y} \sim \user1{P}\left( {\user1{x, y}} \right)\)
2. \( \sim \forall y\exists \user2{xP}\left( {\user2{x,y}} \right)\)is \(\exists \user1{y}\forall \user1{x} \sim \user1{P}\left( {\user1{x, y}} \right)\)
3. \( \sim \forall y\forall \user2{x}\left( {\user2{P}\left( {\user2{x,y}} \right) \vee \user2{Q}\left( {\user2{x,y}} \right)} \right)\)is \(\exists \user1{y}\exists \user1{x}\left( { \sim \user1{P}\left( {\user1{x, y}} \right) \wedge \sim \user1{Q}\left( {\user1{x, y}} \right)} \right)\)
4. \( \sim \left( {\exists \user2{x}\exists \user2{y} \sim \user2{P}\left( {\user2{x,y}} \right) \wedge \forall \user2{x}\forall \user2{yQ}\left( {\user2{x,y}} \right)} \right)\)is\(\forall \user1{x}\forall \user1{yP}\left( {\user1{x, y}} \right) \vee \exists \user1{y}\exists \user1{x} \sim \user1{Q}\left( {\user1{x, y}} \right)\)
5. \( \sim \forall \user2{x}\left( {\exists \user2{y}\forall \user2{zP}\left( {\user2{x,y,z}} \right) \wedge \exists \user2{z}\forall \user2{yP}\left( {\user2{x,y,z}} \right)} \right)\)is\(\exists \user1{x}\left( {\forall \user1{y}\exists \user1{z} \sim \user1{P}\left( {\user1{x,y,z}} \right) \vee \forall \user1{z}\exists \user1{y} \sim \user1{P}\left( {\user1{x,y,z}} \right)} \right)\).

Step-by-step solution

Introduction to the Concept

When the negation is applied to the quantifiers,\(\forall \)quantifier becomes\(\exists \)quantifier and vice versa, i.e., quantifier\(\exists \)becomes\(\forall \)quantifier.

Solution Explanation

a)

Consider the given statement: \( \sim \forall \user1{x}\forall \user1{yP}\left( {\user1{x,y}} \right)\)

\( \sim \forall x\forall \user2{yP}\left( {\user2{x,y}} \right)\)is the negation of the preceding sentence\(\exists \user1{x}\exists \user1{y} \sim \user1{P}\left( {\user1{x, y}} \right)\)

The following is the negation of the provided statement.

\(\exists \user1{x}\exists \user1{y} \sim \user1{P}\left( {\user1{x, y}} \right)\)

Solution Explanation

b)

Consider the given statement: \( \sim \forall \user1{y}\exists \user1{xP}\left( {\user1{x,y}} \right)\)

\( \sim \forall y\exists \user2{xP}\left( {\user2{x,y}} \right)\)is the negation of the preceding sentence\(\exists \user1{y}\forall \user1{x} \sim \user1{P}\left( {\user1{x, y}} \right)\)

The following is the negation of the provided statement.

\(\exists \user1{y}\forall \user1{x} \sim \user1{P}\left( {\user1{x, y}} \right)\)

Solution Explanation

c)

Consider the given statement: \( \sim \forall \user1{x}\forall \user1{y}\left( {\user1{P}\left( {\user1{x,y}} \right) \vee \user1{Q}\left( {\user1{x,y}} \right)} \right)\)

\( \sim \forall y\forall \user2{x}\left( {\user2{P}\left( {\user2{x,y}} \right) \vee \user2{Q}\left( {\user2{x,y}} \right)} \right)\)is the negation of the preceding sentence\(\exists \user1{y}\exists \user1{x}\left( { \sim \user1{P}\left( {\user1{x, y}} \right) \wedge \sim \user1{Q}\left( {\user1{x, y}} \right)} \right)\)

The following is the negation of the provided statement.

\(\exists \user1{y}\exists \user1{x}\left( { \sim \user1{P}\left( {\user1{x, y}} \right) \wedge \sim \user1{Q}\left( {\user1{x, y}} \right)} \right)\).

Solution Explanation

d)

Consider the given statement: \( \sim \left( {\exists \user1{x}\exists \user1{y} \sim \user1{P}\left( {\user1{x,y}} \right) \wedge \forall \user1{x}\forall \user1{yQ}\left( {\user1{x,y}} \right)} \right)\)

\( \sim \left( {\exists \user2{x}\exists \user2{y} \sim \user2{P}\left( {\user2{x,y}} \right) \wedge \forall \user2{x}\forall \user2{yQ}\left( {\user2{x,y}} \right)} \right)\)is the negation of the preceding sentence\(\forall \user1{x}\forall \user1{yP}\left( {\user1{x, y}} \right) \vee \exists \user1{y}\exists \user1{x} \sim \user1{Q}\left( {\user1{x, y}} \right)\)

The following is the negation of the provided statement.

\(\forall \user1{x}\forall \user1{yP}\left( {\user1{x, y}} \right) \vee \exists \user1{y}\exists \user1{x} \sim \user1{Q}\left( {\user1{x, y}} \right)\).

Solution Explanation

e)

Consider the given statement: \( \sim \forall \user1{x}\left( {\exists \user1{y}\forall \user1{zP}\left( {\user1{x,y,z}} \right) \wedge \exists \user1{z}\forall \user1{yP}\left( {\user1{x,y,z}} \right)} \right)\)

\( \sim \forall \user2{x}\left( {\exists \user2{y}\forall \user2{zP}\left( {\user2{x,y,z}} \right) \wedge \exists \user2{z}\forall \user2{yP}\left( {\user2{x,y,z}} \right)} \right)\)is the negation of the preceding sentence\(\exists \user1{x}\left( {\forall \user1{y}\exists \user1{z} \sim \user1{P}\left( {\user1{x,y,z}} \right) \vee \forall \user1{z}\exists \user1{y} \sim \user1{P}\left( {\user1{x,y,z}} \right)} \right)\)

The following is the negation of the provided statement.

\(\exists \user1{x}\left( {\forall \user1{y}\exists \user1{z} \sim \user1{P}\left( {\user1{x,y,z}} \right) \vee \forall \user1{z}\exists \user1{y} \sim \user1{P}\left( {\user1{x,y,z}} \right)} \right)\).