Q:

Algebraic Solution to Prove Tautology

I need an algebraic solution to show this is a tautology:

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

Thanks

A:

$a\rightarrow b \equiv \neg(a)\lor b$, so what you have is equivalent to
$$\neg\left[(p\lor q) \land [\neg p \lor r] \land [\neg q\lor r]\right] \lor r$$
By De Morgan's Law, this is equivalent to:
$$\neg(p\lor q) \lor \neg(\neg p\lor r) \lor \neg(\neg q\lor r) \lor r$$
which in turn is equivalent to:
$$(\neg p\land \neg q) \lor (p\land \neg r) \lor (q\land \neg r) \lor r$$
which is the same as
$$(\neg p\land \neg q)\lor\Bigl( ( p\land \neg r)\lor (q\land \neg r)\Bigr) \lor r$$
which in turn is the same as
$$(\neg p\land \neg q)\lor\Bigl( ( p \lor q)\land \neg r\Bigr)\lor r$$
which gives
$$(\neg p\land \neg q)\lor\Biggl( \bigl(( p\lor q)\lor r\bigr)\land (\neg r\lor r)\Biggr)$$
which gives
$$(\neg p\land \neg q) \lor \Biggl( \bigl( (p\lor q)\lor r\bigr) \land 1\Biggr)\equiv
(\neg p\land \neg q) \lor \Bigl(  (p\lor q)\lor r\Bigr)$$
Distributing, we get
$$\Bigl( \neg p \lor p \lor q\lor r\Bigr) \land\Bigl( \neg q\lor p \lor q \lor r\Bigr)$$
Which is
$$\Bigl( 1\lor q \lor r\Bigr) \land \Bigl( p\lor 1 \lor r\Bigr) \equiv 1\land 1 \equiv 1.$$

