Модели на множества от безкванторни формули и на множества от универсални затворени формули

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

Ще предполагаме, че разглежданите термове и формули са в сигнатура с поне една константа.

Необходимо и достатъчно условие за съществуване на модел на множество от безкванторни формули. Нека Γ е множество от безкванторни формули и нека Γ° е множеството на всички затворени частни случаи на формули от Γ. За да притежава множеството Γ модел, необходимо и достатъчно е да е изпълнимо множеството Γ°, при това в този случай съществува и ербранова структура, която е модел за Γ.

Доказателство.Ако множеството Γ има модел, то множеството Γ° е изпълнимо, защото формулите от него са верни във всяка структура, която е модел за Γ. Да предположим сега, че множеството Γ° е изпълнимо, и да означим с S₀ някоя структура, в която са верни всички формули от Γ°. Благодарение на твърдението за съществуване на ербранова структура с отнапред дадено множество на верните затворени атомарни формули съществува такава ербранова структура S, че измежду всички затворени атомарни формули да бъдат верни в S точно онези, които са верни в S₀. Чрез индукция, съобразена с дефиницията за безкванторна формула, се проверява, че за всяка безкванторна формула F е в сила равенството

F^S = F^S₀. Оттук става ясно, че всички формули от множеството Γ° са верни в S. Знаем обаче, че когато в една ербранова структура са верни всички затворени частни случаи на една безкванторна формула, тази формула е тъждествено вярна във въпросната структура. Поради това всички формули от множеството Γ са тъждествено верни в S, т.е. ербрановата структура S е модел за Γ. _□

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

Доказателство. Нека е дадено едно изпълнимо множество от универсални затворени формули. Да означим с Γ множеството на безкванторните части на тези формули. Моделите за даденото множество от формули и моделите за множеството Γ са едни и същи. Оттук получаваме, че Γ притежава модел, а следователно съществува ербранова структура, която е модел за Γ. Тя ще бъде модел и за даденото множество. _□

Забележка. Ако Γ е множество от положителни хорнови клаузи, то измежду ербрановите структури, които са модели за Γ, има, както знаем, една с най-малко множество на верните затворени атомарни формули. За произволно изпълнимо множество Γ от безкванторни формули това свойство не винаги е налице. Нека например множеството Γ има като свой единствен елемент дизюнкцията на две различни затворени атомарни формули. Една структура е модел за Γ точно тогава, когато в нея е вярна някоя от тези две формули. Като разгледаме ербранова структура, в която от двете формули е вярна само първата, и ербранова структура, в която от тях е вярна само втората, виждаме, че измежду ербрановите струиктури, които са модели за Γ, няма такава, която да е с най-малко множество на верните затворени атомарни формули.

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

Previous Next Contents