Алгоритми зведення формул до ПНФ

1. Виключити з формули логічні зв’язки «~» «» із застосуванням правил:

2. Внести знак заперечення всередину формули, для того використати закони:

- Подвійного заперечення

- Де Морана

- Еквівалентні відношення 1і 2 .

3. Оскільки квантор існування не дистрибутивний відносно кон’юнкції, а квантор загальності відносно диз’юнкції, то для складниих формул, що містять вирази виду , необхідно ввести нові змінні, які б дозволили використати еквівалентні відношення 7-10

4. Використовуючи формули 3-10 винести квантори у префікс, отримаємо ПНФ.

Приклад 1. Звести формулу Тут була виражена логіка зв’язка «» і застосоване відношення 1; внесено квантор існування у префіксах за еквівалентним відношенням 4.

Приклад 2. Звести формулу до ПНФ предикатної формули

Розв’язання:

Скориставшись законами де Моргана отримаємо:

Використовуючи еквівалентні відношення 1і 2, змістимо символи заперечення безпосередньо до символів предикатів:

Оскільки квантор існування не є дистрибутивний відносно кон’юнкції, вводимо нову зміну в другому предикаті:

скориставшись відношенням 11 отримаємо:

Оскільки, квантор загальності не дистрибутивний відносно кон’юнкції, остаточно отримаємо:

. Отже, ПНФ вихідна предикатної формули має вигляд:

Приклад 3. Звести формулу (x;z) до ПНФ

Розвязання:

)

Запитання для самоперевірки.

1. Які формули називаються еквівалентними?

2. Які є основні еквівалентні відношення?

3. Що таке ПНФ?

4. Як звести формулу до ПНФ?

Література

1. (Б2), с.220-227.

2. (Б8), с.32-37

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