1

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) $$

Jojojustin
  • 51
  • What exactly are the formal rules that you are allowed to use? There are many different proof systems with different sets of rules each, so a proof in one system may not be a proof in another. So, we need to know what rules of the system you have to work with before we can help anser your question. – Bram28 Oct 27 '16 at 12:25

2 Answers2

2

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.

Mauro ALLEGRANZA
  • 94,169
1

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}$

Kenny Lau
  • 25,049