# First Order Logic and equivalence rules

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.

• The first is wrong: too many $\lnot$ and you have forgotten De Morgan... Apr 16, 2016 at 20:14
• @MauroALLEGRANZA Fixed De Morgan's but too many $\neg$? Apr 16, 2016 at 20:16
• ¬[∀xA(x)∨B(y)] by De Morgan is equivalent to ¬∀xA(x)∧¬B(y). Apr 16, 2016 at 20:18
• For the rule ¬∀xp≡∃x¬p, it is not a predicate but the sub-formula being the scope of the quantifier. The correct writing is ¬∀x(...) where in place of the dots you may have a "complex" formula. Thus, you have to proceed step-by-step; first ∃x¬(...) and then consider the part ¬(...). If there is a new quantifier, apply again the quantifier rules; if not, go on (if needed) with propositional equivalences, like De Morgan. Apr 16, 2016 at 20:22

$$\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)$$
$\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))$.
• Is $P(x)=A(x)\lor B(x)$? Apr 16, 2016 at 20:16