7
$\begingroup$

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

$\endgroup$

closed as off-topic by user91500, Jack's wasted life, Davide Giraudo, Stefan Mesken, Michael Hoppe Nov 14 '16 at 22:04

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user91500, Jack's wasted life, Davide Giraudo, Stefan Mesken, Michael Hoppe
If this question can be reworded to fit the rules in the help center, please edit the question.

18
$\begingroup$

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.

$\endgroup$
  • $\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$ – Namaste 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$ – Namaste 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
12
$\begingroup$

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."

$\endgroup$
  • 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
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$