Simplifying Quantified Statement

Question

For my assignment, I have to simplify this statement leaving no negations in the end.

$$\neg\exists x\ \forall x(\neg B(x) \wedge C(x))$$

Everything I've tried so far leaves me with a single negation sign on $B(x)$ or $C(x)$ and I just cannot figure this out.

Answer 1

I assume that the negation on the very outside applies to the entire block.

What is the negation of a statement of the form $\exists x P(X)$? We should have $\forall x \neg P(x)$.

What is the negation of a statement of the form $\forall x Q(x)$? We should have $\exists x\neg Q(x)$.

Using these two rules, you can pass the negation all the way in towards the actual formula, and then use DeMorgan to finish the job. When you are left with a disjunction of two terms, you can combine them into an implication instead.

Answer 2

Are you sure that expression is correct? You cannot quantify over the same variable twice.

Also, if that is a typo, please post the correct expression together with some of your work so we can help :).

Answer 3

Everything I've tried so far leaves me with a single negation sign on B(x) or C(x) and I just cannot figure this out.

Indeed, and to be exact, the negation should be on $C(x)$.   Quantifier Duality, de Morgan's, and Double Negation Equivalences will get you only so far.

$$\neg \exists x~\forall x~(\neg B(x)\wedge C(x)) \iff \forall x~\exists x~(B(x)\vee\neg C(x))$$

Now if only we knew some other equivalence for $\neg C(x)\vee B(x)$ ...

Answer 4

$\forall$x quantifies the x so $\exists$x can be removed giving an equivalent statement .The statement in parenthesis is equivalent to $\neg$(C(x)$\Rightarrow$B(x)). Now using the equivalence of "not for every not" and there is gives $\exists$x(C(x)$\Rightarrow$B(x)) . This has no negation sign. If they didn't tell you that implication was in the game then the problem is unfair .How ever this is the way to get rid of the negative sign.