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

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

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/