Съдържание 
 

СВЕЖДАНЕ НА ВЪПРОСА ЗА СЪЩЕСТВУВАНЕ НА МОДЕЛ ЗА МНОЖЕСТВО ОТ ДИЗЮНКТИ КЪМ СЪЩИЯ ВЪПРОС ЗА МНОЖЕСТВО ОТ ЗАТВОРЕНИ ДИЗЮНКТИ

    Ще предполагаме, че е дадена една сигнатура Σ и че всички понятия, зависещи от избора на сигнатура, се отнасят именно за сигнатурата Σ. За всяко множество от дизюнкти Δ ще означаваме с Δ° множеството на на затворените частни случаи на дизюнктите от Δ (разбира се, имаме пред вид дизюнкти при сигнатура Σ и техни частни случаи, получени с помощта на субституции при тази сигнатура).

    Твърдение 1. Нека Δ е произволно множество от дизюнкти. Тогава:
      А. Всяка структура, която е модел за Δ, е модел и за Δ°;
      Б. Всяка ербранова структура, която е модел за Δ°, е модел и за Δ.

    Доказателство. Казаното в точка А е в сила, защото ако една структура е модел за Δ, тя е модел и за всяко множество от частни случаи на дизюнкти от Δ, в частност    за множеството Δ° (това е така, защото, както знаем от текста Дизюнкти. Метод на резолюцията, всички частни случаи на дизюнкт, тъждествено верен в дадена структура, също са тъждествено верни в нея). За да се убедим в казаното в точка Б, да предположим, че дадена ербранова структура S е модел за множеството Δ°. Нека δ е произволен дизюнкт от Δ. Понеже δ има поне един затворен частен случай, а всички затворени частни случаи на δ са верни в структурата S, ясно е, че δ не е празен и значи е съответен на някоя елементарна дизюнкция φ. Всички нейни затворени частни случаи са верни в S, защото съответните им дизюнкти са затворени частни случаи на δ. Оттук се вижда, че формулата φ е тъждествено вярна в S (използваме следствие 2 от текста Ербранови структури и достатъчното условие за свеждане на тъждествена вярност и на изпълнимост на формула към вярност на нейни затворени частни случаи, разгледано във текста Основни следствия от теоремата за стойността на резултат от прилагане на субституция към формула). Следователно и съответният й дизюнкт δ е тъждествено верен в S.  

    Забележка. Ако в сигнатурата Σ няма нито една константа, точка Б от твърдение 1 става безсъдържателна, защото при такава сигнатура изобщо не съществуват ербранови структури.

    Твърдение 2. Нека в сигнатурата Σ има поне една константа и нека Δ е произволно множество от дизюнкти. Тогава следните четири условия са равносилни:
      а) съществува структура, която е модел за Δ;
      б) съществува структура, която е модел за Δ°;
      в) съществува ербранова структура, която е модел за Δ°;
      г) съществува ербранова структура, която е модел за Δ.

    Доказателство. От твърдение 1 е ясно, че от условието а) следва условието б), а от условието в) следва условието г). Тъй като от условието г) очевидно следва условието а), достатъчно е да покажем, че от условието б) следва условието в). Нека дадена структура S е модел за множеството Δ°. Понеже очевидно няма противоположни затворени литерали, едновременно верни в структурата S, твърдение 1 от текста Необходимо и достатъчно условие за съществуване на модел за множество от затворени литерали гарантира съществуването на ербранова структура S, в която са верни всички затворени литерали, верни в S. Тъй като S е модел за Δ°, сред елементите на всеки дизюнкт от Δ° има литерал, верен в S, а значи и в S. С това е показано, че ербрановата структура S също е модел за Δ°.  

    Следствие. Нека в сигнатурата Σ има поне една константа и нека Γ е произволно множество от безкванторни формули, за което съществува модел. Тогава съществува ербранова структура, която е модел за Γ.

    Доказателство. За всяка формула от Γ избираме по едно множество от дизюнкти, което я представя. Нека Δ е обединението на така избраните множества от дизюнкти. Една структура е модел за Γ точно тогава, когато е модел за Δ. Оттук е ясно, че Δ има модел, а следователно съществува и ербранова структура, която е модел за Δ. Същата е модел и за Γ.  

    Резултатите от настоящия въпрос могат да се използват, за да се изследва дали дадени множества от дизюнкти притежават модел. Ще илюстрираме това с два примера.

    Пример 1. Нека Δ е множеството от двата дизюнкта

p(a,x), ¬p(x,x)},  {p(x,x), p(a,x)}
където p е двуместен предикатен символ, а a е константа, която е единственият функционален символ на разглежданата сигнатура (за това множество стана дума в пример 1 от текста Дизюнкти. Метод на резолюцията). Тогава Δ° е множеството от двата дизюнкта
p(a,a)},  {p(a,a)},
а то очевидно не притежава модел. Оттук е ясно, че и Δ не притежава модел.

    Пример 2. Нека Δ е множеството от двата дизюнкта

{p(a,X), p(b,X), p(X,X)},  {¬p(X,Y), ¬p(Y,Z), ¬p(Z,X)}.
където p е двуместен предикатен символ, а a и b са константи, които са единствените функционални символи на разглежданата сигнатура. Тогава Δ° се състои от следните шест дизюнкта:
{p(a,a), p(b,a)},  {p(a,b), p(b,b)},  p(a,a)},  p(b,b)},  p(a,a), ¬p(a,b), ¬p(b,a)},  p(b,b), ¬p(b,a), ¬p(a,b)}.
Лесно се съобразява, че една структура е модел за Δ° точно тогава, когато измежду затворените атомарни формули верните в нея са p(b,a) и  p(a,b). Оттук и от втората основна лема за ербрановите структури следва, че Δ° притежава модел, а значи и Δ има такъв.

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