Логічні відношення між формулами

Поряд із виділенням логічних законів у системі S^[XXXVI] розв’язується ще одна задача, яка встановлює логічні від­ношення (за істинністю і хибністю) між формулами.

В якості фундаментальних логічних відношень у S¹ виділяють:

— відношення сумісності за істинністю;

— відношення сумісності за хибністю;

— відношення логічного слідування.

Дефініція: «Формули деякої множини Γ¹ є сумісними за істинністю в S¹ тоді і тільки тоді, якщо в S¹ існує інтерпретація нелогічних символів, які входять до складу вказаних формул, при якій кожна формула із Γ приймає значення «істина». У протилежному випадку формули будуть несумісними за істинністю».

Дефініція. «Формули із множини Γ є сумісними за хибністю в S¹ тоді і тільки тоді, якщо в S¹ існує інтер­претація нелогічних символів, що входять до складу вказаних формул, при якій кожна формула із Г приймає значення «хиба». У протилежному випадку ці формули будуть несумісними за хибністю».

Найбільш важливим є відношення логічного слідування.

Дефініція. «Із множини формул Γ логічно слідує фор­мула В у S¹ тоді і тільки тоді, якщо в S¹ не існує ін­терпретації нелогічних символів, що входять до Γ і до В, при якій кожна формула із Γ приймає значення «іс­тина», а формула В — значення «хиба». У протилеж­ному випадку В не слідує із Г».

Твердження «Із Г слідує В» записується так:

Щоб краще зрозуміти логічні відношення між форму­лами в S¹ звернемося до прикладів.

Візьмемо формулиі побудуємо для

них спільну таблицю істинності, щоб розглянути названі логічні відношення.

Розглянемо, які ж логічні відношення мають місце між наведеними формулами. Критерієм сумісності за істинніс­тю, хибністю та логічним слідуванням будуть вище наве­дені дефініції.

Якщо в спільній таблиці істинності знайдеться, у крайньому разі, один рядок, в якому кожна формула приймає значення істинності «і», то ці формули вва­жаються сумісними за істинністю. У протилежному випадку вони не будуть сумісними за істинністю.

Якщо у спільній таблиці істинності знайдеться хоча б один рядок, де кожна формула приймає значення хиб­ності «х», то ці формули сумісні за хибністю. У про­тилежному випадку вони не будуть сумісні за хибніс­тю.

Таким способом можна розглядати логічні відношення між будь-якими формулами в системі S¹.

6. Нормальні форми логіки висловлювань

Серед нормальних форм логіки висловлювань виді­ляють:

а) кон’юнктивну нормальну форму (КНФ);

б) диз’юнктивну нормальну форму (ДНФ);

в) досконалу кон’юнктивну нормальну форму (ДКНФ);

г) досконалу диз’юнктивну нормальну форму (ДДНФ);

д) скорочену кон’юнктивну нормальну форму (СКНФ);

е) скорочену диз’юнктивну нормальну форму (СДНФ).

Кожна із цих формул має свій власний спосіб утворення і розв’язує характерні для неї задачі.

а) Кон’юнктивна нормальна форма (КНФ)

Перш ніж аналізувати КНФ зробимо одне зауваження.

У сучасній логіці існує таке поняття як «проблема розв’язання». Воно уточнюється стосовно кожного розділу сучасної логіки. В алгебраїчній системі логіки висловлю­вань цю проблему можна визначити так:

«Проблема розв’язання — це встановлення ефектив­ної процедури, яка кінцевим числом кроків дозволяє встановити чи є дана формула тотожно-істинною, чи тотожно-хибною, чи виконуваною».

У S¹ такими процедурами є:

1) побудова таблиць істинності і

2) зведення формули до КНФ і ДНФ.

Про таблиці істинності йшлося вище. Розглянемо КНФ.

Кон’юнктивною нормальною формою (КНФ) є кон’юнкція елементарних диз’юнкцій.

КНФ записується так:

У другій формулі кон’юнктивний член С розглядається як вироджена диз’юнкція з одним диз’юнктом. Будь-яку формулу логіки висловлювань можна звести до КНФ.

Для того щоб звести формулу до КНФ необхідно ви­конати такі дії:

1. За допомогою відповідних законів треба звільнити­ся від ∨, ∞, ⊃, якщо вони наявні у вихідній формулі.

2. Усунути загальне заперечення і подвійне запере­чення відповідно конкретних законів.

3. До отриманої формули застосувати закон дис­трибутивності диз’юнкції по відношенню до кон’юнкції.

За допомогою КНФ розв’язуються такі задачі:

1) є дана формула тотожно-істинною чи ні;

2) чи є формула С наслідком із формул Λ₁, Λ₂,... Λ_n.

Розглянемо зведення формули до КНФ на такому при­кладі:

До цієї формули застосовуємо закон виключення імплі­кації:

Застосовуємо другий закон де-Моргана:

Скористаємося законом подвійного заперечення:

Звернемося до закону дистрибутивності диз’юнкції по відношенню до кон’юнкції:

Ми отримали КНФ. Кожен із кон’юнктів містить диз’юнкцію змінної і її заперечення

тобто тавтологію, а це означає, що вихідна формула є тавтологією.

Формула може мати не одну КНФ. Наприклад, візьмемо формулу

Завдяки структурним особливостям КНФ за зовнішнім її виглядом можна визначити, чи є вихідна формула тав­тологією чи ні.

Наприклад, маємо формулу:

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

Як уже зазначалося, другою задачею, яку розв’язують КНФ, є з’ ясування питання: «Чи є довільна формула логі­чним наслідком із інших формул чи ні?».

Щоб перевірити, чи є довільна формула С наслідком із формул Λ₁, А₂,... А_п, необхідно приєднати через імплі­кацію формулу С до формул Λ₁, Λ₂,... Λ_n а потім отри­маний вираз звести до КНФ.

Якщо отримана КНФ буде тавтологією, то це буде підтвердженням того, що формула С випливає із фор­мул Λι, Λ2,... Λ_n.

Приєднаємо до них імплікативно С:

Зведемо отриману формулу до КНФ:

б) Досконала кон’юнктивна нормальна форма (ДКНФ)

Кожна не тотожно-істинна формула має одну ДКНФ, яка називається досконалою кон’юнктивною нормаль­ною формою.

ДКНФ має такі ознаки:

1) у ДКНФ немає двох однакових кон’юнктів;

2) жоден кон’юнкт не має двох однакових змінних

3) жоден кон’юнкт не має змінної і її заперечення

4) у кожному кон’юнкті наяні всі змінні, що входять до складу вихідної формули.

Щоб привести формулу до ДКНФ, необхідно виконати такі дії:

а) звести вихідну формулу до КНФ;

б) співставити отриману КНФ із перерахованими ознаками ДКНФ;

в) якщо в якомусь із кон’юнктів відсутня змінна, що

наявна у вихідній формулі, то необхідно диз’юнктивно приєднати до цього кон’юнкта протиріччяа

потім застосувати закон дистрибутивності диз’юнкції по відношенню до кон’юнкції.

За допомогою ДКНФ розв’язують задачу знаходження всіх логічних наслідків із даних формул.

Наведемо приклади.

Приведемо цю формулу до ДКНФ. Спочатку отримаємо КНФ.

Отримали КНФ. Тепер співставимо її з ознаками ДКНФ. Виявляється, що в першому кон’юнкті відсутня змінна А, яка є у вихідній формулі. Припишемо диз’юн­ктивно до першого кон’юнкту протиріччя (А ∧ A ) і засто­суємо закон дистрибутивності диз’юнкції по відношенню до кон’юнкції.

Отже, ми отримали ДКНФ, яка дає можливість огля­нути всі логічні наслідки із даних формул. Цими нас­лідками є:

Дана ДКНФ представляє всі можливі наслідки із да­них формул. Якщо до вихідної формули 1 приєднати ім- плікативно будь-який із законів, то отримана формула бу­де тавтологією.

в) Скорочена кон’юнктивна нормальна форма (СКНФ)

СКНФ має такі ознаки:

1) Жоден кон’юнкт не утримує двох однакових змін­них (А V В V А);

2) У СКНФ відсутні два однакових кон’юнкти;

3) У СКНФ відсутні кон’юнкти, до складу яких вхо­дить змінна і її заперечення.

Щоб привести формулу до СКНФ, необхідно виконати такі дії:

1) отримати із вихідної формули КНФ;

2) співставити отриману КНФ із ознаками СКНФ;

3) до отриманого виразу послідовно застосовувати закони виявлення і закони поглинання.

Завдяки СКНФ розв’язують задачу знаходження всіх простих наслідків із кон’юнкції заданих формул.

За допомогою ДКНФ знаходять всі логічні наслідки із даних формул. Але виникає потреба знайти лише прості наслідки.

Простим наслідком називається такий наслідок, який не поглинається ніяким, більш сильним, наслід­ком^[XXXVII]. _

Ми отримали КНФ. Співставимо її з ознаками СКНФ. Потім до формули 2 послідовно застосуємо закони вияв­лення і закони поглинання.

Формула 3 отримана у результаті застосування закону ви­явлення (19) до 2 формули.

Формула 4 отримана у результаті застосування закону поглинання (22) до формули 3. Отже, кожен із кон’юн- ктів є простим наслідком.

Розглянемо ще одни приклад. _ _

Перейдемо до розгляду групи диз’юнктивних нормаль­них форм.

г) Диз’юнктивна нормальна форма (ДНФ)

Кожна формула в S¹ може бути приведена до ДНФ.

Диз’юнктивною нормальною формою даної формули на-

Щоб привести формулу до ДНФ, необхідно виконати такі дії:

1) за допомогою відповідних законів послідовно звіль­нитися відякщо вони є у вихідній формулі;

2) віднести загальне заперечення до елементарних висловлювань;

3) застосувати до отриманої формули закон дис­трибутивності кон’юнкції по відношенню до диз’юнкції.

ДНФ дозволяє встановити, чи є довільна формула тотожно-хибною чи ні.

В отриманій ДНФ у восьмому рядку кожен диз’юнкт має змінну і їі заперечення, а це означає, що дана фор­мула тотожно-хибна.

д) Досконала диз’юнктивна нормальна форма (ДДНФ)

Кожна не тотожно-хибна формула в S¹ має одну доско­налу диз’юнктивну форму.

ДДНФ має такі характерні ознаки:

1) у ДДНФ немає двох однакових диз’юнктів;

2) жоден диз’юнкт не містить змінної і їі заперечення;

3) жоден диз’юнкт не має двох однакових змінних;

4) кожен диз’юнкт містить всі змінні, що наявні у вихідній формулі.

Щоб привести формулу до ДДНФ, необхідно викона­ти такі дїі:

1) звести формулу до ДНФ;

2) співставити отриману ДНФ з ознаками ДДНФ;

3) якщо в якомусь диз’юнкті не вистачає змінноі, яка є у вихідній формулі, то до нього потрібно кон’юн- ктивно приписати диз’юнкцію цієі змінноі і іі запере­чення

За допомогою ДДНФ розв’язують задачу огляду всіх гіпотез даноі формули.

Дефініція. «Гіпотезою формули В називається така формула А, якщо А ⊃ В є тотожно-істинною формулою».

Диз’юнкти ДДНФ даної формули є різні гіпотези, при істинності яких дана формула істинна.

Наприклад, приведемо до ДДНФ формулу:

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

Кожен кон’юнкт отриманої КНФ має змінну і її запере­чення, а це означає, що A ∧ B дійсно є гіпотезою для ви­хідної формули.

Розглянемо скорочену диз’юнктивну нормальну форму.

е) Скорочена диз’юнктивна нормальна форма (СДНФ)

Скороченою диз’юнктивною нормальною формулою є ДНФ, якій притаманні такі характерні ознаки:

1) у жодному диз’юнкті немає двох однакових кон’юн- ктів;

2) якщо є два однакових диз’юнкти, то один з них скорочується;

3) жоден диз’юнкт не містить змінної і її заперечення.

Для того, щоб привести формулу до СДНФ, необхідно виконати такі дії:

1) привести вихідну формулу до ДНФ;

2) співставити отриману ДНФ із ознаками СДНФ;

3) послідовно застосувати до отриманого виразу за­кони виявлення і закони поглинання.

За допомогою СДНФ знаходять всі прості гіпотези довільної формули.

Дефініція. «Гіпотеза А формули В називається про­стою, якщо вона не поглинається ніякою іншою гіпоте­зою формули В».

Наприклад, візьмемо формулу:

Знайдемо всі її прості гіпотези, тобто приведемо її до СДНФ.

Формула у 4 рядку є ДНФ вихідної формули. Приведе­мо її до СДНФ. Для цього послідовно застосовуємо закони виявлення і закони поглинання.

Ми отримали чотири прості гіпотези:

Якщо імплікативно приєднати до будь-якої гіпотези вихідну формулу, то отримаємо тавтологію:

Зведемо цю формулу до КНФ:

>

Розглянемо ще один приклад.

Знайдемо прості гіпотези для формули

Остання формула є СДНФ, яка містить всі прості гіпо­тези вихідної формули.

Ознайомленням із нормальними формами завершується аналіз характерних особливостей S¹ і тих завдань, які вони розв’язують. ^{[38] [39] [40] [41]}

4. Синтаксис метамови в S¹.

5. Семантика метамови в S¹.

6. Характеристика завдань, які розв’язуються засобами S¹.

7. Структура алфавіту S¹.

8. Визначення нелогічних термінів.

9. Характеристика логічних символів.

10. Дефініція формули.

11. Типологія формул за синтаксичними ознаками.

12. Поняття підформули.

13. Поняття степеня формули.

14. Способи розстановки дужок у формулі.

15. Визначення головного логічного знака у формулі.

16. Порядок виконання дій над формулою.

17. Фіксація логічної форми висловлювань природної мови за­собами словника S¹.

18. Характерні особливості бездужкової логічної мови Я. Лу- касевича.

19. Семантика метамови.

20. Поняття інтерпретації.

21. Правила інтерпретації Sem ML в S¹.

22. Таблиці істинності.

23. Порядок побудови таблиці істинності.

24. Типологія формул за семантичними ознаками.

25. Тавтології і логічні закони.

26. Поняття рівносильної формули.

27. Характеристика відношення рівносильності.

28. Основні закони логіки та їх функції.

29. Відношення сумісності за істинністю між формулами.

30. Відношення сумісності за хибністю між формулами.

31. Відношення логічного слідування.

32. Поняття нормальної форми логіки висловлювань.

33. Проблема розв’язання в S¹.

34. КНФ, способи її отримання, і задачі, які вона розв’язує.

35. ДКНФ, способи її отримання і задачі, які вона розв’язує.

36. Характерні особливості СКНФ, способи отримання і задачі, які вона розв’язує.

37. ДНФ, способи отримання і задачі, які вона розв’язує.

38. ДДНФ, способи її отримання і задачі, які вона розв’язує.

39. СДНФ, способи її отримання і задачі, які вона розв’язує.

40. Перевірити, чи є формулами логіки висловлювань такі ви­рази: