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.
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.
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).$
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}$