Showing tautology ((q and(p implies ~q)) implies ~p)

Question

Im having difficulty with this. Ive been able to go from

((q and(p implies ~q)) implies ~p) to ~(~p and q) or ~p

Not sure whats next. Can I get some help please.

Answer 1

There are many ways to show that the following is a tautology. There are five example techniques, however, the last one is just a kind of teaser.

$$q \land(p \implies \neg q) \implies \neg p$$

1. Brute-force checking, there are only 2 variables, so only $4 = 2^2$ possibilities to check.

2. Use the fact that $$\alpha \implies \beta \quad \text{ is equivalent to } \quad \neg\alpha \lor \beta $$ and then expand $$ \neg(q \land (\neg p \lor \neg q)) \lor \neg p$$ and simplify the formula using De Morgan laws $$ \neg(q \land \neg (p \land q)) \lor \neg p$$ $$ \neg q \lor (p \land q) \lor \neg p$$ $$ (p \land q) \lor \neg p \lor \neg q $$ $$ (p \land q) \lor \neg (p \land q) $$

3. Use the contrapositive statement, that is

$$\alpha \implies \beta \quad \text{ is equivalent to } \quad \neg\beta \implies \neg \alpha $$

for example

$$q \land(p \implies \neg q) \implies \neg p$$ $$q \land(q \implies \neg p) \implies \neg p$$

and conclude that it is a tautology by using modus ponens.

4. Use the fact that the only way

$$q \land(p \implies \neg q) \implies \neg p$$

could fail is when $p$ is true. However, $p \implies \neg q$ equals then $\neg q$ and the premise could be simplified to $q \land \neg q$ which is obviously false and thus the whole implication holds.

5. Use Curry-Howard isomorphism, that is rewrite

$$q \land(p \implies \neg q) \implies \neg p$$

into this type

$$q \times (p \to (q \to \bot)) \to (p \to \bot)$$

and prove by providing an element

$$\lambda \langle q, f \rangle.\ \lambda p.\ f\ p\ q$$

of the required type and thus showing that it is inhabited.

Cheers!

Answer 2

$$(q~\wedge(p\to\sim q))\equiv(q~\wedge(\sim p\vee \sim q))\equiv(q~\wedge\sim p)\vee(q~\wedge\sim q)\equiv (q~\wedge\sim p)\vee F\equiv q~\wedge\sim p$$ and so $$(q~\wedge(p\to\sim q))\to\sim p\equiv~ \sim(q~\wedge\sim p)\vee\sim p\equiv\sim q$$ Do the same calculation for RHS and see $\sim q\to\sim q$.

Answer 3

Use deMorgan's law to say $\sim(\sim p $ and $ q) \equiv p $ or $ \sim q$

Answer 4

There are only 4 possible assignments to $(p,q)$. Check that the two formulae match for each assignment.