Съдържание 
 

ОСИГУРЯВАНЕ НА ЕДНОЗНАЧЕН ПРОЧИТ С ПОМОЩТА НА СКОБИ И РАЗДЕЛИТЕЛИ

      Този въпрос играе подготвителна роля за описанието на формален език, подходящ за нуждите на математическата логика. Да предположим, че е дадена една азбука Α, сред чиито букви не фигурират двете скоби  (  и  ) . Нека Β е азбука, получена от Α чрез добавяне на тези две скоби и на някои други букви, непринадлежащи на Α, които ще наричаме разделители. Например Α може да бъде основната азбука, за която ставаше дума в текста „Сигнатури и структури“, а Β да се получава от Α чрез добавяне на скобите и запетаята (при това положение запетаята ще бъде единственият разделител). Друга възможност (от нея ще се възползваме малко по-късно) е Α да бъде азбуката, получена от основната чрез добавяне на знаците за отрицание, за общност и за съществуване, а пък Β да се получава от Α чрез добавяне на скобите, запетаята, знака за конюнкция и знака за дизюнкция (тогава разделители освен запетаята ще бъдат още знакът за конюнкция и знакът за дизюнкция).

      За коя да е да е дума θ над азбуката Β ще означаваме с l(θ) и с r(θ) съответно броя на участията на лява скоба и броя на участията на дясна скоба в θ. Думите θ, за които  l(θ) = r(θ),  ще наричаме уравновесени. Ще казваме, че думата θ е приемлива, ако тя е уравновесена и за всяко нейно начало λ, което завършва с разделител, имаме неравенството  l(λ) ≥ r(λ),  а ще казваме, че θ е силно приемлива, ако тя е уравновесена и за всяко нейно начало λ, което завършва с разделител, имаме строгото неравенство  l(λ) > r(λ)  (условията относно началата на θ, които завършват с разделител, смятаме за изпълнени и в случаите, когато не съществуват такива начала на θ, т.е. когато в θ няма разделители). Ясно е, че всяка силно приемлива дума е приемлива. Обратното не е вярно (например еднобуквена дума, на която буквата е разделител, не е силно приемлива, въпреки че е приемлива).

      Очевидно всички думи над азбуката Β, в които не участват скоби, са приемливи, а думите над азбуката Α са даже силно приемливи. При заграждане на приемлива дума в скоби се получава дума, която е силно приемлива, т.е. за всяка приемлива дума θ думата  (θ)  е силно приемлива. Действително, нека θ е приемлива дума. Тогава

l((θ)) = l(θ)+1 = r(θ)+1 = r((θ))
и за всяко начало  λ  на думата  (θ) ,  което завършва с разделител, имаме равенство от вида  λ = (μ  с някое начало  μ  на  θ,  завършващо с разделител, откъдето получаваме, че
l(λ) = l(μ)+1 ≥ r(μ)+1 = r(λ)+1 > r(λ).
Освен това конкатенацията на всеки две приемливи думи е пак приемлива дума, а конкатенацията на две силно приемливи думи е пак силно приемлива дума. За да докажем първото от тези две твърдения, да предположим, че  θ1  и  θ2  са приемливи думи и нека  θ = θ1θ2 . Тогава думата  θ  е приемлива, защото
l(θ) = l(θ1)+l(θ2) = r(θ1)+r(θ2) = r(θ),
а за всяко начало λ на θ, което завършва с разделител, е налице някой от следните два случая: а) λ е начало на θ1 и б) λ = θ1μ  за някое начало μ на θ2, завършващо с разделител. В случая а) верността на неравенството  l(λ) ≥ r(λ)  е непосредствено ясна, а в случая б) тя се вижда така:
l(λ) = l(θ1)+l(μ) = r(θ1)+l(μ) ≥ r(θ1)+r(μ) = r(λ).
Доказателството на второто от твърденията е аналогично. От доказаното разбира се е ясно, че конкатенацията на всякакъв краен брой приемливи думи е пак приемлива дума, а конкатенацията на всякакъв краен брой силно приемливи думи е пак силно приемлива дума.

      Забележка 1. От току-що отбелязаните свойства на приемливостта и на силната приемливост следва, че ако  θ1 ,  θ2 ,  … ,  θn−1 ,  θn ,  където  n ≥ 1,  са приемливи думи,  γ1 ,  γ2 ,  … ,  γn−1   са разделители и ω е дума над азбуката Α, то думата

ω(θ1γ1θ2γ2…θn−1γn−1θn)
е силно приемлива (считаме, че при  n = 1  изразът  θ1γ1θ2γ2…θn−1γn−1θn  означава  θ1).

      Важна роля по-нататък ще играе следното твърдение.

      Лема за еднозначния прочит. Ако една дума може да се представи във вида
(1) θ1γ1θ2γ2…θn−1γn−1θn ,     
където  n ≥ 1,  θ1 ,  θ2 ,  … ,  θn−1 ,  θn   са силно приемливи думи, а  γ1 ,  γ2 ,  … ,  γn−1   са разделители, то представянето й в този вид е единствено.

      Доказателство. Ще опишем един алгоритъм, преобразуващ всяка дума от вида (1), за която са изпълнени формулираните условия, в редицата от думи
(2)θ1γ1 ,  θ2γ2 ,  … , θn−1γn−1 ,  θn .     
За целта ще разгледаме един итеративен процес, който преобразува непразни крайни редици от думи пак в такива редици. Произволна стъпка на процеса може да бъде описана с помощта на следното указание: ако последният член на редицата има уравновесено начало, завършващо с разделител, то заменяме този член с двойка думи, първата от които е най-късото му уравновесено начало, завършващо с разделител, а втората е останалата част от този член след въпросното начало. Процесът завършва тогава, когато се стигне до редица, чийто последен член няма уравновесено начало, завършващо с разделител. Ще покажем, че ако се тръгне от едночленна редица, на която единственият член е дума от вида (1) при изпълнени условията от лемата, то след  n−1  на брой стъпки процесът завършва, при което се получава редицата (2). И наистина, с индукция относно  i,  използваща силната приемливост на думите  θ1 ,  θ2 ,  … ,  θn−1 ,  лесно се показва, че при  i = 0, 1, …, n−1,  ако тръгнем от редицата с единствен член (1), то след  i  на брой стъпки ще стигнем до редицата

θ1γ1 ,  θ2γ2 ,  … , θiγi,  θi+1γi+1θi+2γ2…θn−1γn−1θn, 
(приемаме, че при  i = n−1 изразът  θi+1γi+1θi+2γ2…θn−1γn−1θn  означава  θn ). В частност се получава, че след  n−1  стъпки ще стигнем до редицата (2). Понеже и думата  θn  е силно приемлива, с получаването на тази редица процесът завършва.  □

      Пример. Приемайки, че сме в условията на някой от споменатите в началото на настоящия текст два варианта за азбуките Α и Β, ще проследим как протича процесът от горното доказателство, когато дадената дума е

f(g(a,b),c),f(a,g(b,c)),g(f(a,b),c),g(a,f(b,c)) .
Едночленната редица, с която започва процесът, и последователно получаващите се в хода му други редици са следните (при записването на онези, които са с повече от един член, за отделяне на съседните им членове са използвани интервали вместо запетаи, за да се избегне объркване със запетаите, които са в самите членове): 
f(g(a,b),c),f(a,g(b,c)),g(f(a,b),c),g(a,f(b,c))
f(g(a,b),c),  f(a,g(b,c)),g(f(a,b),c),g(a,f(b,c))
f(g(a,b),c),  f(a,g(b,c)),  g(f(a,b),c),g(a,f(b,c))
f(g(a,b),c),  f(a,g(b,c)),  g(f(a,b),c),  g(a,f(b,c))  
Полученият резултат показва, че ако дадената дума има представяне от вида, разглеждан в лемата, то при това представяне са в сила равенствата
n = 4,   θ1 = f(g(a,b),c) ,   θ2 = f(a,g(b,c)) ,  θ3 = g(f(a,b),c) ,  θ4 = g(a,f(b,c)) ,
а разделителите γ1,  γ2 и γ3 са запетаи. Лесно се вижда, че така намерените думи θ1, θ2, θ3 и θ4 са силно приемливи, следователно дадената дума наистина има представяне от вида, разглеждан в лемата.

      Забележка 2. Силно приемливите думи θ1, θ2, θ3 и θ4, които се получиха в горния пример, са от вид, който е обичаен за математиката. Думи от подобен вид са обичайни и за езика Пролог. Съществуват обаче и странни силно приемливи думи, които не се срещат нито в математиката, нито в Пролог, и едва ли биха могли да имат някаква употреба. Такава е например думата  )((,))( . Всъщност обичайно срещащите се силно приемливи думи удовлетворяват и следното допълнително условие: за всяко начало λ на думата (независимо дали завършва или не завършва с разделител) да бъде в сила неравенството  l(λ) ≥ r(λ)..

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