Show that the proposition is a tautology using logical equivalences

Question

$$ (p \vee q ) \wedge (\lnot p \vee r) \to q \vee r$$

So far what I have is:

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

$$(\lnot(p \vee q) \vee \lnot(\lnot p \vee r)) \vee (q \vee r)$$

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

This is where I'm stuck.

Answer 1

First apply conditional equivalence then apply de morgan's law twice, this is correct so far, after that, to prove this with Logical equivalence, all we need is keep using Associative law, Commutative law, Distributive law, Negation law, Identity law, and in the end we need to apply Domination law twice:

\begin{align} &(p \vee q ) \wedge (\lnot p \vee r) \to q \vee r\\ \equiv&\lnot((p \vee q) \wedge (\lnot p \vee r)) \vee (q \vee r)\tag*{Conditional Equivalence}\\ \equiv&((\lnot p \wedge \lnot q) \vee (p \wedge \lnot r)) \vee (q \vee r)\tag*{De Morgan's laws$\times 2$}\\ \equiv&(\lnot p \wedge \lnot q) \vee ((p \wedge \lnot r) \vee (q \vee r))\tag*{Associative law}\\ \equiv&(\lnot p \wedge \lnot q) \vee ((p \wedge \lnot r) \vee (r \vee q))\tag*{Commutative law}\\ \equiv&(\lnot p \wedge \lnot q) \vee (((p \wedge \lnot r) \vee r) \vee q)\tag*{Associative law}\\ \equiv&(\lnot p \wedge \lnot q) \vee (q\vee((p \wedge \lnot r) \vee r))\tag*{Commutative law}\\ \equiv&((\lnot p \wedge \lnot q) \vee q)\vee((p \wedge \lnot r) \vee r))\tag*{Associative law}\\ \equiv&((\lnot p\vee q) \wedge (\lnot q\vee q))\vee((p\vee r) \wedge (\lnot r\vee r))\tag*{Distributive law}\\ \equiv&((\lnot p\vee q) \wedge \top)\vee((p\vee r) \wedge \top)\tag*{Negation law}\\ \equiv&(\lnot p\vee q)\vee(p\vee r)\tag*{Identity law}\\ \equiv&(q\vee\lnot p)\vee(p\vee r)\tag*{Commutative law}\\ \equiv&((q\vee\lnot p)\vee p)\vee r\tag*{Associative law}\\ \equiv&(q\vee(\lnot p\vee p))\vee r\tag*{Associative law}\\ \equiv&(q\vee\top)\vee r\tag*{Negation law}\\ \equiv&\top\tag*{Domination law$\times2$}\\ \end{align}

Hence we proved it's a tautology.

Answer 2

Sometimes it is easier to show that an expression is a contradiction (always false).

Using another more convenient way to write logical expressions you have

• $E = ((p+q)(p'+r))' + q+r$

Now using DeMorgan rules

$$E' = (p+q)(p'+r)q'r' \stackrel{xx'=0}{=}(0+pr+qp'+qr)q'r' = 0+0+0+0 = 0$$

So, $E'$ is a contradiction, hence $E$ is a tautology.