Multiple choice

Consider the following logic program P

$\begin{align*} A(x) &\gets B(x,y), C(y) \ &\gets B(x,x) \end{align*}$

Which of the following first order sentences is equivalent to P?

  1. $(\forall x) [(\exists y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land \neg (\exists x)[B(x,x)]$
  2. $(\forall x) [(\forall y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land \neg (\exists x)[B(x,x)]$
  3. $(\forall x) [(\exists y) [B(x,y) \land C(y)] \Rightarrow A(x)] \vee \neg (\exists x)[B(x,x)]$
  4. $(\forall x) [(\forall y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land (\exists x)[B(x,x)]$
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

The logic program has two rules: A(x) if B(x,y) and C(y) (with existential quantification on y), and a constraint that ¬B(x,x) for all x. In first-order logic: (∀x)[(∃y)(B(x,y) ∧ C(y)) ⇒ A(x)] represents the first rule (existential y in body becomes existential in antecedent of implication). The constraint ¬(∃x)B(x,x) represents the second rule. These are connected by ∨ (disjunction) because in logic programs, rules are implicitly disjunctive.

Keep practicing — related questions