Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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.


share|cite|improve this answer

$$(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|cite|improve this answer
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$

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.