3
$\begingroup$

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?

2 Answers 2

4

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

  • 0
    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.2012-03-04
2

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.