Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
1 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Кіровоградський державний педагогічний університет Імені Володимира Винниченка З.П. Халецька, В.В. Нарадовий МАТЕМАТИЧНА ЛОГІКА ТА ТЕОРІЯ АЛГОРИТМІВ Кропивницький – 2016 2 ББК 22.12:73 УДК 510.5 З.П. Халецька, В.В. Нарадовий Математична логіка та теорія алгоритмів: Навчальний посібник. – Кропивницький: РВВ КДПУ ім.. В. Винниченка, 2017. – 128 с. ISBN Даний посібник охоплює матеріал модулів «Алгебра та числення висловлень», «Логіка предикатів», «Теорія алгоритмів» відповідно до програми курсу «Математична логіка та теорія алгоритмів». Викладення теоретичного матеріалу ілюструється прикладами. В кожному розділі після теоретичного блоку наведено запитання для самоконтролю та вправи для самостійного розв’язання. Посібник рекомендується для студентів всіх спеціальностей денної та заочної форми навчання, які вивчають математичну логіку та теорію алгоритмів. Він може бути корисним вчителям математики та інформатики. Рецензенти: Безущак О.О., заслужений працівник освіти, кандидат фізико-математичних наук, доцент кафедри алгебри та математичної логіки, Київський національний університет імені Тараса Шевченка; Якименко С.М., кандидат фізико-математичних наук, завідувач кафедри вищої математики та фізики, Кіровоградський національний технічний університет. Затверджено до друку Вченою Радою Кіровоградського державного педагогічного університету імені Володимира Винниченка (протокол № 7 від “30” січня 2017 року) ISBN © З.П. Халецька, В.В. Нарадовий, 2017 3 ЗМІСТ ПЕРЕДМОВА ............................................................................................................... 5 1. АЛГЕБРА ВИСЛОВЛЕНЬ ..................................................................................... 6 1.1. ВИСЛОВЛЕННЯ ТА ОПЕРАЦІЇ НАД НИМИ. ФОРМУЛИ АЛГЕБРИ ВИСЛОВЛЕНЬ ..................................................................................................6 1.2 ВІДНОШЕННЯ РІВНОСИЛЬНОСТІ НА БАЗІ АЛГЕБРИ ВИСЛОВЛЕНЬ .......................................................................................................................... 14 1.3 НОРМАЛЬНІ ФОРМИ ФОРМУЛ АЛГЕБРИ ВИСЛОВЛЕНЬ ТА ЇХ ЗАСТОСУВАННЯ. .......................................................................................... 18 1.4 БУЛЕВІ ФУНКЦІЇ. ФУНКЦІОНАЛЬНА ПОВНОТА. ПОЛІНОМИ ЖЕГАЛКІНА ................................................................................................... 23 1.5 ТЕХНІЧНІ ЗАСТОСУВАННЯ АЛГЕБРИ БУЛЕВИХ ФУНКЦІЙ ......... 31 1.6 ВІДНОШЕННЯ ЛОГІЧНОГО НАСЛІДКУ .............................................. 37 2. ЧИСЛЕННЯ ВИСЛОВЛЕНЬ ............................................................................... 49 2.1 АЛФАВІТ, ФОРМУЛИ, АКСІОМИ, ПРАВИЛА ВИВОДУ ЧИСЛЕННЯ ВИСЛОВЛЕНЬ L 1 . ПРИКЛАДИ ДОВЕДЕНЬ В ЧИСЛЕННІ L 1 ..................... 50 2.2. ВИВІДНІСТЬ ІЗ ГІПОТЕЗ. МЕТАТЕОРЕМА ДЕДУКЦІЇ. ДОДАТКОВІ ПРАВИЛА ВИВОДУ....................................................................................... 53 3. ЛОГІКА ПРЕДИКАТІВ ........................................................................................ 59 3.1. ПРЕДИКАТИ ТА ОПЕРАЦІЇ НАД НИМИ. ............................................ 59 3.2. ФОРМУЛИ ЛОГІКИ ПРЕДИКАТІВ. ІНТЕРПРЕТАЦІЯ ФОРМУЛ. ВИКОНУВАНІ ТА ЛОГІЧНО ЗАГАЛЬНОЗНАЧУЩІ ФОРМУЛИ ............ 67 3.3. ВІДНОШЕННЯ РІВНОСИЛЬНОСТІ В ЛОГІЦІ ПРЕДИКАТІВ. ЗВЕДЕНА ТА ПРЕНЕКСНА НОРМАЛЬНІ ФОРМИ ...................................................... 73 3.4. МЕТОД РЕЗОЛЮЦІЙ .............................................................................. 79 3.5. ЗАСТОСУВАННЯ ЛОГІКИ ПРЕДИКАТІВ ........................................... 87 3.5.1 Застосування символіки логіки предикатів в математичних формулюваннях ............................................................................................. 87 3.5.2 Використання елементів математичної логіки для аналізу структури математичних теорем ................................................................................ 88 4 4. ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ ........................................................................ 94 4.1. ПОНЯТТЯ АЛГОРИТМУ. ....................................................................... 94 4.2. НОРМАЛЬНІ АЛГОРИТМИ ................................................................... 94 4.3. РЕКУРСИВНІ ФУНКЦІЇ .......................................................................... 95 4.4. МАШИНА ТЬЮРИНГА ........................................................................ 104 4.5. МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ ................. 121 СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ............................................................... 126 ПРЕДМЕТНИЙ ПОКАЗЧИК ................................................................................. 127 5 ПЕРЕДМОВА Даний посібник є переробленим та доповненим виданням посібника «Математична логіка та теорія алгоритмів», що був виданий у 2009 році колективом авторів В.М. Євладенко, З.П. Халецька, В.В. Нарадовий, та протягом семи років використовувався для студентів спеціальностей «Математика*», «Інформатика» та «Статистика» фізико-математичного факультету Кіровоградського державного педагогічного університету імені Володимира Винниченка. Даний посібник охоплює матеріал модулів «Алгебра та числення висловлень», «Логіка предикатів», «Теорія алгоритмів» відповідно до програми курсу «Математична логіка та теорія алгоритмів». Викладення теоретичного матеріалу ілюструється прикладами. В кожному розділі після теоретичного блоку наведено запитання для самоконтролю та вправи для самостійного розв’язання. До кожної теми у посібнику подано формулювання означень основних понять, теорем та інших фактів, знання яких необхідне для опанування цієї теми. Наводяться розв’язані приклади з детальним поясненням, що дозволить читачам самостійно опрацьовувати даний матеріал і краще розуміти деякі, традиційно складні для студентів, теми. До кожної теми розділів підібрані вправи для самостійного розв’язування. Їх кількість достатня для роботи на практичних заняттях та для виконання поточних домашніх завдань. Крім того, кожна тема завершується запитаннями для самоконтролю, що допоможе студентам при підготовці до модульних та підсумкового контролів. Для зручності користування в кінці посібника вміщено предметний покажчик. Посібник рекомендується для студентів денної та заочної форм навчання спеціальностей «Математика*», «Статистика», а також він буде корисним студентам спеціальності «Інформатика» при вивченні даних розділів у курсах «Дискретна математика» та «Теорія алгоритмів та математична логіка». 6 1. АЛГЕБРА ВИСЛОВЛЕНЬ 1.1. ВИСЛОВЛЕННЯ ТА ОПЕРАЦІЇ НАД НИМИ. ФОРМУЛИ АЛГЕБРИ ВИСЛОВЛЕНЬ Висловлення – вихідне, неозначувальне поняття алгебри висловлень. Під висловленням розуміють таке речення, про яке можна говорити, що воно істинне чи хибне. У логіці висловлень висловлення розглядаються лише з точки зору їх істинності чи хибності; ніякими іншими властивостями висловлень не цікавляться; значення істинності чи хибності висловлень не аналізується, а береться як дані. Відповідь про істинність чи хибність висловлення дає галузь науки чи людської діяльності, до якої воно належить. У подальшому дотримуватимемось точки зору двозначної класичної логіки, в якій приймаються два основних припущення: 1) кожне висловлення є або істинним, або хибним, тобто третього не дано (закон виключеного третього); 2) жодне висловлення не є одночасно істинним і хибним (закон виключення суперечності або закон протиріччя). Зазначимо, що сучасна логіка розглядає так звані багатозначні логіки, де ці закони місця не мають. Висловлення бувають простими і складеними. Прості висловлення це висловлення, які не можна подати як логічну композицію більш коротких висловлень (їм відповідають прості розповідні речення). Їх позначають малими літерами латинського алфавіту a,b,c,… або тими ж буквами з індексами внизу, та називають пропозиційними (логічними, висловлювальними) буквами або змінними. Наприклад: а: «Київ – столиця України»; b: «Пряма 0 6 2 y x проходить через точку з координатами (2,2)»; c: «Аристотель – український філософ»; d: «Простих чисел нескінченна кількість»; p: «Річка Ніл впадає в Чорне море». Домовимось записувати |а|=1, якщо висловлення а – істинне і |а|=0, якщо висловлення а – хибне. У першому випадку говорять, що значення істинності висловлення а (значення функції істинності для даного значення аргументу) дорівнює 1, а в другому, що значення істинності висловлення а дорівнює 0. Для наведених прикладів висловлень маємо наступні логічні значення: 7 |а| = 1, |b| = 1, |c| = 0, |d| = 1, |p| = 0. Складені (складні) висловлення утворюються з простих за допомогою логічних зв'язок (операцій). Розглядатимемо тільки істинно-функціональні комбінації висловлень, в яких істинність чи хибність нових висловлень однозначно визначається істинністю чи хибністю складових. Основними логічними операціями є заперечення, кон’юнкція, диз’юнкція, імплікація та еквіваленція. Запереченням висловлення а називається нове висловлення a або a (читається “не а”), яке істинне, якщо вихідне висловлення а – хибне і хибне, якщо |а| =1. Зв’язок логічних значень висловлень a та а ілюструємо в наступній таблиці істинності: Табл.1. Таблиця істинності операції заперечення. a a 0 1 1 0 Пропозиційні змінні та їх заперечення називають літералами. Кон’юнкцією двох висловлень а і b, називається нове висловлення b a , яке істинне лише в тому випадку, коли обидва висловлення а і b є істинними, і хибне, коли хоч одне з висловлень а або b хибне. Еквівалентні назви – «логічний добуток», «і», «AND». Диз’юнкцією двох висловлень а і b називається нове висловлення b a , яке істинне в тих випадках, коли хоч одне з висловлень а або b є істинним, і хибне тільки в тому випадку, коли обидва висловлення а і b є хибними. Еквівалентні назви – «логічна сума», «або», «OR». Імплікацією двох висловлень а і b називається нове висловлення а→b, яке є хибним в одному випадку, а саме, коли висловлення а істинне, а b – хибне, а в інших випадках /а→b/=1. У висловленні а→b висловлення а називається умовою або антецедентом, а висловлення b – наслідком або консеквентом. Умова b є необхідною для виконання а, а умова а є достатньою для виконання b. Еквіваленцією двох висловлень а і b, називається нове висловлення а↔b, яке істинне лише в тому випадку, коли обидва висловлення а і b набувають однакових значень істинності – вони або обидва істинні, або обидва хибні, в інших випадках /а↔b/=0. Умова b є необхідною і достатньою для виконання а. Табл.2 Таблиця істинності бінарних логічних операцій. 8 a b b a b a b a b a 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 1 1 1 Кожне із введених означень операцій над висловленнями можна розглядати як означення деякої дії над символами 0 і 1, тобто як визначення деякої операції (функції) на двохелементній множині {0,1}. Це дає можливість записати рівності для обрахунку логічних значень висловлень: a , b a , b a , а→b,а↔b, відповідно. a a , b a b a * * , де знак * означає один із символів операцій , , , Пропозиційні букви, символи логічних операцій та дужки становлять вихідні символи мови алгебри висловлень, тобто її алфавіт. Будь-яка скінченна послідовність вихідних символів є виразом або словом мови. З множини всіх слів виділяють так звані формули, які в мові алгебри висловлень відповідають реченням природної мови. Формулами алгебри висловлень називаються пропозиційні букви і вирази виду B A B A B A B A A , , , , , де B A, - формули. При цьому пропозиційні букви називають елементарними або атомарними формулами. Очевидно, що за скінченне число кроків завжди можна встановити, чи є той чи інший вираз формулою логіки висловлень. Означення формули вимагає, щоб кожній логічній операції відповідала пара дужок. Дужки у формулі однозначно визначають порядок виконання операцій. Проте наявність великої кількості дужок робить запис формули досить громіздким. Для спрощення запису формул користуються такими правилами: 1) зовнішні дужки в записі формули опускають; 2) логічним операціям приписують певний ранг (старшинство операцій), згідно якого операції виконуються в такому порядку: , , , , Приклад 1. Обчислити значення істинності формули А= c a b a якщо |a| = 1, |b| = 1, |c| = 1. Розв’язання. Дана формула є скороченим записом наступної формули: ))) ( ( ) (( c a b a Послідовно знаходимо | b |=0, | b a |= 0 1 =0, | c |=0, | c a |= 0 0 1 , | c a b a |= 0 0 =1. 9 Отже, при даній інтерпретації логічних змінних значення істинності формули дорівнює 1. Результати обчислень значень істинності формули для всіх можливих наборів значень істинності пропозиційних змінних зручно подавати у вигляді таблиці, яку називають таблицею істинності формули. Так, для формули А= c a b a таблиця істинності матиме такий вигляд: |a| |b| |c| | b | | b a | | c | | c a | | c a b a | 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 Кожному символу логічної операції в формулі А виділено окремий стовпчик таблиці істинності. Зазначимо, що кожний стовпчик таблиці для формули А відповідає певному кроку процесу побудови формули А (певній підформулі). Фактично ж таблицю істинності формули утворюють стовпчики значень істинності пропозиційних змінних (перших три стовпчики) і останній стовпчик, який визначає функцію істинності даної формули. Інші стовпчики (стовпчики істинності підформул) носять допоміжний характер. Таблиця істинності формули ) ,... , ( 2 1 n a a a A містить 2 n рядків (кожна пропозиційна змінна незалежно від інших може набувати одного з двох значень: 0 або 1, тобто число всіх можливих різних наборів значень n пропозиційних змінних є 2 n ). Формули алгебри висловлень поділяються на наступні типи: тавтології (тотожно істинні), суперечності (тотожно хибні) та нейтральні. Формула алгебри висловлень ) ,... , ( 2 1 n a a a A називається тавтологією, якщо при всіх можливих значеннях пропозиційних букв n a a a ,..., , 2 1 вона істинна, тобто її функція істинності тотожно дорівнює 1. Позначення: ) ,... , ( 2 1 n a a a A 10 Формула логіки висловлень, значення істинності якої дорівнює 0 при всіх можливих значеннях істинності її пропозиційних змінних називається суперечністю. Отже, суперечності – це такі формули, значення істинності яких не дорівнює 1 при жодній інтерпретації. Формула, яка не є ні тавтологією, ні суперечністю, називається нейтральною. Будь-яку формулу, яка не є суперечністю називають виконуваною, а не тотожно істинну – спростовною. Якщо формула А залежить від невеликої кількості змінних, то для з’ясування її типу зручно користуватися таблицями істинності. У деяких випадках доцільно застосовувати метод міркувань від супротивного. Приклад 2. Довести, що якщо формули B A і B A тавтології, то формула А – також тавтологія. Розв’язання. Оскільки А і В –довільні формули, то ми не можемо використати таблиці істинності. Застосуємо метод від супротивного. Припустимо, що А – не тавтологія, тобто існує набір значень пропозиційних змінних, від яких залежить А, на якому А набуває логічного значення 0. Тобто 0 A . Тоді 1 A . За умовою 1 B A і 1 B A . Звідки 1 B і одночасно 1 B , що неможливо. Отже, припущення невірне. |