Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
2. ЧИСЛЕННЯ ВИСЛОВЛЕНЬ В основу викладу алгебри висловлень було покладено поняття висловлення. При цьому вимагалось, щоб будь-яке висловлення було або істинним, або хибним. Ця вимога (закон виключеного третього) стосувалась нескінченної сукупності всіх висловлень. Такий підхід не прийнятний в основах математики, зокрема там, де необхідно обґрунтувати, що використання цього закону не приводить до суперечності. Розглянемо формалізовану аксіоматичну теорію, яка адекватна алгебрі висловлень і вільна від указаної вище вимоги. Цю формалізовану аксіоматичну теорію прийнято називати численням висловлень. Числення висловлень є складовою частиною інших логічних числень. Формалізація будь-якої змістовної теорії передбачає перетворення її на об'єкт вивчення. Для цього спочатку чітко описується мова даної теорії, а саме: вказується алфавіт теорії - множина усіх її вихідних символів (Символи теорії розглядаються як матеріальні знаки, які означають лише те, що про них буде сказано в аксіомах, і з якими працюють тільки так, як це буде сказано в правилах перетворень (виводів). При цьому символи, що не належать до алфавіту теорії, називаються метaсимволами); серед слів (скінченних послідовностей символів), записаних в алфавіті даної теорії, виділяють ті, що називаються формулами; з класу формул виділяються аксіоми; вказуються точно правила переходу від одних формул даної теорії до інших формул цієї ж теорії. їх називають правилами виводу. Аксіоми і правила виводу вибирають так, щоб з множити аксіом за допомогою правил виводу можна одержати всі тотожно істинні формули змістовної теорії, і тільки їх. Таким чином, тотожно істинні формули змістовної теорії виявляються теоремами відповідної формальної теорії. При побудові числення висловлень можуть бути вибрані різні системи аксіом і вказані різні правила виводу. Проте спільним для них є те, що кожного разу множина формул числення висловлень, яку можна одержати за допомогою вказаних правил виводу з заданої системи аксіом, збігається з множиною тавтологій алгебри висловлень. 50 2.1 АЛФАВІТ, ФОРМУЛИ, АКСІОМИ, ПРАВИЛА ВИВОДУ ЧИСЛЕННЯ ВИСЛОВЛЕНЬ L 1 . ПРИКЛАДИ ДОВЕДЕНЬ В ЧИСЛЕННІ L 1 Розглянемо одну з можливих аксіоматизацій алгебри висловлень, яку коротко називатимемо численням висловлень L 1 1. Алфавіт теорії L 1 складають: 1) символи першої категорії - малі латинські букви і ці ж букви з натуральними індексами (їх будемо називати пропозиційними буквами, або пропозиційними змінними); 2) символи другої категорії - логічні зв'язки: , , , . За ними зберігаються лише відповідні назви з алгебри висловлень: заперечення, кон'юнкція, диз'юнкція, імплікація; 3) символи третьої категорії – допоміжні або розділові: (,), (їх називають відповідно лівою і правою дужками); 4) інших символів в алфавіті теорії L 1, крім вказаних в пунктах 1) - 3), немає. Скінченні послідовності символів алфавіту утворюють слова. Серед слів вибираються формули. Точне означення формули носить рекурсивний характер. 2. Формулами теорії L 1 є такі слова: 1) будь-яка пропозиційна буква - формула; 2) якщо А і В формули, то формулами будуть слова B A B A B A B A , , , , ; 3) інших формул теорії L 1 , крім зазначених в пунктах 1) і 2), немає. Звертаємо увагу на те, що символи для позначення формул – А, В, С, …. не є символами алфавіту теорії L 1 , тобто це метасимволи. Вони використовуються для скороченого позначення формул. Якщо формула є пропозиційною буквою, то її називають елементарною формулою. Використання дужок для запису формул дозволяє поділити побудову формули на етапи і на кожному етапі перевіряти, чи є те чи інше підслово формулою. Оскільки таких кроків скінченне число, то питання про те, чи є дане слово формулою, завжди може бути вирішеним. Як і в алгебрі висловлень, домовляються не записувати зовнішніх дужок. Крім цього, опускають дужки, враховуючи силу логічних зв'язок (за спаданням) , , , 51 З. - Аксіомами числення висловлень L 1 є формули: 1.1 a b a ; 1.2 c a b a c b a ; 2.1 a b a ; 2.2 b b a ; 2.3 c b a c a b a ; 3.1 b a a ; 3.2 b a b ; 3.3 c b a c b c a ; 4.1 a b b a ; 4.2 a a ; 4.3 a a Аксіоми розбиті на 4 групи залежно від наявності в них тих чи інших логічних зв'язок: 1 група - " "; 2 група - " ", " "; 3 група - " ", " "; 4 група - " ", " ". 4. Правила виводу в численні висловлень L 1 : 1) Правило підстановки. Нехай А - формула, яка містить пропозиційну букву а. Тоді, якщо А - вивідна формула числення L 1 , то замінюючи в ній всі входження букви а довільною формулою В, одержимо вивідну формулу. Скорочений запис підстановки - A S B a 2) Правило modus ponens (скорочено МР). Якщо А і B A вивідні формули числення L1, то вивідною буде і формула В. Це правило називають також правилом висновку або правилом відокремлення і скорочено записують так: B B A A , В формулюваннях правил виводу фігурує поняття "вивідна формула". Означення. Формула А називається вивідною в численні висловлень L 1 , якщо існує така скінченна послідовність формул n B B B ,.., , 2 1 , в якій A B n і кожна формула ) , 1 ( n i B i є або аксіомою, або одержана з попередньої за допомогою правила підстановки, або одержана з двох попередніх за допомогою правила МР. 52 Вивідну формулу А називають теоремою числення висловлень L1 і записують A , а послідовність формул n B B B ,.., , 2 1 називається виводом (доведенням) формули А в численні L1. Число п називається довжиною виводу формули А.. Таким чином, кожна аксіома є вивідною формулою з довжиною виводу 1. Користуючись правилами виводу і виходячи з аксіом, одержують нові вивідні формули числення висловлень. Приклад 1. Візьмемо аксіому 1.1 і виконаємо підстановку c a a S . Одержимо c a b c a - теорема з довжиною виводу п=2. В свою чергу, якщо в одержаній формулі здійснимо підстановки c c a b a S , то одержимо нову вивідну формулу (теорему) числення висловлень: c c a c c c a , яка має довжину виводу п=3. Приклад 2. Довести, що формула a a b a є теоремою, та визначити довжину побудованого виводу. Розв'язання. Побудуємо вивід (доведення) для вказаної формули. Беремо аксіому 1.2 і здійснюємо підстановку a c S Одержимо: a a b a a b a Оскільки a b a , бо це аксіома 1.1, то за правилом МР маємо a a b a Випишемо всі формули, що утворюють вивід: 1) c a b a c b a - аксіома 1.2; 2) a a b a a b a - ) 1 ( a c S ; 3) a b a - аксіома 1.1; 4) a a b a - правило МР(2,3). Отже, довжина побудованого виводу дорівнює 4. Приклад 3. Довести, що коли I , то I A для будь-якої формули А. Розв'язання. Візьмемо аксіому 1.1 і здійснимо підстановки A I b a S Одержимо I A I . За умовою I . Тоді за правилом МР маємо I A Приклад 4. Довести, що a a 53 Розв'язання. За доведеним в прикладі 2 маємо a a b a . В цій формулі зробимо підстановку a b b S . Одержимо: a a a b a Оскільки a b a , бо це аксіома 1.1, то за правилом МР маємо a a , що і треба було довести. Запитання для самоконтролю 1. Яку аксіоматичну теорію прийнято називати численням висловлень? 2. Які кроки опису мови довільної формальної теорії? 3. За яким принципом обирають аксіоми і правила виводу формальної теорії? 4. Які символи містить числення висловлень L 1 ? 5. Що називається формулою числення висловлень L 1 ? 6. Які групи аксіом має числення висловлень L 1 та що їх характеризує? 7. В чому суть правила підстановки ( A S B a )? 8. В чому суть правила виведення modus ponens (МР)? 9. Яка формула називається вивідною в численні висловлень L 1 ? Що таке вивід, довжина виводу? 10. Що таке теорема числення висловлень L 1 ? Наведіть приклади теорем числення висловлень L 1 2.2. ВИВІДНІСТЬ ІЗ ГІПОТЕЗ. МЕТАТЕОРЕМА ДЕДУКЦІЇ. ДОДАТКОВІ ПРАВИЛА ВИВОДУ. Застосування тільки двох правил формального доведення значно ускладнює процес побудови виводів формул. Крім того, такі доведення відрізняються від багатьох змістовних доведень в математиці, бо в останніх, крім аксіом і доведених раніше теорем, широко використовують певні припущення. Тому для скорочення виводів і наближення їх до практики математичних доведень розглядають виводи з припущень (гіпотез) і вводять додаткові правила виводу. Нехай Γ - деяка множина формул числення висловлень. Означення. Формула А називається вивідною з множини формул Г, якщо існує скінченна послідовність формул n B B B ,.., , 2 1 , в якій A B n , і кожна формула є або формулою множини Г, або вивідною в численні висловлень L1 або одержана з попередніх за допомогою правила МР. При цьому послідовність формул n B B B ,.., , 2 1 називається виводом (доведенням) формули А з множини формул Г. Формули з Γ називаються 54 припущеннями або гіпотезами. Запис Γ A означає, що формула А вивідна з множини формул Г. В тому разі, коли Γ=, маємо A , тобто А - теорема числення висловлень. При розгляді формалізованих теорій розрізняють теореми формалізованої теорії (вивідні формули) і теореми про формалізовану теорію. Теореми числення висловлень в сукупності складають формалізовану теорію числення висловлень. А міркування про теорію, про окремі теореми цієї теорії, про зв'язки між теоремами і т.д. становлять так звану метатеорію даної формалізованої теорії - в нашому випадку метатеорію числення висловлень. Твердження метатеорії називатимемо метатеоремами. Доведення метатеорем не формалізовані, а змістовні. Вкажемо деякі важливі властивості поняття вивідності з припущень. Метатеорема 2.2.1 1) Якщо Γ A і Γ , Δ A 2) Γ A тоді і тільки тоді, коли в Γ є така скінченна або порожня підмножина Г 1 , що Γ 1 A 3) Якщо Γ A для будь-якої формули А Δ і Δ B , то Γ B Метатеорема 2.2.2. (дедукції). Якщо A C C C C m m , ,... , 1 2 1 , то A C C C C m m 1 2 1 ,... , Наслідок 1. A C C C C m m , ,... , 1 2 1 тоді і тільки тоді, коли A C C C C m m 1 2 1 ,... , Наслідок 2. A C C C C m m , ,... , 1 2 1 тоді і тільки тоді, коли ))...) ( ( ( 1 2 1 A C C C C m m Другий наслідок ілюструє можливість переходу від вивідності з припущень до теорем числення висловлень, і навпаки. Приклад 5. Довести, що c a c b b a Розв'язання. Використовуючи наслідок 2 з метатеореми дедукції, маємо: c a c b b a c a c b b a , , . Побудуємо виведення з припущень: 1. b a припущення; 2. c b припущення; 55 3. а припущення; 4. b МР(1,3); 5. c МР(2,4). Таким чином, c a c b b a , , . Отже c a c b b a Тепер нехай А,В,С – довільні формули числення висловлень. Виконаємо підстановку C B A c b a S в одержану вивідну формулу: C A C B B A Отже, якщо B A і C B , то за правилом МР буде і C A . Таким чином ми одержали нове правило виводу, яке називається правилом силогізму: C A C B B A , Метатеорема 2.2.3 В численні висловлень мають місце наступні похідні правила виведення: 1. Правило силогізму: C A C B B A , 2. Правило вилучення кон’юнкції: B B A A B A , 3. Правило введення кон’юнкції: B A B A , 4. Правило вилучення диз’юнкції: C B A C B C A , 5. Правило введення диз’юнкції: B A B B A A , 6. МТ (modus tollens): A B B A , 7. Правило контрапозиції: A B B A , Приклад 6. Провести змістовне і формальне доведення теореми про три перпендикуляри: «Для того щоб пряма, що лежить у площині, була перпендикулярна до похилої, необхідно і достатньо, щоб ця пряма була перпендикулярна до проекції похилої». Розв'язання. Розглянемо доведення достатності (доведення необхідності аналогічне і рекомендується для самостійного опрацювання). |