Съдържание 
 

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

      Нека е дадена една сигнатура Σ. Ще наричаме формули в сигнатура Σ на предикатното смятане от първи ред (по-кратко формули в сигнатура Σ на предикатното смятане или още по-кратко формули в сигнатура Σ ) някои думи над основната азбука, разширена освен със знаците лява кръгла скоба, дясна кръгла скоба и запетая още със знака за отрицание, знака за конюнкция, знака за дизюнкция, квантора за общност, квантора за съществуване и знака интервал (често ще пропускаме частта "в сигнатура Σ" на термина). Дефиницията е индуктивна:
        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)
∀x ∃y (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 positive(x) (10)
∃y (positive(difference(x,y))&∃x (positive(difference(y,x))&positive(x))). (11)
Когато по-нататък дефинираме строго семантиката на формулите на предикатното смятане, тези две формули ще могат безпроблемно да бъдат осмислени като условия, отнасящи се до стойността на x, така, че условието, отговарящо на формулата (10), ще бъде изпълнено точно за онези цели числа, които са положителни, а условието, отговарящо на формулата (11)  -  точно за онези, които са по-големи от 2.

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

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

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

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

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

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

      Когато при прилагане на четвъртата точка от дефиницията формулата φ не е атомарна, може да се пропусне предвиденият в тази точка знак интервал без от това да пострада еднозначността на прочита, защото в този случай и първият знак на φ не участва в никоя променлива. Ние не включваме тази възможност в дефиницията, за да не я усложним, но ще разглеждаме получаващата се при пропускането на знака интервал дума като съкратен запис на същинската формула, която се получава според дефиницията. Ще използваме този съкратен запис и в съкратени записи на формули, получени от въпросната формула чрез по-нататъшни прилагания на точки от дефиницията. Например формулата (8) от примера по-горе ще има следното малко по-кратко записване:

∀x∃y(positive(difference(y,x))&¬∃z(positive(difference(z,x))&positive(difference(y,z)))).

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

      Когато една формула е получена по третата точка от дефиницията и тази формула се използва самостоятелно, а не като част от някоя по-сложна, можем да не пишем лявата скоба, която е в началото, и дясната, която е в края, и да смятаме, че те се подразбират. Ако обаче такава формула е част от някоя по-сложна, пропускането на споменатите скоби би създало опасност от двусмислица и затова не трябва да се прави (поне ако не се приемат подходящи допълнителни уславяния). Например при самостоятелно използване на формулата (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))), 
получен чрез премахване на най-външните й скоби.
 

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