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

Question

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

Answer 1

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$

Answer 2

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

Answer 3

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