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.

The final transformation must be: $∀x ∃x \ (Cx \to Bx)$ which is equivalent to: $∃x \ (Cx \to Bx)$. We need the tautological equivalence : $(\lnot p \lor q) \equiv (p \to q)$ (also called Material Implication rule. — Mauro ALLEGRANZA, Mar 27 '18 at 10:02

score 1 · Answer 1 · answered Mar 27 '18 at 03:28

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.

score 1 · Answer 2 · answered Mar 27 '18 at 03:29

1

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 :).

answered Mar 27 '18 at 03:29

Jackozee Hakkiuz

5,583
1
14
35

1

You can actually quantify over the same variable twice; it is quite legal, but not good practice because it causes confusion. It must be noted that the variable $x$ does not occur free inside the scope of the existential; it is bound by the universal quantifier. – Graham Kemp Mar 27 '18 at 03:58

score 1 · Answer 3 · answered Mar 27 '18 at 04:05

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

score 0 · Answer 4 · answered Mar 27 '18 at 04:19

$\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.

Simplifying Quantified Statement

4 Answers4