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

Question

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?

Answer 1

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.

Answer 2

I hope this will help you:

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.

Answer 3

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.

Answer 4

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!

Answer 5

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.

Answer 6

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.

You can read more about this method in the Handbook of Tableau Methods .

I hope that helps :)

---

NB: the code for the diagram above is here.

Answer 7

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*}

Answer 8

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