How can I prove this propositional sequent without using the Principle of Explosion (ex falso quodlibet) I'm beginning to study propositional logic from a book called Elementary Logic by Brian Garrett.
In the chapter on the disjunctive connective, I've come across an exercise that seems to require the Principle of Explosion, but this rule is never introduced anywhere in the book. I only know about this principle because others have solved this very problem using it, but I want to solve it using the rules provided in the book, which are the introduction and elimination of the five connectives ($\land\lor\neg\implies\iff$) and assumptions.
Here is the problem: $\neg A \lor \neg B \models (A \implies C) \lor (B \implies C)$
My understanding is that I must prove the following
$\neg A \implies ((A \implies C) \lor (B \implies C))$
$\neg B \implies ((A \implies C) \lor (B \implies C))$
I don't understand how to introduce the term C into this proof without the Principle of Explosion; I'm assuming you need a term C to introduce any kind of implication involving C as its consequent. I understand that with the explosion principle, I can introduce anything after a contradiction, which is how C enters this problem and how I can then deduce the conditionals $A \implies C$ and $B \implies C$
With explosion, the following is what I have:
$
\neg A \lor \neg B\\           
\quad\mid\neg A\\            
\quad\quad\mid A\\ 
\quad\quad\mid A \land \neg A\\
\quad\quad\mid C \qquad\qquad Principle \, of \, Explosion\\
\quad\mid A \implies C\\
\quad\mid (A \implies c) \lor (B \implies C)\\
\neg A \implies ((A \implies C) \lor (B \implies C))\\
\quad\mid\neg B\\            
\quad\quad\mid B\\ 
\quad\quad\mid B \land \neg B\\
\quad\quad\mid C \qquad\qquad Principle \, of \, Explosion\\
\quad\mid B \implies C\\
\quad\mid (A \implies c) \lor (B \implies C)\\
\neg B \implies ((A \implies C) \lor (B \implies C))\\
(A \implies C) \lor (B \implies C)
$
Given that this text never discusses this principle, and restricts all solutions to using the primary connectives and basic assumptions, which seems to follow minimal logic, can this problem actually be solved? If not, I wonder why this problem presents itself in the book.
Any and all help will be greatly appreciated. Thank you.
 A: The rules, as I know them from this book, for implication is that if $P$ was used to derive $Q$, then we can derive $P \implies Q$. The negation rule is that if from $P$ we derive $Q \land \neg Q$, then we can derive $\neg P$.
At this point in the book, it is suggested that there is no need to use equivalent propositions, or any derived rules to solve the exercise sequences. I'm new to all this, but it seems that using the explosion principle is a derived rule that allows me to deduce $C$, whereas I believe its necessary to assume $C$ or $\neg C$ given the rules above.
I think the following is correct and consistent with the primary rules stated above without using the explosion principle. Please, let me know otherwise. Greatly appreciated.
$
\neg A \lor \neg B\\           
\quad\mid\neg A\\            
\quad\quad\mid A\\ 
\quad\quad\quad\mid \neg C\\
\quad\quad\quad\mid A \land \neg A\\
\quad\quad\quad\mid \neg C \land (A \land \neg A)\\
\quad\quad\quad\mid A \land \neg A\\
\quad\quad\mid C\\
\quad\mid A \implies C\\
\quad\mid (A \implies C) \lor (B \implies C)\\
\neg A \implies ((A \implies C) \lor (B \implies C))\\
\quad\mid\neg B\\            
\quad\quad\mid B\\ 
\quad\quad\quad\mid \neg C\\
\quad\quad\quad\mid B \land \neg B\\
\quad\quad\quad\mid \neg C \land (B \land \neg B)\\
\quad\quad\quad\mid B \land \neg B\\
\quad\quad\mid C\\
\quad\mid B \implies C\\
\quad\mid (A \implies C) \lor (B \implies C)\\
\neg B \implies ((A \implies C) \lor (B \implies C))\\
(A \implies C) \lor (B \implies C)\\
$
