2
$\begingroup$

I have a first order logic clause and I have to transform it to its normal clausular form. $$\forall x \exists y \left[A(x) \land \lnot B(x) \implies C(x,y) \land\exists zD(z)\right]$$

But I have several problems with the hierarchy when I have an implication in the middle of the formula.

So, I imagine these relationships as if they were of propositional logic: $a\lor b \implies c \lor d$, but now my question is:

$a\lor v \implies c \lor d$ is equal to $(a \lor b) \implies (c \lor d)$? or is equal to $a \lor (b \implies c) \lor d$?

Thanks.

$\endgroup$
  • $\begingroup$ The first option is correct. The scope of $\to$ is larger which is to say both $\lor$ and $\land$ take precedence over $\to$. This is just a convention. $\endgroup$ – Git Gud Jun 22 '14 at 20:59
  • $\begingroup$ But, if I have $a \lor b \implies c$ it isn't equal to $(a \lor b ) \implies c$? $\endgroup$ – Tomi Jun 22 '14 at 21:03
  • $\begingroup$ Yes, that's what I'm saying. $\endgroup$ – Git Gud Jun 22 '14 at 21:04
  • $\begingroup$ So, finally, mi Normal Clausular Form is $\forall x[(\lnot A(x) \lor B(x)) \lor (C(x,f(x)) \land D(c))]$? Thanks! $\endgroup$ – Tomi Jun 22 '14 at 21:07
  • $\begingroup$ I don't know what Normal Clausular Form is, sorry. $\endgroup$ – Git Gud Jun 22 '14 at 21:10
2
$\begingroup$

Yes, it is right.

The formula, written with parentheses :

$∀x∃y[(A(x)∧¬B(x)) \rightarrow (C(x,y)∧∃zD(z))]$

is equivalent to :

$∀x∃y[\lnot (A(x) \land \lnot B(x)) \lor (C(x,y) \land ∃zD(z))]$

[by equivalence between $p \rightarrow q$ and $\lnot p \lor q$] which in turn is equivalent to :

$∀x∃y[(\lnot A(x) \lor B(x)) \lor (C(x,y) \land ∃zD(z))]$

[by De Morgan and double negation].

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