Construct Natural Deduction proofs

Question

Construct Natural Deduction proofs for the following

¬p ∨ q $\vdash$ p → q

$\neg \neg p \vdash p$

¬p∧¬q $\vdash$ ¬(p∨q)

$\vdash$ ¬(p∧¬p)

$\vdash$ p∨¬p

I studied natural deduction in A concise introduction to logic (where these problems are from), but I feel like I'm misunderstanding some of the introduction/elimination rules. I thought you could just directly eliminate double negatives (2), and I thought we were able to add $p \lor \neg p$ to anything (5), but those proofs are supposedly longer, so I'm not sure what to do. Any help on any of these problems would be great. Thank you in advance!

Answer 1

Hint

For 1) : assume $p$ and apply $∨$-elim to the premise.

For 3) : assume $p ∨ q$ and apply $∨$-elim to it.

For 4) : assume $p ∧ ¬p$ and derive $⊥$.

Regarding 5) : it depends on the set of rules available.

Answer 2

You seem to be using the turnstile symbol $\vdash$ as a replacement for "therefore" to indicate the conclusion of an argument, so I treat it as such in the below proofs. In order to prove the latter two you must employ conditional proofs (review chapter 7.5 of A Concise Intro to Logic, 11th ed., by Hurley). Observe the use of the double negation and addition rules.

Show: ¬p ∨ q ⊢ p → q

1. $\neg p \vee q$ premise
2. $p \rightarrow q$ implication rule, 1

   ---

Show: ¬¬p⊢p

1. $\neg \neg p$ premise
2. $p$ double negation rule, 1

   ---

show: ¬p∧¬q ⊢ ¬(p∨q)

1. $\neg p \wedge \neg q$ premise
2. $\neg (p \vee q)$ DeMorgan's Rule, 1

   ---

Show: ⊢ ¬(p∧¬p)

1. $p$ assumption of conditional proof
2. $p \vee \neg p$ disjunction introduction (aka addition rule), 1
3. $p \rightarrow (p \vee \neg p)$ conditional proof, 1-2
4. $\neg p \vee (p \vee \neg p)$ implication rule, 3
5. $\neg p \vee (\neg p \vee p)$ commutative rule, 4
6. $(\neg p \vee \neg p) \vee p$ associative rule, 5
7. $\neg p \vee p$ idempotent rule (aka tautology rule), 6
8. $\neg p \vee \neg \neg p$ double negation rule, 7
9. $\neg (p \wedge \neg p)$ DeMorgan's Rule, 8

---

Show: ⊢ p∨¬p

1. $\neg p$ assumption of conditional proof
2. $\neg p \vee p$ disjunction introduction (aka addition rule), 1
3. $\neg p \rightarrow (\neg p \vee p)$ conditional proof, 1-2
4. $\neg \neg p \vee (\neg p \vee p)$ implication rule, 3
5. $p \vee (\neg p \vee p)$ double negation rule, 4
6. $p \vee (p \vee \neg p)$ commutative rule, 5
7. $(p \vee p) \vee \neg p$ associative rule, 6
8. $p \vee \neg p$ idempotent rule (aka tautology rule), 7