Съдържание 
 

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

      Както досега, формулите, за които ще става дума, ще бъдат формули при дадена сигнатура Σ. Да предположим на първо време, че е дадена една структура S=(Σ,D,I) с тази сигнатура. За една формула φ ще казваме, че е тъждествено вярна в S, ако φ е вярна в S при всяка оценка на променливите, и ще казваме, че φ е изпълнима в S, ако φ е вярна в S при някоя оценка на променливите.

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

      Забележка 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 при оценката vd], а това показва, че формулата ξφ е вярна в S при оценката v. Понеже v беше произволна, с това е показано, че ξφ е тъждествено вярна в S. Обратно, да предположим, че ξφ е тъждествено вярна в S. Тогава за всяко d от D формулата φ ще бъде вярна в S при съответната оценка vd] и остава само да забележим, че тази съответна оценка е всъщност самата оценка v, когато в качеството на d се вземе елементът v(ξ).  

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

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

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

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

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

      В текста Променливи на формула дефинирахме какво ще разбираме под универсално и под екзистенциално затваряне на една формула, като тези затваряния са затворени формули. Казаното по-горе показва, че ако дадена формула φ има универсално затваряне ψ и екзистенциално затваряне θ, то φ е тъждествено вярна в дадена структура S точно тогава, когато ψ е вярна в S, и φ е изпълнима в S точно тогава, когато θ е вярна в S.

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

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

(positive(x)¬positive(x)).

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

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

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

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

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

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

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

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

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

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

(positive(x)¬positive(x))
заключаваме, че е тъждествено вярна и формулата
x(positive(x)¬positive(x)).

 

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