Тема 6.2. Числення висловлювань
[4. гл.15, § 4; 6, гл.І, § 4-6; 26, гл.З. § З.1]
Вказівки щодо використання літературних джерел.
Матеріал даної теми - ключовий для розуміння дуже важливого розділу дискретної математики "Теорія формальних систем" і більшої частини досліджень у галузі штучного інтелекту.
Необхідно сформувати уявлення про аксіоматичну теорію, її мову, аксіоми й правила виведення й тільки після цього розглядати числення висловлювань як приклад аксіоматичної теорії.
Можливий також варіант, коли спочатку вивчається числення висловлювань, а потім формується загальне уявлення про аксіоматичні теорії й проблеми їхнього дослідження. Аналіз таких властивостей числення висловлювань, як повнота, несуперечність, розв’язуваність, дозволить глибше зрозуміти їхню сутність і значення для більш багатих теорій.
На закінчення рекомендується дослідити інші аксіоматизації числення висловлень і спробувати, з'ясувавши зв’язок виведення й абсолютної істинності, поширити аксіоматичний метод на інші важливі властивості висловлювань або інших конструкцій.
Треба розглядати побудову виводу в численні як аналог гри за певними правилами. Правила гри прості й формальні. Тому комп’ютер можна легко навчити цій грі.
В особливостях мови числення висловлювань допоможе розібратися уявлення про побудову складних висловлювань за допомогою зв’язок. Тому визначення мови числення включає визначення формул числення, що нагадують складні висловлювання, до складу яких входять прості висловлювання, які замінені літерами.
Визначення формул числення висловлювань працює як генератор формул: спочатку вводяться кілька формул шляхом включення до множини формул пропозиційних літер; потім формули можна отримати з уже побудованих формул застосуванням символів , 7, причому знову отримані формули, в свою чергу, включаються до процесу утворення все нових і нових формул.
Таким чином, множина скінчених формул числення висловлювань потенційно нескінчена.
Для того, щоб уявлення про побудову формул стало повнішим, глибшим, розглянемо визначення формул, яке не дозволяє одержати довільні формули числення висловлювань.
Нехай формули визначені таким чином:
І) кожна пропозиційна літера суть формула;
2) формулами є також 7А, 7В , А В, де А, В - пропозиційні літери;
З) у численні висловлювань немає інших формул, окрім визначених у п.п. 1 і 2.
Очевидно, що у цьому разі в численні висловлень не буде місця формулам, наприклад,
(A B) (B A), 7 (А В) тощо.
Припустимо, пункт 2 у визначенні сформульований у такому вигляді: 2) формулами є 7A, 7B, де A , В - пропозиційні літери, й A B, де A, B - формули. Тоді в численні висловлень не було б місця формулі, наприклад, 7(A B) тощо.
Труднощі чекають користувача гри за такими простими правилами саме при побудові виводів. Побудова виводу підстановкою в нього аксіом і результатів за правилами виведення може виявитися дуже довгим процесом, якщо задана формула, для якої треба побудувати вивід. Скоротити процес виводу можна, набувши певного досвіду й виробивши якісь ефективні прийоми. Так, рекомендується побудова виводу у зворотному напряму від результату до аксіом: спочатку підібрати формули для одержання потрібної, а потім, перевіривши, чи є аксіомами ці формули, чи їх можна вивести з аксіом. Можна поєднувати рух у прямому й зворотному напрямах. Аксіоми рекомендується розглядати насамперед ті, які містять потрібний результат.
Проаналізовані ускладнення при побудові виводів привели до необхідності більш глибокого дослідження їхніх властивостей, які називаються дедуктивними. Одержано результат, відомий як теорема дедукції Ербрана. Її широке застосування полегшує побудову виводів. У дисципліні "Штучний інтелект" розглядатимуться найефективніші способи побудови виводів. Та й сам аналіз дедуктивних властивостей потрібен не для того, щоб дослідник міг швидше доводити теореми у формальній теорії, а щоб він міг навчити цьому комп’ютер.
Помічено, що студентам при побудові виводів властиві деякі поширені помилки. З них найчастіша - бажання перенести на вивід відомі тотожності булевої алгебри висловлювань, наприклад, отримати формулу у виводі заміною у попередній формулі 77А на А; чи 7А /\ A на A /\ 7A тощо.
Каменем спотикання для багатьох студентів є з'ясування співвідношення між аксіомою, теоремою та гіпотезою.
У численні висловлень L, як і будь-якій теорії з незалежними аксіомами, жодна аксіома не може бути виведена як теорема з інших аксіом. У той же час формула, яка є теоремою, може бути виведена з аксіом і, в свою чергу, може бути використана для виведення інших теорем (дозвіл записувати її у вивід з умовою, що на це місце може бути підставлений її вивід, формально нагадує використання теореми як аксіоми).
Між теоремою й аксіомою числення висловлювань, таким чином, зв’язок визначений через виведення. Тому і аксіоми, і теореми є абсолютно істинними формулами.
Гіпотеза - довільна формула, яка може набувати довільного значення істинності. Гіпотезу в загальному випадку вивести неможливо. Гіпотези можна використовувати у виводі, відзначаючи, проте, цей факт стосовно отриманої теореми. Таким чином, для однієї й тієї самої формули А результати суттєво відрізняються: D |— A; |— A.
Перший з них підтверджує існування виводу для A, в якому, крім аксіоми, використані формули з множини гіпотез D . Другий же підкреслює, що вивід для A може бути побудований без використання гіпотез.
Як приклад наводимо вивід, незалежно побудований студентами С.Голодняком (гр. КС-62), В.Рибкіним (гр. КС-83) та іншими: 7A гіпотеза, 7A (7B7A) (аксіома), 7B 7A (наслідок за правилом виведення), (7B 7A) ((7B A)B) (аксіома), (7В A)B (наслідок за правилом виведення), A ( 7B A) (аксіома), A B (за наслідком 1теореми дедукції Ербрана).
Таким чином, встановлено, що виведена формула A B, але з використанням гіпотези 7A. Тому ми не маємо права записати |— A B, але маємо право записати 7A |— A B.
Легко перевірити, що ні 7A, ні A B абсолютно істинними формулами не є. Але це не повинно бентежити дослідника, оскільки він пам’ятає, що одержав висновок A B тільки за умови 7A. Це ще раз підтверджує ідею успадкування теоремами властивостей аксіом і гіпотез. Включили до виводу гіпотезу 7A, яка не є абсолютно істинною формулою, і отримали теорему A B, яка також не є абсолютно істинною формулою.
Гідно пильної уваги те, що, застосувавши теорему дедукції Ербрана, отримаємо з 7A |— A B теорему 7A (A B), яка є абсолютно істинною формулою.
Подолати перешкоду, висунуту внутрішнім співвідношенням аксіом, теорем і гіпотез в численні висловлювань, допоможе ще один приклад виведення:
A77A (гіпотеза), 77A B (теорема). Таким чином, можна записати (A77A) |— (77AA), звідки, за теоремою дедукції Ербрана, отримаємо теорему (A77A) (77AA).
Погодившись з тим фактом, що, беручи участь у виведенні, не абсолютно істинна гіпотеза може привести до теореми, що має ті ж самі властивості й об’єднується за допомогою теореми дедукції Ербрана з гіпотезою в теорему, яка є абсолютно істинною формулою, студент стикається з новою неприємною ситуацією. У цьому прикладі гіпотеза не бере участі конструктивно (тобто в одержанні наслідків за правилом виведення) у формуванні останньої формули виводу.
Тому багато студентів вважають, що погодження з коректністю такого виводу приведе їх до можливості виводу довільної формули шляхом підстановки замість 77AA будь-якої формули. При цьому вони забувають, що замість 77AA може бути підставлена або аксіома, або теорема, або сама гіпотеза, але ніяк не довільна формула.
Досвід підтверджує, що якими б складними не здавалися поняття й методи цього розділу математичної логіки, вони стають ефективними й зручними засобами розв’язання практичних проблем. Природно, для цього потрібен деякий період часу й певні зусилля.
Особливу увагу слід звернути на фундаментальний результат, відомий під назвою теореми про повноту числення висловлювань. У цьому результаті полягає основна ідея, що широко використовується в системах штучного інтелекту:
- комп’ютер "не розуміє" істинності, але його легко, як ми бачили, навчити "розуміти", тобто виводити, теореми;
- теорема про повноту встановлює еквівалентність для числення висловлювань абсолютної істинності та виводимості формули;
- підтверджується можливість формальними засобами (побудова виводу) аналізувати змістовні або семантичні поняття (істинність).
Співвідношення змістовних і формальних понять можна характеризувати у графічному вигляді.
На допомогу приходить інтерпретація теорії. Під формулою теорії будемо розуміти висловлювання конкретної області застосування. Тоді множини Ф і Ф0 збігаються. Дослідника конкретної області застосування цікавлять абсолютно істинні висловлювання. Формально теорія буде корисна у плані вирішення цієї задачі у тому й тільки в тому випадку, коли множина абсолютно істинних висловлювань Т0 області застосування збігається з множиною теорем Т теорії. Саме це і стверджує теорема про повноту числення висловлювань L. Тоді, знаючи всі теореми числення висловлювань L, ми можемо одержати всі абсолютно істинні висловлювання застосування. Тобто визначення абсолютно істинних висловлювань переводиться в площину конструктивності - мова йде про те, що, отримуючи виведення формули як теореми, ми одержуємо відповідь на питання про те чи є відповідне їй висловлювання застосування абсолютно істинним.
Ще один важливий аспект поняття повноти теорії. Підемо від супротивного і припустимо, що множина теорем Тп теорії не збігається з множиною абсолютно істинних формул. Кажуть, що така теорія не повна. Тоді множина Тп теорем теорії є підмножиною множини абсолютно істинних висловлень Т0 області застосування. Це означає, що існує абсолютно істинна формула, наприклад В (див. рисунок), що належить множині Т0 \ Тп така, що не може бути побудоване її виведення у даній теорії.
Наведене дозволяє зробити висновок про важливість вибору аксіом теорії. На поширене запитання "Як були відібрані аксіоми теорії числення висловлювань L?" можна відповісти, що незалежно від того, як це було зроблено, важливий кінцевий результат - числення висловлювань L повне. А сам добір аксіом є творчою задачею, при розв'язанні якої можна виходити як із бажаної множини теорем, так і з цікавого набору аксіом.
На закінчення необхідно відзначити такий факт. Перконавшися в ефективності теореми дедукції Ербрана, багато студентів уважніше досліджують правила побудови висновків, намагаючись знайти корисні властивості. Так, студент групи КС-82 А.Абдулах знайшов властивість виведення, яку можна сформулювати у вигляді наступної теореми.
Теорема 1. Якщо A |— B і 7A |— B, то |—B .
Доведення. Двічі застосовуючи теорему дедукції, дістанемо |— А В і |— 7А В. Використовуючи побудоване для формули (АВ)((7АВ)В) вправи 1 теми 6.2 виведення, можемо записати послідовність формул: АВ, 7АВ, (АВ)((7АВ)В), (7АВ)В, В. Очевидно, вона задовольняв визначенню виводу. Таким чином, формула В - теорема, тобто |—В. Теорема доведена.
Приклад використання теореми 1. Побудуємо виведення формули 7 7А А. Згідно з теоремою потрібні два виведення з множини гіпотез {A} і {7A}:
1) A (гіпотеза), A(77AA) (аксіома), 77AA (наслідок за правилом виведення), тобто A|— 77AA;
2) 7A (гіпотеза), 7A(77AA) (теорема A(7AC), див. вправу 1 теми 6.2), 77AA (наслідок за правилом виведення), тобто 7A|—77AA.
Тоді за теоремою 1 формула 77AA є теоремою, тобто |—77AA.
Вправи до теми 6.2.
Вправа І. Побудувати виводи в численні висловлювань L для таких формул:
1) 77А А; 2) А 77А;
3) 7А (А В); 4) (7B 7A) (А В);
5) (А В) (7B 7А); 6) А (7B 7(А B));
7) (А В) ((7А B) В); 8) (В В) (А А);
9) (((A B) A) A); 10) 77(C D) 77(C D);
11) A (B 7(A 7B)); 12) B (7B С);
12) (((А (В С)) А) А); 14) С (7(А B) 7(С (А В))).
Приклад: Побудуємо вивід в численні L формули (В В) (А А)
1) А ((A А) А – аксіома схеми A1 теорії L;
2) (А ((A А) А)) ((A (A A) (A A)) - аксіома схеми А2 числення L;
3) (A (A A)) (A A) із формул 1, 2 - за правилом виведення числення L;
4) A (A A) - аксіома схеми А1 числення L;
5) A A - із формул 3, 4 - за правилом виведення числення L;
6) ( А А) (( В В) (А А)) - аксіома схеми А1 числення L;
7) ( В В)( А А ) із формул 5, 6 - за правилом виведення числення L.
О
L
|—
(В
В)
(А
А).
Вправа 2. Показати як спрощується виведення формули А А в численні L за умови використання теореми дедукції Ербрана.
Вправа 3. Використовуючи властивість повноти числення висловлювань L довести, що формули із вправи 1 є теоремами.
Вправа 4. Побудуємо числення висловлювань L+, додавши до числення висловлювань L у якості аксіоми довільну формулу, яка є теоремою числення висловлювань L. Довестити, що числення висловлювань L+ несуперечливе.
Вправа 5. Побудуємо числення висловлювань L*, додавши до числення висловлювань L довільну формулу А у вигляді додаткової схеми аксіом. Нехай формула А не є абсолютно істинною формулою. Довестити, що числення висловлювань L* суперечливе.
Вправа 6. Нехай в численні висловлювань L1 використовуються зв’язки \/, 7 (А В є скороченням для формули 7А \/ В), визначені чотири схеми аксіом:
1) А \/ АА; 2) АА \/ В;
3) А \/ ВB \/ А; 4) (BС) (А \/ B А \/ С),
єдиним правилом виведення є правило тоdus ponens (MР).
Треба довести, що наступні формули є теоремами, побудувавши для кожної із них вивід в численні висловлювань L1:
1) (АВ) ((СА) (СВ)) 2) АА
3) А \/ 7 А 4) А 77 А
5) 7А(АС) 6) А \/ (B \/ C) B \/ (A \/ C)
7) (B \/ (А \/ С)) \/ АВ \/ (А \/ С) 8) А \/ (В \/ С) ((B \/ (А \/ С)) \/ А)
9) (А (ВС))В(АC) 10) (СА) ((АB) (СB))
11) (А /\ В) \/ 7(А /\ В) 12) (А \/ В) (А \/ B)
13) (АА) (BВ) 14) ((А \/ B) \/ (B \/ С)) (B \/ ((А \/ B) \/ С)).
Приклад: Покажемо, що |— АА. Для цього побудуємо послідовність формул в численні висловлювань L1:
1) (А \/ AA) (7А \/ (А \/ А) 7А \/ А) - аксіома схеми 4 числення висловлювань L1;
2) А \/ А А - аксіома схеми 1 числення висловлювань L1;
3) 7А \/ (А \/ А) 7А \/ А - із формул 1, 2 за правилом виведення за правилом МР числення висловлювань L1;
4) (А А \/ А) (АА) – запис формули 3 з використанням прийнятого в численні висловлювань L1 скорочення;
5) А A \/ А - аксіома схеми 2 числення висловлювань L1;
6) А А - із формул 4, 5 за правилом виведення за правилом МР числення висловлювань L1.
Оскільки послідовність формул 1) – 6) задовольняє визначення виводу в аксіоматичній теорії, то АА виводиться в численні висловлювань L1, тобто |— А А. При цьому необхідно враховувати, що поки ще не існує конкретних процедур, що дозволяють побудувати вивід будь-якої формули, яка є теоремою числення, без зайвих кроків. Це пов’язане з тим, що при побудові виводу в кожний момент ми не знаємо, яка з аксіом або застосування правила МР до яких попередніх формул швидше приведе до потрібного результату. Тому існують тільки загальні рекомендації та процедури, пов’язані з перебиранням варіантів.
Можна запропонувати такі рекомендації:
а) за виглядом формули визначити відповідні аксіоми, застосування до яких правила МР дозволить отримати подібні формули;
б) будувати вивід не тільки в прямому, але й в зворотному порядку, визначаючи попередні формули, з яких безпосередньо за правилом МР випливає кінцевий результат, та перевіряючи, чи не містяться вони серед вже виведених формул;
в) виконувати формальні перетворення після того, як окреслена деяка послідовність кроків, яка може привести до результату за задумом конструктора виводу;
г) опрацювавши досвід побудови виводів, відібрати найефективніші схеми застосування аксіом та правил виведення тощо.
Числення висловлювань L1 описане в [12, розд. І, § 6, с. 48-51].
Вправа 7. Показати, що в численні висловлювань L формула B(АС) виводиться із формули А(ВС), тобто А(ВС) |— B(АС).
Вправа 8. Нехай у численні висловлювань L2 використовуються зв’язки /\,7 (АВ використовується для скорочення запису 7(А /\ 7В)), визначені три схеми аксіом:
1) А (А/\А); 2) A /\ B-А; 3) (АВ) (7(А/\С) 7(С/\А)),
правилом виведення є правило МР.
Треба показати, побудувавши вивід, що наступні формули є теоремами числення висловлювань L2:
1) 7(7A /\ A); 2) A /\ B B /\ A;
3) 77A A; 4) (A (BC)) ((A /\ B) C);
5) 7(A /\ B) (B7A); 6) ((A /\ B) C) (A (BC));
7) A 77A; 8) A (BA /\ B);
9) (A B) (7B7A); 10) A (BA);
11) A A; 12) (7A A)A.
Вправа 9. Розглянемо інтерпретацію числення висловлювань L, яка складаеться з множини D = {I,X} та відповідності, згідно а якою висловлювання С, В набувають значення І, а A - значення X.
Встановити значення істинності при цій інтерпретації таких формул:
1) (A B) (BA) 2) (7A (B7B) A)
3) (7А7B) (BА) 4) (А7В) (7АВ)
5) (7АА) А 6) А(B7(А7B))
7) (АB) (А(BC)) 8) (А (BС)) (BC).
Вправа 10. Розглянемо інтерпретацію числення висловлювань L, яка складається з множини простих висловлювань:
1) в НТУУ “Київський політехнічний інститут” вивчається дисципліна "Основи дискретної математики";
2) у робочу навчальну програму дисципліни "Основи дискретної математики" включено розділ "Вступ до математичної логіки”;
3) для дисципліни "Основи дискретної математики" немає методичних вказівок до самостійної роботи студентів
та відповідності, згідно з якою символу А відповідає висловлювання 1, символу В - висловлювання 2, символу С - висловлювання 3. Встановити значення істинності формул вправи 9 при цій інтерпретації.
Вправа 11. Які труднощі виникають при формалізації формулами числення висловлювань висновків такого вигляду:
1) кожна абсолютно істинна формула логіки висловлювань - теорема числення висловлювань;
2) формула А - абсолютно істинна в логіці висловлювань;
3) формула В - теорема числення висловлювань.
Вправа 12. Навести приклади інших логічних висновків, при формалізації яких у численні висловлювань виникають нездоланні труднощі.
Вправа 13. Нехай в численні висловлювань L існують виводи А |— С та 7А|— С. Чи можна стверджувати, що формула С є теоремою в численні висловлювань L, тобто |— С?
Вправа 14. Нехай числення висловлювань суперечливе. Чи можна стверджувати, що це числення висловлювань повне?
Вправа 15. Нехай колами Ейлера задане співвідношення множини формул Ф, множини абсолютно істинних формул І, множини теорем Ψ, множини аксіом А числення виоловливань Lr. Встановити властивості числення виоловливань Lr та можливість його визначення.
Варінти кіл Ейлера.
Приклад: Розглянемо варіант 4. Оскільки А І, то кожна аксіома - абсолютно істинна формула. Тоді існування теорем, які не є абсолютно істинними формулами, неможливе, якщо правила виведення мають властивість зберігати абсолютну істинність висновків при абсолютній істинності засновків, або можливе, якщо правила виведення числення цієї властивості не мають, але тоді теорія Lr, втрачає практичну цінність і множини Ф та Ψ повинні співпадати.
Вправа 16. Нехай формула А є абсолютно істинною. Коли можна стверджувати, що вона може буги виведена як в теорії Lі, так і в теорії Lj, які властивості повинні мати теорії Lі і Lj)?
Вправа 17. Побудуємо числення висловлювань L**, вилучивши з числення висловлювань L схему аксіом А3 та додавши до нього довільну формулу А у вигляді додаткової схеми аксіом. Нехай формула А не є абсолютно істинною формулою. Встановити, чи є числення висловлювань L** суперечливим.
Вправа 18. Нехай для довільних формул A, A1,…, An в численні L виконується умова A1,…, An |—A та 7A1,…, 7An |—A. Чи можна тоді стверджувати, що в численні L |—A.
Вправа 19. Побудуємо числення висловлювань L***, вилучивши з числення висловлювань L схему аксіом А3 та додавши до нього формулу АA у вигляді додаткової схеми аксіом. Як зміняться модельні властивості числення висловлювань L*** відносно модельних властивостей числення висловлювань L.
Вправа 20. Нехай в численні висловлювань L існують виводи , А |— С та , 7А|— С. Чи можна стверджувати, що формула С виводиться в численні висловлювань L з множини гіпотез , тобто |— С? Якщо відповідь позитивна, то вказати напрямки спрощення доведення оберненої теореми про повноту числення висловлювань L.
Вправа 21. Побудуємо числення висловлювань L’, добавивши до мови числення висловлювань L зв’язки ,, та схеми аксіом числень висловлювань L1 та L2 до аксіом числення висловлювань L. Як зміняться модельні властивості числення висловлювань L’ відносно модельних властивостей числення висловлювань L.