Зведення формул до ПНФ

План

ПНФ.

1. Еквівалентні відношення. Їх застосування.

1. Означення:

Формули називаються еквівалентними якщо при будь-яких підстановках констант вони приймають однакові значення. В тому числі тотожно-істинні формули (і всі тотожньо- хибні) еквівалентні. Якщо формули F₁ і F₂ еквівалентні, то - тотожно-істинні формули.

Множина тотожно істинних формул логіки предикатів входять в будь-яку теорію, дослідження цієї множини– важливе завдання логіки предикатів. При цьому виділяють дві проблеми:

1). отримання тотожно-істинних формул;

2). перевірка формул та істинність.

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

В логіці предикатів справедливі всі еквівалентні співвідношення логіки висловлень, а також власні еквівалентні відношення, що включають зв’язки

Основні еквівалентні відношення такі:

Використовуючи відношення 1і 2, можна виразити один квантор через інший. Визначення 3 і 4 показують дистрибутивність квантора загальності відносно кон'юнкції і квантора існування відносно диз'юнкції. Якщо в цих виразах поміняти місцями квантори ,то отримаємо відношення справедливе в одну сторону:

Тому що в таких випадках еквівалентних відношень застосовують перейменування змінної x в одному предикатів на нову зміну:

Відношення 5 в 6 виражають комутативність однойменних кванторів, що не виконуються для різнойменних кванторів, наприклад – не є еквівалентними. Відношення 7-10 дозволяють виносити формулу, що не містить змінної х, за межі дії квантора, що зв’язую цю змінну. Даних наведених відношень, а також відношень логіки предикатів є достатньо для перетворення формули логіки предикатів.

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

2. Означення:

Префіксною нормальною формою (ПНФ) називається формула, що містить тільки операції диз’юнкції, кон’юнкції і заперечення, причому символ заперечення знаходиться тільки перед символом предикатів. Тобто ПНФ має вигляд:

- квантори – це або ), а F- формула.

У логіці предикатів для будь-якої формули існує еквівалента їй префікса нормальна формула

Дата добавления: 2014-01-07