# A Natural-Deduction proof of $\{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D$.

I would like to prove

$\{ \neg N,\neg N \to L,D \leftrightarrow \neg N \} \vdash (L \lor A) \land D$.

My work until now is as follows: $$\begin{array}{l|ll} 1 & \neg N & \text{Premise} \\ 2 & (\neg N \to L) \land (D \leftrightarrow \neg N) & \text{Premise} \\ 3 & \vdash (L \lor A) \wedge D & \text{Premise} \\ 4 & \neg N \to L & \text{ \land -Elimination from  2 } \\ 5 & (D \leftrightarrow \neg N) & \text{ \land -Elimination from  2  and  4 } \end{array}$$ What’s next? This is where I’ve been for the past $3$ hours. Help me out if you can, and please suggest me books for Logic and Natural Deduction.

Thanks.

## 3 Answers

The conclusion is not a premise.   You can't use it to prove itself; that's circular reasoning.   Circular reasoning is bad because circular reasoning is bad.

$$\begin{array}{r|ll} 1- & ¬N &\text{Premise} \\ 2- & (¬N → L) \wedge (D ↔ ¬N) &\text{Premise} \\ 3- & ¬N → L &\wedge \text{ Elimination from }2 \\ 4- & & \text{Modus Ponens from }1, 3 \\ 5- & & \vee \text{ Introduction from }4 \\ 6- & (D ↔ ¬N) & \wedge \text{ Elimination from }2 \\ 7- & (D\to \neg N)\wedge (\neg N \to D) & \text{Equivalent restatement of }6 \\ 8- & & \wedge \text{ Elimination from }7 \\ 9- & & \text{Modus Ponens from }1, 8 \\ 10 - & (L\vee A)\wedge D & \wedge \text{ Introduction of }5, 9 \\ \hline \therefore & \{\neg N, (\neg N\to L)\wedge (D\leftrightarrow \neg N)\}\vdash (L\vee A)\wedge D & \Box \end{array}$$

Can you fill in the blanks?

As complement to the answer above, I would suggest you to begin with:

• Hodges & Chirswell's Mathematical Logic (2007) - The very book begin by taking an informal exposal of natural deduction in Chapter 2 before they got more serious on the subject taking the propositional (p.53) and first-order calculus (p.177)

After you get some feeling of it, maybe you would like to take a look at:

• Van Dalen's Logic and Structure (2004) - See p.30 for the propopositional logic and p.91 for first-order calculus. Van Dalen's exposition seems more rigorous, which is why maybe is better to read his book after having some previous knowledge first.

You can also take a look at Peter Smith's wonderful study guide, Teach Yourself Logic.

Here is what the OP would like to prove:

{¬N,¬N→L,D↔¬N}⊢(L∨A)∧D

The attempt, however, combines premises 2 and 3 into one conjunction. It is best to copy the premises as they are into the first lines of the proof.

The OP would also like the following:

...please suggest me books for Logic and Natural Deduction.

The following proof uses the proof checker associated with the forallx Calgary Remix: An Introduction to Formal Logic text. This is a beginning truth-functional and first-order logic textbook. See links below. They may complement the references provided by Bruno Bentzen or what you are using now.

Here is the proof using that proof checker:

Here is the proof in words:

• The first premise allows us to derive $$L$$ from the second premise using conditional elimination (→E).
• The first premise also allows us to derive $$D$$ from the third premise using biconditional elimination (↔E).
• Having $$L$$ we can use disjunction introduction (vI) to "or" anything to it. In particular, we "or" the $$A$$ that we need.
• We have both sentences that we need on lines 5 and 6 and so we use conjunction introduction (∧I) to reach the goal of the proof.

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, Winter 2018. http://forallx.openlogicproject.org/