# How to negate the following proposition

If I have the the proposition: $\forall y, \exists x, \exists z [(Bx,y \wedge Rz,y) \vee (Bx,y \wedge Gz,y) \vee (Rx,y \wedge Gz,y)]$.

(B,R and G are some other propositions but that doesn't matter now)

Now I want to negate that but I'm not sure if I did it right:

$\exists y \forall x \forall z [\neg Bx,y \vee \neg Rz,y \vee \neg Bx,y \vee \neg Gz,y \vee \neg Rx,y \vee \neg Gz,y]$

$=\exists y \forall x \forall z [\neg Bx,y \vee \neg Rz,y \vee \neg Gz,y \vee \neg Rx,y]$

I'm not sure but I think I did something wrong.. Hope you can help.

• $\exists$ becomes $\forall$ and vice-versa, as you did. Also $\lnot (a\vee b)=(\lnot a)\wedge (\lnot b)$ and $\lnot (a\wedge b)=(\lnot a)\vee (\lnot b)$. You forgot to reverse the $\vee$s, it seems. Nov 12, 2015 at 15:11

Let's walk through this, making each step more explicit:

$\neg\forall y\exists x\exists z[(Bxy\wedge Rzy)\vee(Bxy\wedge Gzy)\vee(Rxy\wedge Gzy)]$

When you have a negated quantifier, you may remove the negation, change the quantifier to the other type of quantifier, and negate the formula quantified over:

$=\exists y\neg\exists x\exists z[(Bxy\wedge Rzy)\vee(Bxy\wedge Gzy)\vee(Rxy\wedge Gzy)]$ $=\exists y\forall x\neg\exists z[(Bxy\wedge Rzy)\vee(Bxy\wedge Gzy)\vee(Rxy\wedge Gzy)]$ $=\exists y\forall x\forall z\neg[(Bxy\wedge Rzy)\vee(Bxy\wedge Gzy)\vee(Rxy\wedge Gzy)]$

Now, when you have a negated disjunction, you may apply DeMorgan's rule. This amounts to switching every disjunction to a conjunction, and negating each new conjunct:

$=\exists y\forall x\forall z[\neg(Bxy\wedge Rzy)\wedge\neg(Bxy\wedge Gzy)\wedge\neg(Rxy\wedge Gzy)]$

Now, apply DeMorgan's again (three times). This time, we switch the conjunctions to disjunctions and negate each new disjunct:

$=\exists y\forall x\forall z[(\neg Bxy\vee\neg Rzy)\wedge(\neg Bxy\vee\neg Gzy)\wedge(\neg Rxy\vee\neg Gzy)]$

Now that negations are only applied to predicates, we can't simplify any more. We are done. I don't think the formula you got at the end is equivalent to the one I got. This is because:

$A\vee B\vee C\vee D\neq(A\vee B)\wedge(A\vee C)\wedge(D\vee C)$

To show why this inequality holds, consider the truth assignment: $A\mapsto\top$, $B\mapsto\top$, $C\mapsto\bot$, $D\mapsto\bot$. It is easy to see that this assignment satisfies the formula on the left, but not the one on the right. I think that

$=\exists y\forall x\forall z[(\neg Bxy\vee\neg Rzy)\wedge(\neg Bxy\vee\neg Gzy)\wedge(\neg Rxy\vee\neg Gzy)]$

is as far as you can simplify this formula. You can see that the conjunction inside the square brackets is the same form as the conjunction $(A\vee B)\wedge(A\vee C)\wedge(D\vee C)$.

Hope this helps!