За атомарни формули понятието стойност, за което става дума, вече сме го дефинирали в текста "Семантика на атомарните формули". Разпространяваме дадената там дефиниция с помощта на равенствата:

      Когато за дадена формула φ и дадена оценка v в S имаме равенството φ^S,v = 1, казваме, че φ е вярна в S при оценката v, и пишем  S,v ⊨ φ, а за да изразим, че φ не е вярна в S при оценката v, пишем  S,v ⊭ φ. Дадените дотук дефиниции осигуряват валидността на следните твърдения при всеки избор на оценка v в S, на формули φ, ψ и на променлива ξ: 
      1. Отрицанието на φ е вярно в S при оценката v точно тогава, когато φ не е вярна в S при оценката v. 
      2. Конюнкцията на φ и ψ е вярна в S при оценката v точно тогава, когато всяка от формулите φ и ψ е вярна в S при оценката v. 
      3. Дизюнкцията на φ и ψ е вярна в S при оценката v точно тогава, когато някоя от формулите φ и ψ е вярна в S при оценката v. 
      4. Генерализацията на φ относно ξ е вярна в S при оценката v точно тогава, когато φ е вярна в S при оценката v[ξ→d] за всеки елемент d на множеството D. 
      5. Екзистенциализацията на φ относно ξ е вярна в S при оценката v точно тогава, когато φ е вярна в S при оценката v[ξ→d] за някой елемент d на множеството D.

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

Формулата (3) не е вярна в S при никоя оценка, а формулата (5) е вярна в S при всяка оценка.

Нека v е произволна оценка в S. Бидейки конюнкция на формулите (1) и (2), формулата (3) е вярна в S при оценката v точно тогава, когато всяка от формулите (1) и (2) е вярна в S при оценката v, т.е. точно тогава, когато числото v(x) удовлетворява невъзможното изискване да е едновременно положително и отрицателно. Значи формулата (3) със сигурност е невярна в S при оценката v, следователно формулата (5), която е отрицанието на (3), със сигурност е вярна в S при оценката v.

Формулата (4) е вярна в S точно при онези оценки v, за които v(x) е различно от 0.

Нека v е произволна оценка в S. Понеже формулата (4) е дизюнкция на формулите (1) и (2), за да бъде тя вярна в S при оценката v, необходимо и достатъчно е поне една от формулите (1) и (2) да е вярна в S при оценката v, т.е. числото v(x) да е положително или отрицателно. Значи (4) е вярна при S при оценката v точно тогава, когато v(x) е различно от 0.

Формулата (6) е вярна в S при всяка оценка.

Формулата (6) е отрицание на екзистенциализацията на (3) относно x. Споменатата екзистенциализация да бъде вярна в S при дадена оценка v би означавало формулата (3) да бъде вярна в S при оценката v[x→d] за някое d от D, а (3) не е вярна в S при никоя оценка. Следователно разглежданата екзистенциализация не е вярна в S при никоя оценка и значи (6) е вярна в S при всяка оценка.

Формулата (7) не е вярна в S при никоя оценка.

Нека v е произволна оценка в S. Понеже (7) е генерализация на (4) относно x, за да бъде (7) е вярна в S при оценката v, необходимо и достатъчно е (4) да е вярна в S при оценката v[x→d] всяко d от D. При d=0 обаче формулата (4) не е вярна в S при оценката v[x→d]. Следователно формулата (7) не е вярна в S при оценката v.

Формулата (8) е вярна в S точно при онези оценки v, за които v(y)=v(x)+1.

Нека v е произволна оценка в S. Понеже (8) е конюнкция на двете формули positive(difference(y,x)),
¬∃z (positive(difference(y,z))&positive(difference(z,x))), за верността на (8) в S при оценката v е необходимо и достатъчно всяка от въпросните две формули да е вярна в S при оценката v. Първата от тях е вярна в S при оценката v точно тогава, когато v(y)>v(x), а втората  -  точно тогава, когато в S при оценката v не е вярна формулата ∃z (positive(difference(y,z))&positive(difference(z,x))), т.е. точно тогава, когато формулата (positive(difference(y,z))&positive(difference(z,x))) не е вярна в S при оценката v[z→d] за никое d от D. Последното е равносилно с несъществуването на число d от D, удовлетворяващо неравенствата v(y)>d>v(x). Да не съществува такова d и да бъде изпълнено неравенството v(y)>v(x) е равносилно с равенството v(y)=v(x)+1.

Формулата (9) е вярна в S при всяка оценка.

Нека v е произволна оценка в S. Като използваме последователно твърденията 4 и 5, виждаме, че за да бъде вярна (9) в S при оценката v, необходимо и достатъчно е за всяко d от D да съществува такова e от D, че формулата (8) да е вярна в S при оценката v[x→d][y→e]. Тъй като верността на (8) при споменатата оценка е равносилна с равенството e=d+1, ясно е, че за всяко d от D можем да осигурим вярност на формулата (8) в S при оценката v[x→d][y→e], вземайки в качеството на e числото d+1.

Формулата (10) е вярна в S точно при онези оценки v, за които v(x) е положително.

Нека v е произволна оценка в S. Понеже (10) е генерализация на (1) относно y, за да бъде вярна (10) в S при оценката v, необходимо и достатъчно (1) да е вярна в S при оценката v[y→d] за всяко d от D, а това е равносилно с условието v(x) да е положително.

Формулата (11) е вярна в S точно при онези оценки v, за които v(x)>2.

Нека v е произволна оценка в S. Понеже (11) е екзистенциализация относно y на формулата (positive(difference(x,y))&∃x (positive(difference(y,x))&positive(x))), за да бъде вярна (11) в S при оценката v, необходимо и достатъчно е да съществува такова d от D, че в S при оценката v[y→d] да бъде вярна всяка от двете формули positive(difference(x,y)),
∃x (positive(difference(y,x))&positive(x)). Нека d е произволно число от D. Верността на първата от тези две формули в S при оценката v[y→d] е равносилна с условието v(x)>d. Верността на втората в S при оценката v[y→d] пък е равносилна с условието да съществува такова e от D, че всяка от двете формули positive(difference(y,x)),
positive(x) да е вярна в S при оценката v[y→d][x→e], т.е. със съществуването в D на положително число e, което е по-малко от d. В крайна сметка верността на формулата (11) в S при оценката v се оказва равносилна със съществуването на числа d и e от D, удовлетворяващи неравенствата v(x)>d>e>0, а съществуването на такива d и e е равносилно с неравенството v(x)>2.
 

      Лемата за базисна роля на променливите на една атомарна формула се обобщава за произволни формули по следния начин.

      Лема за базисна роля на свободните променливи на една формула. Ако две оценки в S съвпадат върху множеството на свободните променливи на дадена формула φ, то стойностите на φ в S при тези две оценки са равни. В частност, ако φ е затворена, то стойността на φ в S при всяка оценка в S е една и съща.

      Доказателство. Разбира се достатъчно е да се докаже първото от горните две твърдения. Доказателството му се извършва чрез индукция, съобразена с дефиницията на понятието формула. За атомарни формули верността на това твърдение вече е установена, защото за тях множеството на свободните променливи съвпада с множеството на променливите. Индуктивните стъпки за случаите на отрицание, конюнкция и дизюнкция са прости. Например, ако една формула θ е конюнкция на две други, за които твърдението на лемата е в сила, а дадени оценки v и w в S съвпадат върху множеството FVAR(θ), те ще съвпадат и върху множеството на свободните променливи на всяка от въпросните други две формули (понеже то се съдържа във FVAR(θ)), следователно всяка от тях ще има в S равни стойности при оценките v и w, а оттук се вижда, че и формулата θ ще има равни стойности в S при оценките v и w. Малко повече труд изискват случаите на генерализация и на екзистенциализация. Нека например θ е формулата ∀ξφ за някоя променлива ξ и за някоя формула φ, за която твърдението на теоремата е в сила. Да предположим, че дадени оценки v и w в S съвпадат върху множеството на свободните променливи на θ. Тогава при всеки избор на елемент d на D оценките v[ξ→d] и w[ξ→d] ще съвпадат върху множеството на свободните променливи на φ (за произволна измежду тези променливи разглеждаме поотделно случая, когато тя е различна от ξ, и случая, когато тя е ξ). Оттук получаваме, че

      Ако φ е произволна затворена формула, то независещото от избора на оценката v в S число φ^S,v ще наричаме стойност на φ в S и ще го означаваме с φ^S (досега разполагахме с това понятие само за атомарните затворени формули). Въведеното за затворени атомарни формули понятие за вярност също се обобщава за произволни затворени формули. В случай, че φ е затворена формула и имаме равенството φ^S = 1, казваме, че φ е вярна в S, и пишем  S ⊨ φ, а за да изразим, че φ не е вярна в S, пишем  S ⊭ φ.

      Пример 2. Нека S е структурата от примера в текста "Сигнатури и структури". Затворените формули (6) и (9) от примера в текста "Формули на предикатното смятане" са верни в S, а затворената формула (7) от същия пример не е вярна в S (вж. пример 1 по-горе).

      Обобщава се и понятието за представяне на предикат от дадена формула, което засега сме дефинирали само за случая на атомарна формула. Нека φ е произволна формула. Ако ξ₁, …, ξ_n, където n>0, са две по две различни променливи и q е n-местен предикат в носителя D на S, ще казваме, че φ представя q от ξ₁, …, ξ_n в S, ако за всяка оценка v в S е изпълнено равенството φ^S,v = q(v(ξ₁), …, v(ξ_n)). Ако e е нулместен предикат (т.е. e е някое от числата 0 и 1), ще казваме, че φ представя e в S, ако за всяка оценка v в S е изпълнено равенството φ^S,v = e.

      Нека ξ₁, …, ξ_n, където n>0, са две по две различни променливи. Непосредствено се проверява, че са в сила следните твърдения:

        1. Ако дадена формула φ представя q от ξ₁, …, ξ_n в S, където q е даден n-местен предикат в D, то отрицанието на φ представя отрицанието на q от ξ₁, …, ξ_n в S, формулата ∀ξ_nφ представя резултата от универсална квантификация на q от ξ₁, …, ξ_n−1 в S, а формулата ∃ξ_nφ представя резултата от екзистенциална квантификация на q от ξ₁, …, ξ_n−1 в S.
        2. Ако дадени формули φ и ψ представят съответно q от ξ₁, …, ξ_n и r от ξ₁, …, ξ_n в S, където q и r са дадени n-местни предикати в D, то конюнкцията на φ и ψ представя конюнкцията на q и r от ξ₁, …, ξ_n в S, а дизюнкцията на φ и ψ представя дизюнкцията на q и r от ξ₁, …, ξ_n. в S.

      Непосредствена е и проверката на следните твърдения:

        1₀. Ако дадена формула φ представя q в S, където q е даден нулместен предикат в D, то отрицанието на φ представя отрицанието на q в S.
        2₀. Ако дадени формули φ и ψ представят съответно q и r в S, където q и r са дадени нулместни предикати в D, то конюнкцията на φ и ψ представя конюнкцията на q и r в S, а дизюнкцията на φ и ψ представя дизюнкцията на q и r в S.

      С помощта на твърденията 1, 2, 1₀ и 2₀ могат да се докажат аналози на твърдението за изразимост и твърдението за представимост, формулирани в края на текста "Семантика на термовете". В тези аналози ще става дума за изразимост и за безкванторна изразимост в S на предикати вместо на функции и тези понятия ще се свързват със семантиката на произволни формули и семантиката на безкванторни формули, като в първия случай вместо за променливи на формулата ще става дума за нейни свободни променливи. Единствената трудност, която възниква, е при доказателството на твърдението за изразимост във варианта му за произволни формули. Трудността е в индуктивната стъпка за формула от вида ∀ξφ или от вида ∃ξφ. И при такава стъпка трябва разбира се да предположим, че всички свободни променливи на въпросната формула са сред членовете на дадена крайна редица от две по две различни променливи. Ако променливата ξ не е член на тази редица, можем да използваме обстоятелството, че като добавим ξ след всички членове на редицата, получаваме крайна редица от две по две различни променливи, сред които са всички свободни променливи на формулата φ. Така обаче не може да се постъпи, когато ξ е член на дадената редица от променливи (това може да се случи, защото е възможно сред членовете на редицата да има и произволни други променливи освен свободните променливи на разглежданата формула). В този случай бихме могли на първо време да отстраним члена ξ на дадената редица и тогава да работим както в първия случай, а след това от получения изразим в S предикат да получим такъв, какъвто ни е нужен, чрез добавяне на фиктивен аргумент (то може да се осъществи чрез суперпозиция с подходящи проекционни функции).
 

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