Multiple choice

Consider the following logic program P A(x) <- B(x, y), C(y) <- B(x,x) Which of the following first order sentences is equivalent to P?

  1. (∀x)[(∃y)[B(x,y)∧C(y)]⇒A(x)]∧¬(∃X)[B(x,x)]

  2. (∀x)[(∀y)[B(x,y)∧C(y)]⇒A(x)]∧¬(∃X)[B(x,x)]

  3. (∀x)[(∃y)[B(x,y)∧C(y)]⇒A(x)]∨¬(∃X)[B(x,x)]

  4. (∀x)[(∀y)[B(x,y)∧C(y)]⇒A(x)]∧(∃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); and C(y) if B(x,x) with negation. The first rule translates to: for all x, if there exists y such that B(x,y) and C(y), then A(x). The second rule C(y) means y is such that NOT exists x with B(x,x). These must be combined with OR because the second rule has no body - it's a fact. Option C correctly uses OR to combine the universal quantification with the negation.