Както обикновено, ще предполагаме, че е дадена една сигнатура и под формули и структури ще разбираме съответно формули при тази сигнатура и структури с тази сигнатура.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      Ще посочим как с помощта на въведените понятия може да се характеризира възможността за положително решение на някои основни видове задачи на логическото програмиране. Модел за едно множество Γ от формули ще наричаме коя да е структура, в която всички формули от Γ са тъждествено верни (ако те са затворени, условието е равносилно с това те да са верни във въпросната структура). Да предположим, че в някаква ситуация формулите от Γ биват използвани като клаузи на една логическа програма. Тогава получените чрез тази програма положителни отговори на запитвания всъщност важат за всеки модел за Γ. Поради това положителен отговор на запитване, изразяващо се чрез затворена формула, може да бъде даден точно тогава, когато тя е вярна във всеки модел за Γ. На запитване пък, изразяващо се чрез каква да е формула, положителен отговор може да бъде даден точно тогава, когато тя е изпълнима във всеки модел за Γ.

      Забележка 1. Ако Γ е произволно множество от формули, а Δ е получено чрез замяна на всяка формула от Γ чрез нейно универсално затваряне, то всеки модел за Γ е модел за Δ и обратно. Това е ясно от доказаното по-горе твърдение за свеждане на въпроса за тъждествена вярност към съответен въпрос за универсалното затваряне.

      Забележка 2. Ако Γ е множеството на членовете на дадена конюнкция, то модели за Γ са точно онези структури, в които въпросната конюнкция е тъждествено вярна.

      Забележка 3. Една формула F е изпълнима във всеки модел за дадено множество от формули Γ точно тогава, когато не съществува модел за множеството  Γ ∪ { ¬ F }.  Това се проверява лесно, като се използва обстоятелството, че за да бъде формулата F изпълнима в дадена структура, необходимо и достатъчно е формулата  ¬ F  да не е тъждествено вярна в тази структура (беше отбелязано в твърдението за взаимна изразимост на тъждествената вярност и изпълнимостта).
 

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

Previous  Next  Contents