Следване на формула от множество от формули

СЛЕДВАНЕ НА ФОРМУЛА ОТ МНОЖЕСТВО ОТ ФОРМУЛИ

И тук ще предполагаме, че е дадена една сигнатура, като под формули и под структури ще разбираме съответно формули при тази сигнатура и структури с тази сигнатура. Нека Γ е едно множество от формули. За една формула φ ще казваме, че следва от Γ, ако винаги, когато всички формули от Γ са верни в дадена структура S при дадена оценка v в S на променливите, формулата φ също е вярна в S при оценката v. Твърдението, че φ следва от Γ, ще записваме така: Γ⊨φ.

Пример 1. Ако φ и ψ са произволни формули, то формулата φ следва от множеството {φ∨ψ,¬ψ}. И наистина, ако формулите φ∨ψ и ¬ψ са верни в дадена структура S при дадена оценка v в S, то някоя от формулите φ и ψ е вярна в S при оценката v, като същевременно ψ не е вярна в S при оценката v, следователно φ е вярна в S при оценката v.

Пример 2. Ако φ и ψ са произволни формули, а ξ е произволна променлива, то формулата ∃ξφ следва от множеството {∀ξ(φ∨ψ),∃ξ¬ψ}. И наистина, да предположим, че двете формули от въпросното множество са верни в дадена структура S при дадена оценка v в S. Верността на втората от тези формули в S при оценката v позволява да се избере такъв елемент d от носителя на S, че формулата ¬ψ да е вярна в S при оценката v[ξ→d]. Понеже и първата формула от множеството е вярна в S при оценката v, формулата φ∨ψ също е вярна в S при оценката v[ξ→d], а оттук по установеното в предходния пример следване на φ от множеството {φ∨ψ,¬ψ} заключаваме, че φ е вярна в S при оценката v[ξ→d]. Следователно ∃ξφ е вярна в S при оценката v. По аналогичен начин може да се докаже, че формулата ∃ξφ следва и от множеството {∃ξ(φ∨ψ),∀ξ¬ψ}.

Забележка 1. В специалния случай, когато Γ е множество от затворени формули, следването от Γ на една формула φ е равносилно с това φ да бъде тъждествено вярна във всеки модел на Γ, който е с дадената сигнатура (ако освен формулите от Γ още и φ е затворена, то вместо думите „тъждествено вярна“ ще можем да използваме думата „вярна“).

Една формула φ следва от дадено множество от формули Γ точно тогава, когато множеството Γ∪{¬φ} е неизпълнимо. Това е така, защото както следването на φ от Γ, така и неизпълнимостта на Γ∪{¬φ} са равносилни с изискването да не съществуват такава структура S и такава оценка v в S, че всички формули от Γ да са верни в S при оценката v, а φ да не е вярна в S при оценката v.

За две формули θ и φ ще казваме, че φ следва от θ, и ще пишем θ⊨φ, ако φ следва от едноелементното множество с единствен елемент θ. Ясно е, че условието φ да следва от θ е равносилно с изискването винаги, когато формулата θ е вярна в дадена структура S при дадена оценка v в S на променливите, формулата φ също да е вярна в S при оценката v.

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

φ&ψ⊨φ, φ&ψ⊨ψ, φ⊨φ∨ψ, ψ⊨φ∨ψ. .
Пример 4. За всеки три формули θ, φ и ψ, ако θ⊨φ и θ⊨ψ, то θ⊨φ&ψ, а ако φ⊨θ и ψ⊨θ, то φ∨ψ⊨θ.

Пример 5. За всяка формула φ и всяка променлива ξ имаме съотношенията ∀ξφ⊨φ и φ⊨∃ξφ. Това е така благодарение на обстоятелството, че за всяка структура S и всяка оценка v в нея имаме равенството v=v[ξ→v(ξ)], от което получаваме, че φ^S,v=φ^{S,v[ξ→v(ξ)]}.

Пример 6. Ако p е двуместен предикатен символ на дадената сигнатура, то имаме съотношенията ∀yp(x,y) ⊨ p(x,x) и p(x,x)⊨ ∃y p(x,y). Това е така благодарение на обстоятелството, че за всяка структура S и всяка оценка v в нея имаме равенството

p(x,x)^S,v = p^S(v(x),v(x)) = p(x,y)^{S,v[y→v(x)]}.
Пример 7. Нека φ и ψ са такива формули, че φ⊨ψ, и нека ξ е променлива. Тогава: (a) ако ξ не е свободна променлива на φ, то φ⊨∀ξψ; (b) ако ξ не е свободна променлива на ψ, то ∃ξφ⊨ψ. И наистина, нека S е коя да е структура, а v е оценка в S. За доказателството на твърдението (a) да предположим, че ξ не е свободна променлива на φ и формулата φ е вярна в S при оценката v. Нека d е произволен елемент на носителя на S. Формулата φ ще бъде вярна в S и при оценката v[ξ→d], тъй като v[ξ→d] съвпада с v върху множеството на свободните променливи на φ. Оттук получаваме, че формулата ψ също ще бъде вярна в S при оценката v[ξ→d], а поради произволността на d това показва, че формулата ∀ξψ е вярна в S при оценката v. За доказателството на твърдението (b) да предположим, че ξ не е свободна променлива на ψ и формулата ∃ξφ е вярна в S при оценката v. Тогава при някой избор на елемент d на носителя на S формулата φ ще бъде вярна в S при оценката v[ξ→d]. При такъв избор на d формулата ψ също ще бъде вярна в S при оценката v[ξ→d]. Тъй като v[ξ→d] съвпада с v върху множеството на свободните променливи на ψ, формулата ψ ще бъде вярна в S и при оценката v.

Забележка 2. Твърденията от примери 5 и 6 са частни случаи от общо твърдение, което ще формулираме и докажем по-нататък (формулировката му ще използва понятието за прилагане на субституция към формула).

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

Можем да отбележим още очевидния факт, че от неизпълнима формула следва всяка формула, а тъждествено вярна формула следва от всяка.

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