# Determining the truth value of certain quantifiers based on this proposition being false.

Can you help me verify if I answered this question correctly?

Consider

$[(\forall x)(P(x)) \land (\exists x)(\lnot Q(x))] \implies \{(\forall x)(P(x)) \iff [\lnot(\forall x)(R(x)) \lor (\exists x)(S(x))]\}$

If you know that this proposition is false, then determine the truth values of the following:

$(\forall x)(P(x))$

$(\forall x)(Q(x))$

$(\exists x)(\lnot R(x))$

$(\exists x)(S(x))$

Since we know that this implication is false, it must be of the form $V_0\implies F_0$

Since the rightmost proposition is false, we should negate it. That is to say,

$\lnot \{(\forall x)(P(x)) \iff [\lnot(\forall x)(R(x)) \lor (\exists x)(S(x))]\}$

The negation of $P \iff Q$ is $(P \land \lnot Q) \lor (\lnot P \land Q)$, so the above becomes this:

$\{(\forall x)(P(x)) \land \lnot[\lnot(\forall x)(R(x)) \lor (\exists x)(S(x))]\} \lor \{\lnot(\forall x)(P(x)) \land [\lnot(\forall x)(R(x)) \lor (\exists x)(S(x))]\}$

$\{(\forall x)(P(x)) \land [(\forall x)(R(x)) \land \lnot (\exists x)(S(x))]\} \lor \{\lnot(\forall x)(P(x)) \land [\lnot(\forall x)(R(x)) \lor (\exists x)(S(x))]\}$

$\{(\forall x)(P(x)) \land [(\forall x)(R(x)) \land (\forall x)(\lnot S(x))]\} \lor \{(\exists x)(\lnot P(x)) \land [(\exists x)(\lnot R(x)) \lor (\exists x)(S(x))]\}$

Now, if you look at the rightmost part of this disjunction, you will see that we got a conjunction. One of the propositions in this conjunction is $(\exists x)(\lnot P(x))$, but that happens to be false because we know that $(\forall x)(P(x))$. So the whole conjunction is false, and by disjunctive syllogism we end up with only the leftmost part of the disjunction:

$\{(\forall x)(P(x)) \land [(\forall x)(R(x)) \land (\forall x)(\lnot S(x))]\}$

At the end, we got all of these facts:

$(\forall x)(P(x)) \land (\exists x)(\lnot Q(x)) \land (\forall x)(R(x)) \land (\forall x)(\lnot S(x))$

So the answers to the question would be:

$(\forall x)(P(x)) \equiv V_0$

$(\forall x)(Q(x)) \equiv F_0$

$(\exists x)(\lnot R(x)) \equiv F_0$

$(\exists x)(S(x)) \equiv F_0$

• I went through your reasoning, and it all looks fine to me! – Danu Sep 29 '13 at 23:16

You can use Wolfram Alpha to generate a truth table, provided you know the correct syntax. Here is the table for your schema.

We identify $$p = (\forall x) P(x)$$ $$q = (\forall x) Q(x)$$ $$r = (\forall x) R(x)$$ $$s = (\exists x) S(x)$$

The table shows that there is only 1 assignment that makes the statement false, namely $$p \equiv T, \ q \equiv F, \ r\equiv T, \ s \equiv F$$ which gives $$(\forall x) P(x) \equiv T$$ $$(\forall x) Q(x) \equiv F$$ $$\neg (\forall x) R(x) \equiv (\exists x)(\neg R(x)) \equiv F$$ $$(\exists x) S(x) \equiv F$$ the same as you surmised originally.

Your reasoning looks fine to me. For comparison, here is a calculational approach which may shed some additional light.

\newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\then}{\mathrel{\Rightarrow}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}}First, let's simplify things by abbreviating the "target expressions" $\;(\forall x)(P(x))\;$, $\;(\forall x)(Q(x))\;$, $\;(\exists x)(\lnot R(x))\;$, and $\;(\exists x)(S(x))\;$ as $\;p\;$, $\;q\;$, $\;r\;$, and $\;s\;$, respectively. By several appeals to DeMorgan, that allows us to write the original proposition as $$\tag 0 p \land \lnot q \;\then\; (p \;\equiv\; r \lor s)$$ which is a lot easier on the eyes.

What does it mean for $\ref 0$ to be false? Let's calculate:

$$\calc \lnot(p \land \lnot q \;\then\; (p \;\equiv\; r \lor s)) \calcop\equiv{use antecedent \;p\; in the consequent of \;\then\;; simplify \;\true \equiv X\; to \;X\;} \lnot(p \land \lnot q \;\then\; r \lor s) \calcop\equiv{write \;X \then Y\; as \;\lnot X \lor Y\;; DeMorgan} \lnot(\lnot p \lor q \lor r \lor s) \calcop\equiv{DeMorgan} p \land \lnot q \land \lnot r \land \lnot s \endcalc$$

Therefore $\ref 0$ being false implies, and is even equivalent to, $\;p\;$ being true and $\;q\;$, $\;r\;$ and $\;s\;$ all being false.