Повна версія

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

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


<<   ЗМІСТ   >>

КОН'ЮНКТИВНА І ДІЗ'ЮНКТІВНАЯ НОРМАЛЬНІ ФОРМИ

Кожну формулу логіки висловлювань можна перетворити в еквівалентну формулу деякого стандартного виду, в якій використовуються тільки зв'язки-л, v і л. Познайомимося з двома стандартними видами формул: з кон'юнктівной нормальною формою (КНФ) і з диз'юнктивній нормальною формою (ДНФ). Під еквівалентністю двох формул тут мається на увазі їх синтаксична еквівалентність, під перетворенням розуміється побудова виведення однієї формули з іншого. Визначимо точно ці поняття.

Визначення. Формула А називається синтаксичним наслідком (кажуть ще синтаксично виведена з) безлічі формул Г , що позначається Г-А, якщо є така послідовність формул A h А 2 , ..., А п , що А п є А і для будь-якого / е { 1, 2, ..., п } формула А, - є або аксіома, або одна з формул безлічі Г , або виходить по одному з правил виведення з попередніх формул A h A 2, |. Послідовність формул А 1 , А 2 , ..., А " називається доказом , або висновком , формули А з безлічі Г. Самі формули, що входять в безліч Г , називаються посьикамі , або гіпотезами.

Визначення. Якщо 0 [А, то формула А називається теоремою і позначається -А.

Визначення. Формула А називається синтаксично еквівалентною формулою В , якщо А [В і В -А справедливо одночасно.

Виявляється, що синтаксична еквівалентність формул А і В означає У (А = В ), тобто еквівалентність А = В є теоремою. Тому поняття синтаксична еквівалентність і еквівалентність є синонімами. Це дозволяє уникати побудови виведення для отримання з формули А її КНФ або ДНФ. Для того щоб виконати перетворення формули А в КНФ або ДНФ, досить використовувати закони логіки висловлювань, будуючи ланцюжка еквівалентностей подібно до того, як в алгебрі будуються ланцюжка рівності в ході алгебраїчних перетворень. Наступне твердження по суті є метатеореми логіки висловлювань, що обгрунтовує зазначеної спосіб отримання КНФ і ДНФ.

Теорема. Формули Л і В синтаксично еквівалентні, тобто Л [В і В [А справедливі одночасно тоді і тільки тоді, коли | - (А = В).

Це твердження є наслідком теореми дедукції, доведеною Ж. Ербраном (1930 г.).

Теорема дедукції. Нехай Г безліч формул, А і В - деякі формули. Якщо Г [{А } -У, то Г | - (Л - »#). Зокрема , якщо А [В, то | - (А ^> В).

Приведення формул до КНФ і ДНФ проводиться з використанням законів логіки висловлювань і наступних теорем:

Тут awb - довільні формули.

Визначення . Формула виду я, va 2 v ... va n v-, b [ v-ib 2 v ... vi b m називається диз'юнкт, або пропозицією, а формула виду я, ля 2л ... ля "л-1 />, л- 1 /> 2 л ... л-Д" називається Кон'юнктів, де я ,, я 2 , ..., а п , Ь і Ь ь Ь т - пропозіціональние символи. При цьому а ,, а 2 , а п називаються позитивними, а -> -> Ь 2 , -> Ь т негативними членами диз'юнкт або кон'юнктив.

У диз'юнктів і кон'юнктив можуть повністю бути відсутнім позитивні або негативні члени. Це означає, що формули

зокрема, формули я, і -> />, теж є диз'юнкт. аналогічно формули

зокрема, формули я, і теж є Кон'юнктів.

Визначення . Кон'юнктівной нормальною формою (КНФ) називається формула, що представляє собою кон'юнкцію кінцевого числа диз'юнктів.

Іншими словами: КНФ - це кон'юнкція пропозицій. У загальному вигляді КНФ можна представити формулою

де Z) ,, D 2 , D k - пропозиції (диз'юнкт).

Визначення . Диз'юнктивній нормальною формою (ДНФ) називається формула, що представляє собою диз'юнкцію кінцевого числа Кон'юнктів.

У загальному вигляді ДНФ можна представити формулою

в якій С ,, С ь ..., С до - Кон'юнктів. Цілком можливо, що ДНФ складається з єдиного Кон'юнктів; точно також КНФ може складатися з єдиного диз'юнкт.

Теорема. Будь-яка формула логіки висловлювань еквівалентна деякій КНФ і деякою ДНФ.

Справедливість цієї теореми встановити нескладно. Наступний алгоритм перетворення довільної формули в еквівалентну їй КНФ по суті є обґрунтуванням цієї теореми. Той же алгоритм, як пізніше буде показано, можна використовувати для перетворення довільної формули в еквівалентну їй ДНФ.

 
<<   ЗМІСТ   >>