Съдържание 
 

ТЕРМОВЕ И ЕДНОЗНАЧНОСТ НА ПРОЧИТА ИМ

      Нека е дадена една сигнатура Σ. Ще дефинираме понятието терм в сигнатура Σ, като всеки такъв терм ще бъде дума над основната азбука, разширена чрез добавяне на двете кръгли скоби и запетаята. Дефиницията е индуктивна и се състои от следните три точки:
        1. Всяка променлива е терм в сигнатура Σ.
        2. Всяка константа на Σ е терм в сигнатура Σ.
        3. Винаги, когато m е положително цяло число, ω e m-местен функционален символ на Σ и τ1, , τm са термове в сигнатура Σ, думата ω(τ1,,τm) също е терм в сигнатура Σ.

      Забележка 1. В точка 3 на горната дефиниция скобите и запетаите фигурират в означението ω(τ1,,τm) като формални символи и не означават нищо друго освен самите себе си (за разлика от останалите запетаи в същата точка, които изпълняват присъщата им в българския език и в математиката пунктуационна роля).

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

difference(difference(x,x),x))
е терм в сигнатура Σ.

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

      Дадената индуктивна дефиниция позволява да доказваме общи свойства на термовете с помощта на индукция, съобразена с нея. А именно, за да докажем, че всеки терм има дадено свойство, достатъчно е да покажем от една страна, че то е налице за променливите и за константите (това е тъй наречената база на индукцията), и от друга, че то се запазва при прилагането на третата точка от дефиницията (т.е. винаги, когато m е положително цяло число, ω e m-местен функционален символ и τ1, , τm са термове, притежаващи даденото свойство, термът ω(τ1,,τm) също го притежава    това е тъй наречената индуктивна стъпка). По такъв начин могат да се докажат например следните две леми.

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

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

      Забележка 3. Свойството от лема 2 се приема за налично по тривиални причини за онези термове, които нямат начала, завършващи със запетая (очевидно това са термовете, които не съдържат запетаи). Бихме могли да избегнем това приемане, като преформулираме въпросното свойство по следния начин: не съществува начало на терма, завършващо със запетая, в което знакът лява кръгла скоба да не участва повече пъти от знака дясна кръгла скоба.

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

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

      Остава да видим, че не може една дума по два различни начина да се окаже терм въз основа на третата точка, т.е. не може при два различни избора на цялото положително число m, на m-местния функционален символ ω и на термовете τ1, , τm съответната дума ω(τ1,, τm) да се окаже една и съща. Лесно е да се види, че функционалният символ ω се определя еднозначно по тази дума    той е най-дългото измежду нейните начала, в които всички знаци са от основната азбука. Оттук е ясно, че числото m и думата τ1,,τm също се определят еднозначно по ω(τ1,, τn). Поради това е достатъчно да докажем, че не може за някое положително цяло число m при два различни избора на термовете τ1, , τm съответната дума τ1,,τm да се окаже една и съща, а тази цел ще бъде постигната, ако покажем, че термът τ1 се определя еднозначно по думата τ1,,τm. В последното се убеждаваме, като забележим, че τ1 е най-късото начало на τ1,,τm, имащо следните две свойства: (а) в това начало знаците лява кръгла скоба и дясна кръгла скоба участват равен брой пъти и (б) началото съвпада с цялата дума или непосредствено след него в думата стои запетая. От лема 1 е ясно, че τ1 е едно начало на думата τ1,,τm което има свойствата (а) и (б). Да допуснем, че някое по-късо нейно начало γ също ги притежава. Тогава поради свойството (б) на γ думата, получена чрез добавяне на запетая след γ, ще бъде начало на τ1 и значи (според лема 2) в нея ще има повече участия на лява кръгла скоба отколкото на дясна    в противоречие със свойството (а) на γ.

      Забележка 4. Чрез леко допълване на горните разсъждения можем да се убедим във верността на едно по-силно твърдение, а именно: ако една дума може да се представи във вида τ1,,τm, където m е положително цяло число, а τ1, , τm са термове, то представянето й в този вид е единствено (усилването е в това, че и числото m се определя еднозначно по думата τ1,,τm, докато в горните разсъждения то се предполагаше вече известно). Доказателството става, като се използва и забележката, че в думата τ1,,τm има поне едно начало, завършващо със запетая и съдържащо равен брой леви и десни скоби, ако m>1, и няма такова начало при m=1.

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