Съдържание 
 

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

      За да осигурим някои удобства при дефинирането на понятието за формула на предикатното смятане, ще въведем това понятие само за сигнатури, удовлетворяващи едно допълнително условие от технически характер. За една сигнатура Σ ще казваме, че е удобна, ако равенството ξπ=ξπ е невъзможно, когато ξ и ξ са различни променливи, а π и π са предикатни символи на Σ с един и същ брой аргументи. Лесно се проверява, че поотделно всяко едно от следните условия е достатъчно, за да бъде дадена сигнатура Σ удобна:
        А. Не съществува непразна дума, която е едновременно край на някоя променлива и начало на някой предикатен символ на Σ.
        Б. Никой предикатен символ на Σ не е край на друг предикатен символ на Σ, който е със същия брой аргументи.
        В. Никоя променлива не е начало на друга променлива.

      В случая, за който става дума в забележка 2 от текста Сигнатури и структури, всяка сигнатура удовлетворява условието А (това е така, защото във въпросния случай всеки допустим сигнатурен символ започва с буква, неучастваща в никоя променлива). Следователно в този случай всяка сигнатура е удобна.

      Нека е дадена една удобна сигнатура Σ=(Φ,Π,ρ). Ще наричаме формули в сигнатура Σ на предикатното смятане от първи ред (по-кратко формули в сигнатура Σ на предикатното смятане или още по-кратко формули в сигнатура Σ ) някои думи над основната азбука, разширена освен със знаците лява кръгла скоба, дясна кръгла скоба и запетая още със знака за отрицание, знака за конюнкция, знака за дизюнкция, знака за общност и знака за съществуване (често ще пропускаме частта в сигнатура Σ на термина). Дефиницията е индуктивна:
        1. Всяка атомарна формула в сигнатура Σ е формула в сигнатура Σ.
        2. Всеки път, когато φ е формула в сигнатура Σ, думата  ¬φ  също е формула в сигнатура Σ (нарича се отрицание на φ и се чете не φ).
        3. Всеки път, когато φ и ψ са формули в сигнатура Σ, думите  (φ&ψ)  и  (φψ)  също са формули в сигнатура Σ (наричат се съответно конюнкция и дизюнкция на φ и ψ, като първата се чете φ и ψ, а втората    φ или ψ).
        4. Всеки път, когато φ е формула в сигнатура Σ и ξ е променлива, думите  ξφ  и  ξφ  също са формули в сигнатура Σ (наричат се съответно генерализация и екзистенциализация на φ относно ξ, като първата се чете за всяко ξ φ, а втората    за някое ξ φ; думите от вида ξ и думите от вида ξ, където ξ е променлива, се наричат съответно квантори за общност и квантори за съществуване).

      Забележка 1. Вместо за някое ξ φ" ще използваме, когато е по-подходящ, прочита съществува такова ξ, че φ.

      Пример. Нека Σ е сигнатурата от примера в текста Сигнатури и структури. Тогава всяка от следните думи е формула в сигнатурата Σ:
positive(x) (1)
positive(difference(difference(x,x),x)) (2)
(positive(x)&positive(difference(difference(x,x),x))) (3)
(positive(x)positive(difference(difference(x,x),x))) (4)
¬(positive(x)&positive(difference(difference(x,x),x))) (5)
¬x(positive(x)&positive(difference(difference(x,x),x))) (6)
x(positive(x)positive(difference(difference(x,x),x))) (7)
(positive(difference(y,x))z(positive(difference(y,z))&positive(difference(z,x)))) (8)
xy(positive(difference(y,x))z(positive(difference(y,z))&positive(difference(z,x)))) (9)
Като се имат пред вид структурата S от гореспоменатия пример, семантиката на атомарните формули (включително пример 1 от текста за тази семантика) и посоченият в дефиницията начин на четене на формулите, получени по точки 2, 3 и 4 от нея, получаваме следните интуитивни тълкувания на горните формули: 
Атомарните формули (1) и (2) изразяват съответно условието едно цяло число да е положително и условието числото да е отрицателно (наред с това интуитивно тълкуване можем да изкажем и точното твърдение, че ако означим с p и с q едноместните предикати в D с множества на истинност, състоящи се съответно от положителните и от отрицателните цели числа, то формулите (1) и (2) представят в S съответно p от x и q от x). 
Формулата (3) изразява неизпълнимото условие едно цяло число да е едновременно положително и отрицателно. 
Формулата (4) изразява условието дадено число да е положително или отрицателно    условие, което е изпълнено за всяко цяло число, различно от 0, но не е изпълнено за нулата. 
Формулата (5) изразява изпълненото за всяко цяло число отрицание на условието, изразено чрез (3). 
Формулата (6) изразява вярното твърдение, че не съществува цяло число, което да удовлетворява условието, изразено чрез (3). 
Формулата (7) изразява невярното твърдение, че за всяко цяло число е положително или отрицателно (числото 0 е противоречащ пример за това общо твърдение). 
Формулата (8) изразява условието за дадени цели числа x и y да е в сила неравенството y>x и да няма нито едно цяло число помежду тях (това условие е изпълнено точно тогава, когато y=x+1). 
Формулата (9) изразява вярното твърдение за всяко цяло число съществува такова по-голямо от него цяло число, че между двете да няма нито едно цяло число. 
      Следните две думи също са формули в сигнатурата Σ (за по-лесното разчитане на първата от тях бихме могли да оставим интервал между буквите y и p в нея, но дефиницията, която дадохме, не предвижда оставянето на такъв интервал, тъй че наличието му е допустимо само във визуализацията на формулата, но не и в самата формула, разглеждана като формален обект):
ypositive(x) (10)
y(positive(difference(x,y))&x(positive(difference(y,x))&positive(x))). (11)
Интуитивното тълкуване на формулите (10) и (11) е донякъде затруднено, защото прочитът им води до необичайно звучащи изречения (например от първата бихме получили такова изречение: За всяко цяло число y числото x е положително). Когато по-нататък дефинираме строго семантиката на формулите на предикатното смятане, тези две формули ще могат безпроблемно да бъдат осмислени като условия, отнасящи се до стойността на x, като условието, отговарящо на формулата (10), ще бъде изпълнено точно за онези цели числа, които са положителни, а условието, отговарящо на формулата (11)    точно за онези, които са по-големи от 2.

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

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

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

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

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

      Като разполагаме с тези леми, да предположим, че за някои формули φ, ψ, φ, ψ имаме равенство от вида (φγψ)=(φγψ), където и γ, и γ е знак за конюнкция или знак за дизюнкция. Ще покажем, че в такъв случай имаме равенствата φ=φ, γ=γ, ψ=ψ. За тази цел е достатъчно да отбележим, че от предположеното равенство следва разбира се равенството φγψ=φγψ, а пък от него и от изказаните преди малко две леми е ясно, че думите φ и φ трябва да имат равни дължини.

      Остана да разгледаме случая на точка 4. Очевидно разглеждането му се свежда до доказване на следното твърдение: ако за дадени променливи ξ и ξ и дадени формули φ и φ имаме равенството ξφ=ξφ, то ξ=ξ (и следователно φ=φ). Да предположим, че ξφ=ξφ за дадени променливи ξ и ξ и дадени формули φ и φ. Не е възможно едната от формулите φ и φ да е атомарна, а другата да не е, защото при такова положение някой от знаците за отрицание, конюнкция, дизюнкция, общност и съществуване би участвал в едната от страните на равенството, без да участва в другата. Ако никоя от формулите φ и φ не е атомарна, равенството ξ=ξ следва от обстоятелството, че в този случай φ започва със знак, неучастващ в ξ, а φ    със знак, неучастващ в ξ, тъй че ξ и ξ трябва да са с равни дължини. Остава да разгледаме възможността и двете формули φ и φ да са атомарни. Ако едната от тях е нулместен предикатен символ, то и другата е такъв, защото в противен случай в едната страна на равенството ξφ=ξφ биха участвали скоби, без те да участват в другата. Значи ако някоя от формулите φ и φ е нулместен предикатен символ, можем направо да използваме предположението, че сигнатурата Σ е удобна. Ако пък никоя от тях не е нулместен предикатен символ, то ще имаме

φ=π(τ1,,τm),    φ(τ1,,τm)
за някои положителни цели числа m и m, някой m-местен предикатен символ π, някой m-местен предикатен символ π и някои термове τ1,m1,m. Тогава, понеже в никоя от думите ξ, π, ξ, π не участва лява скоба, от равенството ξφ=ξφ следва, че
ξπ=ξπ,    τ1,,τm1,,τm.
Оттук, като използваме забележка 4 от текста Термове и еднозначност на прочита им, заключаваме, че m=m, тъй че ρ(π)=ρ(π) и значи пак можем да използваме обстоятелството, че сигнатурата Σ е удобна.

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

 positive(x)&positive(difference(difference(x,x),x)). 
Ако обаче в съдържащата я формула (5) пропуснем същите скоби, ще получим
 ¬positive(x)&positive(difference(difference(x,x),x)), 
което съвпада със съкратения запис на различната от (5) формула
 (¬positive(x)&positive(difference(difference(x,x),x))), 
получен чрез премахване на най-външните й скоби.

      Забележка 2. Дадената в настоящия текст дефиниция за формула на предикатното смятане би имала смисъл за произволна сигнатура, но е подходяща само за удобните сигнатури, тъй като само за тях е налице еднозначност на прочита на всички форнули, получени чрез поставяне на квантор пред атомарна формула. За да се постигне еднозначност на прочита на формулите в случая на произволна сигнатура, нужни са някои изменения в дефиницията. Например би могло в точка 4 от дефиницията да се предвиди оставяне на интервал между променливата ξ и формулата φ, стига основната азбука да не съдържа знака интервал (ако тя го съдържа, бихме могли вместо него да използваме подходящ друг знак).

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

Последно изменение: 5.11.2007
По-стар вариант:  9.01.2007