ТЕРМОВЕ

    Т1. Всяка дума от W₀ИX е терм.
    Т2. Ако wОW_n, където n>0, и t₁, ..., t_n са термове, то думата w(t₁,...,t_n) също е терм.

    Тази дефиниция може да се представи чрез индуктивен механизъм в множеството U на думите над споменатото разширение на A, състоящ се от всички индуктори от вида Ж/t, където tОW₀ИX, и от всички индуктори от вида {t₁,...,t_n}/w(t₁,...,t_n), където n е положително цяло число, wОW_n и t₁, ..., t_n са елементи на U.

    Аналогично дефинираме понятието затворен терм:

    ЗТ1. Всяка дума от W₀ е затворен терм.
    ЗТ2. Ако wОW_n, където n>0, и t₁, ..., t_n са затворени термове, то думата w(t₁,...,t_n) също е затворен терм.

    Ясно е, че затворените термове са термове, а обратното не е вярно (например променливите са термове, които не са затворени).

    Очевидно термовете, които се получават по Т2, са различни от онези, които се получават по Т1, и затворените термове, които се получават по ЗТ2, са различни от онези, които се получават по ЗТ1 (думите, получени по Т2 или ЗТ2, съдържат скоби, докато думите, посочени в Т1 или ЗТ1, не съдържат). Освен това, ако един терм е получен по Т1, то неговото получаване е еднозначно в смисъл, че той не може да бъде едновременно в W₀ и в X (понеже XЗW=Ж). Важно е да се отбележи, че имаме еднозначност на получаването на термовете и на затворените термове и по Т2 и ЗТ2 в следния смисъл: ако wОW_n, wўОW_nў, където n и nў са положителни цели числа, и t₁, ..., t_n, t₁ў, ..., t_nўў са термове, то равенството между думи
(1)                w(t₁,...,t_n)= wў(t₁ў,...,t_nўў)
е налице само тогава, когато имаме и равенствата w=wў, n=nў, t₁=t₁ў, ..., t_n=t_nў. Това се установява с помощта на следните две леми, на които доказателството е с индукция, съобразена с дефиницията за терм:

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

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

    Прилагането на лемите става по следния начин. От равенството (1) веднага се вижда, че w=wў и следователно n=nў, а това позволява да твърдим, че думите t₁,...,t_n и t₁ў,...,t_nў са равни. Оттук заключаваме най-напред, че t₁=t₁ў. Ако n=1, то това е ясно, а при n>1 допускането, че думите t₁ и t₁ў имат различни дължини, противоречи на лемите, тъй че и в този случай тези две думи ще се окажат равни (като еднакво дълги начала на една и съща дума). При n>1 установеното равенство t₁=t₁ў показва, че и думите t₂,...,t_n и t₂ў,...,t_nў също са равни, с което си послужваме по подобен начин, за да установим, че t₂=t₂ў, и т.н.

    Еднозначността на получаването на термовете и на затворените термове по точките от съответните индуктивни дефиниции ще наричаме още еднозначност на синтактичния им анализ. Тя позволява коректно да се дефинират понятията стойност на затворен терм в дадена структура и стойност на терм в дадена конфигурация. Въпросните стойности ще бъдат елементи на носителя на дадената структура или конфигурация. Ще дадем първо малко по-простата дефиниция за стойност на затворен терм в дадена структура S=(C,I). Тази дефиниция е с индукция, съответна в известен смисъл на индуктивната дефиниция на понятието затворен терм, и има следния вид:

    СЗТ1. Ако wОW₀, то w има стойност I(w) в S.
    СЗТ2. Ако wОW_n, където n>0, и t₁, ..., t_n са затворени термове, имащи в S стойности съответно c₁, ..., c_n, то термът w(t₁,...,t_n) има стойност I(w)(c₁,...,c_n) в S.

    Можем да считаме, че горната дефиниция действа в множеството на всички наредени двойки, на които първият и вторият член са съответно затворен терм и елемент на C, и че тя определя за кои двойки от това множество приемаме, че вторият им член е стойност на първия в дадената структура. При такава гледна точка дефиницията може да се представи с индуктивен механизъм, състоящ се от всички индуктори от вида Ж/(w,I(w)), където wОW₀, и от всички индуктори от вида

    Като се използва индукция, съобразена с индуктивната дефиниция на понятието затворен терм, доказва се, че всеки затворен терм има точно една стойност в S (при доказателството за единственост на стойността се използва още и еднозначността на синтактичния анализ на затворените термове). Ако t е произволен затворен терм, то неговата стойност в S ще означаваме с t^S. От точки СЗТ1 и СЗТ2 получаваме веднага следните две твърдения:

    СЗТ1⁼. Ако wОW₀, то w^S=I(w).
    СЗТ2⁼. Ако wОW_n, където n>0, и t₁, ..., t_n са затворени термове, то w(t₁,...,t_n)^S=I(w)(t₁^S,...,t_n^S).

    Сега ще дадем дефиницията за стойност на произволен терм в дадена конфигурация (S,v), където от своя страна S=(C,I). Дефиницията се състои от следните приемания:

    СТ1. Ако wОW₀, то w има стойност I(w) в (S,v).
    СТ1а. Ако xОX, то x има стойност v(x) в (S,v).
    СТ2. Ако wОW_n, където n>0, и t₁, ..., t_n са термове, имащи в (S,v) стойности съответно c₁, ..., c_n, то термът w(t₁,...,t_n) има стойност I(w)(c₁,...,c_n) в (S,v).

    Аналогично на случая на дефиницията за стойност на затворен терм в структура, и тук се доказва съществуване и единственост на стойността - т.е. доказва се, че всеки терм има точно една стойност в (S,v). Уславяме се стойността на произволен терм t в (S,v) да означаваме с t^S,v. При така въведеното означение точки СТ1, СТ1а и СТ2 дават следните твърдения:

    СТ1⁼. Ако wОW, то w^S,v=I(w).
    СТ1а⁼. Ако xОX, то x^S,v=v(x).
    СТ2⁼. Ако wОW_n, където n>0, и t₁, ..., t_n са термове, то w(t₁,...,t_n)^S,v=I(w)(t₁^S,v,...,t_n^S,v).

    Стойността на един терм в дадена конфигурация (S,v) ще наричаме още негова стойност в S при оценка v.

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