1
$\begingroup$

I'm given three sentences:

(a) If Frodo destroys the ring, then the world will be saved. (b) Gollum stole the ring from Frodo or Frodo destroyed the ring. (c) The world will be saved or Gollum stole the ring from Frodo.

I have to prove that sentences (a) and (b) jointly entail (c). I'm not quite sure how to do this.


I started by assigning the following variables:

$p$ = Frodo destroys the ring

$q$ = The world will be saved

$r$ = Gollum stole the ring.


Sentence (a) translates to: ($p \rightarrow q$)

Sentence (b) translates to: ($r \lor p$)

Sentence (c) translates to: ($q \lor r$)


I wrote up a truth table for all three variables, and then for each statement. I tried making the truth table for the statement $( p \rightarrow q) \land (r \lor p)$ equivalent to the one for $(q \lor r)$, but was not able to. Any ideas what I am doing wrong?

$\endgroup$
9
  • 1
    $\begingroup$ According to your wording, you're not looking for an equivalence, but an implication. So $a \land b \implies c$ $\endgroup$ Jan 24, 2016 at 6:06
  • $\begingroup$ Ok, how do I prove that implication? Can I do so using a truth table? $\endgroup$
    – dibdub
    Jan 24, 2016 at 6:16
  • $\begingroup$ According to the definition of "entail" (which I had to look up on the net BTW), you need to prove $\neg(c)\implies\neg(a\wedge b)$. $\endgroup$ Jan 24, 2016 at 6:17
  • $\begingroup$ @barakmanos Why bother with the contrapositive? Just prove $a\land b\to c$. $\endgroup$
    – BrianO
    Jan 24, 2016 at 6:22
  • $\begingroup$ How do I prove that? Sorry, I'm new at this. $\endgroup$
    – dibdub
    Jan 24, 2016 at 6:26

3 Answers 3

2
$\begingroup$

Entailment means: Whenever $p\to q$ and $p\vee r$ are both true, then $q\vee r$ is also true.

Your truth table just needs to show that every row that has a truth in both those columns also has a truth in the later column -- not necessarily the other way around. $$\begin{array}{|c:c:c|c:c|c:c|l|} \hline P & Q & R & P\to Q & R\vee P & (P\to Q) \wedge (R\vee P) & R\vee Q & \text{test: second last column is...} \\\hline \top & \top & \top & \top & \top & \top & \top & \checkmark\text{(true so must check that the last column also is)} \\ \top & \top & \color{red}\bot & \top & \top & \top & \top & \checkmark\text{(true so must check that the last column also is)} \\ \top & \color{red}\bot & \top & \color{red}\bot & \top & \color{red}\bot & \top & \checkmark \text{(false so don't care)} \\ \top & \color{red}\bot & \color{red}\bot & \color{red}\bot & \top & \color{red}\bot & \color{red}\bot& \checkmark \text{(false so don't care)} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \hline \end{array}$$

$\endgroup$
0
1
$\begingroup$

As others have pointed out, what you're doing wrong in your truth table calculations is trying to prove equivalence. You only need to prove that a) and b) imply c). You can't prove that c) implies a) and c) — it doesn't! (In fact, c) doesn't imply either of a) or b): there's an assignment of values to $p,q,r$ that makes c) true but a) false, and another that makes c) true but b) false.)

You can also prove the result deductively. The following is a tautology, and a theorem of whatever proof system for propositional logic you want to use (natural deduction, a Hilbert style axiomatic system, truth tables, ...): $$ ((p\to q)\land (p\lor r))\to(q\lor r).\tag{*} $$

If you construct the truth table for (*), the value of the formula will be T in every row.

The antecedent of (*) is exactly the conjunction of your premises a) and b), so by modus ponens we can conclude: $$ (q\lor r), $$ which is what you wanted to prove.

$\endgroup$
4
  • $\begingroup$ Ok, this makes more sense. I guess what I'm having a hard time understanding is how you got (1). The way I would have written the statement the a) and b) imply c) would have been ((p→q)∧(p∨r))→(q∨r). Why is this not the case? $\endgroup$
    – dibdub
    Jan 24, 2016 at 6:47
  • $\begingroup$ It is the case. After I saved the answer I realized it would be simpler and better to use that formula. I even used it in my comment and in the first paragraph! So I simplified the answer.. and then I saw your comment :) Great minds, I guess... The form that I had at first is completely equivalent, however, because $A\to (B\to C)$ is equivalent to $(A\land B)\to C$ for all formulas $A,B,C$ (feel free to verify that yourself). $\endgroup$
    – BrianO
    Jan 24, 2016 at 6:51
  • $\begingroup$ Awesome, thought I was going crazy. Thanks you so much for the help! $\endgroup$
    – dibdub
    Jan 24, 2016 at 6:58
  • $\begingroup$ Haha! You seem sane enough ;/ You're welcome, and thank you. $\endgroup$
    – BrianO
    Jan 24, 2016 at 6:59
0
$\begingroup$

As hinted at in the comments, your proving the wrong thing. To prove the statement $A\rightarrow B$, make a truth table for both, A and B under all the options, and then compute the truth value of $A\rightarrow B$. If it's all True, then the implication holds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.