Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Depends, what are your axioms? –  Thomas Andrews Sep 26 '12 at 19:29
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$. –  Brian M. Scott Sep 26 '12 at 19:30

4 Answers 4

up vote 3 down vote accepted

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

share|improve this answer

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?

share|improve this answer

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

share|improve this answer
    
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}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.