Need Help with Propositional Logic

Question

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.

Answer 1

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.

Answer 2

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?

Answer 3

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 $