Множество на променливите на терм.

МНОЖЕСТВО НА ПРОМЕНЛИВИТЕ НА ТЕРМ.

И тук под термове ще разбираме термове в дадена сигнатура Σ, която за краткост няма да споменаваме. На всеки терм τ ще съпоставим едно множество от променливи, което ще означаваме с VAR(τ). Елементите на това множество ще наричаме променливи на τ, а самото множество ще наричаме разбира се множество на променливите на τ. Дефиницията е индуктивна, като нейната еднозначност следва от еднозначността на прочита на термовете:
1. Ако τ е променлива, то VAR(τ) = {τ}.
2. Ако τ е константа, то VAR(τ) е празното множество.
3. Ако τ = ω(τ₁,…,τ_m), където m е положително цяло число, ω e m-местен функционален символ и τ₁, …, τ_m са термове, то VAR(τ) е обединението на множествата VAR(τ₁), …, VAR(τ_m).

Променливите на един терм са, тъй да се каже, онези променливи, които се използват при неговото построяване въз основа на дефиницията за терм. Чрез индукция, съобразена с нея, веднага се вижда, че за всеки терм τ множеството VAR(τ) е крайно и че всеки терм има поне една променлива или е затворен. Вижда се също, че всяка от променливите на един терм е негова поддума (оттук пак следва, че множеството на променливите му е крайно). В общия случай обаче не може да се твърди, че всяка променлива, която е поддума на даден терм, принадлежи на множеството на неговите променливи. Например би могло да се случи една дума, която е променлива, да е поддума на друга такава дума.

Един терм е затворен точно тогава, когато множеството на неговите променливи е празно. И наистина, това, че термовете без променливи са затворени, следва непосредствено от отбелязаното по-горе обстоятелство, че всеки терм има поне една променлива или е затворен. От друга страна чрез индукция, съобразена с дефиницията на понятието затворен терм, веднага се установява, че всеки затворен терм е с празно множество на променливите.

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

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

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

τ^S,v = v(τ) = w(τ) = τ^S,w. Ако τ е константа, то за всеки две оценки v и w в S имаме τ^S,v = τ^S = τ^S,w. Да предположим сега, че τ е термът ω(τ₁,…,τ_m), където m е положително цяло число, ω e m-местен функционален символ и τ₁, …, τ_m са термове, за които доказваното свойство е налице (т.е. ако две оценки в S съвпадат върху множеството на променливите на даден терм τ_k, то стойностите на τ_k в S при тези две оценки са равни). Нека v и w са оценки в S, които съвпадат върху множеството VAR(τ). Ако k е кое да е от числата 1, …, m, то v и w ще съвпадат и върху множеството VAR(τ_k), тъь като то се съдържа в VAR(τ), следователно ще имаме равенството τ_k^S,v = τ_k^S,w. Оттук получаваме τ^S,v = ω^S(τ₁^S,v, …, τ_m^S,v) = ω^S(τ₁^S,w, …, τ_m^S,w) = τ^S,w. _□

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