Съдържание |
В случая, за който става дума в забележка 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) |
∀x∃y(positive(difference(y,x))&¬∃z(positive(difference(y,z))&positive(difference(z,x)))) | (9) |
∀ypositive(x) | (10) |
∃y(positive(difference(x,y))&∃x(positive(difference(y,x))&positive(x))). | (11) |
Ясно е, че за съществуването на формули в дадената сигнатура е необходимо и достатъчно съществуването на поне една атомарна формула в тази сигнатура, а това е равносилно с наличието на поне един предикатен символ в сигнатурата.
Лесно се вижда, че никоя формула не е същевременно терм – за атомарните формули това вече го знаем, а за останалите следва от обстоятелството, че всяка от тях съдържа някой от знаците за отрицание, за конюнкция или за дизюнкция или пък някой от двата квантора – знаци, които не участват в никой терм.
Ще покажем, че и при формулите е налице еднозначност на прочита, т.е. всяка формула може да се получи само по една от четирите точки на дефиницията и само по един начин. За целта първо отбелязваме, че формулите, получени по точка 1, не могат да се получат по никоя от останалите три точки, тъй като не съдържат никой от изброените преди малко няколко знака. От друга страна първите знаци на формулите, получени по различни измежду точките 2, 3 и 4, са винаги различни. Остава да покажем, че не може една и съща формула да бъде получена по два различни начина по някоя от точките 2, 3 и 4. За случая на точка 2 това е очевидно. За да докажем, че и по точка 3 никоя формула не може да се получи по два различни начина, ще си послужим със следните леми, на които доказателството е с индукция, съобразена с индуктивната дефиниция на понятието формула.
Лема 1. Във всяка формула броят на участията на лява кръгла скоба е равен на броя на участията на дясна кръгла скоба.
Лема 2. Във всяко начало на формула, завършващо със знак за конюнкция или знак за дизюнкция, броят на участията на лява кръгла скоба е по-голям от броя на участията на дясна кръгла скоба.
Като разполагаме с тези леми, да предположим, че за някои формули φ, ψ, φ′, ψ′ имаме равенство от вида (φγψ)=(φ′γ′ψ′), където и γ, и γ′ е знак за конюнкция или знак за дизюнкция. Ще покажем, че в такъв случай имаме равенствата φ=φ′, γ=γ′, ψ=ψ′. За тази цел е достатъчно да отбележим, че от предположеното равенство следва разбира се равенството φγψ=φ′γ′ψ′, а пък от него и от изказаните преди малко две леми е ясно, че думите φ и φ′ трябва да имат равни дължини.
Остана да разгледаме случая на точка 4. Очевидно разглеждането му се свежда до доказване на следното твърдение: ако за дадени променливи ξ и ξ′ и дадени формули φ и φ′ имаме равенството ξφ=ξ′φ′, то ξ=ξ′ (и следователно φ=φ′). Да предположим, че ξφ=ξ′φ′ за дадени променливи ξ и ξ′ и дадени формули φ и φ′. Не е възможно едната от формулите φ и φ′ да е атомарна, а другата да не е, защото при такова положение някой от знаците за отрицание, конюнкция, дизюнкция, общност и съществуване би участвал в едната от страните на равенството, без да участва в другата. Ако никоя от формулите φ и φ′ не е атомарна, равенството ξ=ξ′ следва от обстоятелството, че в този случай φ започва със знак, неучастващ в ξ′, а φ′ – със знак, неучастващ в ξ, тъй че ξ и ξ′ трябва да са с равни дължини. Остава да разгледаме възможността и двете формули φ и φ′ да са атомарни. Ако едната от тях е нулместен предикатен символ, то и другата е такъв, защото в противен случай в едната страна на равенството ξφ=ξ′φ′ биха участвали скоби, без те да участват в другата. Значи ако някоя от формулите φ и φ′ е нулместен предикатен символ, можем направо да използваме предположението, че сигнатурата Σ е удобна. Ако пък никоя от тях не е нулместен предикатен символ, то ще имаме
Когато една формула е получена по третата точка от дефиницията и тази формула се използва самостоятелно, а не като част от някоя по-сложна, можем да не пишем лявата скоба, която е в началото, и дясната, която е в края, и да смятаме, че те се подразбират. Ако обаче такава формула е част от някоя по-сложна, пропускането на споменатите скоби би създало опасност от двусмислица и затова не трябва да се прави (поне ако не се приемат подходящи допълнителни уславяния). Например при самостоятелно използване на формулата (3) можем да я пишем във вида
Забележка 2. Дадената в настоящия текст дефиниция за формула на предикатното смятане би имала смисъл за произволна сигнатура, но е подходяща само за удобните сигнатури, тъй като само за тях е налице еднозначност на прочита на всички форнули, получени чрез поставяне на квантор пред атомарна формула. За да се постигне еднозначност на прочита на формулите в случая на произволна сигнатура, нужни са някои изменения в дефиницията. Например би могло в точка 4 от дефиницията да се предвиди оставяне на интервал между променливата ξ и формулата φ, стига основната азбука да не съдържа знака интервал (ако тя го съдържа, бихме могли вместо него да използваме подходящ друг знак).
Оттук нататък, когато ще става дума за формули на предикатното смятане, винаги, дори и да не е изрично казано, ще се предполага, че е дадена някоя удобна сигнатура и разглежданите формули са всъщност формули в тази сигнатура.