1
$\begingroup$

For a homework assignment I have to prove that one of the statements entails the other.

The statements are:

$(A \lor B) \to C$

$(A \to C) \lor (B \to C)$

The only thing that I got so far is either $\lnot(A \lor B) \to C$ or $(A \to C) \land (B \to C)$.

I can use the rules of Modus Ponens, Modus Tollens, Simplification, Conjunction, Disjunction, Conjunctive and Disjunctive Syllogism, Hypothethical Syllogism and Conditional Proof.

The equivalence rules I can use are Double Negation, De Morgan's Laws, Biconditional Equivalence,and I think, Transposition and Material Implication, too.

Is there someone who can help me? I've tried so much already...

Edit:

The answer they wanted to hear was:

  1. (A v B) -> C
  2. A supp/CP
  3. A v B disj
  4. C 1,3MP
  5. A -> C 2-4 CP
  6. (A -> C) v (B -> C) 5 disj
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

HINT: Use the fact that $p\to q$ is equivalent to $\neg p\lor q$. Thus,

$$(A\lor B)\to C)\equiv\neg(A\lor B)\lor C\equiv(\neg A\land\neg B)\lor C\equiv(\neg A\lor C)\land(\neg B\lor C)\;,$$

where I’ve also used De Morgan’s law and distributivity. Now expand use the same fact to convert this to an expression involving $A\to C$ and $B\to C$, and compare that with $(A\to C)\lor(B\to C)$; one of the two expressions is easily shown to imply the other.

$\endgroup$
13
  • $\begingroup$ In your last step (¬A∧¬B)∨C≡(¬A∨C)∧(¬B∨C), is there a rule for this equivalence? Because I know this intuitively, but I have to justify every step I make $\endgroup$
    – marieke
    Oct 3, 2015 at 16:25
  • $\begingroup$ @marieke: That’s distributivity of $\lor$ over $\land$: $$(p\land q)\lor r\equiv (p\lor r)\land(q\lor r)\;.$$ You might see it with the $r$ on the left of the $p\land q$, in which case you’d also need to use commutativity. $\endgroup$
    – Brian M. Scott
    Oct 3, 2015 at 16:26
  • $\begingroup$ Okay, but than I only see how to get (A -> C) ^ (B -> C), where the ^ should be an v... there is, for as far as I know, no way to make those two the same. Even though the or is inclusive $\endgroup$
    – marieke
    Oct 3, 2015 at 16:46
  • $\begingroup$ @marieke: It’s not clear to me what you’re trying to say. However, I just noticed that my suggestion in the answer is unnecessarily complicated; give me a moment or two, and I’ll improve it. $\endgroup$
    – Brian M. Scott
    Oct 3, 2015 at 16:49
  • $\begingroup$ @marieke: Ah, I think that I just realized what you meant. Are you saying that if you follow the current version of my answer, you get $$(A\to C)\land(B\to C)$$ from the first expression? That’s true. Now, which of $p\land q$ and $p\lor q$ implies the other? $\endgroup$
    – Brian M. Scott
    Oct 3, 2015 at 16:52
1
$\begingroup$

As Wikipedia notes,

A valid logical argument is one in which the conclusion is entailed by the premises, because the conclusion is the consequence of the premises.

So to answer the question we need to ask which of these two statements could be the conclusion of the other. Using a truth table we can see that they do not entail each other:

enter image description here

However, the first sentence does entail the second:

enter image description here

We can create a natural deduction proof of that as well. The desired natural deduction proof should look like the following:

The answer they wanted to hear was: (A v B) -> C

A supp/CP

A v B disj

C 1,3MP

A -> C 2-4 CP

(A -> C) v (B -> C) 5 disj

That such a proof would work can be verified by using a proof checker.

enter image description here

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/

"Logical Consequence" Wikipedia https://en.wikipedia.org/wiki/Logical_consequence

Stanford Truth Table Tool http://web.stanford.edu/class/cs103/tools/truth-table-tool/

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .