Пример 1. Нека S е структурата от примера в текста "Сигнатури и структури". Тогава формулата (5) от примера в текста "Формули на предикатното смятане" е тъждествено вярна в S, формулата (3) от същия пример не е изпълнима в S, а формулата (4) от него е изпълнима в S, но не е тъждествено вярна в S (вж. пример 1 от текста "Семантика на формулите").

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

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

      Ще отбележим следните връзки между тъждествена вярност или изпълнимост на неатомарни формули и тъждествена вярност или изпълнимост на по-простите от формули, от които тя е получена:

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

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

      3. Конюнкцията на две формули е тъждествено вярна в S точно тогава, когато всяка от двете формули е тъждествено вярна в S.

      4. Дизюнкцията на две формули е изпълнима в S точно тогава, когато някоя от двете формули е изпълнима в S.

      5. Генерализацията на една формула относно дадена променлива е тъждествено вярна в S точно тогава, когато самата формула е тъждествено вярна в S.

      6. Екзистенциализацията на една формула относно дадена променлива е изпълнима в S точно тогава, когато самата формула е изпълнима в S.

      Всяко от горните твърдения се доказва, като се използва условието за вярност на съответния вид формули, отбелязано във въпроса "Семантика на формулите" (след дефиницията за стойност на формула в дадена структура при дадена оценка на променливите). Понеже доказателствата на първите четири от горните твърдения са непосредствени, предоставяме въпросните доказателства на читателя, а ще се занимаем само с доказателствата на твърденията 5 и 6.

      Доказателство на твърдението 5. Нека φ е произволна формула, а ξ е произволна променлива. Да предположим най-напред, че φ е тъждествено вярна в S, и да разгледаме произволна оценка v в S. За всеки елемент d на D формулата φ, бидейки тъждествено вярна в S, ще бъде вярна в S при оценката v[ξ→d], а това показва, че формулата ∀ξφ е вярна в S при оценката v. Понеже v беше произволна, с това е показано, че ∀ξφ е тъждествено вярна в S. Обратно, да предположим, че ∀ξφ е тъждествено вярна в S. Тогава за всяко d от D формулата φ ще бъде вярна в S при съответната оценка v[ξ→d] и остава само да забележим, че тази съответна оценка е всъщност самата оценка v, когато в качеството на d се вземе елементът v(ξ).  _□

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

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

      Пример 2. В случая, разгледан в пример 1 по-горе, твърдението 6 позволява от неизпълнимостта на формулата (3) да заключим за неизпълнимостта в S и на нейната екзистенциализация относно x, а понеже тази екзистенциализация е затворена формула, значи и за нейната невярност в S. В същия случай твърдението 5 пък позволява от факта, че формулата (4) не е тъждествено вярна в S, да заключим, че и нейната генерализация относно x не е тъждествено вярна в S. Понеже тази генерализация е затворена формула (тя е всъщност формулата (7) от примера в текста "Формули на предикатното смятане"), получаваме, че тя не е вярна в S (нещо, което по-рано го показахме директно).

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

      От твърденията 5 и 6 чрез индукция относно n се получава, че за произволна формула φ и произволна крайна редица ξ₁,…,ξ_n от променливи формулата ∀ξ₁…∀ξ_nφ е тъждествено вярна в дадена структура S точно тогава, когато формулата φ е тъждествено вярна в S, а формулата ∃ξ₁…∃ξ_nφ е изпълнима в S точно тогава, когато формулата φ е изпълнима в S. В специалния случай, когато φ няма свободни променливи, различни от ξ₁, …, ξ_n, формулите ∀ξ₁…∀ξ_nφ и ∃ξ₁…∃ξ_nφ са затворени и можем да твърдим, че първата от тях е вярна в S точно тогава, когато φ е тъждествено вярна в S, а втората е вярна в S точно тогава, когато φ е изпълнима в S.

      За произволна формула φ ще наричаме съответно нейно универсално затваряне и нейно екзистенциално затваряне всяка затворена формула от вида ∀ξ₁…∀ξ_nφ и всяка затворена формула от вида ∃ξ₁…∃ξ_nφ, където ξ₁, …, ξ_n са различни помежду си свободни променливи на φ (когато φ е затворена, споменатите формули съвпадат с нея). Очевидно всяка формула притежава поне едно универсално затваряне и поне едно екзистенциално затваряне. Когато дадена формула има повече от една свободна променлива, универсалното и екзистенциалното затваряне не са еднозначно определени (редът на променливите ξ₁, …, ξ_n може да се избира по различни начини), Ако дадена формула φ има универсално затваряне ψ и екзистенциално затваряне θ, то φ е тъждествено вярна в дадена структура S точно тогава, когато ψ е вярна в S, и φ е изпълнима в S точно тогава, когато θ е вярна в S.

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

      Пример 3. Нека Σ е сигнатурата от примера в текста "Сигнатури и структури". Всяка от формулите (1)-(11), разгледани в текста "Формули на предикатното смятане", е изпълнима, но никоя от тях не е тъждествено вярна. И наистина, повечето от тези формули са изпълними в структурата S от същия пример (някои от тях са даже тъждествено верни в нея). Не са изпълними в нея само формулите (3) и (7), но те са изпълними (и даже тъждествено верни) например в онези структури, за които множеството на истинност на предиката, интерпретиращ предикатния символ positive, съвпада с носителя на структурата. От друга страна измежду формулите (1)-(11) само формулите (5), (6) и (9) са тъждествено верни в разглежданата структура S, но пък никоя от тези три формули не е тъждествено вярна (и даже не е изпълнима) в споменатите по-горе други структури. Тъждествено верни формули все пак съществуват. Такава е например формулата

      От повечето отбелязани дотук общи свойства на тъждествената вярност и на изпълнимостта в дадена структура лесно се получават с тяхна помощ техни модификации, отнасящи се за въведения по-горе вариант на тези понятия. За целта най-често е достатъчно във формулировките на свойствата само да се пропусне споменаването на структурата. Например в сила е следната модификация на казаното в забележка 1: всяка тъждествено вярна формула е изпълнима, обратното в общия случай не е в сила, но то е в сила за затворените формули. В сила са и следните модификации на свойствата 1-6:

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

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

      3*. Конюнкцията на две формули е тъждествено вярна точно тогава, когато всяка от двете формули е тъждествено вярна.

      4*. Дизюнкцията на две формули е изпълнима точно тогава, когато някоя от двете формули е изпълнима.

      5*. Генерализацията на една формула относно дадена променлива е тъждествено вярна точно тогава, когато самата формула е тъждествено вярна.

      6*. Екзистенциализацията на една формула относно дадена променлива е изпълнима точно тогава, когато самата формула е изпълнима.

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

      Също така за произволна формула φ и произволна крайна редица ξ₁,…,ξ_n от променливи формулата ∀ξ₁…∀ξ_nφ е тъждествено вярна точно тогава, когато формулата φ е тъждествено вярна, а формулата ∃ξ₁…∃ξ_nφ е изпълнима точно тогава, когато формулата φ е изпълнима. Ако дадена формула φ има универсално затваряне ψ и екзистенциално затваряне θ, то φ е тъждествено вярна точно тогава, когато ψ е тъждествено вярна, и φ е изпълнима точно тогава, когато θ е изпълнима.

      Пример 4. Нека Σ е сигнатурата от примера в текста "Сигнатури и структури". От тъждествената вярност на формулата

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