Ако F и G са две формули, казваме, че от F следва G, и пишем  F ъ= G,  ако винаги, когато формулата F е вярна в дадена структура S при дадена оценка v в S на променливите, формулата G също е вярна в структурата S при оценката v. Т.е. приемаме, че  F ъ= G,  ако не съществуват такава структура S и такава оценка v в S на променливите, че в S при оценката v формулата F да е вярна, а формулата G да е невярна Разбира се ще пишем  F ъ№ G,  за да изразим, че от F не следва G. Лесно се съобразява, че съотношението  F ъ= G  е налице точно тогава, когато за всяка структура S и всяка оценка v в S на променливите е в сила неравенството F^S,v ≤ G^S,v. Разбира се, ако някоя от формулите F и G е затворена, нейната вярност или невярност не зависи от избора на оценката v и в казаното дотук могат да се направят съответни изменения.

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

    Пример 2. За всяка n-ка от формули F₁, F₂, ..., F_n са налице съотношенията

    Пример 3. Нека са дадени формули F₁, F₂, ..., F_n и G. Ако G ъ= F_i за i=1,2,...,n, то  G ъ= and(F₁,F₂...,F_n),  а ако F_i ъ= G за i=1,2,...,n, то  or(F₁,F₂...,F_n) ъ= G.

    Пример 4. Нека формулите F, G и H са съответно универсално затваряне, частен случай и екзистенциално затваряне на дадена безкванторна формула G₀. Тогава  F ъ= G  и  G ъ= H. За да се убедим в първото от тези две твърдения, достатъчно е да отбележим, че ако формулата F е вярна в една структура S, то в S формулата G₀ е тъждествено вярна и следователно формулата G също е тъждествено вярна в S. Във второто твърдение пък се убеждаваме, като отбележим, че ако формулата G е изпълнима в една структура S, то в S е изпълнима и формулата G₀ и следователно формулата H е вярна в S.

    Пример 5. Нека X и Y са две различни променливи, а F е произволна формула. Ще покажем, че  $X "Y F ъ= "Y $X F. Действително, нека S и v са такава структура и такава оценка в нея на променливите, че  S,v ъ= $X "Y F. Тогава съществува елемент x на носителя на S, такъв, че  S,v[X:x] ъ= "Y F и следователно  S, v[X:x][Y:y] ъ= F за всяко y от носителя на S. Тъй като обаче  v[X:x][Y:y] = v[Y:y][X:x],  това гарантира, че за всяко y от носителя на S е налице съотношението  S,v[Y:y] ъ= $X F  и значи  S,v ъ= "Y $X F.

    Пример 6. Нека X и Y да са пак две различни променливи, но F да е формулата p(X,Y), където p е двуместен предикатен символ. Тогава  "X $Y F ъ№ $Y "X F. За да се убедим в това, достатъчно е да разгледаме например такава структура S с носител D, състоящ се от поне два елемента, че интерпретацията на двуместните предикатни символи да съпоставя на p предиката, който приема стойност 1 за двойките от D² с равни членове и стойност 0 за останалите двойки от D² - при такъв избор на S затворената формула "X $Y F е вярна в S, а затворената формула $Y "X F не е вярна в S.

    От дефиницията на отношението следване веднага се вижда, че това отношение е рефлексивно, т.е  F ъ= F за всяка формула F,  и е транзитивно, т.е. винаги, когато за три формули F, G и H имаме съотношенията  F ъ= G  и  G ъ= H,  имаме и съотношението  F ъ= H.

    Ще отбележим още следното свойство, наречено закон за контрапозиция: ако за две формули F и G имаме съотношението  F ъ= G,  то то за тях е налице и съотношението  Ш G ъ= Ш F. И наистина, да предположим, че  F ъ= G  и формулата Ш G е вярна в дадена структура S при дадена оценка v в S на променливите. Тогава очевидно не е възможно формулата F да е вярна в S при оценката v, следователно формулата Ш F е вярна в дадената структура при разглежданата оценка.
 

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

Previous  Next  Contents