# How can I Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology?

Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology Laws of logic

I tried prove it by using truth table but it didn't produce a tautology.

This is my work so far: $$[(p \to \neg q) \wedge q] \to \neg p\\ [(\lnot p \vee \lnot q) \wedge q] → \lnot p\\ \lnot [(\lnot p \vee \lnot q) \wedge q] \vee \lnot p\\ [\lnot (\lnot p \vee \lnot q) \vee \lnot q] \vee \lnot p\\ [(p ∧ q) \vee \lnot q ] \vee \lnot p\\$$

Can anyone help me?

• I think using truth tables would be easier! Oct 23, 2012 at 12:20
• Try using the contrapositive of $p\to\neg q$. Oct 23, 2012 at 12:22
• Hold on... Did you just say "truth tables imply it's not a tautology"? And now you want to prove it is a tautology? Oct 23, 2012 at 12:27
• It all depends on exactly which axiomatization of predicate logic you're working within. The best answer also depends on what auxiliary rules of inference you already have available. Probably the easiest is to assume both p and [(p → ¬q) ∧ q], and derive a contradiction. Oct 23, 2012 at 12:36
• I undid an edit by Flower Ahmed that changed the $\lnot p$ to $\lnot q$. On one hand the answers were already written for the original question, and on the other hand the new formula is no longer a tautology, so it would be impossible to prove it is a tautology. Oct 23, 2012 at 14:12

First off: apologies for the formatting of this, I have absolutely no idea how to make a table! Hopefully it'll still be clear enough.

$$\begin{array}{cccc|cc|c} p & q & ¬p & ¬q & (p\rightarrow ¬q) & (p\rightarrow¬q)∧q & (p\rightarrow¬q)∧q\rightarrow¬p\\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 1 & 0 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{array}$$

And so it's a tautology. Alternatively, if this is from a formal logic course, you're going to want to show $\vDash ((p\rightarrow ¬q)∧q)\rightarrow ¬p)$, which should be simple enough at least for propositional logic. However, I've not done any logic in a good while, so I wouldn't want to try and attempt that off the top of my head. Or if you're that far, you could do a formal proof using NNO to resemble a proof by contradiction and then use the completeness theorem to transfer that over.

• That looks much better, thanks axblount! Oct 23, 2012 at 12:48
• The use of truth table is limited, what of if you have at least $5$ propositional variables? Sep 27, 2014 at 6:43

If $[(p \to\neg q) \wedge q] \Rightarrow \neg p$, then $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology.

$$\begin{array}{c|cc} 1 & (p \to\neg q) \wedge q\\ \hline 2 & p \to\neg q &\hspace{1cm}\text{1. Simplification}\\ 3 & q &\hspace{1cm}\text{1. Simplification}\\ 4 & \neg\neg q \to\neg p &\hspace{1cm}\text{2. Contrapositive}\\ 5 & \neg \neg q &\hspace{1cm}\text{3. Double negation}\\ \hline 6 & \neg p &\hspace{1cm}\text{4. & 5. Modus Ponens}\\ \end{array}$$

We see now that $[(p \to\neg q) \wedge q] \Rightarrow \neg p$ . Therefore $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology.

• What Double Negation rule is being used in getting from 4 to 5??? Oct 23, 2012 at 13:28
• @PeterSmith See Edit
– Onur
Oct 23, 2012 at 13:36

Call $r = [(p \to ¬q) \wedge q]$ and use first the fact that $[a \to b] = [\neg a \vee b]$ for every $a$ and $b$ and then the fact that $[(a \vee b) \wedge c] = [(a \wedge c) \vee (b \wedge c)]$ for every $a$, $b$ and $c$.

This yields $r = [(\neg p \vee \neg q) \wedge q] = [(\neg p \wedge q) \vee (\neg q \wedge q)] = (\neg p \wedge q)$ since $(\neg q \wedge q) = 0$ and $[a \vee 0] = a$ for every $a$. Thus, one is asked to prove that $[(\neg p \wedge q) → \neg p]$ is always true, which is indeed a tautology.

This is a tautology, simple proof by Curry-Howard isomorphism is as follows: $$\lambda (a,q).\ \lambda p.\ a\ p\ q$$

More involved proof by reasoning:

There is only single possibility for the formula to be false: $$[(p → ¬q) ∧ q] → ¬p$$

• we need $p$ to be true (because of right side of implication),
• and $q$ to be true (because of conjunction).

Still, in this setting $p \to \neg q$ is false, so the conjunction is false and whole formula is true, hence a tautology.

Cheers!

• what about when p is false and q is true-- this lead as to p→¬q to be true and conjunction also true then the whole formula is false Oct 24, 2012 at 8:23
• yes its tautology what about that [(p→¬q)∧q]→¬q is not tautology Oct 24, 2012 at 8:36
• @FlowerAhmed In this case $p$ is false, so $\neg p$ is true and the implication is true regardless of its left-hand side. As for your second comment, for following the reasoning schema you get that $q$ needs to be true, and then you can set $p$ to true, which will make the conjunction and hence the whole formula false. Therefore, the second formula is not a tautology. Oct 24, 2012 at 9:03 This was done using Fitch. Assume that the statement you want to prove is false. Show that this assumption entails a contradiction. From here you can reject the original assumption, proving the statement to be true. The statement is a tautology because it can be proved without any premises; it is true by virtue of its true functional connectives.

One way to see this is with the method of analytic tableaux. You start with the negation of $$((p\to\neg q)\wedge q)\to\neg p\tag{1}$$ then apply a series of contradiction-hunting rules to get a tableau, like so ,

which is closed (i.e., each path ends in a contradiction), meaning that our original formula, $(1)$, was indeed a tautology.

I hope that helps :)

NB: the code for the diagram above is here.

I think this answer may be simpler... \begin{equation*} \begin{split} [(p\to \neg p)\wedge q ]\to \neg p & \equiv [(\neg p\vee \neg q)\wedge q]\to \neg p \quad \text{by implication rule}\\ &\equiv [(\neg p\wedge q)\vee(\neg q\wedge q)]\to \neg p \quad \text{by distributive rule}\\ & \equiv [(\neg p\wedge q)\vee F]\to \neg p \quad\text{by negation rule}\\ & \equiv (\neg p\wedge q)\to \neg p\quad\text{by identity rule}\\ & \equiv \neg(\neg p\wedge q)\vee \neg p\quad\text{by implication rule}\\ & \equiv (p\vee \neg q)\vee \neg p\quad\text{by De Morgan's and double negation rules}\\ & \equiv (p\vee \neg p)\vee \neg q\quad\text{by associativity and commutative rules}\\ & \equiv T\vee \neg q\quad\text{by negation rule}\\ & \equiv T \quad\text{by domination rule}\\ \end{split} \end{equation*}

• 6 years late, you have a typo in your answer, it's $p \to \neg q$.
– user757852
Nov 17, 2020 at 20:11

Just applying the disrubutive laws on you last line we get:

1.$[(p \wedge q) \vee¬ q ] \vee ¬p$

2.$((\lnot q\vee p)\wedge (\lnot q\vee q))\vee \lnot p$

Then cancelling $\lnot q \vee q$

3.$\lnot q\vee p\vee \lnot p$

which is clearly a tautology.

The distrubutive laws I used here are:

Double Negation:

1. $p\leftrightarrow \lnot(\lnot p)$

$\vee$ Distribution

1. $(p \vee (q\wedge r))\leftrightarrow (p \vee q) \bigwedge (p\vee r)$