Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

4 Answers 4

up vote 1 down vote accepted

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!

share|improve this answer
add comment

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

share|improve this answer
    
One of my favorite domains: logic! +1 –  amWhy Feb 6 '13 at 2:59
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.