8
$\begingroup$

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

  • 0
    Possible duplicate of [Why is $p\Rightarrow q$ equivalent to $\neg p\lor q$ and how to prove it](http://math.stackexchange.com/questions/58214/why-is-p-rightarrow-q-equivalent-to-neg-p-lor-q-and-how-to-prove-it)2016-11-13

5 Answers 5

18

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.

  • 0
    "That's as good a proof as you need." But a formal proof will tell us that this holds in Bochvar's 3-valued logic as well as some other systems with equivalent axiom sets, which have more than two truth values. The truth-table for Bochvar's 3-valued logic needs more than this answer, or you have to invoke a series of lemmas which ensure that you can decide such questions about those other systems with more truth values by two-valued truth tables. Anyways, nice answer, just a comment.2014-05-15
12

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

  • 3
    "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.2013-01-13
4

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

2

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!

0

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.