Previous  Next  Contents
 

 

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

      Нека F и G са формули. Ще казваме, че F е еквивалентна на G (или че F и G са еквивалентни), и ще пишем  F ≡ G,  ако от F следва G и от G следва F.  От характеризацията на следването чрез неравенство между стойностите на формулите е ясно, че F е еквивалентна на G точно тогава, когато за всяка конфигурация (S,v) е изпълнено равенството  FS,v = GS,v  (ако формулите F и G са затворени, конфигурациите могат да бъдат заменени със структури).

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

      Пример 2. При всеки избор на положително цяло число n и на формули F1, …, Fn, Fn+1 са в сила съотношенията

F1 & … & Fn & Fn+1 ≡ (F1 & … & Fn) & Fn+1,
F1 ∨ … ∨ Fn ∨ Fn+1 ≡ (F1 ∨ … ∨ Fn) ∨ Fn+1.

      Пример 3. Нека F е произволна формула, а ξ е променлива, която не е свободна променлива на F.  Тогава всяка от формулите  ∀ξ F  и  ∃ξ F  е еквивалентна на F.  В това се убеждаваме, като забележим, че за всяка структура S, всяка оценка v в S на променливите и всеки елемент d на носителя на S е в сила равенството

FS,v[ξ→d] = FS,v
(понеже оценките v[ξ→d] и v съвпадат за свободните променливи на F).

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

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

      Пример 5. Ако F е формула от вида π(ξ,η), където π е двуместен предикатен символ, а ξ и η са две различни променливи, то формулите  ∀ξ ∃η F  и  ∃η ∀ξ F  не са еквивалентни. Това е ясно от пример 6 във връзка със следване на една формула от друга.

      Отношението еквивалентност има следните свойства, където  F, F1, …, Fn, G, G1, …, Gn, H  са произволни формули, а ξ е произволна променлива:
        а)  F ≡ F;
        б)  ако  F ≡ G,  то  G ≡ F;
        в)  ако  F ≡ G  и  G ≡ H,  то  F ≡ H;
        г)  ако  F1 ≡ G1, …, Fn ≡ Gn,  то  F1 & … & Fn ≡ G1 & … & Gn  и  F1 ∨ … ∨ Fn ≡ G1 ∨ … ∨ Gn;
        д)  ако  F ≡ G,  то  ¬ F ≡ ¬ G,  ∀ξ F ≡ ∀ξ G  и  ∃ξ F ≡ ∃ξ G;
        е)  ¬ true ≡ fail;
        ж)  ¬ fail ≡ true;
        з)  ¬ (F1 & … & Fn) ≡ ¬ F1 ∨ … ∨ ¬ Fn;
        и)  ¬ (F1 ∨ … ∨ Fn) ≡ ¬ F1 & … & ¬ Fn;
        й)  ¬ ¬ F ≡ F;
        к)  ¬ ∀ξ F ≡ ∃ξ ¬ F;
        л)  ¬ ∃ξ F ≡ ∀ξ ¬ F.

      Едно от тези свойства, а именно свойството б), следва съвсем непосредствено от дефиницията за еквивалентност на формули. Останалите измежду свойствата а) - д) могат да бъдат установени, като се използват свойства на отношението следване, посочени в предходния въпрос. Кое да е от свойствата е) - л) пък може да се докаже например чрез установяване на равенство между стойностите, които имат в произволна конфигурация лявата и дясната страна на еквивалентността от свойството. Да речем свойството к) може да се докаже, като се използва, че винаги, когато S е някоя структура, D е нейният носител и v е оценка в S на променливите, имаме равенствата

(¬ ∀ξ F)S,v = 1 − (∀ξ F)S,v = 1 − min{FS,v[ξ→d]|d∈D} = max{1 − FS,v[ξ→d]|d∈D} = max{(¬ F)S,v[ξ→d]|d∈D} = (∃ξ ¬ F)S,v.

Последно изменение: 19.04.2004 г.
 
 Previous  Next  Contents