№ p q r p Ú q q É r p Ú r

1. і і і і і і

2. і і х і х і

3. і х і і і і

4. і х х і і і

5. х і і і і і

6. х і х і х х

7. х х і х і і

8. х х х х і х

Із цієї таблиці істинності очевидно, що досліджувані формули є сумісними за істинністю, оскільки у 1, 3, 4, 5 рядках усі формули набувають логічного значення “істина”.

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

Якщо рядок, де формули є одночасно хибними відсутній, тоді вони є несумісними за хибністю.

Розглянемо приклад. Візьмо формули p Ú q; q Ù`r; `p Ù q .

Побудуємо для них спільну таблицю істинності.

№	p	q	r	`p	`r	p Ú q	q Ù`r	` p Ù q
1.	і	і	і	х	х	і	х	х
2.	і	і	х	х	і	і	і	х
3.	і	х	і	х	х	і	х	х
4.	і	х	х	х	і	і	х	х
5.	х	і	і	і	х	і	х	і
6.	х	і	х	і	і	і	і	і
7.	х	х	і	і	х	х	х	х
8.	х	х	х	і	і	х	х	х

У останньому 7 і 8 рядку таблиці істинності усі формули набувають логічного значення “хиба”, а отже вони є сумісними за хибністю.

І нарешті, відношення логічного слідування визначається так: логічне слідування – це відношення, яке існує між засновками і висновком міркування.

Якщо засновки міркування представити у вигляді формули А, а його висновок - у вигляді формули В, тоді можна стверджувати, що із формули А логічно випливає формула В, коли імплікація А É В є законом логіки.

Для позначення логічного слідування у логіці застосовують знак “|=”. Вираз “А |= В” читається так: “із А логічно слідує В”.

На підставі встановлення відношення логічного слідування між засновками і висновком міркування стає можливим встановити його правильність чи неправильність.

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

Щоб встановити правильність міркування необхідно виконати такі дії:

1) формалізувати всі засновки міркування і його висновок;

2) поєднати засновки міркування за допомогою логічного сполучника “Ù” (кон¢юнкція), а висновок приєднати за допомогою - “É” (імплікації).

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

Якщо у останньому стовпчику таблиці істинності утворена формула набуває логічного значення “істина”, тобто виражає логічний закон, тоді можна стверджувати, що із кон’юнкції засновків міркування логічно слідує його висновок, отже, міркування оцінюється як правильне. Якщо ж – ні, тоді – як неправильне.

Наприклад. Перевіримо чи є дане міркування правильним, тобто з’ясуємо чи логічно слідує висновок міркування із його засновків.

“Якщо предмет є цікавим, тоді він - корисний. Предмет є цікавим. Отже, він є корисним”.

Формалізуємо це міркування.

Перший засновок - “Якщо предмет є цікавим, тоді він - корисний” відповідає такій формулі - p É q,

Другий засновок – “Предмет є цікавим” відповідає формулі – p.

Висновок- “Отже, він є корисним” відповідає формулі - q.

Тепер створимо формулу цього міркування, тобто поєднаємо засновки міркування через “Ù” (кон’юнкцію) і приєднаємо до утвореного виразу висновок міркування через “É” імплікацію.

((p É q) Ù p) É q.

Скористаємося таблицею істинності для перевірки правильності цього міркування.

№ p q p É q (p É q) Ù p ((p É q) Ù p) É q

1. і і і і і

2. і х х х і

3. х і і х і

4. х х і х і

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

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

Перевіримо правильність такого виводу, тобто з’ясуємо чи існує між засновками і висновком цього виводу відношення логічного слідування:

А É С; В É С

В É А .

Насамперед, поєднаємо засновки цього виводу за допомогою логічного сполучника «кон’юнкція»,

(А É С) Ù (В É С),

а його висновок приєднаємо до утвореного виразу за допомогою логічного сполучника «імплікація» і отримаємо вираз:

((А É С) Ù (В É С)) É (В É А)

Тепер, знову звернемося до таблиці істинності.

№ А В С А É С В É С В É А (А É С) Ù (В É С) ((А É С)Ù(В É С))É (В É А)

1. і і і і і і і і

2. і і х х х і х і

3. і х і і і і і і

4. і х х х і і х і

5. х і і і і х і х

6. х і х і х х х і

7. х х і і і і і і

8. х х х і і і і і

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

Лекція №5. Нормальні форми логіки висловлювань (2 год.).

Поняття "Проблема розв'язання" у логіці. Кон'юнктивна нормальна форма. Досконала кон'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує. Скорочена кон'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує.

Диз'юнктивна нормальна форма. Досконала диз'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує. Скорочена диз'юнктивна нормальна форма, її ознаки та задачі, які вона розв'язує.

Семінарське заняття № 4-5 (4 год.)

1.Кон'юнктивна нормальна форма. Процедура зведення конкретної формули до КНФ.

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

3.Скорочена кон'юнктивна нормальна форма (СКНФ). її характерні ознаки, алгоритм зведення та задача, яка розв'язується за її допомогою.

4.Диз'юнктивна нормальна форма. Процедура зведення конкретної формули до ДНФ.

5.Досконала диз'юнктивна нормальна форма (ДДНФ). її характерні ознаки, алгоритм зведення та задача, яка розв'язується за її допомогою.

6.Скорочена диз'юнктивна нормальна форма (СДНФ). II характерні ознаки, алгоритм зведення та задача, яка розв'язується за її допомогою.

Контрольні запитання та вправи.

1.Що означає поняття "проблема розв'язання" у алгебраїчній системі логіки висловлювань?

2.Що таке кон'юнктивна нормальна форма?

3.Які задачі вирішуються за допомогою КНФ?

4.Які ознаки має досконала кон'юнктивна нормальна форма?

5.Який алгоритм зведення конкретної формули до ДКНФ?

6.Які ознаки має скорочена кон'юнктивна нормальна форма?

7.Який алгоритм зведення конкретної формули до СКНФ?

8.Що таке диз'юнктивна нормальна форма?

9.Які задачі вирішуються за допомогою ДНФ?

10.Які ознаки має досконала диз'юнктивна нормальна форма?

11.Який алгоритм зведення конкретної формули до ДДНФ?

12.Які ознаки має скорочена диз'юнктивна нормальна форма?

13.Який алгоритм зведення конкретної формули до СДНФ?

14. Приведіть до КНФ такі формули і перевірте чи є вони тотожно-істинними чи ні:

· (А É В) Ú (`А Ù С); · (А É В) É (`А Ú В);

· (А É (В Ù`А)); · ((А Ù В) É С) É ((А Ù`С) É`В));

· ((А É`В) Ù С) Ú (`А É С); · (А É В) Ú ((`А Ù С) É В);

· (А Ú В Ú`А); · ((A É B) Ù (B É C) Ù (A Ú`B)) É C;

· (А Ù С) É (А Ú С);

· (А É В) É (`В É`А); · ((A É B) É ((A Ù C) Ú`B));

· (С Ù D) É (В Ù С); · (`A Ú ((B É B) É A));

· (С Ù В) É (`A Ú D);

· ((`A Ù B) Ú (C Ù A) Ú (`C Ù B) Ú (A Ù B Ù C)).

15. Приведіть до ДКНФ такі формули:

· А « (В Ù`А); · A Ú (B Ù`B);

· (А É В) Ú (`А Ù С); · (A Ù B) Ú (`A Ù`B);

· B Ù (`C Ú D); · (A Ù B Ù C) Ú (`A Ù`B ÙC);

· C É (D Ú B); · (A Ù (`A Ú`B));

· D É (A É B); · (A Ù B Ù`C) Ú (`A Ù`B);

· C « (A É D); · (A « B) Ù (A Ù C).

16. Знайдіть всі логічні наслідки із даних формул:

· А É В, `А É С, В É С; · (А « В), (В « С);

· А É (В É С), А É В; · ((А Ù В) É`С), В, С;

· А É В, `В; · А, (А Ú В) Ú (В É`А), С;

· А É В, В Ú С, ((А Ù В) « С); · А É (В É С), А É А, В.

17. Приведіть формулу до СКНФ:

· А, (А Ù В) É (А Ú С);

· `А É С, `С É В, (`А É`С);

· (А Ú В) É С, (С Ù В) « D.

18. Приведіть до ДНФ такі формули:

(А É В) Ú (`А Ù С); · (`В É`А) Ù (А É В);

· ((А É В) Ù (А É С)) É (А É (В Ù С));

· А Ù (`А Ú`В); · (А Ù (А É В));

· `С Ù (С Ù С); · ((А Ú В) É (А Ù В));

· В É (В Ú С); · ((А Ú`В Ú С) É (А Ù В Ù`С));

· (((А É В) É (В É С)) Ù (`С Ú А).

19. Формула приведена до ДНФ. Отримайте для неї КНФ:

· (А Ù В Ù С) Ú (`А Ù`В) Ú (В Ù С);

· (`А Ù В Ù С) Ú (А Ù`В Ù С) Ú (А Ù`С).

20. Приведіть до ДНФ і КНФ такі формули:

· (А É В) Ù (А É С);

· ((А É`В) É (А É С)) É (А É В);

· ((((А É В) É`А) É`В) É`С) É С;

· ((`А É В) Ù С) Ú (`А « С);

· (А É (В É С)) É ((А É`С) É (А É`В));

· ((А É В) É (С É`А)) É ((`В É`С).

21. Приведіть до ДДНФ такі формули:

А « (В Ù`А); · ((`А Ú`В) Ú (А Ù`В));

· (А É В) Ú (`А Ù С); · (А Ù В Ù С) Ú (А Ù`В);

· В Ù (`С Ú D); · А Ù (`В Ú С);

· С É (D Ú B); · (А Ú В Ú С) Ù (`А Ú В Ú`С);

· D É (A É B); · (А É С) Ù А Ù В;

· C « (A É D);

· (А É В) É (В Ù (С É`А)); · (((А Ú В) Ù С) Ú (С É В));

· (А Ú В) Ù (А Ú`В); · (((А Ù В) Ú (`В ÙС)) Ù`В).

22. Знайдіть усі гіпотези для таких формул:

· ((А É В) É С) É ((С É В) É А);

· (А Ú (В Ù С)) É (`В Ú (В Ù`А Ù С)).

23. Привести до ДКНФ і ДДНФ такі формули:

(А É В) Ú (`А ÙС); · (С É А) É ((В Ú С) É А);

· (А É`В) É (С É В);

· (А É`С) É (`А É В); · ((А Ú С)) Ù (А É В).

24. Знайдіть усі прості гіпотези із таких формул:

(((А Ù В) Ú (C Ù D)) É (A Ù`B Ù C));

· ((A Ù B) Ú ((A É C) É`B)).

РЕКОМЕНДОВАНА ЛІТЕРАТУРА:

[ 1: с. 54-56, 58-59; 2: с. 95-97, 108-111; 4: с. 329 - 340; 23: с. 35-42.; 26: с.177 - 193; 29: с. 41-56.]

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ

(6 год.)

Приведіть до ДКНФ і ДДНФ такі формули:

(А É В) Ú (`А Ù С); (С É А) É ((В Ú С) É А);

Методичні вказівки

Вивчаючи цю тему студентам необхідно засвоїти, що у сучасній логіці існує таке поняття як “проблема розв’язання”.

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

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

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

12 3 4 5