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.

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

I've started to work through Applied Mathematics for Database Professionals and have been stuck on one of the exercises for two days. I've been able to prove the expression: $$\left( P\Rightarrow Q \right) \Leftrightarrow \left( \neg Q \Rightarrow \neg P \right)$$ is true using a truth table but can't make the leap using rewrite rules.

Starting with the implication: $$ P \Rightarrow Q$$ Rewrite implication into disjunction: $$\neg P \vee Q $$ By commutativity the expression becomes: $$ Q \vee \neg P $$ Via double negation: $$ \neg \neg Q \vee \neg P $$ This is where I get stuck. The answer in the book shows rewriting the expression back into an implication: $$ \neg Q \Rightarrow \neg P $$ I understand where the $ \neg P $ comes from, it's from the initial rewrite rule. My confusion is, how is the $ \neg Q $ derived?

share|cite|improve this question
up vote 3 down vote accepted

You apparently have a rule that allows you to go back and forth between $A\Rightarrow B$ and $\lnot A\lor B$. You’ve used it in the forward direction to go from $P\Rightarrow Q$ to $\lnot P\lor Q$, with $A=P$ and $B=Q$. Now use it in the reverse direction to go from $\lnot\lnot Q\lor\lnot P$ to $\lnot Q\Rightarrow \lnot P$ by taking $A=\lnot Q$ and $B=\lnot P$.

share|cite|improve this answer
I understand where my confusion was with your answer. I'm thinking algebraically where the double negation has to be applied to both P & Q. – MarkSchoonover Mar 4 '12 at 18:38

The rewrite rule says that $\lnot X \lor Y$ can be replaced by $X\Rightarrow Y$, and vice-versa.

In $\lnot\lnot Q \lor \lnot P$, let $X=\lnot Q$ and $Y=\lnot P$, and use the rewrite rule.

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.