2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ $\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. $\endgroup$
    – Jean-Claude Arbaut
    Nov 12, 2015 at 15:11

1 Answer 1

Reset to default
0
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.