Логическо програмиране 2004/05 - упражнения

Определимост

Нека е дадена структура S = ($$\Sigma$$,D,I). Нека B$$\subseteq$$Aⁿ. Казваме, че множеството B е определимо в структурата S, ако може да се намери формула F със свободни променливи x₁,x₂,...,x_n (толкова на брой, колкото мерно е множеството B), такава че за всеки n елемента d₁,...,d_n$$\in$$ D е изпълнено:

(d₁,...,d_n)$$\in$$ B <=> F^{S,v[x₁->d₁,...x_n->d_n]} = 1.

Казано с други думи: за да покажем, че едно множество е определимо, трябва да намерим формула, която описва точно неговите елементи. Забележете, че едно множество може да е определимо в една структура, а да не е определимо в друга, дори и те да имат един и същ носител D!