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

| cite | improve this question | | | | |

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.

| cite | improve this answer | | | | |
  • $\begingroup$ 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? $\endgroup$ – user45099 Nov 24 '12 at 21:48
  • $\begingroup$ 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. $\endgroup$ – amWhy Nov 24 '12 at 21:50
  • $\begingroup$ 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. $\endgroup$ – amWhy Nov 24 '12 at 22:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Alex Nelson Nov 24 '12 at 22:09
  • 1
    $\begingroup$ Note that the truth tables are equivalent because we define the truth table for "implies" in a certain way. $\endgroup$ – 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."

| cite | improve this answer | | | | |
  • 3
    $\begingroup$ "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. $\endgroup$ – Joe Z. Jan 13 '13 at 14:17

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

| cite | 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!

| cite | improve this answer | | | | |

Source 1 : http://plus.maths.org/content/os/issue36/features/nishiyama/index.
I understand this argument, but it does not feel intuitive.

We are given that $\color{green}{P \Longrightarrow Q}$.
$\boxed{\text{Case 1 of 2 : } \color{green}{P \Longrightarrow Q} \text{ true}}$ Substitute the green into the tautology $\color{green}{P} \vee \lnot P$ to get: $\color{green}{Q} \vee \lnot P$. $\boxed{\text{Case 2 of 2 : } \color{green}{P \Longrightarrow Q} \text{ false}}$ Since an argument is valid if the premises cannot all be true without the conclusion being true as well, thus this case means $[\text{$P$ is true $\& \, Q$ is false]} \iff [\text{$\lnot P$ is false $\& \, Q$ is false]} \iff [\text{$\lnot P \vee Q$ is false]}$.

Altogether, the 2 cases result in: $\left\{ \begin{array}{rcl} \color{green}{P \Longrightarrow Q} \text{ true $\equiv [\lnot$ P $\vee$ Q] is true} \\ \color{green}{P \Longrightarrow Q} \text{ false $\equiv [\lnot$ P $\vee$ Q] is false} \end{array}\right.$.
Thus, the Conditional Law has been proven.

| cite | improve this answer | | | | |