Find the negation of the following quantified sentence $(∀x)(p(x)∨q(x)→¬q(x))$

Question

I'm trying to deny a quantified sentence.

My attempt:

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

So:

$$(∀x)(p(x)∨q(x)→¬q(x))$$

Denying:

$$(∃x) (p(x) ∧ ~q(x) ∧ q(x))$$

Notes:

$\lnot(∀)$ = $∃$
$\lnot(∨)$ = $∧$
$\lnot(→)$ = $∧$
$\lnot(¬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 1

I confirm the conclusion of @MauroALLEGRANZA, using the definition of $P\to Q$, which is $(\lnot P)\vee Q$.

So, since $\forall x\;(p(x)\vee q(x)\to \lnot q(x)$ is the same as $\forall x\;\lnot(p(x)\vee q(x))\vee \lnot q(x)$, its negation is $$\exists x\:\lnot\lnot\bigl(p(x)\vee q(x)\bigr)\wedge\lnot \lnot q(x),\quad \text{i.e.}\quad \exists x\:\bigl(p(x)\vee q(x)\bigr)\wedge q(x). $$

Answer 2

With these types of problems you want to keep in mind logical equivalences. Also, when negating everything you want all the logical operators to be $\land$ or $\lor$. As I noted in the comments, $p\to q \equiv \lnot p \lor q$.

$1. \forall x((p(x) \lor q(x)) \to \lnot q(x)) \\ \text{Lets focus on changing the implies operator ($\to$) to its logical equivalent.} \\ (p(x) \lor q(x)) \to \lnot q(x) \equiv \lnot(p(x) \lor q(x)) \lor \lnot q(x) \equiv (\lnot p(x) \land \lnot q(x)) \lor \lnot q(x)\\ \text{Now sub this logical equivalent back into our statement.} \\ 2. \forall x ((\lnot p(x) \land \lnot q(x)) \lor \lnot q(x)) \\ \text{Start the negation.} \\ 3.\lnot \forall x ((\lnot p(x) \land \lnot q(x)) \lor \lnot q(x)) \\ 4.\exists x \lnot ((\lnot p(x) \land \lnot q(x)) \lor \lnot q(x)) \\ 5.\exists x(\lnot(\lnot p(x) \land \lnot q(x)) \land \lnot\lnot q(x)) \\ 6. \exists x((\lnot\lnot p(x) \lor \lnot\lnot q(x)) \land q(x)) \\ \boxed{7. \exists x ((p(x) \lor q(x)) \land q(x)).} $

Answer 3

Notes:

$\lnot(∨)$ = $∧$

Not quite: the negation of $$A\lor B$$ is $$\lnot A \land\lnot B.$$ Remember, you are negating a sentence, not merely its main logical connective.

$\lnot(→)$ = $∧$

Not quite: the negation of $$A\to B$$ is $$A\land\lnot B.$$

$\lnot(∀)$ = $∃$

Not quite: the negation of $\lnot∀x A(x)$ is $∃x\lnot A(x).$

$\lnot(¬q(x))$ = $q(x)$

Correct.

So:

$$(∀x)(p(x)∨q(x)→¬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 $$∀x\Big(\big(p(x)∨q(x)\big)→¬q(x)\Big)$$ (I removed the unnecessary parentheses around the quantifier).

Denying:

$$(∃x) (p(x) ∧ ~q(x) ∧ q(x))$$

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

Answer 4

You are doing something weird, which is to regard the negation as an operation over operators alone, but that is not a good way to think about it. Yes, when you negate a sentence, you pay attention to what kind of sentence it is (i.e. what is the main operator), but applying the negation to that sentence does not just effect the operator, but it can also effect its operands.

For example, if you think $\neg (\land) = \lor$, then you might be inclined to say: $\neg (A \land B) = A (\neg \land) B = A \lor B$, but that is not correct: you also have to negate the operands, so you get $\neg (A \land B) = \neg A \lor \neg B$

Likewise, you should not do $\neg \forall x P(x) = (\neg \forall) x P(x) = \exists x P(x)$, because the correct answer is that $\neg \forall x P(x) = \exists x \neg P(x)$

"Ah!", you may say: "So I have to negate the operands as well!". That is, maybe we can just stick to the $\neg (*) = *'$ schema, but we just need to make sure that something like $\neg A * B = \neg A *' \neg B$, and that (for a one-place operator) $\neg * A = *' \neg A$.

But that doesn't work either, because now you would have that $\neg \neg A = (\neg (\neg)) \neg A = \neg A$

And (as you yourself noticed) neither one works for the $\to$: there is really no 'nice' operator $*$ such that $\neg (A \to B) = A * B$ or $\neg (A \to B) =\neg A * \neg B$

Long story short: negations apply to whole statements, not just the operator!

Other answer will tell you the details for how to work out the negations involving various operators, but I just want to correct the more conceptual mistake you seem to be making.