Пример 1. Ако сигнатурата Σ е както в пример 3 от текста „Сигнатури и структури“, то думите 

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

      И дефиницията за атомарна формула осигурява еднозначност на прочита. Двата случая в тази дефиниция се изключват взаимно, защото в първия случай атомарната формула се състои само от знаци, принадлежащи на основната азбука, а във втория не е така. Във втория случай предикатният символ π, числото m и термовете τ₁, …, τ_m се определят еднозначно по атомарната формула. Действително, в този случай π е най-дългото измежду онези начала на думата π(τ₁,…,τ_m), на които всички знаци са от основната азбука, значи въпросната дума определя еднозначно кой е предикатният символ π, а следователно също кое е числото m и коя е думата τ₁,…,τ_m. От силната приемливост на термовете и лемата за еднозначния прочит обаче е ясно, че тази дума определя еднозначно кои са термовете τ₁, …, τ_m (вж. текстовете „Термове при дадена сигнатура“ и „Осигуряване на еднозначен прочит с помощта на скоби и разделители“).

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

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

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

      Пример 2. Ако сигнатурата Σ е както в пример 3 от текста „Сигнатури и структури“, то всяка от следните думи е формула:

      Забележка 2. При прочита на формулите (10) и (11) се получават изречения, които звучат повече или по-малко необичайно (например от първата от тези формули бихме получили такова изречение: „За всяко цяло число y числото x е положително“). Когато дефинираме строго семантиката на формулите на предикатното смятане, и тези две формули ще могат безпроблемно да бъдат осмислени.

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

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

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

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

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

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