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

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.

-
Welcome to MSE! If you write your questions using MathJax, they are much more readable and that can help in the number of responses. Regards –  Amzoti Jan 24 '13 at 18:05
(a->b) <=> (~b->~a) so that in your case, (p->~q) <=> (~(~q)->~p) <=> (q->~p) so that you basically have q && (q->~p) therefore ~p. –  Guest 86 Jan 24 '13 at 18:09

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!

-

$$(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$.

-
One of my favorite domains: logic! +1 –  amWhy Feb 6 '13 at 2:59
Use deMorgan's law to say $\sim(\sim p$ and $q) \equiv p$ or $\sim q$
There are only 4 possible assignments to $(p,q)$. Check that the two formulae match for each assignment.