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

      Може една формула да е тъждествено вярна в една структура и да не е тъждествено вярна в друга. Например ако p е едноместен предикатен символ, то формулата  p(X)∨ ¬ p(Y) е тъждествено вярна във всяка структура S, в която предикатът p^S има една и съща стойност навсякъде в дефиниционната си област, но тази формула не е тъждествено вярна в никоя друга структура. Формулите, които са тъждествено верни във всяка структура, се наричат тъждествено верни. Такава е например формулата  p(X)∨ ¬ p(X), за която стана дума по-горе.

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

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

      Доказателство. Нека S е една структура. Ако формулата φ е тъждествено вярна в S, то, каквато и да бъде оценката v в S на променливите, при всеки избор на елемент d на носителя на S формулата φ е вярна в S при оценката v[ξ→d], следователно формулата  ∀ξ φ  е вярна в S при оценката v. Обратно, ако формулата  ∀ξ φ  е тъждествено вярна в S, то, каквато и да бъде оценката v в S на променливите, формулата φ е вярна в S при оценката v[ξ→v(ξ)], която обаче очевидно съвпада с v. _□

      Ако една формула φ има точно m свободни променливи и те са ξ₁, ξ₂, …, ξ_m, то формулата  ∀ξ₁ ∀ξ₂ … ∀ξ_m φ  се нарича универсално затваряне на φ и очевидно е една затворена формула (при m>1 универсалното затваряне на φ не е еднозначно определено, защото са възможни различни подреждания на свободните променливи на φ). Чрез m-кратно прилагане на доказаното по-горе твърдение получаваме следния резултат.

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

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

      Като се използват дефинициите за тъждествена вярност и изпълнимост, а също и семантиката на отрицанието, веднага се вижда, че е в сила следното твърдение:

      Взаимна изразимост на тъждествената вярност и изпълнимостта Нека φ е дадена формула. За да бъде формулата φ тъждествено вярна в дадена структура, необходимо и достатъчно е формулата  ¬ φ  да не е изпълнима в тази структура, а за да бъде формулата φ изпълнима в дадена структура, необходимо и достатъчно е формулата  ¬ φ  да не е тъждествено вярна в тази структура. Следователно за да бъде формулата φ тъждествено вярна, необходимо и достатъчно е формулата  ¬ φ  да не е изпълнима, а за да бъде формулата φ изпълнима, необходимо и достатъчно е формулата  ¬ φ  да не е тъждествено вярна.

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

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

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

      Доказателство. Ако формулата   ∃ξ φ  е изпълнима в дадена структура S, то тази формула е вярна в S при някоя оценка v на променливите и тогава формулата φ ще е вярна в S при оценката v[ξ→d] за някой елемент d на носителя на S. Обратно, ако формулата φ е изпълнима в S, то φ е вярна в S при някоя оценка v в S на променливите и е достатъчно да използваме, че тази оценка съвпада с оценката v[ξ→v(ξ)]. _□

      Ако една формула φ има точно m свободни променливи и те са ξ₁, ξ₂, …, ξ_m, то формулата  ∃ξ₁ ∃ξ₂ … ∃ξ_m φ  се нарича екзистенциално затваряне на φ и очевидно е една затворена формула (при m>1 екзистенциалното затваряне на φ не е еднозначно определено, защото са възможни различни подреждания на свободните променливи на φ). Чрез m-кратно прилагане на доказаното по-горе твърдение получаваме следния резултат.

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

      Тъй като формулите при дадената сигнатура са формули и при всяка друга, която я съдържа, уместно в да се запитаме дали тъждествената вярност и изпълнимостта на една формула могат да се повлияят от замяната на дадената сигнатура с някоя друга, която я съдържа. Отговорът е отрицателен: ако φ е формула при дадена сигнатура Σ, а Σ′ е сигнатура, съдържаща Σ, то φ е тъждествено вярна като формула при сигнатура Σ′ точно тогава, когато φ е тъждествено вярна като формула при сигнатура Σ, и аналогично за изпълнимостта (т.е. φ е тъждествено вярна във всяка структура със сигнатура Σ′ точно тогава, когато φ е тъждествено вярна във всяка структура със сигнатура Σ, и аналогично за изпълнимостта). В това можем да се убедим, като използваме, че всяка структура със сигнатура Σ притежава обогатяване, което е със сигнатура Σ′, и всяка структура със сигнатура Σ′ е обогатяване на някоя структура със сигнатура Σ.

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