Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Закріпимо цей матеріал на прикладі.



Нехай ми маємо довільну формулу p /\ (p ® q). Треба з’ясувати – тотожно істинна вона чи ні?

Насамперед, зводимо її до нормальної форми (НФ), бо другий кон’юнктивний член є імплікацією (p®q). Застосовуємо рівносильність (13) і отримуємо нормальну форму формули p /\ (p ® q), а саме: p /\ (~p \/ q). З огляду формули визначаємо, що змінна „q” входить у формулу нерегулярно, а змінна „p” входить регулярно (із знаком заперечення ~p і без нього – p).

Згідно з п.3 замість нерегулярної змінної підставляємо символ „х” (хиба) і отримуємо формулу: p /\ (~p \/ х). За рівносильністю (50) отримуємо ~p, оскільки (~p \/ х = ~p). Тепер формула набуває вигляду (p /\ ~p). Отже, дана формула не містить нерегулярно вхідних змінних. Тепер чинимо за п.5(а): замість регулярно вхідної змінної (p і ~p) підставляємо символ „і” (істина) і отримуємо вираз: і /\ ~і. Оскільки ~і (не-істина) за рівносильністю (43) є „х” (хибою), то маємо вираз (і /\ х). Так як (і /\ х) за рівносильністю (48) дає нам хибу („х”), то увесь вираз є хибним: і /\ х = х.

Далі діємо за п.5(б): замість регулярно вхідної змінної p підставляємо знак хиби („х”) і отримуємо вираз х /\ ~х. Знаючи, що за рівносильністю (44) ~х = і, маємо вираз: х /\ і, який за рівносильністю (48’) рівний хибі („х”): х /\ і = х.

Отже, результат підстановки у формулу p /\ ~p за пп. 5 (а) та (б) значень „і” та „х” в обох випадках – значення „х” (хиба). Такий результат дає підстави вважати, що зведена до нормальної форми формула p /\ (p ® q) є тотожно хибною, а отже, репрезентоване нею доведення (спростування) є некоректним.

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

 

Завдання.Обґрунтуйте вивідність тези q із аргументів: (a1) p®q та (a2) p розв’язковою процедурою логіки висловлень, звівши адекватну структуру доведення до нормальної форми.

Відповідь.З’єднавши аргументи кон’юнкцією (p ® q) /\ p і приєднавши тезу q імплікацією, утворюємо формулу, що репрезентує доведення: ((p ® q) /\ p) ® q. Отриману формулу зводимо до нормальної форми (НФ): ((p ® q) /\ p) ® q

~((p®q) /\ p) \/ q (13)

(~(p®q) \/ ~p) \/ q (10)

(~(~p \/ q) /\ ~p) \/ q (13)

((~~p /\ ~q) /\ ~p) \/ q (11)

(p /\ ~q) /\ (~p \/ q) (1) НФ

Оскільки змінні p і q входять у формулу нормальної форми регулярно (p і ~p та q і ~q), то застосовуємо припис за п.5 (а, б) до формули (p /\ ~q) \/ (~p \/ q):

а) (p /\ ~q) \/ (~p \/ q) б) (х /\ ~q) \/ (~х \/ q)

/\ ~q) \/ (~і \/ q) х \/\/ q)

~q \/\/ q) х \/ і

~q \/ q і

 

аа) ~q \/ q аб) ~q \/ q

\/ і ~х \/ х

х \/ і і \/ х

і і

Оскільки формула (p /\ ~q) \/ (~p \/ q) набирає значення „істина” (і) в обох випадках, тобто в пп. (б), (аа) та (аб), то маємо підставу вважати, що формула, яка репрезентує доведення {((p ® q) /\ p) ® q}, є тотожно істинною, а отже, доведення тези q на основі аргументів p®q та p є коректним.

Розв’язання можна подавати без пояснення.

 

Завдання.Обґрунтуйте вивідність тези (p /\ q) з аргументів: (a1) p та (a2) q розв’язковою процедурою логіки висловлень за формулою: p ® q ® (p /\ q).

Відповідь.p ® q ® (p /\ q)

~p \/ (~q /\ (p /\ q)) (НФ)

 

а) ~і \/ (~q \//\ q)) б) ~х \/ (~q \//\ q))

х \/ (~q /\ q) і \/ (~q \/ х)

~q \/ q і \/ ~q

і

аа) ~і \/ і аб) ~х \/ х

х \/ і і \/ х

і і

Отже, теза (p /\ q) випливає з аргументів p і q.

У ролі розв’язкових процедур можна використовувати також методи редукції (зведення) формул, що репрезентують доведення чи спростування, шляхом еквівалентних перетворень до таких форм: кон’юнктивної нормальної форми (КНФ), диз’юнктивної нормальної форми (ДНФ), досконалої кон’юнктивної нормальної форми (ДКНФ), досконалої диз’юнктивної нормальної форми (ДДНФ), скороченої кон’юнктивної нормальної форми (СКНФ), скороченої диз’юнктивної нормальної форми (СДНФ).

Розглянемо ці форми в зазначеному порядку.

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

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

Застосовуючи розв’язкову процедуру зведення формули до КНФ чи ДНФ, можна для будь-якої формули з довільного списку формул А1, А2 ,... Аn розв’язати завдання: чи є формула В логічним наслідком із сукупності засновків А1, А2 ,... Аn ,чи ні.

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

Насамперед, нагадаємо, що кон’юнктивна нормальна форма (КНФ) є кон’юнкцією елементарних диз’юнкцій, еквівалентній даній формулі. Формула є КНФ, якщо вона має нормальну форму і в ній немає підформул вигляду (А \//\ С)) та ((В /\ С) \/ А).

Щоб звести будь-яку формулу до КНФ, треба спершу звести її до НФ, а відтак за допомогою рівносильностей (6) та (6’) отримати формулу, що має КНФ. Рівносильності (6) і (6’) є дистрибутивними законами:

(6) А \//\ С) = (А \/ В) /\\/ С)

(6’) (В /\ С) \/ А = (А \/ В) /\\/ С)

Нехай нам треба знайти КНФ формули (p /\ (p ® q)) ® q.

Спершу зводимо її до НФ:

(p /\ (p ® q)) ® q

~(p /\ (p ® q) \/ q (13)

~(p /\ (~p \/ q)) \/ q (13)

~p \/ ~(~p \/ q) \/ q (10)

~p \/ (~~p /\ ~q) \/ q (11)

~p \/ (p /\ ~q) \/ q (1)

(~p \/ q) \/ (p /\ ~q) – закон асоціативності

(~p \/ q \/ p) /\ (~p \/ q \/ ~q) (6) закон дистрибутивності (КНФ)

Отримана формула (~p \/ q \/ p) /\ (~p \/ q \/ ~q) є КНФ формули (p ® (p ® q)) ® q. Навіть з вигляду КНФ можна зробити висновок, що КНФ – тотожно істинна, бо містить в підформулах змінні із запереченням і без нього: ~p \/ p та q \/ ~q, які є тотожно істинними.

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

За допомогою даного методу можна спростовувати демонстрацію.

 

Завдання.З’ясуйте відношення логічного слідування між тезою і аргументами у формулі, що репрезентує доведення: (p \/ q) ® r, де (p \/ q) – аргумент, r – теза.

Розв’язок.(p \/ q) ® r

~(p \/ q) \/ r (13)

(~p /\ ~q) \/ r (11)

(~p \/ r) /\ (~q \/ r) (6’) КНФ

Отже, КНФ не є тотожно істинною. Звідси випливає висновок про те, що між тезою r і аргументом (p \/ q) відсутнє відношення логічного слідування. Таким чином, доведення є некоректним.

 

Вправа.Зведіть до КНФ формулу p ® (p \/ q) та обґрунтуйте вивідність тези-наслідку із аргумента-засновку p.

Розв’язок.p ® (p \/ q)

~p \/ (p \/ q) (13)

(~p \/ p \/ q) КНФ (закон асоціативності)

Формула (~p \/ p \/ q) є тотожно істинною, про що засвідчує наявність у формулі, яка є підформулою самої себе, змінної p із запереченням (~p) і без заперечення (p). Отже, теза (p \/ q) виводиться із аргумента p.

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

За означенням, ДНФ формули є диз’юнкцією елементарних кон’юнкцій, яка еквівалентна цій формулі. Щоб звести формулу до ДНФ, необхідно спершу звести її до НФ, а відтак кожну підформулу вигляду (А /\\/ С)) та ((В \/ С) /\ А) замінити відповідно рівносильними за рівносильностями 7 і 7'.

(7) (А /\\/ С)) = (А /\ В) \//\ С)

(7') ((В \/ С) /\ А) = (А /\ В) \//\ С)

Отримана за рівносильностями 7 і 7’ формула буде диз’юнктивною нормальною формою певної формули.

Нехай нам треба звести до ДНФ таку формулу: ((p ® q) /\ ~q) ® p, яка репрезентує доведення.

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

((p ® q) /\ ~q) ® p

~((~p \/ q) /\ ~q) \/ p (13), двічі

(~(~p \/ q) \/ ~~q) \/ p (10)

((~~p /\ ~q) \/ ~~q) \/ p (11)

((p /\ ~q) \/ q) \/ p (1) НФ

(p \/ q) /\ (~q \/ q) \/ p

(p /\ ~q) \/ (p /\ q) \/ (~q /\ q) \/ (q /\ q) \/ p (7) ДНФ

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

 

Завдання.Чи можливо вивести тезу „r”, якщо доведення постане у вигляді формули (p ® (q ® r)) ® (p ® r).

Відповідь.(p ® (q ® r)) ® (p ® r)

~(~p \/ (~q \/ r)) \/ (~p \/ r) (13) тричі

~~p /\ ~(~q \/ r)) \/ (~p \/ r) (11)

(~~p /\ (~~q /\ ~r)) \/ (~p \/ r) (11)

(p /\ q /\ ~r) \/ (~p \/ r) (1) НФ

(p /\ q /\ ~r /\ ~p) \/ (p /\ q /\ ~r /\ r) (7) ДНФ

ДНФ формули (p ® (q ® r)) ® (p ® r) засвідчує, що теза „r” випливає із аргументів p, q ® r, оскільки обидва кон’юнкти (p /\ q /\ ~r /\ ~p) та (p /\ q \/ ~r /\ r), утвореної ДНФ, містять у собі змінні, які входять один раз із запереченням, а другий раз – без заперечення. Отже, ДНФ вихідної формули є тотожно хибною. Це означає, що теза „r” випливає із вказаних аргументів.

 

Завдання.Чи можливе коректне доведення, якщо воно репрезентоване наступною формулою: ((p ® q) /\ ~q) ® ~p

Відповідь.((p ® q) /\ ~q) ® ~p

~((~p \/ q) /\ ~q) \/ ~p

~(~p \/ q) \/ ~~q) \/ ~p

(~~p /\ ~q) \/ (~~q \/ ~p)

(p /\ ~q) \/ (q \/ ~p) НФ

(p /\ ~q /\ q) \/ (p /\ ~q /\ ~p) ДНФ

Оскільки ДНФ є тотожно хибною, то доведення, репрезентоване формулою (p ® q) /\ ~q) ® ~p, є коректним.

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

Щоб використати ДКНФ в якості методу, мусимо запам’ятати таку умову: кожна не тотожно істинна формула, що має кон’юнктивну нормальну форму (КНФ), називається досконалою.

Щоб отримати досконалу кон’юнктивну нормальну форму з будь-якої нетотожно істинної формули, треба:

· звести формулу до КНФ;

· викреслити з КНФ усі повторювані кон’юнкти і залишити один (напр., (p \/ q) /\ (q \/ p) або p /\ p, q /\ q і т. ін.), за рівносильностями: (2) А /\ В = В /\ А, (4) А \/ В = В \/ А, (8) А /\ А = А;

· викреслити усі повторювання в кон’юнктивних членах КНФ і залишити один на основі рівносильності (4) А \/ В = В \/ А та (9) А \/ А = А;

· вилучити з КНФ ті кон’юнктивні члени, які є тотожно істинними елементарними диз’юнкціями, послуговуючись рівносильностями: (47) А /\ і = А і (47’) і /\ А = А;

· до всіх кон’юнктивних членів, де відсутня змінна, яка значиться у вихідній формулі приписати (на основі рівносильності (50) х \/ А = А або (50’) А \/ Х = А) знак диз’юнкції „ \/ ” і услід за ним тотожно хибну кон’юнкцію (Е /\ ~Е) відсутньої змінної, а відтак застосувати правило заміни за рівносильністю (6) А \//\ С) = (А \/ В) /\\/ С) чи (6’) (В /\ С) \/ А = (А \/ В) /\\/ С). Цю процедуру повторювати доти, поки усі відсутні змінні не увійдуть у кожний кон’юнктивний член ДКНФ.

Нехай нам треба звести до ДКНФ формулу (p ® q) ® ((q ® ~p) ® p).

Спершу зводимо її до НФ, а відтак до КНФ:

(p®q)®((q®~p)®p)

(~p \/ q)®((~~q \/ ~p)®p) (13), двічі

~(~p \/ q) /\ ~(~~q \/ ~p) /\ p (13), двічі

(~~p /\ ~q) /\ (~~~q /\ ~~p) /\ p) (11), двічі

(p /\ ~q) \/ (~q /\ p) \/ p (НФ) (1) тричі

(p \/ p) /\ (p \/ ~q) /\ (p \/ ~q) /\ (p \/ p) (КНФ)

Отримавши КНФ, зводимо її за нашим приписом до ДКНФ:

(p \/ p) /\ (p \/ ~q) /\ (p \/ ~q) /\ (p \/ p)

Викреслюємо повторення і отримуємо формулу:

p /\ (p \/ ~q) /\ p

Виявлені повторення усуваємо:

p /\ (p \/ ~q)

Дописуємо відсутню змінну до змінної p:

p \/ (q /\ ~q) /\ (p \/ ~q)

Застосовуємо закон дистрибутивності:

(p \/ q) /\ (p \/ ~q) /\ (p \/ ~q)

Викресливши повторювані кон’юнкти, отримуємо ДКНФ:

(p \/ q) /\ (p \/ ~q).

Отримана формула є ДКНФ формули (p®q)®((q®~p)®p). Звідси робимо висновок про те, що множина усіх можливих наслідків, що випливають з формули (p®q)®((q®~p)®p), є формули p \/ q і p \/ ~q. Оскільки наслідки містять одну із змінних і її заперечення, то ДКНФ є тотожно істинною. Це дає підставу стверджувати: висновок p випливає із засновків у формулі (p®q)®((q®~p)®p).

Якщо доведення чи спростування репрезентувати мовою логіки висловлень, то процедуру зведення до ДКНФ можна використати для розв’язання проблеми пошуку усіх можливих наслідків із засновків у структурі міркування, а заодно й обґрунтування коректності чи некоректності доведення і спростування як логічних дій.

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

Щоб звести формулу до ДДНФ, треба:

· звести її до ДНФ;

· викреслити в ДНФ повторювані диз’юнкти за рівносильностями: (2) А /\ В = В /\ А, (4) А \/ В = В \/ А, та (9) А \/ А = А;

· на основі рівносильностей (2) та (8) А /\ А = А, усунути усі повторення у диз’юнктивних членах ДНФ; з усіх однакових диз’юнктів залишити один і викреслити решту;

· викреслити на основі рівносильностей (50) х \/ А = А ті диз’юнктивні члени, які є тотожно хибними елементарними диз’юнкціями (А /\ ~А);

· до усіх диз’юнктивних членів, в яких відсутня певна змінна, що входить у вихідну формулу, приписати знак диз’юнкції „ /\ ” і услід за ним записати тотожно істинну диз’юнкцію (Е /\ ~Е), наприклад, (p \/ ~p) відсутньої змінної за рівносильністю (47) А /\ і = А, і застосувати правило заміни за рівносильностями (7) (А /\/\ С)) = (А /\ В) /\/\ С) та (7’) ((В \/ С) /\ А) = (А /\ В) /\/\ С);

· якщо в ДДНФ знову з’являються однакові диз’юнктивні члени, то необхідно викреслити повторення.

Отримана у такий спосіб формула є досконалою диз’юнктивною нормальною формою (ДДНФ).

Продемонструємо вищевикладене на прикладі.

Припустимо, ми маємо отримати в процесі формалізації доведення чи спростувати формулу: (p®q) /\ (~q®p).

Оскільки ви вже засвоїли припис зведення формули до НФ та ДНФ, то обійдемося без коментарів:

(p®q) /\ (~q®p)

(~p \/ q) /\ (~~q \/ р)

(~p \/ q) /\ (q \/ р) НФ

(~p /\ q) \/ (~p /\ р) \/ (q /\ q) \/ (q /\ p) (7’)

Викреслюємо повторення і тотожно хибні диз’юнктивні члени. Отримана формула є ДНФ вихідної формули:

(~p /\ q) \/ (q \/ (p /\ q)) ДНФ

Доповнюємо диз’юнкт (q /\/\ ~p)) і утворюємо формулу:

(~p /\ q) \/ (q /\\/ ~p)) \/ (p /\ q)

Застосовуємо закон дистрибутивності до утвореної шляхом доповнення підформули:

(~p /\ q) \//\ q) \/ (~p /\ q) \/ (p /\ q)

Викреслюємо повторення і отримуємо формулу:

(~p /\ q) \//\ q).

Одержані формули ~p /\ q або р /\ q складають оту множину гіпотез (засновків), з яких побудована вихідна формула.

Оволодівши методом зведення формули до ДДНФ, ви можете приступити до розв’язання завдань на пошук аргументів-засновків, з яких виводяться тези-наслідки.

 

Завдання.Знайдіть усі можливі аргументи до тези: (p /\ q) \/ r.