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


$[(\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$

  • 1
    $\begingroup$ I went through your reasoning, and it all looks fine to me! $\endgroup$ – 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.


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.