Випереджена нормальна форма, алгоритм зведення до випередженої нормальної форми, правила видалення/введення квантора загальності/існування
В логіці висловлень було введено дві нормальні форми: кон'юнктивна і диз'юнктивна. В логіці предикатів вводиться третя нормальна форма, що називається випередженою нормальною формою.
Визначення
Формула F в логіці предикатів знаходиться у випередженій нормальній формі (ВНФ) тоді і тільки тоді, коли вона може бути зображена у вигляді (Q1x1)... (Qnxn)(M),де кожне (Qixi), і = 1, ..., п, є або ("x), або ($х), а М— формула, що не містить кванторів. Причому (Q1x1)... (Qnxn) називається префіксом,а М — матрицею формули F.
Для перетворення виразів довільної форми у ВНФ необхідно по черзі виконати такі етапи перетворення.
1. Виключити логічні зв'язки еквіваленції (~) та імплікації (®), виразивши їх через операції диз'юнкції, кон'юнкції і заперечення за допомогою таких законів:
;
.
2. Опустити знаки операцій заперечення безпосередньо на предикати, використовуючи закон подвійного заперечення Ø(Ø F) = F і закони де Моргана Ø(F Ú G) = ØF ÙØG, Ø(F Ù G) = ØF Ú ØG, у тому числі для кванторів:
; 
.
3. Якщо необхідно, перейменувати зв'язані змінні.
4. Винести квантори на початок формули, використовуючи відповідні закони, для одержання випередженої нормальної форми.
Приклад. Звести формулу ("x)F(x) ® ($x)Q(x) до ВНФ.
Розв'язок. Спочатку виключимо імплікацію, потім опустимо знак операції заперечення безпосередньо на предикат і винесемо квантор на початок:
Приклад. Одержати ВНФ для формули
.
Розв'язок. Скористаємося наведеним вище алгоритмом.
Розглянемо правила висновку, які можна використовувати для проведення дедуктивних умовиводів з висловленнями логіки предикатів, що містять квантори. Ці правила часто використовуються у ході математичних доведень без додаткового пояснення.
Правило видалення квантора загальності
використовується для доведення істинності F(c),де с — довільно обраний елемент предметної області D, у якій справедливе "х F(x). Наприклад, із засновку «Всі студенти бажають одержувати добрі оцінки» робимо висновок: «Студент Петров бажає одержувати добрі оцінки».
Правило введення квантора загальності
стверджує істинність "х F(x), якщо доведена істинність F(c)для будь-якого с, тобто для всіх елементів с з розглянутої предметної області D.
Правило видалення квантора існування в істинній формулі $х F(x)полягає в позначенні імені елемента с (конкретного або гіпотетичного), для якого F(c)істинне:
Правило введення квантора існування
дозволяє вирішити, що $х F(x)є істинним, коли відомий деякий елемент с, для якого істинне F(c).
Крім наведених правил, у логіці предикатів у ході дедуктивного висновку можна використовувати всі правила, які застосовуються для дедуктивних висновків у логіці висловлень.
Приклад. Показати, що з тверджень «Всі у першій групі вивчають математику» і «Маша — студентка першої групи» маємо висновок: «Маша вивчає математику».
Розв'язок. Позначимо через F(x)предикат «х є студент першої групи», а через М(х) — «х вивчає математику». Тоді засновки можна записати у вигляді: "х (F(x)® М(х)) і F(Маша) відповідно, а потрібний висновок — М(Маша). Для одержання цього висновку необхідно здійснити таку послідовність дій:
1. "х (F(x)® М(х)) перший засновок.
2. F(Маша)® М(Маша) крок 1, правило видалення квантора ".
3. F(Маша) другий засновок.
4. М(Маша) кроки 2 і 3, правило відділення. Таким чином, одержано шуканий результат.
Запитання
1. Дайте визначення випередженої нормальної форми.
2. За допомогою яких законів можна опустити знаки операцій заперечення безпосередньо на предикати?
3. Сформулюйте алгоритм перетворення виразів довільної форми у ВНФ.
4. Назвіть правила висновку, які можна використовувати для проведення дедуктивних умовиводів з висловленнями логіки предикатів.
5. В чому полягає правило видалення квантора загальності?
6. Як і навіщо використовується правило введення квантора загальності?
7. Поясніть відмінність у трактуванні елемента предметної області у правилі видалення квантора існування від прийнятої у правилі введення квантора загальності.
8. Яке правило введення квантора існування?
Завдання
1. Звести до ВНФ такі вирази:
а) 
;
б) 
;
в) 
;
г) 
;
д) 
.
2. Визначте, чи є формула ($х) (Р(х) Ù Q(x)) логічним наслідком формул ($х) Р(х)і ($х) Q(x).
3. Застосовуючи дедуктивні правила логіки предикатів, наведіть висновки з таких засновків:
3.1.Якщо хтось з тих людей — автор цих пліток, то він глупий і безпринципний. Але ніхто з тих людей не глупий і не позбавлений принципів.
3.2.Якщо всі ці люди не хоробрі або на них не можна покластися, то вони не належать до нашої компанії. Але вони належать до нашої компанії.
3.3.Якщо хтось з підозрілих здійснив всі ці нерозкриті крадіжки, то він був ретельно підготовлений і мав співучасника. Якщо б всі крадіжки були підготовлені ретельно, то, якщо б був співучасник, вкрадено було б набагато більше. Але останнє не має місця.
3.4.Якщо один з нас піде завтра на перше заняття, то він повинен буде підвестися рано, а якщо ми підемо сьогодні ввечері у кіно, то він ляже пізно спати. Якщо будь-який з нас ляже пізно спати, а підведеться рано, то буде задовольнятися п'ятьма годинами сну. Але ми не можемо задовольнятися п'ятьма годинами сну.
3.5.В бюджеті виникне дефіцит, якщо і тільки якщо не підвищать деякі мита. Державні витрати на всі соціальні нестатки скоротяться, якщо і тільки якщо у бюджеті буде дефіцит. Деякі мита підвищать.
3.6.Якщо всі ціни одночасно підвищуються, то підвищується і заробітна плата. Всі ціни високі або застосовується регулювання цін. Якщо застосовується регулювання цін, то немає інфляції. Спостерігається інфляція.
