# Need to prove $(p \land q) \land (\lnot p \lor r) \rightarrow (q \lor r)$ is a tautology.

I need to prove the following expression is a tautology using propositional logic laws.

My current working out is as follows [not sure if it is correct]:

$$(p \land q)\land ( \lnot p \lor r) \rightarrow (q \lor r)$$

Taking the LHS: $$(p \land q) \land (\lnot p \lor r)$$

$$( (p \land q) \land \lnot p) \lor ( (p \land q) \land r)$$ [Using distributive law]

$$( (p \land \lnot p) \land q) \lor ( (p \land q) \land r)$$ [Using associative law]

$$( F \land q) \lor ( (p \land q) \land r)$$ [Using complement law]

$$F \lor ( (p \land q) \land r)$$ [Using identity law]

This is where I get stuck. Is this the correct working so far? What other laws am I missing to prove the expression is a tautology?

$$p \land q \land (\lnot p \lor r)$$ implies $$q$$ $$\tiny\text{… by simplification}$$

$$q$$ implies $$q \lor r$$ $$\tiny\text{… by addition}$$

The rest is obvious.

• Sorry, I'm not quite sure I follow you. Jul 29, 2019 at 7:15
• It's a natural deduction style argument, rather than propositional calculus. Jul 29, 2019 at 8:16
• That propositional calculus fad is a clumsy way to prove many propositions. Why is it the only thing taught? Have they discarded teaching P., Q|- R. @GrahamKemp Jul 29, 2019 at 9:19

First note that $$F \lor ( (p \land q) \land r)=p \land q \land r$$ Then recall that How to prove that $P \rightarrow Q$ is equivalent with $\neg P \lor Q$?

Hence, from your work, $$(p \land q)\land ( \lnot p \lor r) \rightarrow (q \lor r)$$ is equivalent to $$\lnot(p \land q \land r)\lor (q \lor r)$$ that is, by using De Morgan's laws, $$(\lnot p \lor \lnot q \lor \lnot r) \lor (q \lor r)=\lnot p \lor (\lnot q \lor q) \lor (\lnot r\lor r)=T.$$

• Thanks! I got it now. Jul 29, 2019 at 7:22

In fact, from $$(p\land q)\land (\neg p\lor r)$$ we can even prove $$q\land r$$. Note in particular $$p\land(\neg p\lor r)\to r$$.