Take the 2-minute tour ×
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.

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

share|improve this question
    
Not in Lukasiewicz three-valued or infinite-valued logic! –  Doug Spoonwood May 15 at 19:31

4 Answers 4

up vote 20 down vote accepted

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.

share|improve this answer
    
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
1  
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
1  
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."

share|improve this answer
2  
"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

share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.