I was given to show whether the following argument $$ \neg q,p\to q \vdash \neg q $$ is valid.

I believe it is invalid, as the correct implication is $\neg p$, according to Modus Tollens.

However, I cannot find an error in the following "justification" that seemingly establishes that the argument is valid: \begin{align} (\neg q \land (p \to q)) \to \neg q &\equiv (\neg q \land (\neg p \lor q )) \to \neg q \\ &\equiv ((\neg q \land \neg p) \lor (\neg q \land q)) \to \neg q \\ &\equiv ((\neg q \land \neg p) \lor F) \to \neg q \\ &\equiv (\neg q \land \neg p) \to \neg q \\ &\equiv \neg(\neg q \land \neg p) \lor \neg q \\ &\equiv (q \lor p) \lor \neg q \\ &\equiv q \lor \neg q \lor p \\ &\equiv T \lor p \\ &\equiv T. \end{align} Edit: Okay, so it is apparently valid, and there probably isn't an error in my justification.


Of course it is valid: the conclusion is exactly the same as one of the premises, and so it certainly follows from the premises!

And indeed your justification is perfectly correct ... though exploiting the fact that the conclusion is one of the premises it can be done a bit more quickly:

$$(\neg q \land (p \rightarrow q)) \rightarrow \neg q \equiv$$

$$\neg (\neg q \land (p \rightarrow q)) \lor \neg q \equiv$$

$$q \lor \neg (p \rightarrow q) \lor \neg q \equiv$$

$$q \lor \neg q \lor \neg (p \rightarrow q) \equiv$$

$$\top \lor \neg (p \rightarrow q) \equiv$$



The error is in presuming that there can be only one valid conclusion from a set of premises.   There can be several.   Further, we can always conclude a premise when we assume the premise (it is the rule of Restatement, aka Identity: $\alpha\vdash\alpha$).

$\neg q, p\to q\vdash \neg p$ is valid.   Via modus tollens or "deny the consequent".

$\neg q, p\to q\vdash \neg q$ is also valid.   Via restatement.

$\neg q, p\to q\vdash p\to q$ is valid, as well.   Via restatement.

$\neg q, p\to q\vdash \neg q\to \neg p$ is valid, too.   Via contraposition.


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.