How would I match up the following sentences with their respective negations?

Question

This is supposed to be done with logical identities and the rules for negation with quantifiers.

A-D are the sentences and 1-4 are the negations.

A) ∀x(P(x) ∧ [(∃yP(y)) ∧ (∃yR(x, y)) ⇒ (∃yP(y))])

B) ∀x∀y(¬R(x, y) ∨ ¬P(x))

C) ∀x(P(x) ⇔ ∃yR(x, y))

D) ∀x∀y(P(x) ∧ R(x, y) ⇒ R(y, x))

1) ∃x∃y(P(x) ∧ R(x, y) ∧ ¬R(y, x))

2) ∃x([P(x) ∨ ∃yR(x, y)] ∧ [¬P(x) ∨ ∀y¬R(x, y)])

3) ∃x∃y(P(x) ∧ R(x, y))

4) ∃x¬P(x)

Intuitively, it seems that A and C are supposed to match with one of 2 or 4 and B and D are supposed to match with one of 1 and 3. I might be wrong though.

I have tried to use these basic formulas:

¬∀xP(x) = ∃x¬P(x) and ¬∃xP(x) = ∀x¬P(x)

but the expressions above seem the be much longer and seem to involve far more manipulation.

Any help?

Answer 1

In addition to those quantifier negation rules, you can also use the good old propositional logic equivalences, such as Commutation, Association, DeMorgan's Laws, laws for rewriting biconditionals and conditionals, etc.

For example, let's take B) and negate it:

$$\neg \forall x \forall y (\neg R(x,y) \lor \neg P(x)) \Leftrightarrow \text{ (Quantifier Negation)}$$

$$\exists x \exists y \neg (\neg R(x,y ) \lor \neg P(x)) \Leftrightarrow \text{ (DeMorgan)}$$

$$\exists x \exists y (R(x,y) \land P(x)) \Leftrightarrow \text{ (Commutation)}$$

$$\exists x \exists y (P(x) \land R(x,y))$$

OK, so that matches 3 ... can you do the others?

...

OK, you matched D correctly with 1. I would show a few more steps though:

$$\neg \forall x \forall y ((P(x) \land R(x,y)) \rightarrow R(y,x)) \Leftrightarrow \text{ (Quantifier Negation)}$$

$$\exists x \exists y \neg ((P(x) \land R(x,y)) \rightarrow R(y,x)) \Leftrightarrow \text{ (Implication)}$$

$$\exists x \exists y \neg (\neg (P(x) \land R(x,y)) \lor R(y,x)) \Leftrightarrow \text{ (DeMorgan)}$$

$$\exists x \exists y ((P(x) \land R(x,y)) \land \neg R(y,x))$$

For C, it's a good idea to rewrite the biconditional, since none of 1 through 4 contain a biconditional:

$$\neg \forall x (P(x) \leftrightarrow \exists y R(x,y)) \Leftrightarrow \text{ (Quantifier Negation)}$$

$$\exists x \neg (P(x) \leftrightarrow \exists y R(x,y)) \Leftrightarrow \text{ (Equivalence)}$$

$$\exists x \neg ((P(x) \land \exists y R(x,y)) \lor (\neg P(x) \land \neg \exists y R(x,y)))$$

... can you take it from here?

Answer 2

I have managed to come up with proofs for D and C, but I only managed to do the quantifier negation of A.

Could you be so kind to verify that my proofs for D and C are correct and possibly how I could proceed with the proof of A. Each of the proofs begin with their respective letter. Thank you so much!