How could we prove that $(p \vee q) \wedge( \neg p \vee r )\rightarrow (q \vee r)$ is a tautology?

How could we prove that $(p \vee q) \wedge( \neg p \vee r )\rightarrow (q \vee r)$ is a tautology?

I am more interested in the algebraic method. We can use all the rules of inferences except the Resolution.

-
Depends, what are your axioms? – Thomas Andrews Sep 26 '12 at 19:29
Work out the truth table and make sure that the truth value of the formula is T for all eight combinations of truth values of $p,q$, and $r$. – Brian M. Scott Sep 26 '12 at 19:30

We have \begin{align*} (p \vee q) \wedge( \neg p \vee r )\rightarrow (q \vee r) &\equiv (p \wedge \neg p) \vee (q \wedge \neg p) \vee (q \wedge r) \vee (p \wedge r) \to q \vee r\\ &\equiv \neg \bigl((q \wedge \neg p) \vee (q \wedge r) \vee (p \wedge r)\bigr) \vee q \vee r\\ &\equiv \bigl((\neg q \vee p) \wedge (\neg q \vee \neg r) \wedge (\neg p \vee \neg r)\bigr) \vee q \vee r\\ &\equiv (\neg q \vee p \vee q \vee r) \wedge (\neg q \vee \neg r \vee q \vee r) \wedge (\neg p \vee \neg r \vee q \vee r)\\ &\equiv \top \wedge \top \wedge \top \equiv \top. \end{align*}

-

The easiest way is to compute the value of the formula for every possible argument values and make sure it is always 1. The more elegant way is to transform the formula like this:

$(p \vee q) \wedge( \neg p \vee r )\rightarrow (q \vee r)$

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

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

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

next step involves resolution rule (i don't know how to complete the transformation without it)

$\neg p \vee p$ (i joined the first term with the third and the second term with the fourth)

Why are you not allowed to use resolution?

-

Not sure if this fits your requirements: Starting with $(p\lor q)\land(\neg p\lor r)$, you should be able to derive $\neg p\to q$ and $p\to r$. I assume it is known that $p\lor\neg p$ is a tautology. Using constructive dilemma, from $\neg p\to q$, $p\to r$ and $p\lor\neg p$, we obtain $q\lor r$. In summary, we obtained $q\lor r$ from $(p\lor q)\land(\neg p\lor r)$, that is $$(p\lor q)\land(\neg p\lor r)\to (q\lor r).$$

-
Nice one, wish I could +1 :) – Eric Sep 27 '12 at 4:44

Using a different notation, we have

\begin{align} (p + q)(\bar p + r) \to (q + r) &= \overline{((p + q)(\bar p + r))} + (q + r) & \text{material implication} \\ &= \overline{(p + q)} + \overline{(\bar p + r)} + (q + r) & \text{DeMorgan's Law} \\ &= \bar p \bar q + p \bar r + q + r & \text{DeMorgan's Law} \\ &= p + r + \bar p + q & \text{simplification} \\ &= (p + \bar p) + r + q & \text{associativity of+} \\ &= 1 + r + q & \text{complementarity} \\ &= 1 & \text{absorption} \end{align}

-