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

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'

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))$$

• Thank you, I understood the method with multiple quantifiers, but I cannot understand why is it approximated. "these are not equivalences in the strict sense of logical equivalence", Can you explain or provide some links ? – Mathews George Dec 25 '18 at 6:06

$$\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)$$