# 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! –  Mann 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
show 1 more comment

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! –  Peter Oct 23 '12 at 12:48

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 is $[(p \to\neg q) \wedge q] \to \neg p$ 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 → ¬q) ∧ q] and use first the fact that [a → b] = [¬a v b] for every a and b and then the fact that [(a v b) ∧ c] = [(a ∧ c) v (b ∧ c)] for every a, b and c.

This yields r = [(¬p v ¬q) ∧ q] = [(¬p ∧ q) v (¬q ∧ q)] = (¬p ∧ q) since (¬q ∧ q) = 0 and [a v 0] = a for every a. Thus, one is asked to prove that [(¬p ∧ q) → ¬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

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