УНИВЕРСАЛНИ ФОРМУЛИ. МЕТОД НА ЕРБРАН ЗА ИЗСЛЕДВАНЕ ЗА ИЗПЪЛНИМОСТ

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

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

    За да бъде една универсална формула тъждествено вярна в дадена структура S, необходимо и достатъчно е безкванторната част на формулата да бъде тъждествено вярна в S. Поради това едно множество M от универсални формули е силно изпълнимо точно тогава, когато е силно изпълнимо множеството на безкванторните части на формулите от M (нещо повече, двете множества имат едни и същи модели). В частност, ако M е множество от затворени универсални формули, то е налице равносилност между изпълнимост на M и силна изпълнимост на множеството на безкванторните части на формулите от M. Засега ще оставим настрана въпроса как да изследваме дали е изпълнимо произволно множество от универсални формули и ще се ограничим с изследване в това отношение на множества от затворени универсални формули. Това е равносилно с изследване за силна изпълнимост на множества от безкванторни формули (а значи и с изследване за силна изпълнимост на произволни множества от универсални формули). Ще изложим един метод на Ербран за споменатия вид изследване.

    Да наречем конкретизации на една затворена универсална формула затворените частни случаи на нейната безкванторна част. Методът на Ербран може да бъде описан чрез следното твърдение:

    Необходимо и достатъчно условие за изпълнимост на множество от затворени универсални формули. Ако съществува поне един нулместен функционален символ, то за да бъде изпълнимо едно множество M от затворени универсални формули, необходимо и достатъчно е да е изпълнимо множеството на всички техни конкретизации, при това в този случай съществува и Ербранова структура, която е модел на M.

    Доказателство. Нека съществува поне един нулместен функционален символ и нека е дадено едно множество M от затворени универсални формули. Да означим с K множеството на всички конкретизации на формулите от M. Ако множеството M е изпълнимо и дадена структура S е модел на M, то безкванторните части на формулите от M ще бъдат тъждествено верни в S и следователно формулите от K, бидейки затворени частни случаи на такива безкванторни части, ще бъдат верни в S, т.е. S ще бъде модел и на множеството K. Значи ако M е изпълнимо, то и K е изпълнимо. Да предположим сега, че множеството K е изпълнимо. Тъй като K е множество от затворени безкванторни формули, лемата за Ербранова изпълнимост на множество от безкванторни формули позволява да заключим, че съществува Ербранова структура S, която е модел на K. Ако j е безкванторната част на произволна формула от M, то всички затворени частни случаи на j ще принадлежат на K и значи ще бъдат верни в S, следователно j ще бъде тъждествено вярна в S (използваме следствието от достатъчното условие за тъждествена вярност при вярност на затворените частни случаи). И така, безкванторните части на всички формули от M се оказват тъждествено верни в S, а това показва, че всички формули от M са верни в S, т.е. Ербрановата структура S е модел на M и значи M е изпълнимо.

    Забележка 2. Съществуването на нулместен функционален символ не ни гарантира в общия случай, че ако множеството K на конкретизациите на формулите от M е изпълнимо, то всеки модел на K е модел и на M. В това можем да се убедим, като забележим, че ако при условията на пример 2 от предходния въпрос положим M={"xp(x)}, то K ще бъде едноелементното множество {p(w)} и разгледаната в примера структура S ще е модел на K без да е модел на M.

    Сега ще разгледаме някои примери за приложение на току-що доказаната теорема.

    Пример 1 (задачата за бръснаря). Може ли да съществува бръснар, който бръсне точно онези мъже, които не се бръснат сами (има се пред вид някое дадено множество от мъже, на което да принадлежи и самият бръснар)? Добре е известно разсъждението, което показва, че такъв бръснар не би могъл да съществува, тъй като в противен случай би се получило противоречие по въпроса дали той да бръсне или да не бръсне себе си. Сега ще видим как може да се приложи горната теорема при тази задача. За целта записваме изискването на задачата в език на предикатното смятане с един нулместен функционален символ b и един двуместен предикатен символ s, като интуитивно тълкуваме b като означение на въпросния бръснар, а s(x,y) - като "x бръсне y". По този начин поставеният въпрос се представя като въпрос за изпълнимост на формулата

    Пример 2. Може ли да съществуват двама бръснари, такива, че всеки от тях да бръсне точно онези мъже, които не ги бръсне другият и не се бръснат сами (има се пред вид дадено множество от мъже, на което да принадлежат и двамата бръснари)? За да запишем изискването на задачата със средствата на предикатното смятане, ще използваме език с два нулместни функционални символа b₁ и b₂ (знаци за "първи бръснар" и "втори бръснар") и двуместен предикатен символ s със същото тълкуване както в предходния пример. Въпросът тогава се представя като въпрос за изпълнимост на множеството M от двете универсални формули

    Пример 3. В теорията на частично наредените множества е известно едно просто разсъждение, дадено от Алфред Тарски (Alfred Tarski), което показва, че ако f е монотонно растящо изображение на дадено частично наредено множество C в себе си и даден елемент a на C е най-малко решение на неравенството xіf(x), то е в сила равенството a=f(a) (пропускаме точните дефиниции на използваните понятия). Разсъждението е следното: от неравенството aіf(a) и монотонността на f се получава неравенството f(a)іf(f(a)), което показва, че f(a) е решение на неравенството xіf(x); оттук и от минималността на a следва неравенството f(a)іa, а то заедно с наличното неравенство в обратната посока показва, че наистина a=f(a). Ще видим как този резултат (за простота без най-последната стъпка - преминаването от двете противоположни неравенства към равенство) би могъл да бъде получен по метода на Ербран. Ще използваме език на предикатното смятане с един нулместен функционален символ a, един едноместем функционален символ f и един двуместен предикатен символ і, като ще пишем tіtў вместо і(t,tў). Целта ни ще бъде да покажем, че винаги, когато в една структура са верни формулите "x"y(xіy®f(x)іf(y)) и "x(xіf(x)®xіa), където x и y са различни променливи, и е вярна формулата aіf(a), в тази структура е вярна и формулата f(a)іa. Това ще постигнем, като покажем, че не е изпълнимо множеството M от формулите

    Пример 3ў. В пример 3 ние за простота избягнахме най-последната стъпка от разсъждението на Тарски, в която от две неравенства в противоположни посоки се получава равенство. Не би било сложно и тя да се вземе пред вид. За да направим това, би трябвало използваният език на предикатното смятане да има още един двуместен предикатен символ =, и, пишейки t=tў вместо =(t,tў), към множеството M да добавим още формулата "x(xіy&yіx®x=y), а формулата Ш(f(a)іa) да заменим с формулата Ш(а=f(a)). Това ще доведе до добавяне към множеството K на всички формули от вида tіtў&tўіt®t=tў, където t и tў са затворени термове, и до същата замяна както в M. Отново допускаме, че дадена структура S е модел на K. Тогава формулата а=f(a) трябва да е невярна в S и затова (с оглед да достигнем до противоречие) е добре да потърсим сред формулите от K някоя импликация със заключение а=f(a). Такава е импликацията tіtў&tўіt®t=tў, ако в качеството на t и tў вземем съответно термовете a и f(a). Оттук виждаме, че и нейната предпоставка aіf(a)&f(a)іa трябва да е невярна в S. Тъй като обаче първият член aіf(a) на тази предпоставка е формула от K, той трябва да е верен в S, следователно в S трябва да бъде неверен вторият член f(a)іa на предпоставката. Оттук нататък разсъжденията могат да продължат по същия начин както в пример 3.

    Забележка 3. Теоремата, която илюстрирахме чрез горните примери, съдържа едно предположение, което в някои други случаи може да изглежда ограничително. Това е предположението, че има поне един нулместен функционален символ. В действителност обаче то не е ограничително, защото, от една страна, както знаем, винаги можем да разширим една дадена лексика с произволен краен брой (а даже и с изброимо много) нови функционални или предикатни символи с желан от нас брой аргументи, а от друга страна, както лесно се вижда, ако извършим такова разширяване на лексиката, то за произволно множество от формули, отговарящи на първоначалната лексика, изпълнимостта на това множество в случай, че си служим с разширената лексика, е равносилна с неговата изпълнимост при използване на първоначалната лексика.

    Пример 4. Да предположим, че множеството на функционалните символи се състои само от един елемент - един едноместен функционален символ f. Ще искаме да изследваме, дали е изпълнимо множеството M от двете универсални формули

    Забележка 4. Начинът, по който разгледахме пример 4, води до безкраен модел на множеството M от този пример, а именно до Ербранова структура с носител {a,f(a),f(f(a)),f(f(f(a))),...}. Директно може да се провери, че множеството M притежава и модел, на който носителят се състои само от три елемента. Такъв модел е всяка структура ({c,d,e},I), където c, d, e са различни обекти и имаме равенствата

    Пример 5. При същотo предположениe за множеството на функционалните символи както в пример 4 да разгледаме множеството M, състоящо се от трите формули

    Забележка 5. От доказаното необходимо и достатъчно условие може да се заключи (и примерите 1 и 2 го илюстрират), че ако всички функционални символи са нулместни, то съществува алгоритъм, който за всяко крайно множество от затворени универсални формули позволява да установим дали това множество е изпълнимо или не (тук и в другите случаи, когато става дума за прилагане на алгоритъм към крайно множество от формули или от друг вид думи, подразбираме, че е налице списък на елементите на това множество). И наистина, да предположим, че всички функционални символи са нулместни и е дадено едно крайно множество M от затворени универсални формули. Без ограничение на общността можем да приемем, че съществува поне един нулместен функционален символ и благодарение на това споменатото необходимо и достатъчно условие е приложимо към M. Също без ограничение на общността можем да считаме, че функционалните символи са краен брой (дори да разполагаме с безбройно много такива символи, за построяването на коя да е конкретна формула от M са използвани най-много краен брой от тях, които разбира се могат да се извлекат от нея по прост начин). От друга страна, лесно се съобразява, че при такова положение (благодарение на наличието само на нулместни функционални символи) всяка затворена универсална формула има само краен брой конкретизации и те могат да бъдат получени от формулата с помощта на прост алгоритъм. Тогава краен брой ще бъдат и конкретизациите на всички формули от M, като ще имаме прост алгоритъм и за тяхното получаване. Конкретизациите обаче са безкванторни формули, а, както отбелязахме във въпроса за безкванторни формули, въпросът за изпълнимост на крайно множество от безкванторни формули е алгоритмично разрешим.

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

Previous

Next

Contents