1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This is the fallacy of denying the antecedent. $\endgroup$ – Kenny Lau Apr 28 '16 at 14:17
  • $\begingroup$ So, are you saying that my logic is incorrect, or it is not a tautology? @KennyLau $\endgroup$ – CSstudent Apr 28 '16 at 14:18
  • $\begingroup$ The proposition is the fallacy of denying the antecedent, which makes it not a tautology. $\endgroup$ – Kenny Lau Apr 28 '16 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 '16 at 14:21
  • $\begingroup$ I don't think your work was correct.... $\endgroup$ – Kenny Lau Apr 28 '16 at 14:23
2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ That makes sense! Thank you! $\endgroup$ – CSstudent Apr 28 '16 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$ – Daniel W. Farlow Apr 28 '16 at 14:51
1
$\begingroup$

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?

$\endgroup$

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.