Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Теорема 1.6.1. (критерій 1 логічного наслідку). Формула В логічно слідує з множини формул m A A A ,... , 2 1 тоді і тільки тоді, коли формула B A A A m 2 1 є тавтологією. Наслідки: 1) якщо серед посилок є хоч одна тотожно хибна, то будь-яка логічна формула В буде логічним наслідком з цих посилок; 2) якщо B , то B A A A m ,... , 2 1 для будь-яких m i A i , 1 , Теорема 1.6.2. (критерій 2 логічного наслідку). Формула В логічно слідує з множини формул m A A A ,... , 2 1 тоді і тільки тоді, коли формула B A m логічно слідує з множини формул 1 2 1 ,... , m A A A Наслідок. Формула В логічно слідує з множини формул m A A A ,... , 2 1 тоді і тільки тоді, коли формула )...) ...( ( 2 1 B A A A m є тавтологією. Теорема 1.6.3 .Для логічного слідування мають місце такі властивості: 1. m i A A A A i m , 1 , ,... , 2 1 (властивість рефлексивності); 2. якщо B A і C B то C A (властивість транзитивності); 3. якщо B A A A m ,... , 2 1 і А – довільна формула, то B A A A A m , ,... , 2 1 (приєднання довільної формули алгебри висловлень до числа посилок не порушує даного логічного слідування); 4. якщо B A A A m ,... , 2 1 і , i A то B A A A A m i i ,..., ,..., 1 1 1 (вилучення з числа посилок формули, яка є тавтологією, не порушує логічного слідування). Розглянемо основні схеми логічного слідування, які характеризують структуру правильного логічного мислення. 1. Правило МР (modus ponens): B B A A , 41 Тут і далі використовуємо нотацію, в якій над рискою записують посилки, під рискою – висновок, тобто цей запис означає B B A A , . Це правило має кілька назв: правило висновку, правило відокремлення. 2. МТ (modus tollens): A B B A , 3. Правило вилучення кон’юнкції: B B A A B A , 4. Правило введення кон’юнкції: B A B A , 5. Правило вилучення диз’юнкції: C B A C B C A , 6. Правило введення диз’юнкції: B A B B A A , 7. Правило силогізму: C A C B B A , 8. Правило контрапозиції: A B B A , 9. Узагальнення правила введення кон’юнкції: ) , 1 , , 1 ( , ,..., , 2 1 2 1 k j m i A A A A A A j i i i m k Для перевірки того, чи є дана формула В логічним наслідком із даних гіпотез m A A A ,... , 2 1 - можна скористатися теоремами 1.6.1 та 1.6.2, або провести ланцюжок міркувань, застосовуючи схеми логічного слідування. Процес потрібно продовжувати до тих пір, поки не одержимо формулу В. Всі проміжні формули, які при цьому одержуються, будуть також логічними висновками гіпотез. Приклад 3. Перевірити, чи має місце логічне слідування B A , B C C і якщо так, то побудувати дедуктивний ланцюжок міркувань, який веде від посилок до висновку. Пересвідчимося, що формула C B C B A є тавтологією: C B C B A C B C B A C B C B A 1 C B B A C C B A . Тому логічне слідування має місце. Тепер побудуємо дедуктивний ланцюжок: 42 1. B A ; 2. В (отримаємо з 1. за правилом вилучення кон’юнкції ); 3. B C ; 4. C (з 2. і 3. за правилом МТ); 5. C C (на основі закону C C і правила вилучення кон’юнкції); 6. С ( з 4. і 5. за правилом МР). З логічним слідуванням пов’язане питання про сумісність формул алгебри висловлень. Означення. Множина формул Г = n m n x x x A x x x A ,..., , ,..., ,..., , 2 1 2 1 1 логіки висловлень називається сумісною, якщо існує хоча б один набір логічних змінних n x x x ,..., , 2 1 , при якому 1 2 1 m A A A Множина формул, яка не є сумісною називається суперечливою. Теорема 1.6.4. Якщо Г – суперечлива множина формул алгебри висловлень, то для довільної формули В має місце слідування Г B Приклад 4. Чи буде суперечливою множина формул: b a , c a , c a , b c ? Знайдемо для кожної формули множину наборів пропозиційних змінних, де вона набуває істинних значень, тобто її область істинності: 1 , 1 , 1 , 0 , 1 , 1 \ 1 , 0 1 \ 1 , 0 , , 3 3 1 b a c b a I , 1 , 1 , 0 , 1 , 0 , 0 \ 1 , 0 1 \ 1 , 0 , , 3 3 2 c a c b a I , 0 , 0 , 0 , 0 , 1 , 0 \ 1 , 0 1 \ 1 , 0 , , 3 3 3 c a c b a I , 1 , 0 , 1 , 1 , 0 , 0 \ 1 , 0 1 \ 1 , 0 , , 3 3 4 b c c b a I Оскільки, 0 , 0 , 1 4 3 2 1 I I I I , то дана множина формул не є суперечливою. Можна задачу поставити іншим чином, наприклад: знайти всі формули В, які є логічними висновками з даних гіпотез m A A A ,... , 2 1 Всяка тотожно істинна формула (тавтологія) є логічним висновком з будь- якої системи гіпотез (бо завжди |А→1| = 1) і логічними висновками з тотожно істинних гіпотез є будь-які тотожно істинні формули, і тільки вони (бо |1→В| = 1 тоді і тільки тоді, коли |В| = 1). Тоді, за умов, що не всі гіпотези m A A A ,... , 2 1 є 43 тавтологіями, і серед логічних висновків з них не враховуватимемо тавтологій, справедлива наступна теорема. Теорема 1.6.5. Формула В є логічним наслідком з гіпотез m A A A ,... , 2 1 тоді і тільки тоді, коли, коли елементарні диз’юнкції ДКНФ(В) містяться серед елементарних диз’юнкцій ДКНФ ( m A A A 2 1 ). Існують комп’ютерні програми, які розроблено для автоматизації міркувань, що виконуються за допомогою доведення логічних теорем. У багатьох із цих програм використано правило виведення, відоме як резолюція. Правило резолюції було запропоноване у 1930 році Жаком Ербраном для доведення теорем у формальних системах першого порядку. На основі правила резолюції Джон Алан Робінсон у 1965 році запропонував метод резолюцій автоматичного доведення логічних теорем, який базується на доведенні від супротивного. Нехай потрібно довести, що істинна деяка формула А. Тоді розглядаємо заперечення формули А, і зводимо A до кон’юнктивної нормальної форми (КНФ). Нагадаємо, що КНФ – це формула, що рівносильна даній формулі і є кон’юнкцією диз’юнктивних одночленів n D D A 1 , де i D - є диз’юнкція скінченного числа пропозиційних змінних або їй заперечень (літералів). Тим самим формується множина диз’юнктів n D D K ,..., 1 - клаузальна множина. Два диз’юнкти, що містять пропозиційні змінні з протилежними знаками, - контрарні літерали, наприклад, x D D x D D k k i i / / , , формують третій диз’юнкт – резольвенту / / k i D D , з якої виключено контрарні літерали, Тобто має місце правило логічного виводу, що носить назву правила резолюції: / / / / , k i k i D D x D x D Для його обґрунтування, досить переконатися, що має місце тавтологія / / / / k i k i D D x D x D Дійсно, виконуючи ланцюг рівносильних перетворень, одержимо: / / / / / / / / k i k i k i k i D D x D x D D D x D x D / / / / / / / / k k i i k i k i D x D D x D D D x D x D 1 1 / / / / / / / / / / k i k i k k k i i i D D D x D x D x D D D x D D 44 Поступово застосовуючи правило резолюції до множини диз’юнктів прагнемо отримати порожній диз’юнкт. Поява порожнього диз’юнкта вказує на протиріччя, оскільки порожня резольвента одержується з двох суперечних диз’юнктів x та x , кожен з яких є логічним наслідком формули A . Це завершує доведення висновком, що A хибне, отже А істинне. Дж. Робінсон показав, що метод резолюції є коректним і повним в тому розумінні, що порожній диз’юнкт виводиться із вхідної множини диз’юнктів шляхом деякої послідовності кроків резолюції тоді і тільки тоді, коли множина диз’юнктів суперечлива. Саме по собі правило резолюції утворює повну систему правил виводу для множини диз’юнктів логіки висловлень. Іншими словами, при використанні одного правила резолюції можна вивести будь-який наслідок з множини формул, які подані у вигляді множини диз’юнктів. Приклад 5. Довести логічний наслідок методом резолюцій: S Q P R Q P , Q S P Посилки уже записані у кон`юнктивній нормальній формі. Отже, їм відповідатиме така множина диз’юнктів: R Q P , S Q P Подамо заперечення висновку у кон`юнктивній нормальній формі Q S P Q S P Q S P ) ( Отже, отримали таку клаузальну множину: Q S P S Q P R Q P , , , , Для окремої зручності запишемо елементи (диз’юнкти) цієї множини в позначеннях: 1 = ; R Q P 2 = ; R Q P 3 = P ; 4 = ; S 5 = Q До диз’юнктів 5 1 застосуємо резолюційний процес. Застосувавши правило резолюцій до диз’юнктів 3 і 2 , дістанемо резольвенту 6 = S Q 6 і 4 породжують резольвенту 7 = Q , а 7 і 5 породжують порожній диз’юнкт □. Це означає, що співвідношення має місце. Алгоритм резолюційного процесу зручно подати у вигляді дерева. Так, для наведеного прикладу дедуктивне дерево матиме такий вигляд: S Q P P S Q S 45 Q Q □ Зазначимо, що оскільки доведення логічного слідування Q S P з припущень R Q P і S Q P рівносильне дослідженню формули Q S P S Q P R Q P на тотожну істинність, то задачу можна розв’язувати й як перевірку на невиконуваність заперечення цієї формули. Подамо заперечення її в кон`юнктивній нормальній формі: Q S P S Q P R Q P Отже, маємо такий самий, як і в попередньому випадку, набір диз’юнктів. Застосувавши до них резолюційний процес, отримуємо порожній диз’юнкт. А це означає, що заперечення формули є суперечністю. Отже, сама формула є тавтологією. Запитання для самоконтролю 1. Яка формула В логічно слідує (називається логічним наслідком) з формул m A A A ,... , 2 1 ? 2. Як узгоджується позначення логічного наслідку та тавтології? 3. Які міркування називають логічними, а висновок правильним? 4. Сформулюйте критерії 1 та 2 логічного наслідку. 5. Які властивості має відношення логічного наслідку? 6. Як формулюються наступні схеми логічного слідування: 1) modus ponens, 2) modus tollens, 3) правило вилучення кон’юнкції, 4) правило контра позиції, 5) правило вилучення диз’юнкції, 6) правило введення диз’юнкції, 7) правило силогізму, 8) правило введення кон’юнкції? 7. Яка множина формул алгебри висловлень називається сумісною (суперечливою)? 8. Як шукати логічні наслідки з гіпотез m A A A ,... , 2 1 , що не всі є тавтологіями? 9. Яке правило логічного слідування носить назву правила резолюції? 10. В чому суть методу резолюцій? В яких задачах можна його використовувати? ВПРАВИ 1.44 Чи правильно стоїть знак логічного наслідку у співвідношеннях: a) c b a c b a c b a , ; b) c a b a b c b c b a , , ; 46 c) a b a b a , ; d) b a d b d c b a , , ; e) d b a f e c f e d c b a , , 1.45. Довести, що для довільних формул А, В, С алгебри висловлень мають місце співвідношення логічного наслідку: a) МТ (modus tollens): A B B A , ; b) Правило вилучення кон’юнкції: B B A A B A , ; c) Правило введення кон’юнкції: B A B A , ; d) Правило вилучення диз’юнкції: C B A C B C A , ; e) Правило введення диз’юнкції: B A B B A A , ; 1.46. Пересвідчитись, що для довільних формул А, В, С алгебри висловлень справедливі твердження: a) з B A та C B випливає C A ; b) з C B A , випливає C B A ; c) з B A випливає A B ; d) з C B A випливає C B A ; e) якщо B A тавтологія, то B A і A B ; f) якщо B A тавтологія, то і A B ; 1.47 Користуючись поняттям логічного наслідку з’ясувати, чи є логічними наступні міркування: a) Якщо Іван є учасником олімпіади з математики, то він обов’язково розумний і добре володіє матеріалом. Але він не учасник цієї олімпіади. Отже, він або не розумний, або ж не володіє матеріалом. b) Студент не складе екзамен, якщо погано підготується до нього або захворіє. Якщо ж він не складе екзамен, то не буде отримувати стипендію. Але студент не 47 хворий. Отже, якщо студент погано підготується до екзамену, то він не матиме стипендії. c) Якщо число розкладається на добуток s різних простих чисел, то воно має різних дiльникiв. Дане число має точно різних дiльникiв. Отже, воно розкладається на добуток s різних простих чисел; d) Якщо заданий чотирикутник – ромб, то його діагоналі взаємно перпендикулярні. Якщо діагоналі чотирикутника не взаємно перпендикулярні, то він не є квадратом. Якщо даний чотирикутник – квадрат, то його можна вписати в коло. Неправильно, що даний чотирикутник не можна вписати в коло, або його діагоналі взаємно перпендикулярні. Отже, даний чотирикутник не є ні ромбом, ні квадратом; e) Якщо Іван поїде в Київ, то Сергій поїде в Одесу. Іван поїде в Київ або в Донецьк. Якщо Іван поїде в Донецьк, то Роман залишиться дома. Але Роман дома не залишиться, отже, Іван поїде в Київ. 1.48 Перевірити, чи буде суперечливою множина формул: a) c b a c b a , ; b) c b a c b a c b a , , ; c) a c b c b a , , ; d) c a c a b c b a , , , 1.49 Перевірити, чи є сумісною множина висловлень: a) Якщо контрольна робота буде на наступному тижні, то Наташа підготується до неї. Вона не підготується до контрольної роботи, якщо поїде на змагання. Наташа поїде на змагання тоді тільки тоді, коли одержить стипендію. Контрольна робота буде на наступному тижні і Наташа не одержить до того часу стипендії. b) Якщо водій автобуса порушив правила руху, то свідок говорить правду. Якщо в момент аварії на світлофорі було зелене світло, то свідок говорить неправду. Мотоцикліст порушив правила руху тоді і тільки тоді, коли на світлофорі в момент аварії було зелене світло. Як водій автобуса,так і мотоцикліст порушили правила руху; c) Якщо курс цінних паперів росте або зменшується процентна ставка, то або падає курс акцій, або податки не збільшуються. Курс акцій падає тоді і тільки тоді, коли росте курс цінних паперів і збільшуються податки. Якщо зменшується 48 процентна ставка, то або курс акцій не падає, або курс цінних паперів не росте. Або збільшуються податки, або падає курс акцій і зменшується процентна ставка. 1.50 Знайти всі нерівносильні між собою і не тотожно істинні формули алгебри висловлень, які є логічними наслідками множини формул: a) a c b c b a , , ; b) c a c a b c b a , , , ; c) c b a c a а b a , , ; d) b a c b a c a , , 1.51 Довести логічний наслідок методом резолюцій для схем із завдання 1.45. 1.52 Користуючись методом резолюцій перевірити, чи є формула тавтологією: a) ) ( b a c b a ; b) c a b a c b a ; c) c b a c a b a ; d) c b a c b c a ; e) a b b a |