Съдържание 
 

ПРЕИМЕНУВАНЕ НА СВЪРЗАНА ПРОМЕНЛИВА НА ПРЕНЕКСНА ФОРМУЛА

    Ще докажем следното твърдение:

    Лема за преименуване на свързана променлива на пренексна формула. Нека φ е пренексна формула, ξ е нейна свободна променлива, а ξ' е променлива, която не е нито свободна, нито свързана променлива на φ. Нека  φ' = φ[ξ/ξ'] . Тогава са в сила съотношенията

∀ξ φ ≡ ∀ξ' φ',   ∃ξ φ ≡ ∃ξ' φ' .

    Доказателство. Ще се занимаем с първата от двете еквивалентности, а втората се доказва аналогично. За произволна конфигурация (S,v), означавайки с D носителя на структурата S, имаме

(∀ξ' φ' )S,v = min{φ' S,v[ξ'→d] | d∈D} = min{φS,v[ξ'→d][ξ→ξ' S,v[ξ'→d]] | d∈D} = min{φS,v[ξ'→d][ξ→d] | d∈D} = min{φS,v[ξ→d] | d∈D} = (∀ξ φ)S,v
(освен семантиката на квантора за общност използваме твърдение 2 от въпроса „Заместване на променлива с терм в пренексна формула“ и обстоятелството, че оценките  v[ξ'→d][ξ→d]  и  v[ξ→d]  съвпадат върху множеството на свободните променливи на φ).  □

    Забележка 1. Левите и десните страни на еквивалентностите в горната лема имат едно и също множество на свободните променливи, а именно  FVAR(φ) \ {ξ} . И наистина, за всяка от двете леви страни това по дефиниция е множеството на свободните й променливи, а пък за множеството на свободните променливи на всяка от двете десни страни получаваме, че е

FVAR(φ') \ {ξ'} = ((FVAR(φ) \ {ξ}) ∪ {ξ'}) \ {ξ'} = (FVAR(φ) \ {ξ} .

    Забележка 2. Формулата φ', за която става дума в лемата, има същите свързани променливи както φ. Като вземем пред вид това, а също и забележка 1, можем да заключим следното: ако са дадени една пренексна формула с ненулев брой свързани променливи и едно крайно множество от променливи, то дадената пренексна формула е еквивалентна на някоя пренексна формула със същия брой свързани променливи и същото множество на свободните променливи, на която най-левият квантор е по променлива, непринадлежаща на даденото множество от променливи.

    Забележка 3. Доказаната лема всъщност е за преименуване на променливата, по която е най-левият от кванторите на една пренексна формула с ненулев брой свързани променливи. При пренексна формула с повече от една свързана променлива може обаче с помощта на тази лема и на свойството д) от въпроса „Еквивалентни формули“ да се преименува и коя да е друга от свързаните променливи на формулата.

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