Еквивалентни формули

ЕКВИВАЛЕНТНИ ФОРМУЛИ

Под формули и под структури пак ще разбираме съответно формули в някоя дадена сигнатура и структури с тази сигнатура. Ако φ и ψ са формули, ще казваме, че φ е еквивалентна на ψ (или че φ и ψ са еквивалентни), и ще пишем φ≡ψ, когато от φ следва ψ и от ψ следва φ. Като вземем пред вид дефиницията на отношението следване между формули, виждаме, че горното условие е равносилно с изискването винаги, когато едната от формулите φ и ψ е вярна в дадена структура S при дадена оценка v на променливите, другата също да е вярна в S при оценката v (разбира се ако формулите φ и ψ са затворени, можем да се интересуваме от тяхна вярност в S вместо от тяхна вярност в S при дадена оценка на променливите).

Пример 1. Всеки две тъждествено верни формули са еквивалентни. Всеки две неизпълними формули също са еквивалентни.

Пример 2. Ако π е едноместен предикатен символ на дадената сигнатура, a ξ и ξ′ са променливи, то

∀ξ π(ξ) ≡ ∀ξ′ π(ξ′), ∃ξ π(ξ) ≡ ∃ξ′ π(ξ′). В първата от двете еквивалентности можем да се убедим, като забележим, че верността на затворените формули ∀ξ π(ξ) и ∀ξ′ π(ξ′) в дадена структура S е равносилна съответно с тъждествената вярност в тази структура на формулата π(ξ) и на формулата π(ξ′), а пък тъждествената вярност на всяка от последните две формули в S е равносилна с изискването предикатът π^S да приема стойност 1 във всяка точка от носителя на S. За да се убедим във втората от еквивалентностите, можем да разсъждаваме по подобен начин, но със замяна на думите "тъждествената вярност" и на думите "във всяка точка" съответно с думата "изпълнимостта" и с думите "в някоя точка".

Вземайки пред вид характеризацията на следването на една формула от друга чрез неравенство между стойностите им, получаваме следната характеризация на еквивалентността на формули чрез равенство на стойностите им: две формули φ и ψ са еквивалентни точно тогава, когато φ^S,v=ψ^S,v за всяка структура S и всяка оценка v в нея.

Пример 3. Нека π е двуместен предикатен символ на дадената сигнатура, τ е терм в нея, а ξ и ξ′ са променливи, които не принадлежат на множеството VAR(τ). Тогава

∀ξ π(ξ,τ) ≡ ∀ξ′ π(ξ′,τ), ∃ξ π(ξ,τ) ≡ ∃ξ′ π(ξ′,τ). За да се убедим в първата от двете еквивалентности, достатъчно е да забележим, че както и да изберем променлива ζ, непринадлежаща на множеството VAR(τ), за всяка структура S и оценка v в нея стойността ∀ζ π(ζ,τ)^S,v е най-малката от стойностите на π^S(d,τ^S,v) при изменението на d в носителя на S, поради което тази стойност не зависи от избора на променливата ζ. Във втората от еквивалентностите можем да се убедим по аналогичен начин.

Забележка 1. Твърденията от примери 2 и 3 са частни случаи на едно твърдение за преименуване на свързана променлива, което ще формулираме и докажем по-нататък.

От свойствата 1-5 на отношението следване между формули веднага се получават такива свойства на еквивалентността на формули (в тези свойства θ, φ, ψ и χ могат да бъдат произволни формули):
1. θ≡θ (рефлексивност).
2. Ако θ≡φ и φ≡ψ, то θ≡ψ (транзитивност).
3. Ако θ≡φ, то ¬θ≡¬φ (запазване на еквивалентността при отрицание).
4. Ако θ≡φ и ψ≡χ, то θ&ψ≡φ&χ и θ∨ψ≡φ∨χ (запазване на еквивалентността при конюнкция и при дизюнкция).
5. Ако θ≡φ, то ∀ξθ≡∀ξφ и ∃ξθ≡∃ξφ при всеки избор на променливата ξ (запазване на еквивалентността при генерализация и при екзистенциализация).

За разлика от следването на една формула от друга еквивалентността между формули има (както се вижда направо от дефиницията) още и свойството симетричност, а именно: ако φ≡ψ, то ψ≡φ.

Следните еквивалентности са в сила при всеки избор на формулите φ, ψ, θ и на променливата ξ (проверката може да се извърши, като се покаже, че за всяка от еквивалентностите формулата отляво и формулата отдясно имат равни стойности във всяка структура при всяка оценка на променливите в нея):

φ&φ≡φ, φ∨φ≡φ, φ&ψ≡ψ&φ, φ∨ψ≡ψ∨φ, (φ&ψ)&θ≡φ&(ψ&θ), (φ∨ψ)∨θ≡φ∨(ψ∨θ), (φ∨ψ)&θ≡(φ&θ)∨(ψ&θ), (φ&ψ)∨θ≡(φ∨θ)&(ψ∨θ), (φ∨ψ)&φ≡φ, (φ&ψ)∨φ≡φ, ¬¬φ≡φ, ¬(φ&ψ)≡¬φ∨¬ψ, ¬(φ∨ψ)≡¬φ&¬ψ, ¬∀ξφ≡∃ξ¬φ, ¬∃ξφ≡∀ξ¬φ.
Tвърдението по-долу показва, че може да се мине без генерализация и без екзистенциализация на формулите относно променливи, които не са техни свободни променливи.

Несъщественост на генерализацията и на екзистенциализацията относно променлива, която не е свободна променлива на формулата. Нека θ е формула, а ξ е променлива, която не е свободна променлива на θ. Тогава всяка от формулите ∀ξθ и ∃ξθ е еквивалентна на θ.

Доказателство. Нека S е произволна структура, а v е произволна оценка в S. Понеже променливата ξ не е свободна променлива на θ, ясно е, че за всеки елемент d на носителя на S оценката v[ξ→d] съвпада с оценката v върху множеството на свободните променливи на θ и следователно θ^S,v[ξ→d]=θ^S,v. Това показва, че във всяка структура и при всяка оценка в нея формулите ∀ξθ и ∃ξθ имат същата стойност както θ. _□

Забележка 2. Вместо горното директно доказателство бихме могли да дадем друго, което използва примери 5 и 7 от текста "Следване на формула от множество от формули. Отношението следване между формули". А именно, пример 5 осигурява следването на θ от ∀ξθ и следването на ∃ξθ от θ, а обратните следвания могат да се получат въз основа на пример 7, като се използват съотношението θ⊨θ и обстоятелството, че ξ не е свободна променлива на θ.

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