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

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

Нека φ и ψ са формули. Ще казваме, че φ е еквивалентна на ψ (или че φ и ψ са еквивалентни), и ще пишем φ ≡ ψ, ако за всяка конфигурация (S,v) е изпълнено равенството φ^S,v = ψ^S,v . Не е трудно да се забележи, че така формулираното условие е равносилно със следното изискване: винаги, когато в дадена конфигурация е вярна едната от формулите φ и ψ, в тази конфигурация да бъде вярна и другата от тях. И наистина, въпросното изискване очевидно е изпълнено, когато φ е еквивалентна на ψ в смисъла на дадената дефиниция, а пък ако споменатото изискване е изпълнено, то няма как равенството φ^S,v = ψ^S,v да бъде нарушено за някоя конфигурация (S,v), защото тогава някоя от двете му страни би била 1 и значи в тази конфигурация би била вярна някоя от формулите φ и ψ, откъдето обаче би следвало, че са верни и двете. Разбира се, ако формулите φ и ψ са затворени, то в условието за тяхната еквивалентност и в разглежданото равносилно на него изискване вместо конфигурации бихме могли да използваме структури.

Пример 1. Нека φ е произволна формула. Тогава всяка от формулите φ & φ и φ ∨ φ е еквивалентна на φ.

Пример 2. За всеки две формули φ и ψ са в сила съотношенията φ & ψ ≡ ψ & φ и φ ∨ ψ ≡ ψ ∨ φ (комутативност на конюнкцията и дизюнкцията). Проверката на това твърдение е непосредствена.

Пример 3 За всеки три формули φ, ψ и θ са в сила съотношенията

(φ ∨ ψ) & θ ≡ (φ & θ) ∨ (φ & θ) , (φ & ψ) ∨ θ ≡ (φ & θ) ∨ (φ ∨ θ) (дистрибутивност на конюнкцията спрямо дизюнкцията и на дизюнкцията спрямо конюнкцията). При проверката фактически се използва, че за всеки три числа r, s и t от множеството {0,1} са в сила равенствата min{max{r,s},t} = max{min{r,t},min{s,t}} , max{min{r,s},t} = min{max{r,t},max{s,t}} .

Пример 4. Нека φ е произволна формула, а ξ и η са две различни променливи. Тогава са в сила съотношенията ∀ξ ∀η φ ≡ ∀η ∀ξ φ и ∃ξ ∃η φ ≡ ∃η ∃ξ φ. Първото от тях може да се докаже, като се използва, че винаги, когато S е някоя структура, D е нейният носител и v е оценка в S на променливите, имаме равенствата

(∀ξ ∀η φ)^S,v = min{(∀η φ)^S,v[ξ→x] | x∈D} = min{min{φ^{S,v[ξ→x][η→y]} | y∈D}| x∈D} = min{φ^{S,v[ξ→x][η→y]} | x∈D, y∈D},
(∀η ∀ξ φ)^S,v = min{(∀ξ φ)^S,v[η→y] | y∈D} = min{min{φ^{S,v[η→y][ξ→x]} | x∈D}| y∈D} = min{φ^{S,v[η→y][ξ→x]} | x∈D, y∈D}, а v[ξ→x][η→y] съвпада с v[η→y][ξ→x] при всеки избор на x и y в D. Второто от съотношенията се доказва по аналогичен начин.

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

Отношението еквивалентност има следните свойства, където φ, ψ, θ и χ са произволни формули, а ξ е произволна променлива:
а) φ ≡ φ;
б) ако φ ≡ ψ, то ψ ≡ φ;
в) ако φ ≡ ψ и ψ ≡ θ, то φ ≡ θ;
г) ако φ ≡ θ и ψ ≡ χ, то φ & ψ ≡ θ & χ и φ ∨ ψ ≡ θ ∨ χ;
д) ако φ ≡ ψ, то ¬ φ ≡ ¬ ψ, ∀ξ φ ≡ ∀ξ ψ и ∃ξ φ ≡ ∃ξ ψ;
е) ¬ (φ & ψ) ≡ ¬ φ ∨ ¬ ψ, ¬ (φ ∨ ψ) ≡ ¬ φ & ¬ ψ;
ж) ¬ ¬ φ ≡ φ, ¬ ∀ξ φ ≡ ∃ξ ¬ φ, ¬ ∃ξ φ ≡ ∀ξ ¬ φ;
з) ∀ξ φ & ∀ξ ψ ≡ ∀ξ (φ & ψ), ∃ξ φ ∨ ∃ξ ψ ≡ ∃ξ (φ ∨ ψ);
и) ако ξ не е свободна променлива на θ, то всяка от формулите ∀ξ θ и ∃ξ θ е еквивалентна на θ.;
й) ако ξ не е свободна променлива на φ, то

φ & ∀ξ ψ ≡ ∀ξ (φ & ψ), φ & ∃ξ ψ ≡ ∃ξ (φ & ψ);
φ ∨ ∀ξ ψ ≡ ∀ξ (φ ∨ ψ), φ ∨ ∃ξ ψ ≡ ∃ξ (φ ∨ ψ); к) ако ξ не е свободна променлива на ψ, то ∀ξ φ & ψ ≡ ∀ξ (φ & ψ), ∃ξ φ & ψ ≡ ∃ξ (φ & ψ);
∀ξ φ ∨ ψ ≡ ∀ξ (φ ∨ ψ), ∃ξ φ ∨ ψ ≡ ∃ξ (φ ∨ ψ). Свойствата а) – в) следват непосредствено от дефиницията за еквивалентност на формули. За проверката на останалите от горните свойства се използват още и съответните дефиниционни равенства за семантиката на формулите. Например второто равенство от свойството ж) може да се докаже, като се използва, че винаги, когато S е някоя структура, D е нейният носител и v е оценка в S на променливите, имаме равенствата (¬ ∀ξ φ)^S,v = 1 − (∀ξ φ)^S,v = 1 − min{φ^S,v[ξ→d] | d∈D} = max{1 − φ^S,v[ξ→d] | d∈D} = max{(¬ φ)^S,v[ξ→d] | d∈D} = (∃ξ ¬ φ)^S,v. В твърдението и) се убеждаваме, като забележим, че ако ξ не е свободна променлива на θ, то за всяка структура S, всяка оценка v в S на променливите и всеки елемент d на носителя на S е в сила равенството θ^S,v[ξ→d] = θ^S,v (понеже оценките v[ξ→d] и v съвпадат за свободните променливи на θ). За да докажем пък второто равенство от свойството й) при направеното там предположение за ξ и φ, използваме, че винаги, когато S е някоя структура, D е нейният носител и v е оценка в S на променливите, имаме равенствата (φ & ∃ξ ψ)^S,v = min{φ^S,v, (∃ξ ψ)^S,v} = min{φ^S,v, max{ψ^S,v[ξ→d] | d∈D}} = max{min{φ^S,v, ψ^S,v[ξ→d]}}| d∈D} = max{min{φ^S,v[ξ→d], ψ^S,v[ξ→d]}}| d∈D} = max{(φ & ψ)^S,v[ξ→d] | d∈D} = (∃ξ (φ & ψ))^S,v (във верността на третото от тези равенства можем да се убедим, като разгледаме поотделно случая, когато лявата му страна е равна на числото φ^S,v, и случая, когато тя е различна от това число).

Забележка 1. Първите и последните равенства от свойствата й) и к) могат да се получат и от свойствата ж) и и), като се използват заедно със свойствата а) – г).

Забележка 2. Свойството к) може да се получи и от свойството й), като се използва пример 2 заедно със свойствата а) – д).

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