Съдържание 
 

УМНОЖЕНИЕ НА СУБСТИТУЦИИ

    Ще покажем, че последователното прилагане на две субституции към даден терм или дадена атомарна формула може да се замени с прилагане на подходяща една субституция. За тази цел ще дефинираме едно действие, наречено умножение на субституции. Нека σ1 и σ2 са дадени субституции. Да дефинираме едно изображение σ на множеството на променливите в множеството на термовете, като положим

σ(ξ) = (ξσ12
за всяка променлива ξ (т.е. полагаме σ(ξ) да бъде резултатът от прилагането на субституцията σ2 към терма ξσ1). Това изображение е субституция, защото ако за някоя променлива ξ равенството σ(ξ)=ξ е нарушено, то за нея със сигурност е нарушено и някое от равенствата σ1(ξ)=ξ и σ2(ξ)=ξ, тъй че равенството σ(ξ)=ξ може да бъде нарушено най-много за краен брой променливи ξ. Субституцията σ, която дефинирахме по този начин, ще наричаме произведение на σ1 и σ2 и ще я означаваме със σ1σ2. Очевидно дефиницията, която дадохме, осигурява, че за всяка променлива ξ е в сила равенството
(1)
ξ(σ1σ2) = (ξσ12.
    Пример 1. Нека ξ0 е променлива, а α1 и α2 са две различни константи. Тогава са в сила равенствата
01][ξ02] = [ξ01],    [ξ02][ξ01] = [ξ02]
(значи произведението на две субституции може да зависи от реда на множителите). Ще проверим само първото от двете равенства, а второто се проверява аналогично. Ще трябва да покажем, че за всяка променлива ξ е в сила равенството
ξ([ξ01][ξ02]) = ξ[ξ01].
Ако ξ е променливата ξ0, това равенство е вярно, тъй като
ξ0([ξ01][ξ02]) = (ξ001])[ξ02] = α102] = α1 = ξ001].
Ако пък ξ е променлива, различна от ξ0, то
ξ([ξ01][ξ02]) = (ξ[ξ01])[ξ02] = ξ[ξ02] = ξ = ξ[ξ01]
и значи равенството пак се оказва вярно.

    Забележка. Горният пример е възможен при условие, че съществуват поне две различни константи. Фактът, че произведението на две субституции може да зависи от реда на множителите, е налице обаче и без такова допълнително предположение. За да се убедим в това, достатъчно е да заменим в разгледания пример двете константи α1 и α2 с две променливи η1 и η2, които са различни както помежду си, така и от ξ0. Лесно се проверява, че при такъв избор на ξ0, η1 и η2 са в сила равенствата

01][ξ02] = [ξ01],    [ξ02][ξ01] = [ξ02]
и следователно имаме неравенството
01][ξ02] 02][ξ01] .

    Пример 2. Нека σ е произволна субституция. Тогава са в сила равенствата

ισ = σι = σ.
Действително, за всяка променлива ξ имаме равенствата ξ(ισ) = (ξι)σ = ξσ,  ξ(σι) = (ξσ)ι = ξσ (последното от тези равенства следва от твърдение 2 от въпроса Субституции).

    Пример 3. Нека η и ζ са две различни променливи. Тогава е в сила равенството

[η/ζ][ζ/η] = [ζ/η]
(а не равенството  [η/ζ][ζ/η] = ι,  както би могло евентуално да се предположи при повърхностен поглед върху нещата). Действително, имаме равенствата
η([η/ζ][ζ/η]) = ζ[ζ/η] = η,
ζ([η/ζ][ζ/η]) = ζ[ζ/η] = η,
а за всяка променлива ξ, която е различна и от η, и от ζ, имаме
ξ([η/ζ][ζ/η]) = ξ[ζ/η] = ξ,
тъй че ζ([η/ζ][ζ/η]) = η, а за всяка променлива ξ, различна от ζ, е в сила равенството ξ([η/ζ][ζ/η]) = ξ.

    Пример 4. Предполагайки отново, че η и ζ са две различни променливи, да приложим установеното в пример 3 с разменени роли на η и ζ. Получаваме равенството [ζ/η][η/ζ] = [η/ζ], а значи и още един пример, че произведението на две субституции може да зависи от реда на множителите (това, че субституциите [ζ/η] и [η/ζ] са различни, се вижда например като сравним стойностите им за променливата η).

    Пример 5. Нека пак η и ζ са две различни променливи и нека σ е субституцията [η/ζ,ζ/η]. Тогава е в сила равенството  σσ = ι . Действително, равенството  ξ(σσ) = ξ  е очевидно, когато ξ е променлива, различна и от η, и от ζ, и се проверява лесно, когато ξ е някоя от тези две променливи.

    Сега ще докажем, че равенството (1) остава в сила и тогава, когато вместо променлива ξ вземем произволен друг терм или пък атомарна формула. По този начин ще покажем, че прилагане на произведението на две субституции към даден терм или дадена атомарна формула винаги е равносилно с последователно прилагане на тези две субституции.

    Прилагане на произведение на две субституции към термове и към атомарни формули. Нека τ е терм или атомарна формула. Тогава за всеки две субституции σ1 и σ2 е в сила равенството
(2)
τ(σ1σ2) = (τσ12.
    Доказателство. Ако τ е променлива, горното равенство следва направо от (1). Ако τ е константа, равенството пак е вярно, защото тогава и двете му страни са равни на τ. Нека сега τ=f(τ1,τ2,τn), където n е положително цяло число, f e n-местен функционален символ и τ1, τ2, , τn са такива термове, че при i=1,2,,n е в сила равенството

τi1σ2) = (τiσ12.
Тогава
τ(σ1σ2) = f(τ1,τ2,τn)1σ2) = f(τ11σ2),τ21σ2),τn1σ2)) = f(1σ12,2σ12,nσ12) = f(τ1σ1,τ2σ1,τnσ1)σ2 = (f(τ1,τ2,τn)σ12 = (τσ12.
Веднаж доказано по този начин за произволни термове, равенството (2) лесно се разпространява и за атомарни формули. 

    Следствие 1 (асоциативен закон на умножението на субституции). За всеки три субституции σ0, σ1 и σ2 е в сила равенството

σ01σ2) = (σ0σ12.
    Доказателство. За всяка променлива ξ имаме
ξ(σ01σ2)) = (ξσ0)(σ1σ2) = ((ξσ012 = (ξ(σ0σ1))σ2 = ξ((σ0σ12).  

    За всяка атомарна формула φ формулите от вида φσ, където σ е субституция, се наричат частни случаи на φ (аналогична дефиниция може да се даде и за случая на термове, но няма да ни се наложи да я използваме). От тази дефиниция следва, че всяка атомарна формула е частен случай на себе си (тъй като за всяка атомарна формула φ имаме равенството φ=φι).

    Следствие 2. Ако φ е атомарна формула, то частните случаи на всеки частен случай на φ са частни случаи и на самата φ.

    Доказателство. Всеки частен случай на φ има вида φσ1, където σ1 е някоя субституция. Следователно частните случаи на кой да е частен случай на φ имат вида (φσ12, където σ1 и σ2 са някои субституции. При това положение е достатъчно да използваме равенството (φσ12 = φ(σ1σ2). 

    Сега ще дефинираме умножение и на друг брой субституции освен на две. А именно, на всяка крайна редица 1, σ2, , σk) от субституции ще съпоставим субституция, която ще наричаме нейно произведение (не изключваме случаите, когато k е 0 или 1, т.е. случаите на празна или едночленна редица). Това ще направим с помощта на следната индуктивна дефиниция:
     1. Под произведение на празна редица от субституции ще разбираме тъждествената субституция ι.
     2. Винаги, когато дадена k-членна редица от субституции 1, , σk) има произведение σ, под произведение на редицата 1, , σk, σk+1), където σk+1 е произволна субституция, ще разбираме субституцията σσk+1.

    Разбира се, при k=0 редицата 1, , σk) е празната, а редицата 1, , σk, σk+1) е с единствен член σ1. Поради това при k=0 точка 2 от горната дефиниция дава, че редицата с единствен член σ1 има произведение ισ1, т.е. тя има произведение σ1. Оттук, прилагайки същата точка при k=1, получаваме, че двучленната редица от субституции 1, σ2) има произведение σ1σ2. Това ни дава основание за всяко положително цяло число k да означаваме произведението на редицата от субституции 1, , σk) с σ1σk. В разглеждания от общ характер ще използваме това означение дори и в случаи, когато не е изключено числото k да е 0. При този начин на означаване съдържащата се в точка 2 от дефиницията връзка между произведение на k-членна редица от субституции и произведение на k+1-членна се записва чрез равенството

σ1σkσk+1 = (σ1σkk+1.
Ще имаме например равенствата  σ1σ2σ3 = (σ1σ23,  σ1σ2σ3σ4 = (σ1σ2σ34  и т.н.

    Като използваме асоциативния закон на умножението на субституции и си послужим с индукция относно l, лесно се убеждаваме, че при всеки избор на естествените числа k и l и на k+l-членната редица от субституции σ1, σ2, , σk, σk+1, σk+2, , σk+l е в сила равенството

σ1σ2σkσk+1σk+2σk+l = (σ1σ2σk)(σk+1σk+2σk+l).
В специалния случай, когато k е 1, това равенство добива вида
σ1σ2σ3σ1+l = σ12σ3σ1+l).
В частност  σ1σ2σ3 = σ12σ3),  σ1σ2σ3σ4 = σ12σ3σ4)  и т.н.

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