If one of the hypotheses holds, then one of the conclusions holds. (looking for a proof)

Question

Using a huge truth table, I proved the theorem below. I cannot find a more elegant proof. I tried to rewrite expressions; e.g. using the distributive laws and the laws of absorption - to no avail. Is there another proof - or any hint? I know that the issue is very basic which makes me feel quite stupid.

---

Theorem

If we have

• $A \Rightarrow A'$ and
• $B \Rightarrow B'$ and
• $A \lor B$,

then we have $A' \lor B'$.

---

P.S.: I know that the theorem is simple and might be accepted without a proof. Still, I am looking for a rigorous proof.

Answer 1

So you want to prove $$((A \Rightarrow A') \wedge (B \Rightarrow B')) \Rightarrow (A \vee B \Rightarrow A' \vee B')$$

You can rewrite it as: $$\begin{align} & \equiv (\neg (A \Rightarrow A') \vee \neg (B \Rightarrow B')) \vee (A \vee B \Rightarrow A' \vee B') \\ & \equiv ((A \wedge \neg A') \vee (B \wedge \neg B')) \vee ((\neg A \wedge \neg B) \vee (A' \vee B')) \\ & \equiv (A \wedge \neg A') \vee (B \wedge \neg B') \vee (\neg A \wedge \neg B) \vee A' \vee B' \end{align}$$

Now it's just a matter of using distributivity law to regroup terms and eliminate all $(p \vee \neg p) \equiv \top$ to get $\top$ in the end.

Answer 2

One of the ways is to get rid of disjunctions using implication. $A \lor B$ is the same as $\lnot B \Rightarrow A$, and $A' \lor B'$ is the same as $\lnot B' \Rightarrow A'$. Also, $B \Rightarrow B'$ is the same as its contrapositive $\lnot B' \Rightarrow \lnot B$.

So, now you are given that $\lnot B' \Rightarrow \lnot B$, $\lnot B \Rightarrow A$, and $A \Rightarrow A'$. You need to show that $\lnot B' \Rightarrow A'$. But now it follows from the "transitivity" of implication.

PS: this isn't very rigorous, but the way to make it more accurate depends on how things are defined, what can be considered as already known, and what standard of rigour you require.

Answer 3

You can prove it by Natural Deduction :

(1) $A \rightarrow \lnot A$ --- (Ass 1)

(2) $A$ --- aux assumption 1

(3) $\lnot A$ --- by $\rightarrow$-elim

(4) $\lnot A \lor \lnot B$ --- by $\lor$-intro

(5) $B \rightarrow \lnot B$ --- (Ass 2)

(6) $B$ --- aux assumption 2

(7) $\lnot B$ --- by $\rightarrow$-elim

(8) $\lnot A \lor \lnot B$ --- by $\lor$-intro

(9) $A \lor B$ --- (Ass 3).

Thus :

$A \rightarrow \lnot A, \quad B \rightarrow \lnot B, \quad A \lor B \quad \vdash \lnot A \lor \lnot B$ --- from (2)-(4) and (6)-(8) and (9) by $\lor$-elim, discharging auxiliary assumptions 1 and 2.

Answer 4

Based on niks' answer, I wrote the following proof, for which any feedback is appreciated. The proof only uses laws that can be easily verified with truth tables.

Hint: I often used $X \lor Y \Leftrightarrow X \lor (Y \land \neg X)$.

---

$ \top \\ (A' \lor B' \lor B) \lor \top \\ (A' \lor B' \lor B) \lor (\neg A \lor A) \\ A' \lor B' \lor B \lor \neg A \lor A \\ A' \lor A \lor B' \lor B \lor \neg A \\ A' \lor A \lor B' \lor B \lor (\neg A \land \neg B) \\ (A' \lor A) \lor (B' \lor B) \lor (\neg A \land \neg B) \\ A' \lor ( A \land \neg A') \lor B' \lor ( B \land \neg B') \lor (\neg A \land \neg B) \\ ( A \land \neg A') \lor ( B \land \neg B') \lor (\neg A \land \neg B) \lor (A' \lor B') \\ \neg (\neg A \lor A') \lor \neg (\neg B \lor B') \lor \neg ( A \lor B) \lor (A' \lor B') \\ \neg ( (\neg A \lor A') \land (\neg B \lor B') \land ( A \lor B)) \lor (A' \lor B') \\ (\neg A \lor A') \land (\neg B \lor B') \land ( A \lor B) \Rightarrow (A' \lor B') \\ ( A \Rightarrow A') \land ( B \Rightarrow B') \land ( A \lor B) \Rightarrow (A' \lor B') \\ ( A \Rightarrow A') \land ( B \Rightarrow B') \land ( A \lor B) \Rightarrow A' \lor B' $

Answer 5

Here is yet another proof, using the fact that $\;P \Rightarrow Q\;$ can be rewritten as $\;P \lor Q \equiv Q\;$. Introducing that equivalence makes possible the following proof which uses only equivalences:

\begin{align} & A' \;\lor\; B' \\ \equiv & \qquad \text{"using $\;A \Rightarrow A'\;$ and $\;B \Rightarrow B'\;$, in the above form"} \\ & A \lor A' \;\lor\; B \lor B' \\ \equiv & \qquad \text{"symmetry of $\;\lor\;$; using $\;A \lor B\;$"} \\ & \text{true} \;\lor\; A' \lor B' \\ \equiv & \qquad \text{"simplify using $\;P \lor \text{true} \;\equiv\; \text{true}\;$"} \\ & \text{true} \\ \end{align}