Damon Stokes

Answered

2022-06-24

Find the negation of the following quantified sentence $(\forall x)(p(x)\vee q(x)\to \neg q(x))$

My attempt:

To negate a quantified sentence, I just need to change the quantifier and connectives.

So: $(\forall x)(p(x)\vee q(x)\to \neg q(x))$

Denying: $(\exists x)(p(x)\wedge \text{}q(x)\wedge q(x))$

$\neg (\forall )=\exists $

$\neg (\vee )=\wedge $

$\neg (\to )=\wedge $

$\neg (\neg q(x))=q(x)$

I'm pretty sure that my solution is correct, the problem is that the denial of the conditional connective is causing me doubts.

My attempt:

To negate a quantified sentence, I just need to change the quantifier and connectives.

So: $(\forall x)(p(x)\vee q(x)\to \neg q(x))$

Denying: $(\exists x)(p(x)\wedge \text{}q(x)\wedge q(x))$

$\neg (\forall )=\exists $

$\neg (\vee )=\wedge $

$\neg (\to )=\wedge $

$\neg (\neg q(x))=q(x)$

I'm pretty sure that my solution is correct, the problem is that the denial of the conditional connective is causing me doubts.

Answer & Explanation

Angelo Murray

Expert

2022-06-25Added 23 answers

Step 1

Notes: $\neg (\vee )=\wedge $

Not quite: the negation of $A\vee B$ is $\mathrm{\neg}A\wedge \mathrm{\neg}B.$.

Remember, you are negating a sentence, not merely its main logical connective.

$\mathrm{\neg}(\to )$

Not quite: the negation of $A\to B$ is $A\wedge \mathrm{\neg}B.$

$\mathrm{\neg}(\forall )$

Not quite: the negation of $\mathrm{\neg}\forall xA(x)$ is $\exists x\mathrm{\neg}A(x).$.

$\mathrm{\neg}(\neg q(x))$

Correct.

Step 2

So: $(\forall x)(p(x)\vee q(x)\to \neg q(x))$

Liberally inserting parentheses helps disambiguate sentences. In any case, the precedence of logical connectives dictates that this sentence ought to be read as $\forall x{\textstyle (}{\textstyle (}p(x)\vee q(x){\textstyle )}\to \neg q(x){\textstyle )}$

(I removed the unnecessary parentheses around the quantifier).

Denying: $(\exists x)(p(x)\wedge \text{}q(x)\wedge q(x))$

This is incorrect, as pointed out in the comments and other answers. My above corrections make clear why.

Notes: $\neg (\vee )=\wedge $

Not quite: the negation of $A\vee B$ is $\mathrm{\neg}A\wedge \mathrm{\neg}B.$.

Remember, you are negating a sentence, not merely its main logical connective.

$\mathrm{\neg}(\to )$

Not quite: the negation of $A\to B$ is $A\wedge \mathrm{\neg}B.$

$\mathrm{\neg}(\forall )$

Not quite: the negation of $\mathrm{\neg}\forall xA(x)$ is $\exists x\mathrm{\neg}A(x).$.

$\mathrm{\neg}(\neg q(x))$

Correct.

Step 2

So: $(\forall x)(p(x)\vee q(x)\to \neg q(x))$

Liberally inserting parentheses helps disambiguate sentences. In any case, the precedence of logical connectives dictates that this sentence ought to be read as $\forall x{\textstyle (}{\textstyle (}p(x)\vee q(x){\textstyle )}\to \neg q(x){\textstyle )}$

(I removed the unnecessary parentheses around the quantifier).

Denying: $(\exists x)(p(x)\wedge \text{}q(x)\wedge q(x))$

This is incorrect, as pointed out in the comments and other answers. My above corrections make clear why.

Lovellss

Expert

2022-06-26Added 5 answers

Step 1

Using the definition of $P\to Q$, which is $(\mathrm{\neg}P)\vee Q$.

Step 2

So, since $\mathrm{\forall}x\phantom{\rule{thickmathspace}{0ex}}(p(x)\vee q(x)\to \mathrm{\neg}q(x)$ is the same as $\mathrm{\forall}x\phantom{\rule{thickmathspace}{0ex}}\mathrm{\neg}(p(x)\vee q(x))\vee \mathrm{\neg}q(x)$, its negation is $\mathrm{\exists}x\phantom{\rule{mediummathspace}{0ex}}\mathrm{\neg}\mathrm{\neg}{\textstyle (}p(x)\vee q(x){\textstyle )}\wedge \mathrm{\neg}\mathrm{\neg}q(x),\phantom{\rule{1em}{0ex}}\text{i.e.}\phantom{\rule{1em}{0ex}}\mathrm{\exists}x\phantom{\rule{mediummathspace}{0ex}}{\textstyle (}p(x)\vee q(x){\textstyle )}\wedge q(x).$

Using the definition of $P\to Q$, which is $(\mathrm{\neg}P)\vee Q$.

Step 2

So, since $\mathrm{\forall}x\phantom{\rule{thickmathspace}{0ex}}(p(x)\vee q(x)\to \mathrm{\neg}q(x)$ is the same as $\mathrm{\forall}x\phantom{\rule{thickmathspace}{0ex}}\mathrm{\neg}(p(x)\vee q(x))\vee \mathrm{\neg}q(x)$, its negation is $\mathrm{\exists}x\phantom{\rule{mediummathspace}{0ex}}\mathrm{\neg}\mathrm{\neg}{\textstyle (}p(x)\vee q(x){\textstyle )}\wedge \mathrm{\neg}\mathrm{\neg}q(x),\phantom{\rule{1em}{0ex}}\text{i.e.}\phantom{\rule{1em}{0ex}}\mathrm{\exists}x\phantom{\rule{mediummathspace}{0ex}}{\textstyle (}p(x)\vee q(x){\textstyle )}\wedge q(x).$

Most Popular Questions