УМНОЖЕНИЕ НА СУБСТИТУЦИИ
Ще покажем, че последователното прилагане на две субституции към даден терм или дадена атомарна формула може да се замени с прилагане на подходяща една субституция. За тази цел ще дефинираме едно действие, наречено умножение на субституции. Нека s1 и s2 са дадени субституции. Да дефинираме едно изображение s на множеството на променливите в множеството на термовете, като положим
s(X) = (Xs1)s2
за всяка променлива X (т.е. полагаме s(X) да бъде резултатът от прилагането на субституцията s2 към терма Xs1). Това изображение е субституция, защото ако за някоя променлива X равенството s(X)=X е нарушено, то за нея със сигурност е нарушено и някое от равенствата s1(X)=X и s2(X)=X,
тъй че равенството s(X)=X
може да бъде нарушено най-много за краен брой променливи X. Субституцията
s, която дефинирахме по този начин, ще наричаме
произведение на s1 и
s2 и ще я означаваме със s1s2. Очевидно дефиницията, която дадохме, осигурява, че за всяка променлива X е в сила равенството
Пример 1. Нека X0 е променлива, а c1 и c2 са две различни константи. Тогава са в сила равенствата
[X0/c1][X0/c2] = [X0/c1], [X0/c2][X0/c1] = [X0/c2]
(значи произведението на две субституции може да зависи от реда на множителите).
Ще проверим само първото от двете равенства, а второто се проверява аналогично. Ще трябва да покажем, че за всяка променлива X е в сила равенството
X([X0/c1][X0/c2]) = X[X0/c1].
Ако X е променливата X0, това равенство е вярно, тъй като
X0([X0/c1][X0/c2]) = (X0[X0/c1])[X0/c2] = c1[X0/c2] = c1 = X0[X0/c1].
Ако пък X е променлива, различна от X0, то
X([X0/c1][X0/c2]) = (X[X0/c1])[X0/c2] = X[X0/c2] = X = X[X0/c1]
и значи равенството пак се оказва вярно.
Забележка. Горният пример е възможен при условие, че съществуват поне две различни константи. Фактът, че произведението на две субституции може да зависи от реда на множителите, е налице обаче и без такова допълнително предположение. За да се убедим в това, достатъчно е да заменим в разгледания пример двете константи c1 и c2 с две променливи Y1 и Y2, които са различни както помежду си, така и от X0. Лесно се проверява, че при такъв избор на X0, Y1 и Y2 са в сила равенствата
[X0/Y1][X0/Y2] = [X0/Y1], [X0/Y2][X0/Y1] = [X0/Y2]
и следователно имаме неравенството
[X0/Y1][X0/Y2] №
[X0/Y2][X0/Y1] .
Пример 2. Нека s
е произволна субституция. Тогава са в сила равенствата
is = si =
s.
Действително, за всяка променлива X имаме равенствата X(is)
= (Xi)s = Xs, X(si) = (Xs)i = Xs (последното от тези равенства следва от твърдение 2 от предходния въпрос).
Пример 3. Нека U и V са две
различни променливи. Тогава е в сила равенството
[U/V][V/U] = [V/U].
Действително, имаме равенствата
U([U/V][V/U]) = V[V/U]
= U,
V([U/V][V/U]) = V[V/U] = U,
а за всяка променлива X, която е различна и от U, и от V, имаме
X([U/V][V/U]) = X[V/U] = X,
тъй че V([U/V][V/U]) = U, а за всяка променлива X, различна от V, е в сила равенството
X([U/V][V/U]) = X.
Пример 4. Предполагайки отново, че U
и V са две различни променливи, да приложим установеното в пример
3 с разменени роли на U и V. Получаваме равенството
[V/U][U/V] = [U/V], а значи и още един пример, че произведението на две субституции може да зависи от реда на множителите (това, че субституциите [V/U] и [U/V] са различни, се вижда например като сравним стойностите им за променливата U).
Пример 5. Нека пак U и V
са две различни променливи и нека s е субституцията [U/V,V/U]. Тогава е в сила равенството ss = i .
Действително, равенството X(ss)
= X е очевидно, когато X е променлива, различна и от U, и от V, и се проверява лесно, когато X е някоя от тези две променливи.
Сега ще докажем, че равенството (1) остава в сила и тогава, когато вместо променлива X вземем произволен друг терм или пък атомарна формула. По този начин ще покажем, че прилагане на произведението на две субституции към даден терм или дадена атомарна формула винаги е равносилно с последователно прилагане на тези две субституции.
Прилагане на произведение на две субституции към термове и към атомарни формули. Нека E е терм или атомарна формула. Тогава за всеки две субституции s1
и s2 е в сила равенството
Доказателство. Ако E е променлива,
горното равенство следва направо от (1). Ако E е константа, равенството пак е вярно, защото тогава и двете му страни са равни на E. Нека сега E=f(E1,E2...,En),
където n е положително цяло число, f e n-местен
функционален символ и E1, E2,
..., En са такива термове, че при i=1,2,...,n е в сила равенството
Ei(s1s2) = (Eis1)s2.
Тогава
E(s1s2) = f(E1,E2...,En)(s1s2) = f(E1(s1s2),E2(s1s2)...,En(s1s2)) = f((E1s1)s2,(E2s1)s2...,(Ens1)s2) =
f(E1s1,E2s1...,Ens1)s2 = (f(E1,E2...,En)s1)s2 = (Es1)s2.
Веднаж доказано по този начин за произволни термове, равенството (2)
лесно се разпространява и за атомарни формули. ї
Следствие (асоциативен закон на умножението на субституции). За всеки три субституции s0,s1
и s2 е в сила равенството
s0(s1s2)
= (s0s1)s2.
Доказателство. За всяка променлива X имаме
X(s0(s1s2)) = (Xs0)(s1s2) = ((Xs0)s1)s2 = (X(s0s1))s2 = X((s0s1)s2).
ї
Сега ще дефинираме умножение и на друг брой субституции освен на две. А именно, когато е дадена произволна крайна редица s1, s2, ..., sk от субституции, където k№2, също ще дефинираме субституция, която ще наричаме тяхно произведение, и ще я означаваме с s1s2...sk. За целта ще приемем, че при kі2 по дефиниция имаме
| (3) |
s1s2...sksk+1 = (s1s2...sk)sk+1,
| |
|
и допълнително ще се условим под произведение на едночленна редица от субституции да разбираме единствения неин член, а под произведение на празна редица от субституции - субституцията i (така дадената дефиниция осигурява верността на равенството (3) и при k<2). Като използваме асоциативния закон на умножението на субституции и си послужим с индукция относно l, лесно се убеждаваме, че при всеки избор на естествените числа k и l и на k+l-членната редица от субституции s1, s2, ..., sk, sk+1, sk+2, ..., sk+l е в сила равенството
s1s2...sksk+1sk+2...sk+l = (s1s2...sk)(sk+1sk+2...sk+l).
Ако E е терм или атомарна формула, приемаме също, че
Es1s2...sksk+1 = (Es1s2...sk)sk+1
за всяко естествено число k и всяка k+1-членна редица от субституции s1, s2, ..., sk, sk+1 (в частност приемаме, че Es1s2 = (Es1)s2 за всеки две субституции s1 и s2). Чрез индукция относно l лесно се доказва равенството
Es1s2...sksk+1sk+2...sk+l = (Es1s2...sk)(sk+1sk+2...sk+l)
(при доказателството се използва доказаното твърдение за прилагане на произведение на две субституции към термове и към атомарни формули). Равенството е вярно и при k=0, като тогава то добива вида
Es1s2...sl = E(s1s2...sl).
Последно изменение: 5.03.2002 г.