# Proving the sentence $X \lor Y {\implies}Z$

I want to prove that $$(\neg b \lor \neg c) {\implies} \neg a.$$

Now, acknowledging that $$\lor$$ is the inclusive 'or', this statement means that showing at least one of $$\neg b$$ or $$\neg c$$ is sufficient to show $$\neg a.$$ So, is there anything logically incorrect about using both $$\neg b$$ and $$\neg c$$ to show $$\neg a$$?

EDIT: I am now realizing that this question is independent of negations/contrapositives. The core of my question is: if $$(X \lor Y) {\implies} Z$$ and since "$$\lor$$" is not exclusive, then may I use $$(X\land Y)$$ to show $$Z$$?

• Do you mean showing $(\neg b \to \neg a) \land (\neg c \to \neg a)$ or $(\neg b \land \neg c) \to \neg a$? The former is the correct way to go, and the latter is equivalent to $a \to (b \lor c)$. Sep 26 at 15:20
• I'm sorry, maybe I don't understand your question. I understand that the contrapositive of $a \implies (b \land c)$ is $\neg(b \land c) \implies \neg a$ which is equivalent to $(\neg b \lor \neg c) \implies \neg a$ by DeMorgan's. The statement $(\neg b \lor \neg c) \implies \neg a$ is the statement I have a question about. Now, that I think about it, this question is independent of negations/contrapositives. Sep 26 at 15:42
• Either way, for proof by cases from a disjunction $A \lor B$ to a conclusion $C$, you must show both $A \to C$ and $B\to C$ (or something to that effect) in order to actually derive $C$. Sep 26 at 15:47
• Your last sentence before the edit is ambiguous, in the way PW_246 pointed out. You need to clarify which you mean. Sep 26 at 15:56
• @PW_246 I understand what you're asking now. I meant the latter Sep 26 at 16:22

If you want to prove $$(\neg b \lor \neg c) \to \neg a$$, you could also try proving proving the equivalent $$a \to (b \land c)$$

(I wonder if maybe that's where the $$(\neg b \lor \neg c) \to \neg a$$ came from in the first place?)

Anyway, proving $$a \to (b \land c)$$ would seem to be a little more direct: just assume $$a$$, and try to prove $$b \land c$$ ... which would merely require you to prove $$b$$ and $$c$$ individually.

Effectively, you would have to prove $$a \to b$$ and $$a \to c$$.

Now, for each of those you could prove the contrapositive .. and note that if you have $$\neg b \to \neg a$$ as well as $$\neg c \to \neg a$$, then you have shown $$(\neg b \to \neg a) \land (\neg c \to \neg a)$$, which is equivalent to $$(\neg b \lor \neg c) \to \neg a$$

So you could say that it really doesn't matter whether you try to prove $$a \to (b \land c)$$ or $$(\neg b \lor \neg c) \to \neg a$$ .. in the end, you need to prove 2 things:

1. Either $$a \to b$$ or its contrapositive $$\neg b \to \neg a$$

2. Either $$a \to c$$ or its contrapositive $$\neg c \to \neg a$$

And note, maybe for the one the direct proof is easier/more intuitive, but for the other one the contrapositive proof is easier to think about.

Also: note that you need to show both of 1 and 2. So, when you say:

this statement [i.e. $$(\neg b \lor \neg c) \to \neg a$$] means that showing at least one of ¬b or ¬c is sufficient to show ¬a

you are expressing what that statement means correctly ... but in order to prove that statement, it is not sufficient to show just one of 1. and 2 ... you need to prove both, so that once you have that statement, anyone who has $$\neg b$$ can infer $$\neg a$$, and that anyone who has $$\neg c$$ can infer $$\neg a$$

In order to derive the formula $$(X \vee Y) \to Z$$, at least two approaches come to mind:

Approach $$1$$ : First, assume $$X \vee Y$$ is true. Then, under that assumption, derive $$Z$$. You are then justified in concluding if $$X \vee Y$$, then $$Z$$. The inference rule that supports this is known as conditional proof, and it stems from the deduction theorem, here applied as follows

$$X \vee Y \vdash Z \Leftrightarrow \hspace{5pt} \vdash (X \vee Y) \to Z$$

Approach $$2$$ : First, assume $$X$$ is true. Then, under that assumption, derive $$Z$$. This allows you to infer $$X \to Z$$ via conditional proof. Secondly, assume $$Y$$ is true. Then, under that assumption, derive $$Z$$. This allows you to infer $$Y \to Z$$ once again via conditional proof. Having inferred both $$X \to Z$$ and $$Y \to Z$$ separately, you are then justified in concluding $$(X \vee Y) \to Z$$. This last piece of reasoning is supported by the inference rule known as conjunction introduction, here applied as

$$X \to Z, Y \to Z \vdash (X \to Z) \wedge (Y \to Z)$$,

together with the following logical equivalencies

$$\begin{array}{l1} (X \to Z) \wedge (Y \to Z) & \\ \equiv (\neg X \vee Z) \wedge (Y \to Z) & \text{Implication Rule} \\ \equiv (\neg X \vee Z) \wedge (\neg Y \vee Z) & \text{Implication Rule} \\ \equiv (\neg X \wedge \neg Y) \vee Z & \text{Distributive Law} \\ \equiv \neg (X \vee Y) \vee Z & \text{DeMorgan's Law} \\ \equiv (X \vee Y) \to Z & \text{Implication Rule}\\ \end{array}$$

I want to prove that $$\color{brown}{(\neg b \lor \neg c) {\implies} \neg a}.$$

is there anything logically incorrect about using both $$\neg b$$ and $$\neg c$$ to show $$\neg a$$?

if $$\color{brown}{(X \lor Y) {\implies} Z}$$ and since "$$\lor$$" is not exclusive, then may I use $$(X\land Y)$$ to show $$Z$$?

$$\color{brown}{(X∨Y→Z)}\tag1$$ $$(X∧Y→Z)\tag2$$

1. To be clear: your goal is simply to prove sentence $$\color{brown}{(1)},$$ rather than to prove that sentence $$\color{brown}{(1)}$$ implies sentence $$(2).$$

2. Observe that conditional $$\color{brown}{(1)}$$ has a weaker condition than the conditional $$(2).$$ This means that $$\color{brown}{(1)}$$ is a stronger sentence than $$(2),$$ which means that sentence $$\color{brown}{(1)}$$ implies sentence $$(2)$$ but not vice versa. Convince yourself that $$(X∧Y→Z) \kern.6em\not\kern-.6em\implies \color{brown}{(X∨Y→Z)}$$ by considering a false $$Z$$ with $$X$$ and $$Y$$ having opposite truth values.

3. A few more relevant logical facts: \begin{align}(X→Z) ∧ (Y→Z) \implies &\color{brown}{(X∨Y→Z)} \\ (X→Z) ∨ (Y→Z) \kern.6em\not\kern-.6em\implies &\color{brown}{(X∨Y→Z)}\\ (X→Z) \kern.6em\not\kern-.6em\implies &\color{brown}{(X∨Y→Z)}.\end{align} Also relevant: the main condition in the middle line is equivalent to sentence $$(2).$$