Svobodni i svyrzani promenlivi

СВОБОДНИ И СВЪРЗАНИ ПРОМЕНЛИВИ

    Когато една формула започва с квантор, неговата променлива играе особена роля - стойността на формулата в произволна структура при коя да е оценка на променливите не зависи от стойността на оценката за споменатата променлива. Това обстоятелство дава повод да се дефинира понятието свързана променлива на една формула. Дефиницията е индуктивна и се състои от следните точки, където x означава произволна дадена променлива:
    СВЪ1,2. Ако j е формула, то x е свързана променлива на "xj и x е свързана променлива на $xj.
    СВЪ3. Ако x е свързана променлива на дадена формула j, то x е свързана променлива и на Шj.
    СВЪ4,5. Ако x е свързана променлива на някоя от формулите j₁ и j₂, то x е свързана променлива на (j₁&j₂) и x е свързана променлива на (j₁Ъj₂).
    СВЪ6,7. Ако x е свързана променлива на дадена формула j, а h е произволна променлива, то x е свързана променлива на "hj и x е свързана променлива на $hj.

    От тази дефиниция могат да се извлекат следните заключения:
    а) атомарните формули нямат свързани променливи;
    б) ако j е формула, то една променлива е свързана променлива на Шj точно тогава, когато е свързана променлива на j;
    в) ако j₁ и j₂ са формули, а g е двувалентен логически знак, то една променлива е свързана променлива на (j₁gj₂) точно тогава, когато е свързана променлива на j₁ или е свързана променлива на j₂;
    г) ако j е формула, h е променлива и k е някой от кванторите "h и $h, то една променлива е свързана променлива на kj точно тогава, когато съвпада с h или е свързана променлива на j.

Горните твърдения позволяват да се докаже по индукция, че за всяка дадена формула множеството на нейните свързани променливи е крайно.

    Със следващата дефиниция, която ще дадем, ще въведем понятието свободна променлива, при това ще го въведем и за термове, и за формули. Дефиницията е пак индуктивна. Състои се от следните точки, където x е произволна променлива:
    СВО1. x е свободна променлива на x.
    СВО2. Ако s принадлежи на W_nИP_n, където n>0, t₁, ..., t_n са термове и x е свободна променлива на поне един от тези термове, то x е свободна променлива на s(t₁,...,t_n).
    СВО3. Ако x е свободна променлива на дадена формула j, то x е свободна променлива и на Шj.
    СВО4,5. Ако x е свободна променлива на някоя от формулите j₁ и j₂, то x е свободна променлива на (j₁&j₂) и x е свободна променлива на (j₁Ъj₂).
    СВО6,7. Ако x е свободна променлива на дадена формула j, а h е променлива, различна от x, то x е свободна променлива на "hj и x е свободна променлива на $hj.

    Винаги, когато q е терм или формула, ние ще означаваме със СВО(q) множеството на свободните променливи на q. От дадената по-горе индуктивна дефиниция се получават следните заключения:
    а) за всяка променлива x е в сила равенството СВО(x)={x};
    б) ако l принадлежи на W₀ИP₀, то СВО(l)=Ж;
    в) ако l принадлежи на W_nИP_n, където n>0, а t₁, ..., t_n са термове, то

СВО(l(t₁,...,t_n)) =

ⁿ
ою
ⁱ⁼¹

СВО(t_i);

г) за всяка формула j е в сила равенството СВО(Шj)=СВО(j);
д) за всеки две формули j₁ и j₂ са в сила равенствата СВО(j₁&j₂)=СВО(j₁Ъj₂)=СВО(j₁®j₂)=СВО(j₁«j₂)=СВО(j₁)ИСВО(j₂); е) за всяка формула j и всяка променлива h са в сила равенствата СВО("hj)=СВО($hj)=СВО(j)\{h}.

От тези твърдения следва разбира се, че за всеки терм и за всяка формула съответното множество на свободните променливи е крайно. При формулите няма никаква задължителна връзка между множеството на свързаните и множеството на свободните променливи;¹ все пак понякога ще предпочитаме да работим с такива формули, на които множеството на свободните променливи няма общи елементи с множеството на свързаните променливи.

С индукция, съобразена с дефиницията на понятието затворен терм, се показва, че затворените термове нямат свободни променливи, а с индукция, съобразена с дефиницията на понятието терм, се доказва, че всеки терм е затворен или има поне една свободна променлива. Оттук се получава, че един терм е затворен точно тогава, когато той няма свободни променливи. Същото веднага се пренася и за атомарни формули: една атомарна формула е затворена точно тогава, когато тя няма свободни променливи. Това ни дава повод за следната обща дефиниция: една формула ще наричаме затворена, ако тази формула няма свободни променливи.

Пример. Ако p е едноместен предикатен символ, а x е променлива, то формулите "xp(x) и $xp(x) са затворени, макар че при тяхното построяване е използвана променливата x (тя е тяхна свързана променлива).

В нашите разглеждания понятието свободна променлива ще играе значителна роля благодарение на следното твърдение, което ще докажем:

Лема за базисна роля на свободните променливи. Нека S е дадена структура. Тогава всеки път, когато m е терм или формула, а v и vў са две оценки, които съвпадат върху свободните променливи на m,² в сила е равенството

m^S,v=m^S,vў. Доказателство. Да положим S=(C,I). В случая, когато m е терм, използваме индукция, съобразена с дефиницията на понятието терм. Очевидно твърдението е вярно, ако m е нулместен функционален символ или променлива, а ако w е n- местен функционален символ, където n>0, и t₁, ..., t_n са термове, притежаващи доказваното свойство, то при всеки избор на оценки v и vў, съвпадащи върху свободните променливи на терма w(t₁,...,t_n), тези оценки ще съвпадат и върху свободните променливи на кой да е от термовете t₁, ..., t_n, поради което ще имаме w(t₁,...,t_n)^S,v=I(w)(t₁^S,v,...,t_n^S,v)=I(w)(t₁^S,vў,...,t_n^S,vў)=w(t₁,...,t_n)^S,vў, т.е. термът w(t₁,...,t_n) също има въпросното свойство. В случая, когато m е формула, доказателството протича с индукция, съобразена с дефиницията на понятието формула. Ако m е нулместен предикатен символ, верността на твърдението е очевидна, а за по-сложните атомарни формули проверката е чрез разсъждения, аналогични на горните. Ако твърдението е вярно за дадена формула j, а v и vў са оценки, съвпадащи за свободните променливи на формулата Шj, то v и vў разбира се съвпадат за свободните променливи на j и следователно (Шj)^S,v=1-j^S,v=1-j^S,vў=(Шj)^S,vў, т.е. формулата Шj също има доказваното свойство. Ако дадени формули j₁ и j₂ имат въпросното свойство, а v и vў са оценки, съвпадащи за свободните променливи на формулата (j₁&j₂), то v и vў ще съвпадат както за свободните променливи на j₁, така и за свободните променливи на j₂, следователно (j₁&j₂)^S,v=min{j₁^S,v,j₂^S,v}=min{j₁^S,vў,j₂^S,vў}=(j₁&j₂)^S,vў и значи формулата (j₁&j₂) също има нужното свойство. По съвсем подобен начин се доказва и запазването на свойството при образуване на дизюнкция. Сега ще покажем, че то се запазва и при поставяне на квантор за общност. Нека j е формула, която притежава разглежданото свойство, x е променлива, а v и vў са оценки, които съвпадат върху свободните променливи на формулата "xj. Тогава за всеки елемент c на C оценките

съвпадат върху свободните променливи на формулата j, защото коя да е свободна променлива на j съвпада с x или е свободна променлива на "xj. Оттук виждаме, че

("xj)^S,v=min

=min

=("xj)^S,vў, т.е. формулата "xj също има доказваното свойство. Запазването на свойството при поставяне на квантор за съществуване се доказва съвсем аналогично.

Следствие. Ако m е затворен терм или затворена формула, то m^S,v=m^S,vў за всеки две оценки v и vў в S на променливите.

Горното следствие показва, че когато m е затворен терм или затворена формула, стойността m^S,v не зависи от избора на оценката v в S на променливите. В случая, когато m е затворен терм, това следва и от известното ни равенство m^S,v=m^S, което е налице в този случай. Вземайки повод от верността на това равенство за произволен затворен терм m, осигуряваме неговата вярност и в случая, когато m е затворена формула, като се уславяме независещата от избора на v стойност m^S,v да означаваме с m^S; тази независеща от избора на v стойност ще наричаме стойност на m в S. Ако m е затворена формула, то при m^S=1 ще казваме, че m е вярна в S, а при m^S=0 ще казваме, че m е невярна в S. Очевидно верността на една затворена формула в S е равносилна с нейната тъждествена вярност в S. Поради това факта, че дадена затворена формула m е вярна в S, можем да запишем, като пишем Sj; разбира се отрицанието на този факт, т.е. неверността на j в S, можем да запишем, като пишем Sj.

За произволна формула j, на която свободните променливи са x₁, x₂, ..., x_n, формулата "x₁"x₂..."x_nj очевидно е затворена (затворена формула от този вид ще наричаме затваряне на j). Следствието от лемата за запазване на тъждествената вярност при поставяне или премахване на квантор за общност показва, че споменатата затворена формула е вярна в дадена структура точно тогава, когато формулата j е тъждествено вярна в същата структура.

Бележки

¹ Лесно може да се види, че ако P_n№Ж поне за едно n, различно от 0, то съществува формула, на която множеството на свързаните променливи и множеството на свободните променливи са произволни отнапред избрани крайни множества от променливи.

² Последното условие се счита изпълнено и в случая, когато m няма свободни променливи.

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

Previous Next Contents