First Order Logic and equivalence rules

Question

I have a couple of questions about first order logic equivalence rules.

• How do you distribute the $\neg$ correctly with the $\exists$ and $\forall$ quantifiers? If let's say I have $$\neg[\forall x\;A(x)\;\lor B(y)]$$ Does it become:$$\neg\forall x\;\neg A(x)\land\neg B(y)$$?

• In something like this: $$\forall c\; A(c)\Rightarrow B(c)$$ Is this equivalent to: $$\neg [\forall c\;A(c)]\lor B(c)$$ Or: $$\forall c\; \neg A(c)\lor B(c)$$?

• For the rule $\neg\forall x\;p\equiv \exists x\;\neg p$, is $p$ all the predicates that contain $x$? Let's say I have: $$\neg[\neg\forall\,c\; A(c, Something)]\lor [\exists\,d\; B(d, SomethingElse)\land \neg C(c, d)]$$Will this yield:$$\neg[\exists\,c\; \neg A(c, Something)]\lor [\exists\,d\; B(d, SomethingElse)\land \neg C(c, d)]$$ Or will I have to move the $\neg$ on the entire statement since $C(c,d)$ is dependent on $c$?

The professor I have didn't explain this very well. I appreciate any help.

Answer 1

$\lnot[\forall x\;P(x)] $ is equivalent to $\exists x \; \lnot P(x)$. Now use De Morgan on $A(x) \lor B(x)$.

$\lnot [ A(x) \lor B(x) ] $ is equivalent to $ ((\lnot A(x)) \land (\lnot B(x))$.

Answer 2

$$\neg\Bigl[\bigl(\forall x\;A(x)\bigr)\lor B(y)\Bigr] \\ \bigl(\neg\forall x\;A(x)\bigr)\land \neg B(y)\\ \bigl(\exists x\;\neg A(x)\bigr)\land \neg B(y)$$ or perhaps you mean $$\neg\Bigl[\forall x\;\bigl(A(x)\lor B(y)\bigr)\Bigr] \\ \exists x\;\neg\bigl(A(x)\lor B(y)\bigr)\\ \exists x\;\bigl(\neg A(x)\land\neg B(y)\bigr)$$

And $$\forall c\;\bigl(A(c)\to B(c)\bigr) $$ is equivalent to $$\forall c\;\bigl(\neg A(c)\lor B(c)\bigr) $$ whereas $$\bigl(\forall c\;A(c)\bigr)\to B(c) $$ (which has some weird concept of free and bound variable use) would be equivalent to $$\neg\bigl(\forall c\;A(c)\bigr)\lor B(c) $$ or $$\bigl(\exists c\;\neg A(c)\bigr)\lor B(c) $$