How to prove this is a tautology

Question

$\forall x : (p(x) \wedge \neg q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)$

The problem is I know that this is a tautology, but I don't know how to prove it. Can anyone can help me?

Answer 1

Edit

Here is a way without EI (a lot quicker,too):

$\forall x : (p(x) \wedge \neg q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x) \Rightarrow$

$\forall x : \neg(\neg p(x) \vee q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)\Rightarrow$

$\exists x : (\neg p(x) \vee q(x)) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)\Rightarrow$

$\exists x : \neg p(x) \vee \exists x: q(x) \vee \exists x: \neg p(x) \vee \neg \exists x: q(x)\Rightarrow$

$\exists x : \neg p(x) \vee (\exists x: q(x) \vee \neg \exists x: q(x))\vee \exists x: \neg p(x)\Rightarrow$

$\exists x : \neg p(x) \vee T \vee \exists x: \neg p(x)\Rightarrow $

$\exists x : \neg p(x) \vee T \Rightarrow T$

Answer 2

Try breaking it up in words. The second two conditions are:

"there is an $x$ such that $p(x)$ is false"

"there is no $x$ such that $q(x)$ is true"

You need to show that if neither of these conditions holds (that is, both of these statements are false), then necessarily the first one ("for every $x$, $p(x)$ is true and $q(x)$ is false") must be true.

Can you see how to prove that?