ПРИЛАГАНЕ НА СУБСТИТУЦИИ КЪМ ПРОИЗВОЛНИ ФОРМУЛИ
(синтактични въпроси)

    Ако s е субституция, j е формула и x е променлива, ще казваме, че s привнася x във j, ако j има такава свободна променлива h, различна от x, че x е свободна променлива на терма s(h) (например, ако p е двуместен предикатен символ, а x и y са различни променливи, то субституцията (y:=x) привнася x в атомарната формула p(x,y), a субституцията (x:=f(x,x)), където f е двуместен функционален символ, не привнася x в споменатата атомарна формула). Явлението колизия на променливите, за което стана дума в предходния въпрос, в определен смисъл се дължи на неподходящо привнасяне на променлива.

    Ако s е субституция, а x е променлива, то ще означаваме с s_x онази субституция, която преобразува x в x, а на всяка друга променлива съпоставя същия терм, който й съпоставя субституцията s (например, ако x и y са две различни променливи, то (x,y:=y,x)_x е субституцията (y:=x)). Преминаването от s към s_x ще ни послужи в случаи, когато искаме да избегнем заместване на променливата x с някой друг терм.

    Сега ще дадем индуктивната дефиниция кога една формула ще считаме резултат от прилагане на дадена субституция към дадена формула, като, както и в предходния въпрос, ще използваме вече дефинирания смисъл на означението s(a) в случай, че s е субституция, а a е атомарна формула. Дефиницията се състои от следните точки:
          РПФ1. Ако a е атомарна формула, то s(a) е резултат от прилагане на s към a.
          РПФ2. Ако jў е резултат от прилагане на s към j, то Шjў е резултат от прилагане на s към Шj.
          РПФ3,4. Ако jў и yў са резултати от прилагане на s съответно към j и y, то jў&yў и jўЪyў са резултати от прилагане на s съответно към j&y и jЪy.
          РПФ5,6. Ако x е променлива, субституцията s не привнася x във j и jў е резултат от прилагане на субституцията s_x към j, то "xjў и $xjў са резултати от прилагане на s съответно към "xj и $xj.

    С помощта на индукция, съобразена с дефиницията за формула, лесно се вижда, че за всяка дадена формула j и субституция s съществува най-много една формула, която е резултат от прилагане на s към j. Чрез индукция, съобразена с дефиницията за безкванторна формула се вижда, че когато j е безкванторна формула, за всяка субституция s дефинираният по-рано резултат s(j) от прилагане на s към j е резултат от прилагане на s към j и в смисъл на горната нова дефиниция. Това ни дава основание и при наличие на квантори във j да означаваме със s(j) резултата от прилагане на s към j винаги, когато той съществува в смисъл на новата дефиниция. Уславяме се също в случаите, когато въпросният резултат съществува, да казваме, че s е приложцма към j.

    Да отбележим, че случаи на неприложимост на субституция към формула има - например, ако p е двуместен предикатен символ, а x и y са различни променливи, то субституцията (y:=x) не е приложима към формулата "xp(x,y). По този повод отбелязваме изрично, че към безкванторна формула е приложима всяка субституция и че от дадените дефиниции произтичат следните необходими и достатъчни условия за приложимост на една субституция s: а) тя е приложима към отрицанието на дадена формула точно тогава, когато е приложима към самата формула; б) s е приложима към конюнкцията на две формули точно тогава, когато е приложима към всяка от двете формули; в) аналогично на предното, но за дизюнкция; г) s е приложима към "xj, където x е променлива и j е формула, точно тогава, когато s не привнася x във j, а субституцията s_x е приложима към j; д) аналогично на предното, но за формулата $xj. Ще отбележим още, че следните равенства ще бъдат верни за произволна субституция s и произволни формули j и y в смисъл, че когато едната от двете страни на равенството има смисъл, другата също има и двете страни означават една и съща формула:

    Сега ще докажем едно твърдение, което посочва широк кръг от случаи на приложимост.

    Твърдение 1. Ако j е произволна формула, то всяка субституция, непривнасяща във j нейни свързани променливи, е приложима към j.

    Доказателство. Ще използваме индукция, съобразена с дефиницията за формула. Да наречем временно една формула j нормална, ако тя има изказаното свойство, т.е. всяка субституция, непривнасяща във j нейни свързани променливи, е приложима към j. Атомарните формули разбира се са нормални, тъй че остава да покажем, че нормалността се запазва при образуване на отрицание, конюнкция и дизюнкция и при поставяне на квантор. Да предположим, че j е нормална формула. Ще покажем, че и формулата Шj е нормална. За целта да разгледаме произволна субституция s, която не привнася в Шj нейни свързани променливи. Благодарение на равенствата СВО(Шj)=СВО(j) и СВЪ(Шj)=СВЪ(j) може да се твърди, че s не привнася и във j нейни свързани променливи. Оттук получаваме, че s е приложима към j, а следователно и към Шj. По подобен, макар и леко по-сложен начин се вижда, че конюнкцията и дизюнкцията на две нормални формули също са нормални. Преминаваме към въпроса за запазване на нормалността при поставяне на квантор. Нека j пак е нормална формула. Трябва да покажем, че формулите "xj и $xj, където x е произволна променлива, също са нормални. Ще се занимаем с първата от тези две формули, а за втората нещата са съвсем аналогични. Нека s е субституция, която не привнася в "xj нейни свързани променливи. Ще покажем, че s е приложима към "xj. Първо ще покажем, че s не привнася x във формулата j. Да допуснем противното. Тогава j ще има такава свободна променлива h, различна от x, че x е свободна променлива на терма s(h). При това положение обаче h ще бъде свободна променлива и на формулата "xj, поради което се получава, че, противно на направеното предположение за s, тя  привнася в последната формула нейната свързана променлива x. Остава да покажем, че субституцията s_x е приложима към j. За тази цел е достатъчно да покажем, че s_x не привнася във j никоя нейна свързана променлива. Да допуснем противното. Тогава j ще има такава свободна променлива h, че съответният й терм s_x(h) да има свободна променлива, различна от h, която същевременно е свързана променлива на j. Тъй като s_x(x)=x, оттук е ясно, че h№x, следователно h е свободна променлива и на формулата "xj и е в сила равенството s_x(h)=s(h). Тъй като свързаните променливи на j са свързани променливи и на формулата "xj, отново получаваме, че s привнася в последната формула нейна свързана променлива, противно на направеното предположение за s.

    Следствие 1. Нека j е произволна формула. Ако s е такава субституция, че за всяка свободна променлива h на j съответният терм s(h) е затворен, то s е приложима към j.

    Забележка 1. Лесно се проверява, че изискването една субституция s да не привнася в дадена формула j нейни свързани променливи е равносилно с това, щото за всяка свободна променлива h на j да бъде изпълнено условието СВО(s(h))ЗСВЪ(j)Н{h}.

    Забележка 2. Условието от твърдение 1 за непривнасяне във j на нейни свързани променливи е само достатъчно за приложимостта на една субституция към j, но то не е необходимо. Например, ако p е едноместен предикатен символ, а x и y са различни променливи, то субституцията (x:=y) е приложима към формулата p(x)&$yШp(y), въпреки че привнася в нея  свързаната й променлива y.

    Ще докажем и няколко твърдения, в които става дума и за самите резултати от прилагане на субституции към произволни формули.

    Твърдение 2. За всяка формула j субституцията (:=) е приложима към j и е в сила равенството (:=)(j)=j.

    Доказателство. Приложимостта на въпросната субституция към произволна формула е ясна от твърдение 1. Ние обаче ще докажем споменатата приложимост директно и едновременно с формулираното равенство, като за произволна формула j установим индуктивно, че j е резултат от прилагане на (:=) към j. За случая, когато j е атомарна формула, този факт е вече известен, а индуктивните стъпки, отнасящи се до образуване на отрицание, на конюнкция и на дизюнкция, са съвсем прости. Затова да преминем веднага към случая на поставяне на квантор. Нека за дадена формула j е известно, че j е резултат от прилагане на (:=) към j, и нека x е някоя променлива. Трябва да покажем, че "xj е резултат от прилагане на (:=) към "xj и $xj е резултат от прилагане на (:=) към $xj. Това обаче е ясно от обстоятелството, че (:=) очевидно не привнася x във j, а от друга страна субституцията (:=)_x съвпада със субституцията (:=), тъй че j е резултат от прилагане и на (:=)_x към j.

    Твърдение 3. Нека j е произволна формула. Тогава за всяка субституция s, приложима към j, са изпълнени равенствата

    Следствие 2. Ако j е формула, а s е такава субституция, че за всяка свободна променлива h на j съответният терм s(h) е затворен, то формулата s(j) е затворена.

    Твърдение 4. Нека j е произволна формула. Ако две субституции съвпадат върху множеството на свободните променливи на j и едната от двете субституции е приложима към j, то другата също е приложима и резултатите от прилагането на двете субституции към j са едни и същи.

    Доказателство. Отново използваме индукция, съобразена с дефиницията за формула. Единствената стъпка, чието извършване изисква известно усилие, е доказателството, че свойството се запазва при поставяне на квантор. Нека j е формула, която има разглежданото свойство, и нека x е дадена променлива. Трябва да покажем, че формулите "xj и $xj също имат това свойство. Ще се ограничим с първата от тях. Да предположим, че две субституции s и sў съвпадат върху множеството на свободните променливи на формулата "xj и субституцията s е приложима към тази формула. Целта ни ще бъде да се убедим, че тогава и субституцията sў е приложима към въпросната формула и е в сила равенството s("xj)=sў("xj). От направените предположения се получава, че субституцията s_x е приложима към формулата j и имаме равенството

    Следствие 3 (от горното твърдение и от твърдение 2). Ако една формула j е затворена, а s е произволна субституция, то s е приложима към j и е изпълнено равенството s(j)=j.

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