Изпълнимост и модели на множество от формули

ИЗПЪЛНИМОСТ И МОДЕЛИ НА МНОЖЕСТВО ОТ ФОРМУЛИ

И тук формулите и структурите, за които ще става дума, ще бъдат формули в дадена сигнатура Σ и структури със сигнатура Σ. Нека Γ е едно множество от формули. Ще казваме, че Γ е изпълнимо в дадена структура S, ако съществува такава оценка v в S на променливите, че всяка формула от Γ да е вярна в S при оценката v. Под модел за Γ ще разбираме такава структура S, че всяка формула от Γ да е тъждествено вярна в S.

Разбира се, ако множеството Γ се състои от една единствена формула, то изпълнимостта на Γ в дадена структура S е равносилна с изпълнимостта на въпросната формула в S. И в общия случай от изпълнимостта на Γ в такава структура следва изпълнимостта на всяка формула от Γ във въпросната структура, но обратното не винаги е в сила.

Пример 1. Нека S е структурата от примера в текста "Сигнатури и структури", а множеството Γ се състои от формулите (1) и (2) от примера в текста "Формули на предикатното смятане". Тогава всяка формула от Γ е изпълнима в S, но множеството Γ не е изпълнимо в S.

Забележка 1. Очевидно е, че ако една структура S е модел за дадено множество от формули Γ, то Γ е изпълнимо в S. Ако елементите на Γ са затворени формули, то за произволна структура S условието S да е модел за Γ и условието Γ да е изпълнимо в S са равносилни помежду си, защото и двете са равносилни с изискването всяка формула от Γ да е вярна в S.

Забележка 2. Нека Δ е множество, получено от множеството Γ чрез замяна на всяка негова формула с нейно универсално затваряне. Тогава Δ е множество от затворени формули, което има същите модели както Γ (поради това обстоятелство понятието модел понякога се въвежда и изучава само за множества от затворени формули).

Ще казваме, че множеството Γ е изпълнимо, ако Γ е изпълнимо в някоя структура. От казаното в забележка 1 е ясно, че ако елементите на Γ са затворени формули, то изпълнимостта на Γ е равносилна със съществуването на модел за Γ. Разбира се и без споменатото ограничение за множеството Γ съществуването на модел за това множество влече изпълнимостта му, но обратното в общия случай не е в сила.

Пример 2. При същата сигнатура както в примера в текста "Сигнатури и структури" нека

Γ = {positive(x),¬positive(y)}. Очевидно множеството Γ е изпълнимо в структурата S от същия пример и значи Γ е изпълнимо. Ако обаче допуснем, че някоя структура е модел за Γ, ще стигнем до заключение, че в нея са едновременно верни и универсалните затваряния ∀x positive(x) и ∀y¬positive(y) на формулите от Γ, а това е невъзможно (всъщност наличието на функционалния символ difference в сигнатурата не се използва в този пример).

Ако множеството Γ е изпълнимо, то разбира се и всяка формула от Γ е изпълнима. Обратното не винаги е в сила, дори и да поискаме формулите от Γ да са затворени.

Пример 3. Нека сигнатурата Σ е получена от онази в предидущия пример чрез замяна на функционалния символ difference с една константа a, т.е. Σ = ({a},{positive},ρ), където ρ(a)=0, ρ(positive)=1. Ако

Γ = {positive(а),¬positive(а)}, то всяка от двете формули, принадлежащи на така определеното множество Γ, е изпълнима, но самото Γ очевидно не е изпълнимо.

Последно изменение: 21.11.2008 г.