Is this proof correct?

(p ∧ q) → r ⊢ (p → r) ∨ (q → r)

  1. (p ∧ q) → r
  2. ¬(p ∧ q) ∨ r
  3. ¬p ∨ ¬q ∨ r
  4. ¬p ∨ (q → r)
  5. ¬p ∨ (q → r) ∨ r
  6. ¬p ∨ r ∨ (q → r)
  7. (p → r) ∨ (q → r)
  • $\begingroup$ Why the votes to close? The post has been edited by the OP, perhaps improved following close votes? $\endgroup$ – Namaste Aug 16 '16 at 15:43
  • $\begingroup$ That looks good, but I would use idempotence to introduce the second $\vee r$ in line 4 and then use implication equivalence in line 5 (rather than the other way around.) $\endgroup$ – Graham Kemp Aug 18 '16 at 0:14

Suppose $$\neg((p\rightarrow r) \lor (q\rightarrow r))$$Then pushing in the negation gives $$(\neg(p\rightarrow r) \land \neg (q\rightarrow r))$$ pushing them in further gives $$(p \land \neg r) \land (q\land \neg r)$$ and so $$(p \land q) \land \neg r$$ But this contradicts $(p\land q) \rightarrow r$.


Usually when you want to prove a disjunction it is convenient to argue contrapositively: instead of $A\to B$ you prove $\neg B\to \neg A$. Using words you would argue e.g. as follows $\neg((p\to r)\vee (q\to r))$ is the same as $\neg(p\to r)\wedge \neg (q\to r)$ which is the same as $p\wedge q\wedge \neg r$, which is exactly $\neg (p\wedge q\to r)$. Now you can mimic this approach in in your culculus.

Ad edit: the argument you wrote make a very good sense.

  • $\begingroup$ About your edit: What did you mean? My proof is correct but it is not formal? Like, it's not valid? $\endgroup$ – Leonardo Benicio Aug 16 '16 at 15:55
  • $\begingroup$ @Leonardo I erased it. I guess it was only confusing. Sorry :) $\endgroup$ – Gur Ismael Aug 16 '16 at 16:03

Your proof looks good to me. I know that this might not be the best advice, but something I like to try and do when working on a logic proof (though, this kind of falls apart at the modal level where my intuition falls apart) is to think about whether, just intuitively, what would happen if the consequent were false. That is, I try and just plug in things for $p$ and $q$ and work through it in English.

So, I would say, "It's not true that 'either dieting leads to health or exercising leads to health'. So, then 'dieting doesn't lead to health' and 'exercising doesn't lead to health'. So, obviously dieting and exercising isn't going to lead to health.

Then, once I have a better intuition about it, I go back and work through the symbols. At least, that's what works for me. See James' answer for the symbolic breakdown.


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.