Previous  Next  Contents
 

 

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

    Ще покажем, че последователното прилагане на две субституции към даден терм или дадена атомарна формула може да се замени с прилагане на подходяща една субституция. За тази цел ще дефинираме едно действие, наречено умножение на субституции. Нека 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)
X(s1s2) = (Xs1)s2.
    Пример 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 е в сила равенството
(2)
E(s1s2) = (Es1)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 от субституции, където k2, също ще дефинираме субституция, която ще наричаме тяхно произведение, и ще я означаваме с 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 г.
 
 Previous  Next  Contents