Got stuck doing a proof with logical equivalences

Question

I have to show that $(p\lor q)\land (\neg p\lor r)\rightarrow (q\lor r)$ is a tautology. I have :

$(p \lor q) \land (\neg p \lor r) \to (q \lor r) \equiv \neg((p \lor q) \land (\neg p \lor r)) \lor (q \lor r)$ implication proof

$\equiv \neg(p \lor q) \lor \neg(\neg p \lor r) \lor (q \lor r)$ De Morgan

$\equiv (\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r)$ De Morgan

I don't know how to proceed from here. Can anybody check and see if I messed up or point me to a right step?

Thanks!

Answer 1

$$(\neg p \land \neg q) \lor (p \land \neg r) \lor (q \lor r) \overset{Association}{\equiv}$$

$$(\neg p \land \neg q) \lor (p \land \neg r) \lor q \lor r \overset{Commutation}{\equiv}$$

$$q \lor (\neg p \land \neg q) \lor r \lor (p \land \neg r) \overset{Reduction \ x \ 2}{\equiv}$$

$$q \lor \neg p \lor r \lor p \overset{Complement}{\equiv}$$

$$\top \lor q \lor r \overset{Annihilation}{\equiv}$$

$$\top$$

So here I used:

Reduction

$P \land (\neg P \lor Q) \equiv P \land Q$

$P \lor (\neg P \land Q) \equiv P \lor Q$

If Reduction is not in your arsenal of equivalence principles, here's how you can do Reduction in terms of other elementary equivalences:

Reduction

$$P \lor (\neg P \land Q) \Leftrightarrow \text{ (Distribution)}$$

$$(P \lor \neg P) \land (P \lor Q) \Leftrightarrow \text{ (Complement)}$$

$$\top \land (P \lor Q) \Leftrightarrow \text{ (Identity)}$$

$$P \lor Q$$

Answer 2

Assume the premise $(p\lor q)\land (\neg p\lor r)$.
There are two cases, p and $\neg p$.
In the first case, conclude r.
In the second case, conclude q.
So from both cases, conclude $q \lor r.$

Answer 3

Here a proof using mainly (1) contraposition (2) exportation rule ( twice) (3) and the domination law :

P OR True is equivalent to True.

Remark : I use True and False as propositional constants ( True = the proposition that is equivalent to any tautology, False = the proposition that is equivalent to any antilogy).

(PvQ) & (~PvR) --> (QvR)

↔ ~ ( QvR) --> ~ [ (PvQ) & (~PvR) ]

↔ (~Q & ~R) --> [ ~ (PvQ) v ~ ( ~P v R) ]

↔ (~Q & ~R) --> [ (PvQ) --> ~ ( ~P v R) ]

↔ [ (~Q & ~R) & (PvQ)] --> ~ ( ~P v R)

↔ [ (~Q&~R & P) v (~Q & ~R & Q) ] --> ~ ( ~P v R)

↔ [ (~Q&~R & P) v False ] --> ~ ( ~P v R)

↔ (~Q&~R & P) --> ~ ( ~P v R)

↔ (~Q&~R & P) --> P & ~ R

↔ ~Q --> [ (P& ~R) --> (P & ~ R ) ]

↔ ~Q --> True

↔ Q v True

↔ True