Prove the following using proof of contradiction:
a → c
b → d
(c ∨ d) → ¬e
(e ∨ f) → (a ∨ b)
∴ ¬e
What I have done so far is:
1. a → c
2. b → d
3. (c ∨ d) → ¬e
4. (e ∨ f) → (a ∨ b)
5. ¬(¬e) Assume for contradiction
6. ¬¬e De Morgan (5)
7. e Double Negation (6)
8. ¬a ∨ c Implication Equivalence (1)
9. ¬b ∨ d Implication Equivalence (2)
What do I do next? Please help
On
Tip: Just assume $\rm e$, so should you manage to derive a contradiction, there you may use negation introduction to immediately arrive at the desired conclusion.
Having assumed $\rm e$, look for a premise in which it occurs. That would be premise 4, where it is a disjunct in the antecedant of a conditional. Introduce a disjunction and eliminate the condtional.
Having so derived $\rm a\lor b$, you need to ... complete the proof by filling in the missing details.
| 1. a → c
| 2. b → d
| 3. (c ∨ d) → ¬e
|_ 4. (e ∨ f) → (a ∨ b)
| |_ 5. e
| | 6. e ∨ f disjunction introduction, 5
| | 7. a ∨ b conditional elimination, 6, 4
: :
| | 19. ¬e disjunction elimination, 7, ..., ...
| | 20. # negation elimination, 5, 19
| 23. ¬e negation introduction, 5-20
$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}{\fitch{~~1.~a \to c \\~~2.~b \to d \\~~3.~(c \vee d) \to \neg e \\~~4.~(e \vee f) \to (a \vee b)}{\fitch{~~5.~e}{~~6.~e\vee f\hspace{10ex}\vee\mathsf I,5\\~~7.~a\vee b\hspace{10ex}\to\mathsf E,6,4\\\fitch{~~8.~a}{~~9.~c\hspace{10ex}\to\mathsf E, 8,1\\10.~c\vee d\hspace{6ex}~\vee\mathsf I, 9}\\11.~a\to c\vee d\hspace{5ex}\to\mathsf I, 8{-}10\\\fitch{12.~b}{13.~d\hspace{10ex}\to\mathsf E, 12,2\\14.~c\vee d\hspace{7ex}\vee\mathsf I, 13}\\15.~b\to c\vee d\hspace{6ex}\to\mathsf I, 12{-}14\\16.~c\vee d\hspace{11ex}\vee\mathsf E, 7,11,15\\17.~\neg e\hspace{13ex}\to\mathsf E, 16, 3\\18.~\bot\hspace{14ex}\neg\, \mathsf E,5,17}\\19.~\neg e\hspace{17ex}\neg\,\mathsf I, 5{-}18}\\\blacksquare}$$
On
In the proof the OP offered are these lines:
- ¬(¬e) Assume for contradiction
- ¬¬e De Morgan (5)
De Morgan's laws would not justify going from line 5 to 6. Rather one can ignore the parentheses in line 5 and write it as $¬¬e$.
The following is a proof using a Fitch-style proof checker. It does not have material implication that was used by the OP in lines 8 and 9 but approaches the proof using modus tollens (MT), conjunction elimination (∧E), conjunction introduction (∧I), De Morgan's laws (DeM), double negative elimination (DNE), disjunction introduction (∨I), negation elimination (¬E) and indirect proof (IP)
Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/
P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Fall 2019. http://forallx.openlogicproject.org/forallxyyc.pdf
Well, under the assumption that $e$, we know that $$(e\vee f)\to(a\vee b) = (\lnot e\wedge \lnot f)\vee a\vee b$$Since $e$, $$(e\vee f)\to(a\vee b) =a\vee b = c\vee d$$But, $$c\vee d\to \lnot e$$ A contradiction. So, $\lnot e$.