Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ДОКАЗ ОБЩЕЗНАЧИМОСТИ ЗА ДОПОМОГОЮ ПРАВИЛА РЕЗОЛЮЦІЇ

Ми опишемо тут одну з процедур, що дозволяє для будь-якої загальнозначущої формули за кінцеве число кроків встановити її общезначімость. Ця процедура пов'язана з використанням при пошуку докази так званого "правила резолюції" - аналога вже відомого нам правила для логіки висловлювань.

Відповідно до даної процедури, доказ общезначимости замкнутої формули F складається з наступних етапів.

Етап 1

Розглядається формула Fo = - * F, і далі вдаються до дій, спрямованих на встановлення нездійсненності формули Fo (тобто формула F доводиться "від протилежного").

етап 2

До формулою Fo застосовується ланцюжок еквівалентних (в сенсі певної вище еквівалентності формул) перетворень: а) використовуються еквівалентні заміни (/ <- + д) - * (/ &? V (- ^ /) & (- * р)), (/ -> д) -> ( "» / V д) дозволяють усунути логічні зв'язки виду б) використовуються заміни виду ( А * QxB) - " Qy {A * S * B), де * - зв'язка V або &, Q - квантор V або 3, А і в - формули, у - предметна змінна не входить ні в А, ні в В. Крім того використовуються заміни -Л / ХЛ - »Зх (- 'Л), -'ЕхЛ -> / х (- > Л).

Заміни зазначені в пункті б), застосовуються до тих пір поки це можливо, вони здійснюють переміщення кванторів до "початку" формули, в результаті чого Fo перетворюється в формулу Fi виду QiX ... Q n x n A де А - бескванторная формула, Qi , ..., Q n - символи кванторів. Про Fi кажуть, що вона знаходиться в попереджання нормальній формі.

етап 3

Лемма 16. Нехай / = Vxj. ,. / х *, 3 x k + g - замкнута формула логіки предикатів, де до > 0, g - формула в попереджання нормальній формі; ф - функціональний символ арності до, що не зустрічається в у (якщо до = 0, то ф - предметна константа); f = Vxj. ..Vx * # ', де g' = x ^ g - резуль

тат заміни всіх вільних входжень змінної x k + l в g на ф (х 1, ..., х *). Тоді f здійсненна тоді і тільки тоді, коли / ' здійсненна.

Доведення. Припустимо, що формула / здійсненна, нехай I - інтерпретація, в якій її значення є І. Розглянемо предикат ( g) j = h {x, .. . , x k + ). Так як

то для будь-яких елементів ai, ..., а * області М інтерпретації I існує елемент а *. +1 цій галузі такою, що

Визначимо на М функцію p (xi, ..., х *,), вважаючи в зазначеній ситуації p (a b . .., a k ) = a fc + 1 . тоді

на М.

Нехай Г - інтерпретація, що відрізняється від I тільки тим, що в ній символу ф зіставляється функція p (xi, ..., х *). Використовуючи лему 15 про інтерпретації, отримаємо, що ( є

результат підстановки в (g) i> = ( g) i = h {x i, ..., x * + 1) функції (ф (х 1, ..., х *)) // = p (xi, ..., Xk) замість змінної Xk + i , тобто (<7 ') /' = і на М. Таким чином, (/ ') // = і, і формула /' здійсненна.

Назад, якщо / 'здійсненна, то розглядаємо інтерпретацію /, в якій (/') / = І, тобто ( д ') / отримано підстановкою в функцію ( g) i = h (x 1, ..., х *, х * + 1) функції (0 (хх, ..., х *)) / = p (xi, ... y Xk) замість змінної x * + i, тобто для будь-яких ai, ..., а * з Л / виконано

І (Я / = І.

Лема доведена. ?

Описане в лемі 16 перетворення / -j? / 'Дозволяє послідовно усувати квантори 3 з кванторного приставки, застосовуючи його необхідну кількість разів до формули Fi, отримаємо в результаті формулу F 2 виду Vxi ... Vx n > 4, де А - бескванторная формула. Кажуть, що F 2 знаходиться в сколемовской нормальній формі. Зауважимо, що общезначімость вихідної функції F еквівалентна нездійсненності формули F 2 .

етап 4

Для аналізу здійсненності формул / виду Vxi ... Vx n p, де д - бескванторная формула, зазвичай використовується теорема Ербра- на. Щоб сформулювати цю теорему, введемо поняття ербра- ського універсуму Hf формули / зазначеного виду. Hf є безліч термів, що задається за допомогою наступного індуктивного визначення:

  • а) для кожної предметної константи а, зустрічається в /, однобуквений терм а входить в Hf , якщо / не має предметних констант, то в Н / включається терм а *, де aj - перша за алфавітним списком предметна константа;
  • б) якщо терми ti належать Hf і функціональний символ ф арності п зустрічається у формулі /, то терм Ф {Ь ь? • -, tn) входить В Hf.

Іншими словами, Я / утворено усіма термами, які можна побудувати за допомогою предметних констант і функціональних символів, що зустрічаються в / (якщо / не має предметних констант, то дозволяється використовувати константу а).

Скажімо, що безліч формул логіки предикатів здійснимо , якщо існує така інтерпретація, в якій кожна формула безлічі визначає не тотожне помилковий предикат.

Має місце наступне твердження.

Теорема 23 (Ербрана). Замкнута формула / виду Vxi ... Vx n g, де g не містить кванторів, здійсненна тоді і тільки тоді, коли кожне кінцеве підмножина безлічі: ? 1, ...,? п € Я /} здійснимо.

Доведення. Якщо в деякій інтерпретації / формула Ух * .. .Vx n g має значення І, то в цій же інтерпретації (відповідно до леми про інтерпретації) істинні і всі формули

..... t « 9-

Припустимо тепер, що здійснимо кожне кінцеве підмножина безлічі Я = 0: * ь ..., t n 6 Я /}, і будемо

доводити здійсненність /.

Перш за все, встановимо існування такої інтерпретації /, в якій всі формули безлічі R мають значення І.

Якщо R - звичайно, то це відразу випливає з зробленого припущення.

Нехай R нескінченно. Розглянемо безліч Л = {Л Ь Л2, ...} всіх можна зустріти в формулах з R подформул виду P (ti ,. .., r m ), де Р - предикатний символ (нагадаємо, що такі формули називаються атомарними або атомами). Легко бачити, що Л нескінченно. Нехай Я * - підмножина безлічі Я, що складається з усіх таких формул, в яких зустрічаються тільки атоми з {Ль Л2, ..., Л *}. Очевидно, що R = U i ^ iRi, причому кожне Я, - звичайно.

Так як кожна формула безлічі Я побудована зі своїх атомів за допомогою одних тільки логічних зв'язок, то визначення істиннісних значень цих атомів в будь-якої інтерпретації дозволяє однозначно визначити і значення самої формули. З огляду на можливість виконання кожного Л », ми можемо розглянути тепер непусті безлічі VJ наборів а , ..., а * істиннісних значень атомів А , ..., Л *, при яких всі формули з Ri мають значення І.

Побудуємо индуктивно нескінченне дерево Т.

Базис індукції. Візьмемо вершину v 0 і оголосимо її коренем дерева Т. В якості першого ярусу дерева беремо елементи з V і від vo до кожної вершині з V проводимо ребро.

Індуктивний перехід. Нехай побудовано дерево Т до ярусу г і Vi - вершини цього ярусу. Будувати (г + 1) -й ярус будемо наступним чином. Як вершин візьмемо елементи К + 1. Якщо (ai, ..., ar »+ i) G К + 1, то зрозуміло, що , ..., а *) € VJ, в цьому випадку вершини (ах, ..., а *) і (ах, ..., ai + x) з'єднуємо ребром.

Оскільки для кожного натурального i безліч Ri здійснимо, а, значить, не порожньо, то дерево Т - нескінченно. Оскільки з побудови Т зв'язно, то згідно з відомим лемме Кеніга з теорії графів, в дереві Т існує нескінченний шлях 7Г = vo, vi, V2, ..., де Vi € Vi при i = 1,2, ____ Згідно побудови дерева Т, якщо v, = (ax, ..., а *) і v i + 1 =

(А .---. А + 1), ТО ах = А. • •? > «I = А-

Порівняємо кожному натуральному i истинностное значення а *, таке що Vj = (71 »• • •, 7» -1> <* ») • Тоді, очевидно, для кожного i = 1,2, ... буде виконано v * = (ax, аг, ... »а»).

Визначимо тепер в якості області М інтерпретації / безліч Hf . Кожному символу предметної константи, зустрічається в /, зіставляємо як значення самого себе, функціональному символу ф> зустрічається в /, зіставляємо функцію ф над термами з - ///, перетворюючу набір ($ i, ...,? П ) таких термів в терм п) - Для кожного натурального г якщо Л * = Pfa , ..., т т ) (тут Тх, ..., г т еяд то значення предиката Pi на наборі (ТХ, ..., т т ) вважаємо рівним а *. В іншому інтерпретацію / доопределять довільно.

За визначенням I атоми А } Л2, ... мають в ній істинності значення ах, а 2 , ---- Якщо / г - довільна формула з R ,

то вона входить у деякий Ri , і приймає на наборі істиннісних значень (qi, ..., а *) своїх атомів ..., Л *, значення І, іншими словами, (Л) / = І, і існування необхідної інтерпретації встановлено .

Покажемо, що (/) / = І. Нехай ( g) j = G (x f ..., х п ). Якщо (т ь ..., т п ) - довільний набір термінів з ///, то відповідно до леми про інтерпретації маємо G ((t) i, ..., (т п ) /) = (S%; :: :?: g) l = І. З іншого боку, згідно з визначенням I маємо (ti) / = т ь ..., (т п ) / = т п . Звідси С (т ь ..., т п ) = І, тобто G - тотожне істинний предикат, і (Vxi ... Vx n

Теорема доведена. ?

Згідно доведеною теоремою, нездійсненність формули F2, отриманої на етапі 3 та має вид Vxi ... Ух п Л, еквівалентна існуванню кінцевого підмножини безлічі? Нр 2 }, що є нездійсненним, так як перевірка здійсненності кінцевого підмножини зазначеного безлічі формул є, по суті перевіркою здійсненності кінцевого безлічі формул логіки висловлювань і алгоритмічно можна реалізувати, то для встановлення нездійсненності F 2 можна застосовувати перебір таких кінцевих підмножин. Ця процедура, однак, є надмірно трудомісткою, і наші подальші дії будуть використовувати теорему Ер брану лише в неявному вигляді.

етап 5

Використовуючи вже описану для логіки висловлювань процедуру, перетворимо формулу А до кон'юнктивній нормальній формі і отримаємо формулу А! виду ji? *, де кожне В { - диз'юнкція атомів або їх заперечень.

Атоми і їх заперечення називаються літерами , диз'юнкції літер - диз'юнкт , логічна константа Л за визначенням також вважається диз'юнкт.

Неважко бачити, що існування кінцевого нездійсненного підмножини безлічі {Sff t " '? FA : 6 Hf 2 }

еквівалентно існуванню кінцевого нездійсненного підмножини безлічі Bi: 6 Hp 2 , i =

1, ..., m}. Останнє нам зручно буде згодом формулювати як існування таких формул / ь не мають

загальних змінних і отриманих з деяких формул списку у ..., В т } переобозначеніе без ототожнення їх змінних xi> ..., x n , а також такий підстановки а замість змінних формул / ь ..., /, термів безлічі Нр 2 , що система {a (/ i), • • • » a ifi)} - нездійсненна. Тут підстановка а розглядається як оператор на безлічі формул.

етап 6

Як і в випадку логіки висловлювань, для встановлення нездійсненності формули F 2 ми введемо допоміжну дедуктивну систему, аксіомами якої будуть визначені вище диз'юнкт У % ... % J3 m , і доведемо, що виводимість в цій системі константи Л еквівалента нездійсненності F2. Для формулювання правил виведення даної дедуктивної системи нам знадобиться наступна лема про уніфікує підстановці (підстановку термів замість змінних

xi, ..., х п розглядаємо як оператор на безлічі бескванторних формул і термів).

Лемма 17 (про що уніфікує підстановці). Якщо fi » 9 i > * • • t fk » 9 k ~ бескванторние формули або терми і існує такал підстановка а, що

то існує мінімальна підстановка (Т, що володіє цією властивістю, тобто

і для будь-якої підстановки 02, що задовольняє умовам

виконано: про 2 = ^ 3 ^ 1 при підходящої підстановці (тут множення підстановок означає їх послідовне застосування).

Доведення. Якщо розглядати кожен, хто входить в бескванторную формулу або терм / символ ф (предикатний символ, функціональний символ або логічна зв'язка) арності п як позначення п-місцевої операції над термами (в разі логічної зв'язки - над бескванторнимі формулами), перетворюючої набір (ti, .. ., t n ) в слово ф (Ь i, ...,? п ), то / визначатиме деякий оператор / *, який на наборі (тХ, ..., т т ) значень змінних хх, ..., х т дорівнюватиме J? Нехай ХХ, ..., i m - всі змінні, що зустрічаються в / ь <7ь • • •> fk) 9 k з умови леми. Тоді виконання умов

для підстановки а термів тх, ..., т т замість змінних х , ..., х т є рішенням системи рівнянь

Для опису в явному вигляді всієї сукупності її рішень використовуємо наступні еквівалентні перетворення даної системи:

а) Якщо при деякому г слова / *, д * мають, відповідно вид ф (Ь , ..., t p ) і ф {Ь , ..., t ' p ) (ф, ф - предикатний символ, функціональний символ або логічна зв'язка - •), то при ф ф ф робимо висновок про несумісності системи (згідно з припущенням леми, це неможливо), а при ф = ф (отже, при р = q) замінюємо рівняння / * = д * на групу рівнянь

l i - 1 »• • • 1 1Р - 1Р

  • б) Якщо } * збігається з д *, то рівняння f * = д * видаляється.
  • в) Якщо при деякому i одне зі слів / *, д * є змінна х, а інше терм t, х ф ?, то в разі, коли t містить х, робимо висновок про несумісності системи (що неможливо за припущенням леми), інакше - підставляємо t замість х в усі залишилися рівняння системи. Дане перетворення виконується тільки за умови, що існує відмінне від } * = д * рівняння містить х.

Перетворення в) зменшує число змінних х, мають явне вираз х = t через інші змінні системи і мають більше одного входження в систему, і воно може бути застосовано лише кінцеве число раз.

Перетворення а), в разі застосування його до рівнянь максимально можливої довжини, зменшує число рівнянь даної або більшої довжини, і таким чином його можна використовувати лише кінцеве число раз по завершенні перетворень в)

Таким чином процес застосування до системи рівнянь перетворень а), б), в) обривається за кінцеве число кроків.

Результуюча система до якої ці перетворення незастосовні може мати лише вид х * г = 0 J, ..., х * ^ = 0 *, де терми 0 , ..., 0 р не містять змінних х » х , ..., х * р .

Виберемо тепер в якості про підстановку термів 9 у ... У 9 Р замість змінних х * ,, ..., х * р . Якщо змінні х * ,, ..., х » р мають своїми значеннями терми 9 , ..., 9 р) а кожна змінна Xj y j € {1, ..., m} {ii, ..., ip ), має значенням однобуквений терм Xjy то рівняння х * х = 0J, ... у х * р = 9 * виконуються, а отже, (Ji (fi) = cri (pi), • • • , <7i (fk) =

Припустимо, що про * - підстановка така, що 02 (/ 1) = 02 (01), • • •> ^ "2 (Л) = Vitek) - Без обмеження спільності можна вважати, що а 2 підставляє терми т у .. . у т ч замість змінних х 1, ..., Xq , q> т. Набір значень т , ..., т т змінних xi, ..., x m задовольняє системі х * х = 0 J, ... , x * p = 9 *. Це означає, що виконані співвідношення:

де {j>. •. , jr) = {1, ..., m} {zi, ..., г р }. Якщо тепер вибрати в якості 03 підстановку термів Tj x , ..., Tj r , r m + 1 , ..., r q замість змінних Xj x , ..., x 7r , x m + i, ..., x q , то отримаємо а 2 = 0304. Лема доведена. ?

Підстановка oi існування якої встановлено в даній лемме, називається уніфікує підстановкою для пар ( f > 0i), •• • »(Д) 9к) -

Як приклад розглянемо процес отримання уніфікує підстановки для для однієї пари формул

  • 1) Спочатку маємо рівняння -> Р (а, у) = - »Р (х у д (х)).
  • 2) Застосовуючи еквівалентну перетворення а), отримаємо Р (а, у) = Р (х, д (х)).
  • 3) Ще раз застосовуючи еквівалентну перетворення а), отримаємо систему рівнянь а = х, у = # (х).
  • 4) Застосовуючи еквівалентну перетворення в), отримаємо уніфікує підстановку х = а, у = у (а).

Замиканням диз'юнкт D (позначається [D]) будемо називати формулу VxiVijьД де Xi, ..., х * - всі вхідні в D предметні змінні.

Якщо певному на безлічі диз'юнктів "правило виведення" дозволяє виводити з диз'юнктів Diy ..., D r лише такі слідства Do, що формула [Do] є логічний наслідок формул [Dj], ..., [D r ], то таке правило виведення назвемо коректним.

Як легко бачити, якщо при використанні деякого набору коректних правил виведення з диз'юнктів В ь ..., В т) введених на етапі 5, вдається за кінцеве число кроків витягти логічну константу Л, то формула F 2 нездійсненна, aF- общезначима.

Передбачувана тут процедура автоматичного доведення теорем використовує при пошуку такого висновку константи Л наступні (як легко бачити, коректні) правила виведення:

R0 (переобозначеніе змінних). З довільного диз'юнкт D виводиться диз'юнкт D ', отриманий з D переобозначеніе без ототожнення змінних, що входять в D.

R1 (правило резолюції). Якщо / 1 V • • • V f s і д V • • • V д г - диз'юнкт, безлічі змінних яких не перетинаються, причому fi має вигляд P (t > ...,? *), A gj - вид ~ ' P (t ' 1} і а

- уніфікуються підстановка для пари

г € {1, ..., s}, j? {1, ..., r}, то виводиться диз'юнкт

(якщо s = г = 1, то виводиться константа Л).

Диз'юнкт одержуваний згідно з правилом R1, називається резольвенти вихідних диз'юнктів.

R2 (правило склеювання). Якщо f V- • • V / s - диз'юнкт і <т - уніфікуються підстановка для (/ », fj) } г Ф j, t, jf € {1, ..., 5}, то виводиться диз'юнкт cr (fi) V- • -V <7 (/ j_i) Va (/ i + i) V- • Vcr (/ 5 ).

Теорема 24. Якщо формула F 2 нездійсненна і її 'кон'юнктивна нормальна форма має вигляд то за кінцеве чис

ло кроків з диз'юнктів В , ..., В т за допомогою правил виведення R0, R1, R2 може бути виведена логічна константа Л.

Доведення. Як було відмічено в кінці етапу 5, нездійсненність F 2 тягне існування таких формул / 1,

які не мають спільних змінних і отриманих з деяких формул списку , ..., В т } переобозначеніе без ототожнення їх змінних х у ..., х п , а також такий підстановки про замість змінних формул f , ..., / 1 термів безлічі Нр 2 , що система { нездійсненна

Кожна формула <т (/ *) має вигляд А * 1 V ••• V Л " а , де А 11 ..., A s - атоми без змінних, а , ..., a s - логічні константи. Якщо деякі А А в цій формулі збігаються між собою, то після їх ототожнення формула cr (/ j) перетворюється в деякий диз'юнкт, який позначимо d {.

Нехай i4i, ..., j4 n - все різні атоми, що зустрічаються в диз'юнкт d y ..., ф, п > 1. Безліч М = {^ i, ..., d /} представимо у вигляді М U М2 U М3, де М - все диз'юнкт, в які не входить Ль М2 - все диз'юнкт виду А V в, Моз - все диз'юнкт виду -> А V В.

Розглянемо безліч М4, утворене всіма диз'юнкт виду В V С, де А V В ? М2, -> Ai V З ? М3 (якщо А ? М2, - "Л1? М3, то в М 4 включається Л). Позначимо М '= Mi U М 4 . Зрозуміло, що безліч М 'не містить атома Ль

Так як {d y ..., а, ..., On атомів ль-., Л П існує формула d? М, що має значення Л. Якщо d? Mi, то? М '. Якщо такої формули d в Mi немає, то при ai = І існує формула d! = -1Л1 V З має значенням Л, а при а = Л - формула d "= А V В, має значення Л, d! ? М3, d"? М2. Таким чином, варіюючи при фіксованих аг, ..., a n , значення ai, знаходимо зазначені формули d! , D " і отримуємо, що формула cf '" = В V С, що належить М 4 , а отже і М', має на наборі значень аг, ..., а ті атомів Л2, • • •, Л л значення Л.

Ми отримали, що для будь-яких істиннісних значень ато-

mob / I2, • • •, A n в M 'є формула, значення якої є Л, тобто М 'нездійсненно і має не більше п - 1 атома.

Нехай диз'юнкт В V С з М 4 отримано з диз'юнктів Ai V В € М2 і - * Ai V З € М3. Л1 V Б виникло з деякого <т (/ ») ототожненням однакових літер. Отже, cr (fi) = cr'icr'iifi), де про " уніфікує ті літери з / *, які збігаються після застосування до них а. Аналогічно, a (fj) = о ^ о 2 (fj). Так як змінні в / * і / j різні, то можна вважати а 2 - про " = о", про ' 2 - cr [= про'. Неважко бачити, що o "(fi) і o" (fj) отримані з / *, fj декількома застосуваннями правила R2.

Виділяючи в <т "(/ *) і cr" (fj) ті атоми, застосування підстановки про ' до яких дає, відповідно, А і - »Ai, матимемо для o" {fi) і такі уявлення:

Розглядаючи далі підстановку р, уніфікує пару (P {0i,.,., 0 S ), Р (0 ' ... отримаємо, що для деякої

підстановки pf виконується а '= р' р. При цьому диз'юнкт р (В ') V р (С') отримано зa "(fj) по правилу R1, причому BvC = p '(p (B') syp (C ')).

Проведені міркування показують, що застосовуючи до {/ ь * ••> //} правила RO, Rl, R2 можна отримати такі формули {<7i, ..., <7г}, які мають загальних змінних, що Mi U М 4 = {^ ( • • •> <7 (<7г)} для відповідної підстановки <т, тобто для <71, ..., <7г виконані ті ж умови, що і для / 1 та число атомів в формулах {cr (< 7i), ..., <т (<7 г )}, хоча б на один менше, ніж в

Продовжуючи описаний процес логічного висновку, за кінцеве число кроків отримаємо систему {/ ii, ..., h q } } задовольняє зазначеним умовам, причому таку, що для неї число атомів у відповідному сімействі (cr (/ ii), ... ^ (h q )} виявиться дорівнює 0. Це означає, що q = 1 іhi = Л, і твердження доведено. ?

Наведемо простий приклад застосування описаної вище процедури автоматичного доведення теорем логіки предикатів. Формула F, общезначімость якої потрібно встановити має вигляд:

Заперечення Fo формули F являє собою кон'юнкцію таких формул:

Неважко перевірити, що описані на етапах 2) -4) перетворення, що дозволяють визначити вихідну сукупність диз'юнктів В , ..., В т , можна застосовувати до кожної з цих формул окремо. У першій формулі позбавляємося від квантора існування, вводячи в розгляд новий функціональний символ д: Ух (Р (х, д (х)) V Q (x, g (x))), в останній формулі для цієї мети використовуємо нову предметну змінну a : Vy-'R (a, y). Остаточно, отримуємо наступну систему диз'юнктів:

Далі переобозначаем змінну у в диз'юнкт 4 на у ' і уніфікуємо R (a, y') з R (x, f (x, y)) з диз'юнкт 2: а = х, у '= f {x, y), у ' = / (а, у). Таким чином, уніфікуються підстановка має вигляд S у у і з її допомогою отримуємо за правилом R1 новий диз'юнкт:

5) -F (a, y)

Далі з диз'юнктів 3, 4 отримуємо аналогічним чином:

6) -> а, у)

Уніфікуємо Р (а, у) з Р (х, д (х)) з диз'юнкт 1: х = а, у = д (а), і отримуємо наслідок диз'юнктів 5, 1:

7) Q (a, g (a))

Нарешті, уніфікуємо Q (a y д (а)) і -> <2 (а, у) (тобто диз'юнкт 6,7) і виводимо константу Л.

 
<<   ЗМІСТ   >>