Diffucult Tautology to Prove

Question

I'm trying to show that the following is a tautology:

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

Can anyone help, as far as I can get is to the following:

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

Answer 1

Suppose “$p$ or $q$” and “not $p$ or $r$” are true. We need to show that “$q$ or $r$” is true.

Case 1: $q$ is true. Then we're done.

Case 2: $q$ is not true. In order to show “$q$ or $r$,” we must prove that $r$ is true. Now, since $q$ is not true but “$p$ or $q$” is, it follows that $p$ is true. Now, “not $p$ or $r$” is true, but “not $p$” is not true (since $p$ is true), so it must be the case that $r$ is true, as required.

Answer 2

A very simple and clean way to do this is to write a table with all the possibillities.

$$\begin{array}{c|c|c|c|c|} \hline & \text{p} & \text{not }p & q & r\\ \hline 1&\text{true} & \text{false} & \text{true} & \text{true}\\ 2&\text{true} & \text{false} & \text{true} & \text{false}\\ 3&\text{true} & \text{false} & \text{false} & \text{true}\\ 4&\text{true} & \text{false} & \text{false} & \text{false}\\ 5&\text{false} & \text{true} & \text{true} & \text{true}\\ 6&\text{false} & \text{true} & \text{true} & \text{false}\\ 7&\text{false} & \text{true} & \text{false} & \text{true}\\ 8&\text{false} & \text{true} & \text{false} & \text{false}\\ \hline \end{array}$$

Now you impose the conditions. Firstly $(p \text{ or } q)$ mean we can remove line 7 and 8 (since both $p$ and $q$ are false there so they are not cases we are interested in). Secondly $(\text{not } p \text{ or } r)$ means we can strike line 2 and line 4. You are then left with

$$\begin{array}{c|c|c|c|c|} \hline & \text{p} & \text{not }p & q & r\\ \hline 1&\text{true} & \text{false} & \text{true} & \text{true}\\ 3&\text{true} & \text{false} & \text{false} & \text{true}\\ 5&\text{false} & \text{true} & \text{true} & \text{true}\\ 6&\text{false} & \text{true} & \text{true} & \text{false}\\ \hline \end{array}$$

We have now shown that $(p \text{ or } q)$ and $(\text{not } p \text{ or } r)$ implies that one of the possibillities above apply. Compare this with what you are trying to prove. Can you take it from here?

Answer 3

Proposition. In the Boolean domain, the following is a tautology: $$(p \vee q) \wedge (\neg p \vee r) \Rightarrow (q \vee r)$$

Proof.

• If $p = 1$, then the formula becomes $r \Rightarrow q \vee r$, which is clearly true.

• If $p = 0$, then the formula becomes $q \Rightarrow q \vee r$, which is clearly true.