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

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

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

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

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

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

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

    Прилагане на произведение на две субституции към термове и към атомарни формули. Нека τ е терм или атомарна формула. Тогава за всеки две субституции σ₁ и σ₂ е в сила равенството

(2)

τ(σ1σ2) = (τσ1)σ2.

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

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

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

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

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

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

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

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

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