# 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! – ILoveMath Oct 23 '12 at 12:20
• Try using the contrapositive of $p\to\neg q$. – axblount Oct 23 '12 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? – Douglas S. Stones Oct 23 '12 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. – Harald Hanche-Olsen Oct 23 '12 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. – Carl Mummert Oct 23 '12 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! – user123123 Oct 23 '12 at 12:48
• The use of truth table is limited, what of if you have at least $5$ propositional variables? – Hassan Muhammad Sep 27 '14 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??? – Peter Smith Oct 23 '12 at 13:28
• @PeterSmith See Edit – Onur Oct 23 '12 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 – Flower Ahmed Oct 24 '12 at 8:23
• yes its tautology what about that [(p→¬q)∧q]→¬q is not tautology – Flower Ahmed Oct 24 '12 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. – dtldarek Oct 24 '12 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*}

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)$