0
$\begingroup$

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'

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Mathews George Dec 25 '18 at 6:06
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.