# Equivalence of $a \rightarrow b$ and $\lnot a \vee b$

Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?

-
Not in Lukasiewicz three-valued or infinite-valued logic! –  Doug Spoonwood May 15 at 19:31

Try using a truth table comparing $p\rightarrow q$ with $\lnot p \lor q$.
That's as good a proof as you need.

$p$ | $q\,$ |$\;p\rightarrow q$ | $\lnot p \lor q$
T | T |$\quad$ T $\quad$|$\quad$ T
T | F |$\quad$ F $\quad$|$\quad$ F
F | T |$\quad$ T $\quad$|$\quad$ T
F | F |$\quad$ T $\quad$|$\quad$ T

Both expressions evaluate false if and only if $\,p\,$ is true and $\,q\,$ is false.

For developing a bit of intuition regarding the conditional (logical implication): see, e.g.,
$(1)$ this post, and
$(2)$ this post.

-
This is basically my problem. I am having hard time understanding imples in logic. Is it like truth of an expression always implies truthness of another? and falseness of p can imply q to be true as well as false? –  user45099 Nov 24 '12 at 21:48
Yes, exactly. false implies anything: true or false. But for $p \implies q$ to be true when $p$ is true, then $q$ must be true. –  amWhy Nov 24 '12 at 21:50
Trust me, you're not the only one who finds "implies" (material implication) difficult to comprehend, as you can see by the links I've included above. It's a very common difficulty encountered by students. –  amWhy Nov 24 '12 at 22:05
Also worth noting is, using De Morgan's laws, the expression for implication is equivalent to $\neg(p\land\neg q)$, which gives us some justification for proof by contradiction. I.e., if $p\land\neg q$ gives us a contradiction, its negation ($p\Longrightarrow q$) must be true. –  Alex Nelson Nov 24 '12 at 22:09
Note that the truth tables are equivalent because we define the truth table for "implies" in a certain way. –  Code-Guru Dec 11 '12 at 4:24

Think of it this way. Suppose I signed a contract to you, saying "If I win the lottery, then I will give you $\$1$billion." The only situation in which my statement would be false (contract violated) is: I win the lottery and don't give you the money I promised. Otherwise, I'm just fine. In particular, if I never win the lottery, you have no claim on any of my money. On the other hand, I can give you the money just for kicks, and I still haven't violated the contract. Similarly, what if I said "If it's raining, I carry an umbrella." You couldn't call me a liar if it isn't raining, nor if I have an umbrella (regardless of the weather). A general conditional statement "if (hypothesis) then (conclusion)" is (by this reasoning) the same as saying "(hypothesis) is false or (conclusion) is true." - "On the other hand, I can give you the money just for kicks, and I still haven't violated the contract." My favourite representation of this is the logician whose son was well-behaved but still went to bed without any supper. – Joe Z. Jan 13 '13 at 14:17 +1 for the instructive intuition. – LePressentiment Sep 20 '13 at 13:53 Suppose we are for the moment using$p \to q$for the informal indicative conditional, if$p$then$q$. 1. Suppose we are given that if$p$then$q$(i.e.$p \to q$). Then, since we have$\neg p \lor p$it follows (arguing by cases) that$\neg p \lor q$. 2. Suppose, conversely, we are given$\neg p \lor q$is true. Then if$p$is true that rules out the first disjunct, so we have$q$. In short, if$p$then$q$, (i.e.$p \to q$). That pair of arguments makes it rather plausible that$p \to q$(the indicative conditional) is inter-dervable with$\neg p \lor q$, and so is equivalent at least as far as truth-conditions go with$\neg p \lor q$. OK: That gives us some reason to suppose that the truth-functional account of the conditional isn't just fanciful -- it gets something important right. Or so a familiar story goes. But do note (important point!) it is a further question whether the truth-functional story about 'if' is the whole story. Compare, arguably '$p$but$q$' is truth-functionally equivalent to$p \land q$: however 'but' doesn't mean just bare conjunction. 'But' does more than '$\land$' -- very roughly it signals the speaker's sense that the joint truth of$p$and$q$is unexpected/surprising. Well likewise, perhaps "if p then q" does more than '$\neg p \lor q$'. E.g. it arguably signals the speaker's willingness to infer$q$should it turn out that$p\$. For more on this, see e.g. http://www.logicmatters.net/resources/pdfs/Conditionals.pdf

-

I'm gonna use p and q.
Natural deduction: \begin{align} &1\ p \rightarrow q &&P\\ &2\ |\ \lnot (\lnot p \lor q) &&H\\ &3\ |\ |\ p &&H\\ &4\ |\ |\ q &&1,3 I \rightarrow\\ &5\ |\ |\ \lnot p \lor q &&4 I \lor\\ &6\ |\ |\ \lnot ( \lnot p \lor q) \land (\lnot p \lor q) && 2,5 I \lor \bot\\ &7\ |\ \lnot p&&3-6 I \lnot\\ &8\ |\ \lnot p \lor q&&7I\lor\\ &9\ |\ (\lnot p \lor q) \land \lnot (\lnot p \lor q)&&2,8\land \bot\\ &10\ \lnot p \lor q&&2\lnot \end{align}

Hope this helps you!

-