How to express propositional functions with multiple quantifiers using "AND" and "OR'?

Question

Consider the quantifier "for every" , it simply means variable '$x$' has to be true for all values of '$x$' upon a propositional function $P(x)$. So we could 'AND' all the values from domain of 'x' and find whether its true.

For example: $\forall x[P(x)]$ is equivalent to : $P(x_1) \land P(x_2) \land \dots \land P(x_n)$

Similar case for "there exists", atleast one of them has to be true. So OR could be used

$\exists x[P(x)]$ is equivalent to : $P(x_1) \lor P(x_2) \lor \dots \lor P(x_n)$

What I am asking is when it comes to proposition involving more than one quantifiers. How to express it in above form ?

For example, consider a proposition involving 2 variables $P(x,y)$. Consider $\exists x \forall x[P(x,y)]$. How can I write it using 'AND' and 'OR'

Answer 1

First of all, please know that these are not equivalences in the strict sense of logical equivalence ... with $n$ terms in $P(x_1) \land ... \land P(x_n)$ the best we can say is that that statement will have the same truth-value as $\forall x \ P(x)$ for any domain with $n$ elements, and where $x_1$, $x_2$ ... are treated as constants that respectively denote each of those $n$ different objects. Indeed, to make that clear, I would use $c_i$'s rather than $x_i$'s

Still, as long as you are careful and understand this restriction, you can indeed usefully work with this 'equivalence' ... which I'll denote by $\approx$

Now to your question. If you have multiple quantifiers you can just work them out step by step:

$$\exists x \forall y \ P(x,y)\approx$$

$$\forall y \ P(c_1,y) \lor \forall y \ P(c_2,y) \lor .... \lor \forall y \ P(c_n,y) \approx$$

$$(P(c_1,c_1) \land P(c_1,c_2) \land ...P(c_1,c_n)) \lor (P(c_2,c_1) \land P(c_2,c_2) \land ...P(c_2,c_n)) \land .... \land (P(c_n,c_1) \land P(c_n,c_2) \land ...P(c_n,c_n))$$

You can also work this out inside out:

$$\exists x \forall y \ P(x,y)\approx$$

$$\exists x (P(x,c_1) \land P(x,c_2)\land ... \land P(x,c_n)\approx$$

$$(P(c_1,c_1) \land P(c_1,c_2) \land ...P(c_1,c_n)) \lor (P(c_2,c_1) \land P(c_2,c_2) \land ...P(c_2,c_n)) \land .... \land (P(c_n,c_1) \land P(c_n,c_2) \land ...P(c_n,c_n))$$

Answer 2

$$\bigl(P(x_1,y_1)\land \ldots\land P(x_1,y-n)\bigr)\lor\bigl(P(x_2,y_1)\land\ldots\land P(x_2,y_n)\bigr)\lor\ldots\lor\bigl(P(x_n,y-1)\land\ldots P(x_n,y_n)\bigr) $$