Natural deduction - finishing the proof

Question

Give a natural deduction proof of ($\neg A \lor B) \Leftrightarrow C$ from hypotheses $\neg A \to C$ and $B \Leftrightarrow C$

My attempt so far:

1. $\neg A \to C$
2. $B \Leftrightarrow C$
3. C
4. $\neg A$ (1,3, $\to e)$
5. $\neg A \lor B$ (4, $\lor i)$

How can I finish the proof?

Answer 1

Are you familiar with deduction trees?

Showing $\neg A \lor B \rightarrow C$: $$ \dfrac { \dfrac { [\neg A \lor B] \quad \dfrac{[\neg A] \quad \neg A \rightarrow C}{C} \quad \dfrac{[B] \quad {\dfrac{B \leftrightarrow C}{B \rightarrow C}}}{C} } { C } } { \neg A \lor B \rightarrow C } $$

Showing $C \rightarrow \neg A \lor B$: $$ \dfrac { \dfrac { \dfrac { [C] \quad \dfrac{B \leftrightarrow C}{C \rightarrow B} } { B } } { \neg A \lor B } } { C \rightarrow \neg A \lor B } $$

Answer 2

To derive $(\neg A \lor B) \Leftrightarrow C$ from hypotheses $\lnot A \to C$ and $B \leftrightarrow C$, you need to obtain $C$ from the assumption of $(\neg A \lor B)$ and $(\neg A \lor B)$ from the assumption of $C$.

$ \def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \def\Ae#1{\qquad\mathbf{\forall\,Elim}\colon #1 \\} \def\Ai#1{\qquad\mathbf{\forall\,Intro}\colon #1 \\} \def\Ee#1{\qquad\mathbf{\exists\,E}\colon #1 \\} \def\Ei#1{\qquad\mathbf{\exists\,Intro}\colon #1 \\} \def\R#1{\qquad\mathbf{R}\colon #1 \\} \def\ci#1{\qquad\mathbf{\land\,I}\colon #1 \\} \def\ce#1{\qquad\mathbf{\land\,E}\colon #1 \\} \def\oe#1{\qquad\mathbf{\lor\,E}\colon #1 \\} \def\ii#1{\qquad\mathbf{\to I}\colon #1 \\} \def\ie#1{\qquad\mathbf{\to E}\colon #1 \\} \def\be#1{\qquad\mathbf{\leftrightarrow E}\colon #1 \\} \def\bi#1{\qquad\mathbf{\leftrightarrow I}\colon #1 \\} \def\qi#1{\qquad\mathbf{=I}\\} \def\qe#1{\qquad\mathbf{=E}\colon #1 \\} \def\ne#1{\qquad\mathbf{\neg E}\colon #1 \\} \def\ni#1{\qquad\mathbf{\neg I}\colon #1 \\} \def\IP#1{\qquad\mathbf{IP}\colon #1 \\} \def\X#1{\qquad\mathbf{\bot\,Elim}\colon #1 \\} \def\DNE#1{\qquad\mathbf{DNE}\colon #1 \\} $

$ \fitch{ \lnot A \to C\\ B \leftrightarrow C }{ \fitch{\lnot A \lor B}{ \vdots\\ C }\\ \fitch{C}{ \vdots\\ \lnot A \lor B } } $

A couple of points about your proof:

• Remember to clearly mark your assumptions. Sometimes, indentation is used to accomplish that task.
• Your line 4 is incorrect: you cannot derive $\lnot A$ from $\lnot A \to C$ and C. The rule of modus ponens states that, for any propositions $P, Q$ $$P \to Q, P \vdash Q$$