Ако v е една оценка в S на променливите, то на всеки терм τ ще съпоставим елемент на D, който ще наричаме стойност на τ в S при оценката v и ще означаваме с τ^S,v. Това ще направим чрез следната индуктивна дефиниция, еднозначността на която следва от еднозначния прочит на термовете:
        1. Ако τ е променлива, то τ^S,v = v(τ).
        2. Ако τ е константа, то τ^S,v = τ^S.
        3. Ако τ е термът ω(τ₁,…,τ_m), където m е положително цяло число, ω e m-местен функционален символ и τ₁, …, τ_m са термове, то τ^S,v = ω^S(τ₁^S,v, …, τ_m^S,v).

      Пример 1. Ако S е структурата от примера в текста "Сигнатури и структури", то за всяка оценка v в S имаме

      Следното твърдение показва, че стойността на един терм в дадена структура при дадена оценка на променливите не зависи от поведението на оценката вън от множеството на променливите на терма.

      Лема за базисна роля на променливите на един терм. Ако две оценки в S съвпадат върху множеството на променливите на даден терм τ, то стойностите на τ в S при тези две оценки са равни. В частност, ако термът τ е затворен, то стойността на τ в S при всяка оценка в S е една и съща.

      Доказателство. Ще си послужим с индукция, съобразена с дефиницията за терм. Ако термът τ е променлива и две оценки v и w в S съвпадат върху множеството VAR(τ), то

      Ако τ е затворен терм, то независещия от избора на оценката v в S елемент τ^S,v на D ще наричаме стойност на τ в S. Когато τ е константа, тази стойност е интерпретацията τ^S на τ в S. Оттук нататък ще означаваме с τ^S стойността в S на всеки затворен терм τ. Очевидно е в сила следното твърдение: ако τ е термът ω(τ₁,…,τ_m), където m е положително цяло число, ω e m-местен функционален символ и τ₁, …, τ_m са затворени термове, то τ^S = ω^S(τ₁^S,…,τ_m^S). Последното равенство би могло да се използва и за директното разпространяване на означението τ^S за произволен затворен терм τ с помощта на индуктивна дефиниция.

      За произволен терм стойността му в S при дадена оценка на променливите в общия случай зависи от избора на оценката. Лемата за базисна роля на променливите на един терм показва, че стойността на терма е функция на стойностите на неговите променливи при въпросната оценка. Ще покажем, че тази функция е изразима в S (припомняме, че изразимостта на една функция в S всъщност означава изразимост на тази функция чрез множеството от функции F^S). Първо ще дефинираме едно понятие за представяне на функции.

      Нека τ е терм. Ако ξ₁, …, ξ_n, където n>0, са две по две различни променливи и g е n-местна функция в носителя D на S, ще казваме, че τ представя g от ξ₁, …, ξ_n в S, ако за всяка оценка v в S е изпълнено равенството τ^S,v = g(v(ξ₁), …, v(ξ_n)). Ако d е нулместна функция в D (т.е. d е някой елемент на D), ще казваме, че τ представя d в S, ако за всяка оценка v в S е изпълнено равенството τ^S,v = d.

      Пример 2. Нека g е функцията в множеството на целите числа, която преобразува всяко от тях в неговото противоположно. Пример 1 показва, че термът difference(difference(x,x),x)) представя g от x в разглежданата там структура S. Термът difference(x,x) пък представя нулместната функция 0 в S, а също така при всеки избор на две по две различни променливи ξ₁, …, ξ_n, където n>0, той представя 0⁽ⁿ⁾ от ξ₁, …, ξ_n в S (независимо от това дали x е някоя от тези променливи).

      Нека ξ₁, …, ξ_n, където n>0, са две по две различни променливи. Непосредствено се проверява, че са в сила следните твърдения:

        1. За всяко i от множеството {1,…,n}, ако g е i-тата n-местна проекционна функция в D, то термът ξ_i представя g от ξ₁, …, ξ_n в S.
        2. Ако τ е константа, а g е n-местният вариант на нулместната функция τ^S в D, то термът τ представя g от ξ₁, …, ξ_n в S.
        3. Нека τ е термът ω(τ₁,…,τ_m), където m е положително цяло число, ω e m-местен функционален символ и τ₁, …, τ_m са термове. Ако g₁, …, g_m са такива n-местни функции в D, че τ_i представя g_i от ξ₁, …, ξ_n в S при i=1,…,m, то τ представя ω^S(g₁,…,g_m) от ξ₁, …, ξ_n в S.

      Непосредствена е проверката и на следните твърдения, които са аналози на твърденията 2 и 3:
        2₀. Ако τ е константа, то τ представя нулместната функция τ^S в S.
        3₀. Ако τ е термът ω(τ₁,…,τ_m), където m е положително цяло число, ω e m-местен функционален символ и τ₁, …, τ_m са термове, представящи в S съответно нулместните функции d₁, …, d_m, то τ представя в S нулместната функция ω^S(d₁,…,d_m).

      Като използваме твърденията 1, 2, 3, 2₀, 3₀ и си послужим с индукция, съобразена с дефиницията за терм, убеждаваме се в истинността на следната уточнена и леко усилена формулировка на твърдението, за което стана дума преди дефиницията за представяне:

      Изразимост на стойността на един терм като функция на стойностите на неговите променливи. За произволен терм τ, ако всички негови променливи са измежду две по две различните променливи ξ₁, …, ξ_n, където n>0, то съществува такава n-местна функция g в D, изразима в S, че τ представя g от ξ₁, …, ξ_n в S. Всеки затворен терм представя в S някоя нулместна функция в D, изразима в S.

      Забележка 1. Усилването, за което стана дума преди малко, се състои в това, че се допуска измежду променливите ξ₁, …, ξ_n да има такива, които не са променливи на τ. Това усилване е удобно за нуждите на доказателството, но не е много съществено, защото запазването на изразимостта при суперпозиция позволява в изразимите функции да се добавят фиктивни аргументи (чрез суперпозиция с подходящо избрани проекционни функции).

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

      С помощта на твърденията 1, 2, 3, 2₀ и 3₀ може да се докаже и следното твърдение, което е в известен смисъл обратно на твърдението за изразимост на стойността на един терм като функция на стойностите на неговите променливи:

      Представимост на изразимите функции чрез термове. Ако n е положително цяло число, g е n-местна функция в D, която е изразима в S, и ξ₁, …, ξ_n са две по две различни променливи, то съществува такъв терм τ, че всички променливи на τ са измежду променливите ξ₁, …, ξ_n и τ представя g от ξ₁, …, ξ_n в S. За всяка нулместна функция в D, която е изразима в S, съществува затворен терм, който я представя в S.

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

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