Problem 1 - Predicate Logic

1.

Transform the following logic formula to a prenex normal form with Skolem variables:

$$P(c, c) \wedge \forall x (\exists y P(x, y) \supset \exists y Q(x, y))$$

where $c$ is a constant.

2.

Find the minimal Herdrand model for the resultant logic formula. Here, consider only the symbols appearing in the formula. Also, the minimal Herbrand model is a minimal subset among subsets of Herbrand bases.

$$P(c, c) \wedge \forall x (\exists y P(x, y) \supset \exists y Q(x, y))$$

$$P(c, c) \wedge \forall x (\exists y P(x, y) \rightarrow \exists y Q(x, y))$$

$$P(c, c) \wedge \forall x (\neg (\exists y P(x, y)) \vee \exists y Q(x, y))$$

$$P(c, c) \wedge \forall x (\forall y \neg P(x, y) \vee \exists y Q(x, y))$$

$$P(c, c) \wedge \forall x (\forall y \neg P(x, y) \vee \exists z Q(x, z))$$

$$\forall x (P(c, c) \wedge (\forall y \neg P(x, y) \vee \exists z Q(x, z)))$$

$$\forall x \forall y (P(c, c) \wedge (\neg P(x, y) \vee \exists z Q(x, z)))$$

$$\forall x \forall y (P(c, c) \wedge (\neg P(x, y) \vee Q(x, f(x, y))))$$

Herbrand universe: $H = \{ c, f(c,c), f(c, f(c,c)), f(f(c,c),f(c,c)), \dots \}$

Ground terms: $c, f(c,c), f(c, f(c,c)), f(f(c,c),f(c,c)), \dots$

Ground atoms: $P(c,c), Q(c,c), P(c, f(c,c)), Q(c,f(c,c)), P(f(c,c),c), \\ Q(f(c,c),c), P(f(c,c),f(c,c))), Q(f(c,c),f(c,c))), \dots$

Herbrand base: $B = \{ P(c,c), Q(c,c), P(c, f(c,c)), Q(c,f(c,c)), P(f(c,c),c), \\ Q(f(c,c),c), P(f(c,c),f(c,c))), Q(f(c,c),f(c,c))), \dots \}$

Herbrand interpretation: $D = H$, $\bar{a}_1 = c$, $\bar{f}_1^2 = f$, there are no restrictions on the assignments of relations over the Herbrand universe to predicates.

Herbrand model: Just choose a subset of the Herbrand base and assign to its elements the $T$ value.

Then, the minimal Herbrand model here is: $\{ P(c,c), Q(c,f(c,c))\}$.