Съдържание 
 

СУБСТИТУЦИИ. ПРИЛАГАНЕ НА СУБСТИТУЦИЯ КЪМ ТЕРМ

      Ще предполагаме, че е дадена една сигнатура Σ. Под субституция при сигнатура Σ ще разбираме такава функция σ с дефиниционна област множеството на всички променливи и със стойности в множеството на термовете при сигнатура Σ, че променливите, за които е нарушено равенството σ(ξ) = ξ, са най-много краен брой (в съгласие с предишно уславяне обикновено ще пропускаме думите „при сигнатура Σ“ и ще говорим просто за субституции и за термове). Ако ξ1, …, ξk , където k≥1, са променливи, които при k>1 са две по две различни, а θ1, …, θk са термове, то ще означаваме със знака [ξ1/θ1,…,ξk/θk] субституцията σ, определена по следния начин: σ(ξ1) = θ1, …, σ(ξk) = θk и σ(ξ) = ξ за всяка променлива ξ, различна от ξ1, …, ξk. Субституцията, която преобразува всяка променлива в самата нея, ще наричаме тъждествена субституция и ще означаваме с ι (тя разбира се може да се представи във вида [ξ1/ξ1], където ξ1 е произволно избрана променлива).

      Нека σ е дадена субституция. За всеки терм τ дефинираме терм στ, който ще наричаме резултат от прилагане на σ към τ (интуитивно въпросният резултат може да се схваща като получен чрез заместване на променливите в терма τ със съответните им стойности на σ). Дефиницията е индуктивна и се състои от следните точки:
       1. Ако ξ е променлива, то σξ = σ(ξ).
       2. Ако ω е константа, то σω = ω.
       3. Ако n е положително цяло число, ω е n-местен функционален символ и τ1, …, τn са термове, то

σω(τ1,…,τn) = ω(στ1,…,στn).
Разбира се еднозначността на тази дефиниция се осигурява от еднозначния прочит на термовете.

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

      Твърдение 1. За всеки терм τ е в сила равенството ιτ = τ.

      Доказателство. Равенството ιτ = τ е очевидно, когато τ е константа или променлива. Да предположим сега, че τ = ω(τ1,…,τn), където n е положително цяло число, ω е n-местен функционален символ и τ1, …, τn са термове, притежаващи доказваното свойство, т.е. термове, за които са в сила равенствата ιτ1 = τ1, …, ιτn = τn. Тогава

ιτ = ω(ιτ1,…,ιτn) = ω(τ1,…,τn) = τ,
т.е. термът τ също притежава доказваното свойство.  □

      Твърдение 2. Нека са дадени две субституции σ и σ'. Ако τ е произволен терм, то равенството στ = σ'τ е изпълнено точно тогава, когато σ и σ' съвпадат върху множеството VAR(τ).

      Доказателство. Ако τ е променлива, то е очевидно, че равенството στ = σ'τ е равносилно със съвпадането на σ и σ' върху множеството VAR(τ). Такава равносилност е налице по тривиални причини и в случая, когато τ е константа. Да предположим сега, че τ = ω(τ1,…,τn), където n е положително цяло число, ω е n-местен функционален символ и τ1, …, τn са такива термове, че при i=1,…,n равенството στi = σ'τi е равносилно със съвпадането на σ и σ' върху множеството VAR(τi). От равенствата

στ = ω(στ1,…,στn),   σ'τ = ω(σ'τ1,…,σ'τn)
е ясно, че равенството στ = σ'τ е изпълнено точно тогава, когато са изпълнени равенствата στi = σ'τi, i=1,…,n. Следователно равенството στ = σ'τ е равносилно със съвпадането на σ и σ' върху всяко от множествата VAR(τi), i=1,…,n, т.е. със съвпадането на σ и σ' върху обединението на въпросните n множества, което пък е точно VAR(τ).  □

      Следствие. Ако σ е субституция и τ е терм, то равенството στ = τ е изпълнено точно тогава, когато σξ = ξ за всяка променлива ξ от множеството VAR(τ). В частност στ = τ за всеки затворен терм τ.

      Доказателство. Прилагаме твърдение 2 при σ' = ι.  □

      Твърдение 3. Нека σ е произволна субституция. Тогава за всеки терм τ множеството VAR(στ) е обединение на множествата VAR(ση), където η принадлежи на VAR(τ).

      Доказателство. Твърдението е тривиално в случая, когато τ е променлива. То разбира се е вярно и в случая, когато τ е константа, защото обединението на празно семейство от множества е празно. Да предположим сега, че τ = ω(τ1,…,τn), където n е положително цяло число, ω е n-местен функционален символ и τ1, …, τn са такива термове, че при i=1,…,n множеството VAR(στi) е обединение на множествата VAR(ση), където η принадлежи на VAR(τi). От равенството στ = ω(στ1,…,στn) получаваме, че VAR(στ) е обединение на множествата VAR(στ1), …, VAR(στn) и следователно VAR(στ) е обединение на множествата VAR(ση), където η принадлежи на обединението на множествата VAR(τ1), …, VAR(τn). Последното обединение обаче е точно VAR(τ).  □

      Следствие. Ако σ е субституция и τ е терм, то термът στ е затворен точно тогава, когато за всяка променлива η на τ съответният терм ση е затворен.

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