Need Help with Propositional Logic

I am stuck with this proof. I am trying to use deduction (or induction I think) to prove for a tautology with logic laws like De Morgan's, distributive , and implication law etc.

Note: I am not allowed to use truth tables.

Here it is:

$((p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)) \rightarrow r$

I have tried using a condition/implication law where $p \rightarrow r$ becomes $\neg p \vee r$ to change the last to compound statements but I got stuck.

Next I tried:

$((p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)) \rightarrow r \\ \equiv [(p \vee q) \wedge ((p \vee q) \rightarrow r)] \rightarrow r$

But I don't know where to go from here.

Need some guidance guys.

• Have you tried constructing a truth table? Feb 6, 2015 at 23:23
• @Zeta10 I'll edit the question. Feb 6, 2015 at 23:26
• Ah! I see. You essentially need a list of logical equivalencies as well as an understanding of what happens when you negate one of these expressions. I know that does not solve your problem, but I am sure you can easily find such a list and then start to make substitutions until all of the puzzle pieces fit into place! Feb 6, 2015 at 23:37
• Actually, I do not see a straightforward list of equivalences that will get the job done. It is possible to simply crank it out, but everything I am getting so far is very long-winded. For this problem and you other problem (the transitivity one), truth tables are actually the most convenient tool it seems. Feb 6, 2015 at 23:38
• @induktio Hello again! Yes it seems like it will be long winded. It makes sense in my head but I cant quite find the right equivalences Feb 6, 2015 at 23:41

We can use these Rules of inference.

Starting wtih :

$$[((p∨q)∧(p→r)∧(q→r))→r] \equiv$$

we can apply Material implication :

$$\equiv \lnot [(p \lor q)∧(\lnot p \lor r)∧(\lnot q \lor r)] \lor r \equiv$$

followed by De Morgan to get :

$$\equiv [\lnot (p \lor q) \lor \lnot [(\lnot p \lor r)∧(\lnot q \lor r)]] \lor r \equiv$$

Then we need Distributivity with : $[(\lnot p \lor r)∧(\lnot q \lor r)] \equiv [r \lor (\lnot p \land \lnot q)]$ to get :

$$[\lnot (p \lor q) \lor \lnot [r \lor (\lnot p \land \lnot q)]] \lor r \equiv$$

Then we use again De Morgan and "rearrange" to get :

$$[r \lor (\lnot p \land \lnot q)] \lor \lnot [r \lor (\lnot p \land \lnot q)].$$

Now the last formula is an instance of Excluded Middle : $\varphi \lor \lnot \varphi$, which is a tautology.

What you want to show is equivalent to $((p\vee q)\wedge(p\to r)\wedge(q\to r))$ implies $r$.

Now we can work with $(p\vee q)$ separately since we have a string of $\wedge$'s, and a case by case analysis of this shows that $r$ is implied by our hypothesis.

Is this similar to what you have done in class?

• so you mean to say you can show that $(p \vee q) \rightarrow r$ separately and then do this for the other compound statements? Feb 7, 2015 at 0:09
• Well it's true that $a\rightarrow c$ and $b\rightarrow c$ implies $(a\vee b)\rightarrow c$. Though maybe that is skipping the part of the argument your teacher wants you to show. Feb 7, 2015 at 0:12
• The key too is to use the deduction theorem to turn your question into a problem with a hypothesis, and a conclusion in mind (namely $r$) Feb 7, 2015 at 0:13

Hint: $((p\vee q)\wedge ((p\vee q)\to r))\to r \\\iff\\ ((p\vee q)\wedge (\neg(p\vee q)\vee r) )\to r$

• Thanks for the hint. I've gotten this far: $[(\neg p \wedge \neg q) \vee ((p \vee q) \wedge r)] \vee r$ Feb 7, 2015 at 5:15
• That should be $[\neg (p\vee q)\vee((p\vee q)\wedge \color{red}{\neg} r)]\vee r$. Also, it's better to treat $(p\vee q)$ as a single entity (say, $X$), and don't use DeMorgan's on it. So you have: $$[\neg X\vee (X\wedge\neg r)]\vee r$$ Now, simplify. Feb 7, 2015 at 9:28