ФОРМУЛИ НА ПРЕДИКАТНОТО СМЯТАНЕ

    Забележка. Използването на думи от вида [x] и <x> в качеството на квантори за общност и за съществуване е нетрадиционно, но то е в съзвучие с означенията в съвременни направления на тъй наречената модална логика, изучаващи повече от един вид необходимост и възможност.

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

    Ще покажем, че и при формулите е налице еднозначност на синтактичния анализ - всяка формула се получава само по една от точките Ф1-Ф6 на дефиницията и само по един начин. За целта първо отбелязваме, че формулите, получени по точка Ф1, не могат да се получат по никоя от останалите пет точки, тъй като не съдържат никой от изброените преди малко няколко знаци. От друга страна първите букви на формулите, получени по различни измежду точките Ф2-Ф6, са винаги различни освен в случая, когато едната формула е получена по точка Ф3, а другата - по точка Ф4. Следователно, ако изключим последния случай, то можем да твърдим, че формули, получени по различни измежду точките Ф2-Ф6, не могат да съвпадат. За да покажем, че не могат да съвпадат и формули, получени по точка Ф3 и точка Ф4, ще си послужим със следните леми, на които доказателството е с индукция, съобразена с индуктивната дефиниция на понятието формула.

    Лема 1. Във всяка формула броят на участията на лява кръгла скоба е равен на броя на участията на дясна кръгла скоба.

    Лема 2. Във всяко начало на формула, завършващо със знак за конюнкция или знак за дизюнкция, броят на участията на лява кръгла скоба е по-голям от броя на участията на дясна кръгла скоба.

    Като разполагаме с тези леми, да предположим, че за някои формули j₁, j₂, j₁ў, j₂ў, имаме равенство от вида (j₁gj₂)=(j₁ўgўj₂ў), където и g, и gў е знак за конюнкция или знак за дизюнкция. Ще покажем, че в такъв случай имаме равенствата j₁=j₁ў, g=gў, j₂=j₂ў. За тази цел е достатъчно да отбележим, че от предположеното равенство следва разбира се равенството j₁gj₂=j₁ўgўj₂ў, а от него пък и от изказаните преди малко две леми е ясно, че думите j₁ и j₁ў трябва да имат равни дължини.

    Току-що установеният факт показва не само това, че не може една формула да бъде получена и по точка Ф3, и по точка Ф4. Той показва още, че когато една формула е получена по някоя от тези две точки, то тя може да бъде получена по нея само по един начин. Последното обаче е очевидно вярно и за всяка от останалите точки от дефиницията. С това еднозначността на синтактичния анализ на формулите е доказана.

    Еднозначността на синтактичния анализ на формулите ни позволява в частност да използваме следната терминология: ако j₁ и j₂ са формули, а j е тяхната конюнкция или тяхната дизюнкция, то формулите j₁ и j₂ ще наичаме съответно пръв член и втори член на j .

    Сега ще искаме да дефинираме кога една формула е вярна в дадена структура S=(C,I) при дадена оценка в S на променливите. Преди това ще дадем една друга дефиниция, имаща отношение към въпроса. В нея ще използваме означенията minB и maxB съответно за най-малкото и най-голямото число в дадено непразно крайно множество от числа B, както и следното означение: ако v е оценка в S на променливите, x е променлива и c е даден елемент на C, то е оценката в S на променливите, която приема стойност c за променливата x, а за всички останали променливи съвпада с v (тази оценка ще наричаме x,c-модификация на v). С дефиницията, която сега ще дадем, ще определим индуктивно кога една формула има в S при дадена оценка на променливите дадена стойност, принадлежаща на множеството {0,1}. Дефиницията се състои от следните приемания, в които v е произволна оценка в S на променливите, x е произволна променлива, а допустимите стойности на b, b₁, b₂ са 0 и 1:
    СФ1. Ако a е атомарна формула, то a има стойност a^S,v в S при оценката v.
    СФ2. Ако дадена формула j има стойност b в S при оценката v, то формулата Шj има стойност 1-b в S при оценката v.
    СФ3. Ако дадени формули j₁ и j₂ имат съответно стойности b₁ и b₂ в S при оценката v, то формулата (j₁&j₂) има стоиност min{b₁,b₂} в S при оценката v.
    СФ4. Ако дадени формули j₁ и j₂ имат съответно стойности b₁ и b₂ в S при оценката v, то формулата (j₁Ъj₂) има стоиност max{b₁,b₂} в S при оценката v.
    СФ5. Ако при всеки избор на елемента c на C дадена формула j има стойност 1 в S при оценката , то формулата "xj има стойност 1 в S при оценката v.
    СФ5ў. Ако при някой избор на елемента c на C дадена формула j има стойност 0 в S при оценката , то формулата "xj има стойност 0 в S при оценката v.
    СФ6. Ако при някой избор на елемента c на C дадена формула j има стойност 1 в S при оценката , то формулата $xj има стойност 1 в S при оценката v.
    СФ6ў. Ако при всеки избор на елемента c на C дадена формула j има стойност 0 в S при оценка , то формулата $xj има стойност 0 в S при оценка v.

    Можем да считаме, че в рамките на горната дефиниция структурата S остава фиксирана и дефиницията действа в множеството на всички наредени тройки (j,v,b), където j е формула, v е оценка в S на променливите, b е елемент на множеството {0,1}, а също, че с тази дефиниция се определя за кои тройки (j,v,b) от въпросното множество приемаме, че b е стойност на j в S при оценка v. При такава гледна точка дефиницията може да се представи чрез индуктивен механизъм в споменатото множество, състоящ се от индукторите от следните видове, където v може да бъде произволна оценка в S на променливите (разбира се тези видове съответстват на отделните приемания от дефиницията):
    Вид 1: Ж/(a,v,a^S,v), където a е атомарна формула.
    Вид 2: {(j,v,b)}/(Шj,v,1-b), където j е формула, а b е число от множеството {0,1}.
    Вид 3,4: {(j₁,v,b₁),(j₂,v,b₂)}/((j₁&j₂),v,min{b₁,b₂}) или {(j₁,v,b₁),(j₂,v,b₂)}/((j₁Ъj₂),v,max{b₁,b₂}), където j₁ и j₂ са формули, а b₁ и b₂ са числа от множеството {0,1}.
    Вид 5,6ў: {(j,,1)|cОC}/("xj,v,1) или {(j,,0)|cОC}/($xj,v,0), където j е формула, а x е променлива.
    Вид 5ў,6: {(j,,0)}/("xj,v,0) или {(j,,1)}/($xj,v,1), където j е формула, x е променлива, c е елемент на C.

    Забележка. В случаите, когато множеството C е безкрайно, посоченият индуктивен механизъм не е финитарен. Това е така, защото в тези случаи предпоставките на индукторите от вид 5,6ў са безкрайни множества.

    Ще покажем, че при произволно избрана оценка v в S на променливите всяка формула има точно една стойност в S при оценка v. Това ще го докажем чрез индукция, съобразена с индуктивната дефиниция на понятието формула; в разсъжденията ще използваме установената преди малко еднозначност на синтактичния анализ на формулите.

    Ако една формула a е атомарна, то точка СФ1 й предписва в S при оценка v стойността a^S,v и само нея, а никоя от останалите точки не предписва стойност на a, защото в тях се предписват стойности само на неатомарни формули.

    Ако дадена формула j има единствена стойност b в S при оценка v, то точка СФ2 предписва на формулата Шj в S при оценка v стойността 1-b и само нея (поради еднозначното представяне на формулата Шj в този вид), а никоя от останалите точки не предписва стойност на Шj, защото формулите, разглеждани в тях, са различни от Шj.

    Ако дадени формули j₁ и j₂ имат съответно единствени стойности b₁ и b₂ в S при оценка v, то точка СФ3 предписва на формулата (j₁&j₂) в S при оценка v стойността min{b₁,b₂} и само нея (поради еднозначното представяне на формулата (j₁&j₂) в този вид), а никоя от останалите точки не предписва стойност на (j₁&j₂), защото формулите, разглеждани в тях, са различни от (j₁&j₂).

    По напълно аналогичен начин се вижда, че и формулата (j₁Ъj₂) има точно една стойност в S при оценка v, когато j₁ и j₂ имат единствени стойности в S при оценка v.

    Да предположим сега, че за всяка оценка в S на променливите дадена формула j има единствена стойност в S при тази оценка. Ще покажем, че същото важи и за формулите "xj и $xj, където x е произволна променлива. Ще се ограничим с разглеждането на въпроса за първата от тези две формули, а за втората разсъжденията са аналогични. Нека v е произволна оценка в S на променливите. Преди всичко ясно е, че стойност на формулата "xj в S при оценка v биха могли да предпишат само точки СФ5 и СФ5ў, като всяка от тях поотделно може да предпише най-много една стойност на въпросната формула. Ако допуснем, че всяка от споменатите точки предписва стойност на "xj, ще се получи, че за някое c от C формулата j има в S при оценка както стойност 1, така и стойност 0, а това противоречи на направеното индуктивно предположение. Оттук е ясно, че формулата "xj има най-много една стойност в S при оценка v. За да се убедим, че тази формула има стойност в S при оценка v, ще отбележим, че е налице някой от следните два случая: а) за всяко c от C единствената стойност на формулата j при оценката е 1; б) за някое c от C единствената стойност на j при оценката е различна от 1 и следователно е 0. В случая а) обаче формулата "xj ще има стойност 1 в S при оценка v, а в случая б) - стойност 0.

    Обобщаваме означението за стойност на атомарна формула в конфигурация, като се уславяме за всяка формула j и всяка оценка v в S на променливите да означаваме с j^S,v единствената стойност на j в S при оценка v. От точки СФ2-СФ6ў на дефиницията за стойност на формула се получава, че при всеки избор на формулите j, j₁, j₂, на променливата x и на оценката v в S са изпълнение следните равенства:

("xj)^S,v=min,  ($xj)^S,v=max.

S,vШj  Ы  S,vj,

S,v(j₁&j₂)  Ы  S,vj₁  и  S,vj₂,

S,v(j₁Ъj₂)  Ы  S,vj₁  или  S,vj₂,

S,v"xj  Ы  S,j  за всяко c от C,

S,v$xj  Ы  S,j  за някое c от C.

    Ако една формула j е вярна в структурата S при всяка оценка в S на променливите, то ще казваме, че j е тъждествено вярна в S и ще пишем Sj. Когато дадена формула j е тъждествено вярна във всяка структура, ще казваме, че j е тъждествено вярна и ще пишем j.

    Пример. Нека p е едноместен предикатен символ, а x и y са две различни променливи. Тогава формулата (p(x)ЪШp(y)) не е тъждествено вярна, но е тъждествено вярна във всяка структура, на която носителят е едноелементно множество. От друга страна, формулата (p(x)ЪШp(x)) е тъждествено вярна.

    Следното твърдение ще бъде твърде полезно при някои по-нататъшни разглеждания.

    Лема за запазване на тъждествената вярност при поставяне или премахване на квантор за общност. Нека j е формула, x е променлива и S е структура. Тогава за да бъде формулата "xj тъждествено вярна в S, необходимо и достатъчно е формулата j да бъде тъждествено вярна в S.

    Доказателство. Нека S=(C,I). Изискването формулата "xj да бъде тъждествено вярна в S е изпълнено точно тогава, когато за всяка оценка v в S на променливите и за всеки елемент c на C формулата j е вярна в S при оценка . Това показва веднага, че ако j е тъждествено вярна в S, то "xj също е тъждествено вярна в S. Съвсем просто обаче се вижда, че и обратно, ако "xj е тъждествено вярна в S, то и j е тъждествено вярна в тази структура. За целта е достатъчно да се отбележи, че ако v е произволна оценка в S на променливите, то v=, където c=v(x).

    Следствие. Ако j е формула, x₁, x₂, ..., x_n са променливи и S е структура, то формулата "x₁"x₂..."x_nj е тъждествено вярна в S точно тогава, когато формулата j е тъждествено вярна в S.

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