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

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

И тук ще предполагаме, че е дадена една сигнатура, като под формули и под структури ще разбираме съответно формули в тази сигнатура и структури с тази сигнатура. Нека Γ е едно множество от формули. За една формула φ ще казваме, че следва от Γ, ако винаги, когато всички формули от Γ са верни в дадена структура 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 е двуместен предикатен символ на дадената сигнатура, то имаме съотношенията ∀y p(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. Ако θ⊨φ, то ∀ξθ⊨∀ξφ и ∃ξθ⊨∃ξφ при всеки избор на променливата ξ (монотонност на генерализацията и на екзистенциализацията).

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

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