Is this proposition a tautology?

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

Knowing that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, I have come up with

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

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

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

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

If this is correct, which I am not sure it is, then I think that this is not a tautology. Can someone confirm/refute my work here?

  • 1
    $\begingroup$ This is the fallacy of denying the antecedent. $\endgroup$
    – Kenny Lau
    Apr 28, 2016 at 14:17
  • $\begingroup$ So, are you saying that my logic is incorrect, or it is not a tautology? @KennyLau $\endgroup$
    – CSstudent
    Apr 28, 2016 at 14:18
  • $\begingroup$ The proposition is the fallacy of denying the antecedent, which makes it not a tautology. $\endgroup$
    – Kenny Lau
    Apr 28, 2016 at 14:19
  • $\begingroup$ By the way, was my work correct in this problem? I know, based on what you're saying, I shouldn't have even had to work anything, but is my logic correct? @KennyLau $\endgroup$
    – CSstudent
    Apr 28, 2016 at 14:21
  • $\begingroup$ I don't think your work was correct.... $\endgroup$
    – Kenny Lau
    Apr 28, 2016 at 14:23

2 Answers 2


Consider this counterexample:

  • $p:\mathbf{F}$
  • $q:\mathbf{T}$

Then $$ [(p\to q)\land\neg p]\to\neg q\equiv[(\mathbf{F}\to\mathbf{T})\land\mathbf{T}]\to\mathbf{F}\equiv\mathbf{T}\to\mathbf{F}\equiv\mathbf{F}. $$

How did I come up with this counterexample? Consider the following: \begin{align} [(p\to q)\land\neg p]\to\neg q&\equiv \neg[(\neg p\lor q)\land\neg p]\lor\neg q\\[1em] &\equiv (p\land\neg q)\lor p\lor\neg q\\[1em] &\equiv [p\land(\neg q\lor p)]\lor\neg q\\[1em] &\equiv (p\lor\neg q)\land(\neg q\lor p)\\[1em] &\equiv p\lor\neg q. \end{align}

  • $\begingroup$ That makes sense! Thank you! $\endgroup$
    – CSstudent
    Apr 28, 2016 at 14:49
  • $\begingroup$ @CSstudent Sure thing! It helps to get really comfortable with different identities in predicate logic. Then you can do all sorts of manipulations on the fly. It also helps to assume the antecedent is true when trying to prove that a proposition is a tautology (doing so can also make it easier to find counterexamples). $\endgroup$ Apr 28, 2016 at 14:51

The proposition concerned: $$((p\rightarrow q) \land \neg p) \rightarrow \neg q$$

Applying that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, the proposition becomes: $$((\neg p \lor q) \land \neg p) \rightarrow \neg q$$

Applying again: $$\neg((\neg p \lor q) \land \neg p) \lor \neg q$$

Particularly, since we know that it is the fallacy of denying the antecedent, we know that it will be false when $p=0$ and $q=1$.

A review of your work:

Step 1: $(\neg p \lor q) \land \neg p) \rightarrow \neg q$

This is a correct usage of the rule.

Step 2: $(\neg p \lor q) \land ((\neg \neg p \lor \neg q)$

However, step 2 dealt with the parentheses incorrectly. This assumed step 1 to be: $$(\neg p \lor q) \land (\neg p \rightarrow \neg q)$$instead of: $$(\neg p \lor q) \land \neg p) \rightarrow \neg q$$which are different.

Step 3: $(\neg p \lor q) \land \neg (\neg p \lor q)$

This step forgot to change the $\lor$ to the $\land$ after applying De Morgan's laws.

Step 4: $(\neg p \lor q) \land (p \lor \neg q)$

The same goes with this step. However, the effect cancelled, making this equivalent with step 2. After all, two wrongs make a right, right?


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .