# Introductory Natural Deduction Question

So I'm new to logic and taking an introductory logic course, and I'm really having trouble with these 2 questions:

1. Using the system of Natural Deduction in the textbook, provide a derivation to establish that the following sentence is a Logical Truth: A ⊃ (B ⊃ A)

2. Using the system of Natural Deduction in the textbook, provide a derivation to establish that the following sentence is a Contradiction: ∼(A ∨ ∼(A & B))

The system of derivation in the textbook is just normal natural deduction (ex. using rules like conditional introduction/elimination, conjunction introduction/elimination, etc. BASIC rules.)

For A ⊃ (B ⊃ A), we have the following derivation :

1) A --- assumed

2) B ⊃ A --- from (1) by ⊃-introduction

3) A ⊃ (B ⊃ A) --- from (1)-(2) by ⊃-introduction.

For ∼(A ∨ ∼(A & B)) the simplest thing is to prove that it is a contardiction (i.e. identically false) via truth table.

In alternative, you can build a proof of (A ∨ ∼(A & B)) showing that it is a tautology (by soundness); thus its negation : ∼(A ∨ ∼(A & B)) must be a contradiction.

The shape of A → (B → A) hints at an obvious solution: assume A to get (B → A). The problem is now simpler (viz. B → A), but still of the same shape, so we again assume B to get A. But we already have A! So we simply reiterate it (this is the first rule below). Since having assumed B we were able to obtain A (lines 3-4), we conclude by →-introduction (B → A). But we have also assumed A and gotten (B → A), so again by →-introduction we conclude the desired conclusion. The second one isn't so straightforward. Suppose, for contradiction, that ⊢ ¬(A ∨ ¬(A ∧ B)). If we were able to obtain ⊢ A or ⊢ ¬(A ∧ B), we could get by ∨-elimination ⊢ (A ∨ ¬(A ∧ B), which would allow us to conclude ⊢ ⊥. So that's the strategy: to prove either ⊢ A or ⊢ (A ∨ ¬(A ∧ B). I didn't see a direct way of proving ⊢ A, so I proceeded to prove ⊢ (A ∨ ¬(A ∧ B) first in order to get ⊢ A (lines 2 to 7). If you were allowed to use a De Morgan's Law [ ¬(φ ∨ ψ ⊢ ¬φ ∧ ¬ψ) ], we could just push the negation in to obtain ¬A ∧ ¬¬(A ∧ B), cancel the double negation to get ¬A ∧ (A ∧ B), open the parens (justified by the associativity of conjunction) to get ¬A ∧ A ∧ B. From this we'd get ⊢¬A and ⊢ A, which by ⊥-introduction would allow us to conclude ⊢⊥.

Hint for 2nd problem:

1. Suppose it is true.
2. Apply DeMorgan.
3. Obtain A & ~A.

Seeking to prove a nested conditional statement, use nested conditional proofs to introduce the conditional connectives. Now then, what assumptions must you make and what argument reaches the final conclusion?

`````` |_
|  |_ ...       Ass
|  |  |_ ...    Ass
|  |  |  ...    ???
|  |  B > A     >I
|  A > (B > A)  >I
``````

It metaphorically writes itself.

In seeking to prove the negation of a disjuntion is a contradiction, use a proof by negation. Since there are no premises to contradict, hopefully the statement is indeed self-contradictory.

``````|_
|   |_ ~(A ∨ ∼(A & B))
|   |  ...
|   |  A v ~(A & B)        Somehow
|   |  #                   ~E
|   ~(~(A v ~(A & B))      ~I
``````

So we seek to show that indeed at least one of the disjunctions must be satisfied. We hope that assuming the contrary of one derives the other, contradicting the initial assumption, thus deducing that the first must be true, also contradiction the initial assumption.

By inspection the second disjunct looks cleanest to work with; since again that involves introducing a negation. And indeed, immediately we can see that A & B derives A as desired.

``````|_
|   |_ ~(A ∨ ∼(A & B))
|   |   |_ A & B
|   |   |  A                &E
|   |   |  A v ~(A & B)     vI
|   |   |  #                ~E
|   |   ~(A & B)            ~I
|   |  A v ~(A & B)        vI
|   |  #                   ~E
|   ~(~(A v ~(A & B))      ~I
``````