Is this proof correct?
(p ∧ q) → r ⊢ (p → r) ∨ (q → r)
- (p ∧ q) → r
- ¬(p ∧ q) ∨ r
- ¬p ∨ ¬q ∨ r
- ¬p ∨ (q → r)
- ¬p ∨ (q → r) ∨ r
- ¬p ∨ r ∨ (q → r)
- (p → r) ∨ (q → r)
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.
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.