Zakoni za kvantori v sekventsii

ЗАКОНИ ЗА КВАНТОРИ В СЕКВЕНЦИИ

За случая на кванторите за общност и за съществуване ще докажем някои твърдения, близки по дух до законите за отрицание, конюнкция, дизюнкция и импликация в предпоставката или в заключението на една секвенция. За разлика от по-раншните, някои от новите твърдения ще дават само достатъчни условия за вярност, а не необходими и достатъчни. В тези случаи ще наричаме твърденията закони за въвеждане на квантори, а когато са налице необходими и достатъчни условия, ще пропускаме думите "въвеждане на".

Закон за въвеждане на квантор за общност в предпоставката. Нека G и D са крайни множества от формули, x е променлива, j е формула, а t е такъв терм, че субституцията (x:=t) е приложима към j. Тогава, ако секвенцията

GИ{(x:=t)(j)}-:D е вярна в дадена конфигурация, то и секвенцията GИ{"xj}-:D е вярна в тази конфигурация.

Доказателство. Знаем, че формулата (x:=t)(j) следва от формулата "xj. Да предположим сега, че секвенцията GИ{(x:=t)(j)}-:D е вярна в дадена конфигурация (S,v), и да допуснем, че секвенцията GИ{"xj}-:D не е вярна в (S,v). Тогава всички формули от множеството GИ{"xj} ще бъдат верни в (S,v), а всички формули от множеството D ще бъдат неверни в (S,v). Като използваме отбелязаното преди малко следване, оттук получаваме, че всички формули от множеството GИ{(x:=t)(j)} са верни в конфигурацията (S,v), а всички формули от множеството D са неверни в нея. Това обаче противоречи на верността на секвенцията GИ{(x:=t)(j)}-:D в (S,v).

Закон за квантор за общност в предпоставката. Нека G и D са крайни множества от формули, x е променлива, j е формула, а t е такъв терм, че субституцията (x:=t) е приложима към j. Тогава, за да бъде секвенцията

GИ{"xj}-:D вярна в дадена конфигурация, необходимо и достатъчно е в тази конфигурация да бъде вярна секвенцията GИ{"xj,(x:=t)(j)}-:D. Доказателство. Нека (S,v) е произволна конфигурация. Ако първата от горните две секвенции е вярна в (S,v), то и втората е вярна в (S,v), защото е разширение на първата. Заключението в обратната посока правим, като разсъждаваме директно или приложим закона за въвеждане на квантор за общност в предпоставката, вземайки GИ{"xj} в качеството на G.

Разбира се, всяко от горните две твърдения остава в сила, ако вместо вярност на секвенциите в дадена конфигурация се разглежда тяхната тъждествена вярност в дадена структура. В твърдението, което сега ще изкажем, направо ще става дума за тъждествена вярност в дадена структура. За по-удобното изказване на това и на някои други твърдения се уславяме да казваме за една променлива h, че е свободна променлива на дадена секвенция, ако h е свободна променлива на някоя формула, принадлежаща на предпоставката или на заключението на секвенцията; по аналогичен начин, макар засега това не ни е нужно, дефинираме кога една променлива е свързана променлива на дадена секвенция.

Закон за квантор за общност в заключението. Нека G и D са крайни множества от формули, x е променлива, j е формула, а h е такава променлива, че субституцията (x:=h) е приложима към j. Нека освен това h не е свободна променлива на секвенцията

G-:DИ{"xj}. В такъв случай, за да бъде гореспоменатата секвенция тъждествено вярна в дадена структура, необходимо и достатъчно е в тази структура да бъде тъждествено вярна секвенцията G-:DИ{(x:=h)(j)}. Доказателство. Нека S=(C,I) е дадена структура. Като използваме, че формулата (x:=h)(j) следва от формулата "xj, веднага виждаме, че ако първата от горните две секвенции е тъждествено вярна в S, то и втората е тъждествено вярна в S.¹ Да предположим сега, че втората от двете секвенции е тъждествено вярна в S. Ще докажем, че и първата е тъждествено вярна в S. За целта да допуснем, че при някоя оценка v в S на променливите всички формули от G са верни в конфигурацията (S,v), а всички формули от DИ{"xj} са неверни в същата конфигурация. Тогава ще има такъв елемент c на C, че формулата j да бъде невярна в S при оценката

. Да означим с vў h,c-модификацията на оценката v. Ще покажем, че формулата (x:=h)(j) е невярна в конфигурацията (S,vў). Това разбира се е очевидно при съвпадане на променливите x и h, а ако тези променливи са различни, използваме, че имаме равенствата (x:=h)(j)^S,vў=j^{(x:=h)(S,vў)}=j^S,vІ, където vІ(x)=vў(h)=c и vІ съвпада с vў за променливите, различни от x, тъй че vІ съвпада с

за променливите, различни от h, която пък в този случай не есвободна променлива на j. Понеже vў може да се отличава от v само за променливата h, която не е свободна променлива на никоя формула от G и на никоя формула от D, получаваме още, че всички формули от G са верни в конфигурацията (S,vў), а всички формули от D са неверни в тази конфигурация. Това заедно с установената невярност на формулата (x:=h)(j) в същата конфигурация противоречи на предположената тъждествена вярност в S на втората от дадените секвенции.

Законите, отнасящи се до квантор за съществуване, са аналогични на горните, като обаче се отличават от тях по това, че се разменят ролите в тях на предпоставката и заключението. Само ще формулираме тези закони, защото доказателствата им са аналогични на изложените по-горе.

Закон за въвеждане на квантор за съществуване в заключението. Нека G и D са крайни множества от формули, x е променлива, j е формула, а t е такъв терм, че субституцията (x:=t) е приложима към j. Тогава, ако секвенцията

G-:DИ{(x:=t)(j)} е вярна в дадена конфигурация, то и секвенцията G-:DИ{$xj} е вярна в тази конфигурация.

Закон за квантор за съществуване в заключението. Нека G и D са крайни множества от формули, x е променлива, j е формула, а t е такъв терм, че субституцията (x:=t) е приложима към j. Тогава, за да бъде секвенцията

G-:DИ{$xj} вярна в дадена конфигурация, необходимо и достатъчно е в тази конфигурация да бъде вярна секвенцията G-:DИ{$xj,(x:=t)(j)}.

Закон за квантор за съществуване в предпоставката. Нека G и D са крайни множества от формули, x е променлива, j е формула, а h е такава променлива, че субституцията (x:=h) е приложима към j. Нека освен това h не е свободна променлива на секвенцията

GИ{$xj}-:D. В такъв случай, за да бъде гореспоменатата секвенция тъждествено вярна в дадена структура, необходимо и достатъчно е в тази структура да бъде тъждествено вярна секвенцията GИ{(x:=h)(j)}-:D.

Навсякъде в отбелязаните тук закони за квантори в секвенции би могло вместо за вярност в конфигурация или за тъждествена вярност в структура да се говори просто за тъждествена вярност. Поради това въпросните закони и споменатите в началото други закони, отнасящи се до съждителни операции в секвенции, могат да служат за установяване на тъждествена вярност на някои секвенции (разбира се за целта бихме могли да използваме и изучените преди това други методи, като заменим интересуващите ни секвенции с еквивалентни на тях формули).

Бележка

¹ Виждаме даже, че ако първата от двете секвенции е вярна в S при дадена оценка на променливите, то втората е вярна в S при същата оценка на променливите; при това в тази част от разсъжденията не се използва предположението h да не е свободна променлива на първата секвенция.

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

Previous Next Contents