Choosing equivalent quantifier expressions

24 Views Asked by At

Which of the following expressions are equivalent to $∃x∀y(P(x,y)∧¬Q(x,y))$

  1. $¬∀x∃y(¬P(x,y)∨Q(x,y))$

  2. $∃x∀y¬(¬P(x,y)∨Q(x,y))$

  3. $∀x∃y(P(x,y)∨¬Q(x,y))$

  4. $∃x∀y(¬P(x,y)∨Q(x,y))$

I chose 1 and 2. 1 due to the negation in front of the first universal quantifier symbol and 2 because of the negation in front of $(¬P(x,y)∨Q(x,y))$. Can someone verify my answers?

1

There are 1 best solutions below

0
On

Yes, so far your answers are correct.

Your answer could be improved by arguing why 3. and 4. are not equivalent to the original formulation. You can do this by finding an example for $P$ and $Q$ such that the results of 3. and 1. or 3. and 4. differ.