2
$\begingroup$

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.

  • 3
    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$.2012-09-26

4 Answers 4

3

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*}

0

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?

0

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

  • 0
    Nice one, wish I could +1 :)2012-09-27
0

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