How to write a natural deduction proof for these formulas?

57 Views Asked by At

I'm new to natural deduction and is having trouble proofing these formulas, any help or hint is appreciated.

$$ \neg \exists p(x)\rightarrow \forall x \neg p(x)\\ \exists x \neg p(x) \rightarrow \neg \forall xp(x) $$

2

There are 2 best solutions below

0
On

Hint

1) $¬∃p(x)$ --- premise

2) $p(x)$ --- assumed [a]

3) $∃p(x)$ --- from 2) by $∃$-intro

4) $\bot$ --- from 1) and 3)

5) $¬p(x)$ --- from 2) and 5) $¬$-intro, discharging [a]

6) $∀x¬p(x)$ --- from 5) by $∀$-intro.

Thus, from 1) and 6) we have :

$¬∃p(x) \vdash ∀x¬p(x)$;

the result follows by $\to$-intro.

0
On

And for the second one:

1. ∃x¬p(x)     premise
  2. ¬p(a)       assumption
    3. ∀xp(x)      assumption
    4. p(a)        ∀elim 3
    5. ⊥           2,4
  6. ¬∀xp(x)     ¬intro 3 5
7. ¬∀xp(x)     ∃elim 1 2-6

$\exists x \neg p(x) \vdash \neg \forall x p(x) \qquad \to\text{intro 1 7}$