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

    Очевидно е, че множество, състоящо се само от една формула, е изпълнимо точно тогава, когато е изпълнима тази формула. Ако M е крайно множество, състоящо се от дадени формули j₁, j₂, ..., j_n, където n>1, то M се удовлетворява от същите конфигурации както конюнкцията j₁&j₂&...&j_n и следователно M е изпълнимо точно тогава, когато е изпълнима споменатата конюнкция. Ако M е празното множество, то по тривиални причини всяка конфигурация удовлетворява M и следователно M е изпълнимо.

    Лесно се съобразява, че тъждествената вярност на формулите и следването на една формула от друга се свеждат до неизпълнимост по следния начин: а) една формула j е тъждествено вярна точно тогава, когато е неизпълнима формулата Шj; б) съотношението jy е налице точно тогава, когато е неизпълнимо множеството {j,Шy}.

    Понятието изпълнимост е важно както само по себе си, така и поради посоченото свеждане към него на понятията тъждествена вярност и следване. Затова наша съществена задача по-нататък ще бъде да разработим удобни методи за изследване на изпълнимостта. Засега ще дефинираме още някои понятия, имащи връзка с изпълнимостта.

    Нека M е множество от формули, а y е формула. Ще казваме, че от M следва y, и ще пишем My, ако всяка конфигурация, която удовлетворява M, удовлетворява и y.

    Ясно е, че при M={j} условието My е равносилно с условието jy, а при M={j₁,j₂,...,j_n}, където n>1, имаме My точно тогава, когато j₁&j₂&...&j_ny. По тривиални съображения може да се твърди, че условието Жy е изпълнено точно тогава, когато формулата y е тъждествено вярна. Очевидно за произволно M имаме My точно тогава, когато множеството MИ{Шy} е неизпълнимо.

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

    За едно множество от формули ще казваме, че е силно изпълнимо, ако то притежава модел; аналогично за една формула ще казваме, че е силно изпълнима, ако тя притежава модел. Веднага се вижда, че всяко силно изпълнимо множество от формули е изпълнимо. За множества от затворени формули е вярно и обратното - всяко изпълнимо множество от затворени формули е силно изпълнимо (следователно едно множество от затворени формули е изпълнимо точно тогава, когато то притежава модел). В общия случай едно множество от формули може да бъде изпълнимо без да е силно изпълнимо.

    Пример. Нека M е множеството {p(x),Шp(y)}, където p е едноместен предикатен символ, а x и y са различни променливи. Тогава лесно се забелязва, че M е изпълнимо, но не е силно изпълнимо (изискването x и y да са различни променливи е съществено за този пример, тъй като множеството {p(x),Шp(x)} е очевидно неизпълнимо).

    Когато едно множество се състои от ненулев краен брой формули, неговата силна изпълнимост може да бъде сведена до силна изпълнимост на една формула аналогично на това как изпълнимостта на такова множество се свежда до изпълнимост на една формула (използва се, че една структура е модел на дадена конюнкция точно тогава, когато е модел на всеки от нейните членове). Разбира се празното множество е силно изпълнимо по тривиални причини.

    Знаем, че за всяка формула j може да се намери затворена формула, вярна точно в онези структури, в които j е тъждествено вярна (въпросната затворена формула може да се получи, като пред j се поставят квантори за общност относно всички нейни свободни променливи). По тази причина силната изпълнимост на произволно множество от формули е равносилна с изпълнимостта на подходящо множество от затворени формули (получени по споменатия начин от формулите, принадлежащи на даденото множество), като при това двете множества имат едни и същи модели. Например, ако M е множеството {p(x),Шp(y)} от разгледания по-горе пример, току-що казаното дава, че за да бъде M силно изпълнимо, необходимо и достатъчно е да е изпълнимо множеството {"xp(x),"yШp(y)} (то обаче не е изпълнимо).

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