Any implication is logically equivalent to its contrapositive. In other words,
¬<em>p</em> ⇒ <em>q</em> ⇔ ¬<em>q</em> ⇒ <em>p</em>
(¬ means the same thing as ~, "not")
To prove this: recall that
<em>p</em> ⇒ <em>q</em> ⇔ ¬<em>p</em> ∨ <em>q</em>
This is because <em>p</em> ⇒ <em>q</em> is true if <em>p</em> is false, or both <em>p</em> and <em>q</em> are true, i.e.
<em>p</em> ⇒ <em>q</em> ⇔ ¬<em>p</em> ∨ (<em>p</em> ∧ <em>q</em>)
Disjunction (∨ or "or") distributes over conjunction (∧ or "and"), so that
<em>p</em> ⇒ <em>q</em> ⇔ (¬<em>p</em> ∨ <em>p</em>) ∧ (¬<em>p</em> ∨ <em>q</em>)
but ¬<em>p</em> ∨ <em>p</em> is always true, or a tautology, so we're just left with ¬<em>p</em> ∨ <em>q</em>.
Then
¬<em>p</em> ⇒ <em>q</em> ⇔ <em>p</em> ∨ <em>q</em>
… ⇔ <em>q</em> ∨ <em>p</em>
… ⇔ ¬(¬<em>q</em>) ∨ <em>p</em>
… ⇔ ¬<em>q</em> ⇒ <em>p</em>
