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