Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень

Довільну формулу F числення висловлень можна змістовно інтерпретувати як складене висловлення, істинність або хибність якого залежить від істинності елементарних висловлень, що до нього входять. Таким чином, кожній формулі F числення висловлень можна аналогічно тому, як це було зроблено в алгебрі висловлень, поставити у відповідність функцію істинності f.

Виникає питання, як пов’язано таке змістовне «істинносне» тлумачення (інтерпретація) формул числення висловлень з їхньою формальною вивідністю.

Теорема 5.5. Будь-яка теорема числення висловлень ЧВ є тотожно істинним висловленням (тавтологією).

Доведення. Тотожна істинність усіх аксіом легко перевіряється безпосередньо побудовою відповідних таблиць істинності для кожної з них (рекомендуємо це зробити самостійно).

Відтак, доведемо, що обидва правила виведення числення висловлень перетворюють тотожно істинні формули у тотожно істинні.

Якщо A(p1,p2,...,pn) - тотожно істинна формула, то для довільного набору значень a1,a2,...,an її пропозиційних змінних A(a1,a2,...,an) є істинною. Отже, тотожно істинною буде і будь-яка формула A, що отримується з формули A шляхом підстановки замість пропозиційних змінних p1,p2,...,pn довільних формул B1,B2,.....,Bn, оскільки останні можуть набувати лише значень 0 або 1.

Доведемо, що коли формули A і AB є тотожно істинними, тоді формула B, яку ми дістаємо з них за правилом висновку, також є тотожно істинною. Припустімо супротивне: нехай B не є тотожно істинною формулою, тобто існує набір значень її змінних, на якому вона набуває значення 0. Тоді підставимо цей набір у формулу AB, оскільки A є тавтологією, то дістанемо вираз 10, значенням якого є 0. Останнє суперечить припущенню про тотожну істинність формули AB.

Таким чином, ми переконалися в тому, що всі аксіоми числення висловлень ЧВ є тотожно істинними формулами алгебри висловлень, а застосування обох правил виведення (підстановки і висновку) до тотожно істинних формул знову приводить до тотожно істинних формул. Отже, всі вивідні формули (теореми) числення висловлень є тотожно істинними формулами алгебри висловлень.

Справедливою є й обернена теорема, яку подамо без доведення.

Теорема 5.6. Будь-яка тотожно істинна формула алгебри висловлень є теоремою числення висловлень ЧВ.

Дві останні теореми дозволяють вирішити три важливі проблеми числення висловлень: проблему несуперечності, проблему повноти і проблему розв’язності. Розглянемо їх послідовно.

1. Проблема несуперечності.

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

Числення є несуперечним, якщо неможливо одночасно вивести з аксіом числення як формулу A, так і її заперечення A.

Наслідок 5.1. Числення висловлень ЧВ є несуперечною формальною теорією.

Справді, якщо формула A вивідна у численні висловлень, то формула A не може бути вивідною, бо за теоремою 5.5 формула A є тотожно істинною в алгебрі висловлень, а формула A - тотожно хибною. Отже, A не може бути теоремою числення висловлень ЧВ.

2. Проблема повноти.