# How does this textbook go from this step to the next in proving this?

Here's the picture of the question:

How does it go from p v ~q to ~p -> ~q?

• one way to convince yourself of this is to construct truth tables for both statements and check if theyre equivalent Commented Dec 16, 2012 at 19:38

$$p\lor \lnot q$$ $$\equiv \lnot\lnot p \lor \lnot q$$ $$\equiv \lnot p \rightarrow \lnot q$$

This is simply applying the rule that $a \rightarrow b \;\equiv \; \lnot a \lor b$,

but in reverse: $\lnot a \lor b \equiv a\rightarrow b$.

In this case, $a$ happens to be $\lnot p$, and $b$ happens to be $\lnot q$.

To double-check, and convince yourself, truth-tables come in handy:

One last note:

$$(a \rightarrow b) \equiv (\lnot b \rightarrow \lnot a)$$

The right-hand side is called the contrapositve of the left-hand side of the equivalence; they are equivalent expressions.

Knowing this, one can conclude, directly, that the converse of $p \rightarrow q$ is equivalent to the inverse of $p \rightarrow q$: $(q\rightarrow p) \equiv (\lnot p \rightarrow \lnot q)$.

• do share, how did you TeX such a pretty looking truth table :) Commented Dec 16, 2012 at 19:56
• @MSEoris Compliments go to WolframAlpha! Commented Dec 16, 2012 at 20:01
• I see, thanks so much. :) Commented Dec 16, 2012 at 20:05
• The "in reverse" part doesn't come as logically coherent, since any equivalence means you can replace either side of the equivalence for the other one. Equivalences don't have "handedness" one might say. The "in reverse" part might read better if it said something like "replacing the right-hand side of the equivalence with the left-hand side". Commented Dec 17, 2012 at 4:26
• @amWhy: Beautifully formatted table - love the color! Oh look, another bade! :-) +1 Commented May 2, 2013 at 1:04

An easy way to remember what $p \Rightarrow q$ means is this: if the implication is true, either the conclusion is true, or the premise is false. That is, $$p\Rightarrow q \equiv \lnot p \lor q$$ So $p \lor \lnot q \equiv \lnot \lnot p \lor \lnot q \equiv \lnot p \Rightarrow \lnot q$

We'd half to know more about this particular text to know how the author(s) did this. That said, following for example Lukasiewicz's introductory text on mathematical logic, you can define (p$\lor$q) as ($\lnot$p$\implies$ q), since they are logically equivalent... (p$\lor$q)$\equiv$($\lnot$p$\implies$ q).

Then from that equivalence just uniformly substitute $\lnot$q for q, and you have (p$\lor$$\lnotq)\equiv(\lnotp\implies$$\lnot$q).

• Cpq==ANpq AND Apq==CNpq, with C as the material conditional, A as alternation, and N as negation (or more shortly... C==AN, A==CN). In other words, you can define alternation and the material conditional by Xpq==YNpq, where X does not equal Y, and X and Y belong to {C, A}. Commented Dec 17, 2012 at 4:45