0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The first is wrong: too many $\lnot$ and you have forgotten De Morgan... $\endgroup$
    – Mauro ALLEGRANZA
    Apr 16, 2016 at 20:14
  • $\begingroup$ @MauroALLEGRANZA Fixed De Morgan's but too many $\neg$? $\endgroup$
    – user332043
    Apr 16, 2016 at 20:16
  • $\begingroup$ ¬[∀xA(x)∨B(y)] by De Morgan is equivalent to ¬∀xA(x)∧¬B(y). $\endgroup$
    – Mauro ALLEGRANZA
    Apr 16, 2016 at 20:18
  • $\begingroup$ 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. $\endgroup$
    – Mauro ALLEGRANZA
    Apr 16, 2016 at 20:22

2 Answers 2

Reset to default
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is $P(x)=A(x)\lor B(x)$? $\endgroup$
    – user332043
    Apr 16, 2016 at 20:16
  • $\begingroup$ @user332043Z: In this case yes, the point is to do one step at a time. $\endgroup$
    – copper.hat
    Apr 16, 2016 at 20:18

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.