Когато една затворена формула е вярна в дадена структура, тя е вярна в нея при всяка оценка на променливите. Може обаче една формула да има последното свойство и без да е затворена. Например ако p е едноместен предикатен символ, а X е променлива, то формулата p(X) Ъ Ш p(X) е вярна във всяка структура при всяка оценка на променливите. За една формула казваме, че е тъждествено вярна в дадена структура, ако е вярна в нея при всяка оценка на променливите. Тази дефиниция позволява да твърдим в частност, че една затворена формула е тъждествено вярна в дадена структура точно тогава, когато е вярна в нея. Имайки това пред вид, разширяваме употребата на означенията S F и S F за случая на произволна формула F, като се уславяме те да изразяват съответно, че F е тъждествено вярна в структурата S и че F не е тъждествено вярна в S.

    Може една формула да е тъждествено вярна в една структура и да не е тъждествено вярна в друга. Например ако p е едноместен предикатен символ, а X и Y са две различни помежду си променливи, то формулата p(X) Ъ Ш p(Y) е тъждествено вярна в структурите, в които предикатът, интерпретиращ p, има една и съща стойност навсякъде в дефиниционната си област, но не е тъждествено вярна в никоя друга структура. Формулите, които са тъждествено верни във всяка структура, се наричат тъждествено верни. Такава е например формулата p(X) Ъ Ш p(X), за която стана дума по-горе (разбира се тъждествено верни са и онези затворени формули, които са верни във всяка структура - най-прост пример за такава формула е празната конюнкция). За да изразим, че една формула F е тъждествено вярна, ще пишем F, а за да изразим, че F не е тъждествено вярна - F.

    Очевидно една конюнкция е тъждествено вярна в дадена структура точно тогава, когато всички членове на конюнкцията са тъждествено верни в същата структура. Следователно една конюнкция е тъждествено вярна точно тогава, когато всичките й членове са тъждествено верни. Сега ще формулираме и докажем едно друго полезно твърдение, отнасящо се до тъждествена вярност на формули.

    Запазване на тъждествената вярност при поставяне и при премахване на квантор за общност. За произволна структура S, произволна формула F и произволна променлива X условията  S F  и  S "X F  са равносилни. Следователно за произволна формула F и произволна променлива X условията  F  и  "X F  са равносилни.

    Доказателство. Ако S F и v е произволна оценка в S на променливите, то при всеки избор на елемент d на носителя на S формулата F е вярна в S при оценката [X:d]v, следователно формулата "X F е вярна в S при оценката v. Обратно, ако S "X F и v е произволна оценка в S на променливите, то формулата F е вярна в S при оценката [X:v(X)]v, която обаче очевидно съвпада с v. _ї

    Ако една формула F има точно m свободни променливи и те са X₁, X₂, ..., X_m, то формулата "X₁"X₂..."X_mF се нарича универсално затваряне на F и очевидно е една затворена формула (при m>1 универсалното затваряне на F не е еднозначно определено, защото са възможни различни подреждания на свободните променливи на F). Чрез m-кратно прилагане на доказаното по-горе твърдение получаваме следния резултат.

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

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

    Една формула се нарича изпълнима, ако е изпълнима в поне една структура. Очевидно всички тъждествено верни формули са изпълними, но обратното не е в сила дори за затворени формули (например всяка атомарна формула е изпълнима, но никоя атомарна формула не е тъждествено вярна).

    Като се използват дефинициите за тъждествена вярност и изпълнимост, а също и семантиката на отрицанието, веднага се вижда, че понятията тъждествена вярност и изпълнимост са свързани по следния начин:
    1. Нека S е дадена структура, а F е дадена формула. За да бъде формулата F тъждествено вярна в S, необходимо и достатъчно е формулата Ш F да не е изпълнима в S, а за да бъде формулата F изпълнима в S, необходимо и достатъчно е формулата Ш F да не е тъждествено вярна в S.
    2. Нека F е дадена формула. За да бъде формулата F тъждествено вярна, необходимо и достатъчно е формулата Ш F да не е изпълнима, а за да бъде формулата F изпълнима, необходимо и достатъчно е формулата Ш F да не е тъждествено вярна.

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

    Първо отбелязваме, че една дизюнкция е изпълнима в дадена структура точно тогава, когато някой член на дизюнкцията е изпълним в същата структура. Следователно една дизюнкция е изпълнима точно тогава, когато някой неин член е изпълним. Друго полезно твърдение, отнасящо се до изпълнимост на формули, е следното:

    Запазване на изпълнимостта при поставяне и при премахване на квантор за съществуване. За произволна структура S, произволна формула F и произволна променлива X условието формулата F да е изпълнима в S е равносилно с условието формулата $X F да е изпълнима в S. Следователно за произволна формула F и произволна променлива X изпълнимостта на формулата F е равносилна с изпълнимостта на формулата $X F.

    Доказателство. Ако формулата $X F е изпълнима в дадена структура S, то тази формула е вярна в S при някоя оценка v на променливите и тогава формулата F ще е вярна в S при оценката [X:d]v за някой елемент d на носителя на S. Обратно, ако формулата F е изпълнима в S, то F е вярна в S при някоя оценка v в S на променливите и е достатъчно да използваме, че тази оценка съвпада с оценката [X:v(X)]v. _ї

    Ако една формула F има точно m свободни променливи и те са X₁, X₂, ..., X_m, то формулата $X₁$X₂...$X_mF се нарича екзистенциално затваряне на F и очевидно е една затворена формула (при m>1 екзистенциалното затваряне на F не е еднозначно определено, защото са възможни различни подреждания на свободните променливи на F). Чрез m-кратно прилагане на доказаното по-горе твърдение получаваме следния резултат.

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

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

Previous  Next  Contents