I am trying to prove the following predicate by using natural deduction rules but I do not see the way to do it:
∀ x(P(x) ∨ Q(x)) ⊢ ~∀x(~P(x) ∧ ~Q(x))
Is this predicate derivable? if yes please provide the natural deduction steps or a hint to solve it.
Solution using @Mauro ALLEGRANZA's hint:
Hint
The conclusion is negated; thus, the first idea is to assume : $∀x(\lnot P(x) ∧ \lnot Q(x))$ and derive a contradicition, concluding with $\lnot$-intro.
Thus, the first steps must be :
1) $∀x(P(x) ∨ Q(x))$ --- premise
2) $∀x(\lnot P(x) ∧ \lnot Q(x))$ --- assumed [a]
3) $\lnot P(x) ∧ \lnot Q(x)$ --- from 2) by $∀$-elim
4) $\lnot P(x)$ --- from 3) by $∧$-elim
5) $\lnot Q(x)$ --- from 3) by $∧$-elim
6) $P(x) ∨ Q(x)$ --- from 1) by $∀$-elim.
Now the derivation is straightforward, using $∨$-elim.