Help with natural deduction

Question

I was able to get this one, it was fairly simple.

¬ (¬p ∨ q) |- p
{
  1. ¬ (¬p ∨ q)             premise
  2. {
       3. ¬p                assume
       4. ¬p ∨ q            ∨i1 3
       5. ⊥                 ¬e 4 1
      }
  6. p                      pbc 2
}

I was able to figure this one out with the help below.

¬ (p ∨ q) |- ¬ (¬ p → q)
 {
   1. ¬ (p ∨ q)             premise
   2.{
         3. ¬ p → q         assume
         4.{
             5. ¬ p         assume
             6. q           ->e 3 5
             7. p ∨ q       Vi2 6
             8.⊥            ¬e 7 1
           }
         12. p              pbc 4
         13. p V q          Vi1 12
         14. ⊥              ¬e 13 1
     }
   15. ¬ (¬ p → q)          ¬i 2
 }

Somewhat started this one as well, but got overwhelmed and lost on what to do next.

¬ (p ∨ q) |- ¬ (¬ p → q)
{
  1. ¬ (p ∨ q)        premise
  2.{
        3. p          assume
        4. p ∨ q      Vi1 3
        5. ⊥          ¬e 4 1
        6. q          ⊥e 5
    }
  3.
}

¬(p → q) ⊢ p ∧ ¬q

¬(p ∨ s), q ∨ ¬r ⊢ r → q

¬(p ∨ q ∨ r) ⊢ ¬p ∧ ¬q ∧ ¬r

Answer 1

For both of these problems you might want to try using the Law of the Excluded Middle (LEM). To use that consider two cases, $p$ and $\lnot p$. In both cases derive the same statement that you can use later in the proof to reach the desired conclusion.

I will provide an example by showing how one could prove the second statement. This also illustrates the use of a proof checker that might come in handy as a supplement to your current text.

Note how in both cases, first using $\lnot P$ on lines 3-5 and second using $P$ on lines 6-7, I derived $P \lor Q$. On line 8 I combined those two cases and justified line 8 with "LEM 3-5,6-7". This led to the contradiction between lines 1 and 8 on line 9.

You can do something similar with the first problem. You already considered the $p$ case. You only have to consider the $\lnot p$ case.

---

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/

Answer 2

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

When seeking to prove something false, assume that it is true with the aim of deriving a contradiction.

How might assumptions of $\lnot(p\lor q), \lnot p\to q$ produce a contradiction? Well, a further assumption of $p$ would derive a contradiction, thus we infer $\lnot p$ by proof of negation, and from that we may derive $q$, so...

• $\lnot (p\lor q)$ by premise
  • $\lnot p\to q$ by assumption
    • $p$ by assumption
    • $p\lor q$ by disjunction introduction ($\vee i$)
    • $\bot$ by negation elimination ($\lnot e$)
  • $\lnot p$ by negation introduction ($\lnot i$)
  • $q$ by conditional elimination ($\to e$; aka modus ponens)
  • $p\lor q$ by disjunction introduction ($\lor i$)
  • $\bot$ by negation elimination ($\lnot e$)
• $\lnot(\lnot p\to q)$ by negation introduction ($\lnot i$)

---

$¬(p → q) ⊢ p ∧ ¬q$

Show that an assumption of $q$ derives a contradiction of the premise, and that an assumption of $\lnot p$ does too. Then use conjunction introduction to tie the results together.

$¬(p ∨ s), q ∨ ¬r ⊢ r → q$

A straight forward conditional proof, since $q\lor\lnot r, r\vdash q$ by disjunctive syllogism.   (Notice: $\lnot(p\lor s)$ is an unnecessary premise.)

$¬(p ∨ q ∨ r) ⊢ ¬p ∧ ¬q ∧ ¬r$

Again, three proofs of contradiction, showing assumptions or $p$, $q$, and $r$ can each derive a contradiction of the premise. Then use conjunction introduction twice to tie the results together.