Лекція 8 План
Властивості числення висловлень.
Проблема повноти.
Несуперечність числення висловлень.
Проблема розв’язності.
Незалежність системи аксіом числення висловлень.
1. Властивості числення висловлень
В основі формалізованого числення висловлень лежать поняття, котрі відносяться до так званої області синтаксису, тобто поняття, котрі є деякими абстрагованими від змісту символами й формальні дії з ними: алфавіт, формула, аксіома, правило виведення, доведення, теорема. Ці поняття прийнято називати синтаксичними.
У той же час в алгебрі висловлень за кожною пропозиційною змінною стоїть конкретне висловлення, кожна формула може перетворюватися в конкретне складне висловлення, котре може бути істинним або хибним. У цій сфері, яка є областю семантики, кожне поняття наповнене певним змістом. Поняття істини, хиби, тотожно істинної й тотожно хибної формул, рівносильності й логічного наслідку формул є поняттями семантики.
2. Проблема повноти
Проблема повноти полягає у з’ясуванні питання, чи достатньо аксіом і правил виведення даного числення для того, щоб можна було вивести будь-яку формулу, яка в змістовному розумінні є тотожно істинною.
Дещо інше поняття повноти системи аксіом ґрунтується на неможливості доповнення системи аксіом будь-якою формулою, яку не можна вивести з даних аксіом.
Система аксіом називається семантично повною, якщо із неї можна отримати всі тотожно-істинні формули, записані засобами цього числення. Це означає, що в даній системі є достатньо аксіом, щоб вивести довільну формулу, котра є істинною прибудь-якому наборі змінних.
Система аксіом називається синтаксично повною, якщо приєднання до неї невивідної у цій системі формули робить систему суперечливою.
Теорема 8.1. Будь яка теорема ЧВ є тавтологією, тобто ├ F ╞ F.
Доведення. Тотожна істинність усіх аксіом перевіряється безпосередньою побудовою таблиць істинності для кожної із них. Отже усі аксіоми тавтології.
Покажемо тепер, що правило виведення МР перетворює тотожно істинні формули в тотожно істинні формули, тобто покажемо, що коли F і FG тотожно істинні, формули то й G тотожно істинна. Припустимо супротивне. Нехай G не є тотожно істинною формулою, тобто існує набір значень її змінних, на якому вона набуває значення 0. Тоді підставимо цей набір у формулу FG .Оскільки F є тавтологією, то дістанемо вираз 10, значення якого є 0. Останнє суперечить припущенню про тотожну істинність формули FG. Отже всі вивідні формули числення висловлень є тотожно істинними формулами тобто тавтологіями.
Має місце й обернена теорема, яку ми наведемо без доведення.
Теорема 8.2. Будь-яка тотожно істинна формула алгебри висловлень є теоремою ЧВ.
Об’єднавши розглянуті теореми одержимо теорему про повноту (теорема тавтології) ЧВ.
Теорема 8.2 (про повноту). Множина теорем числення висловлень збігається з множиною тавтологій алгебри висловлень, тобто ├ F ╞ F.
З теореми про повноту випливає її узагальнення теорема адекватності.
Теорема 8.3 ( адекватності). Формула вивідна в ЧВ із скінченної множини гіпотез Г тоді й тільки тоді, коли вона є логічним наслідком усіх формул цієї множини, тобто F1, F2, ..., Fm ├ G F1, F2, ..., Fm ╞ G.
Доведення. Нехай F1, F2, ..., Fm ├ G . Тоді за наслідком 7.2 теореми про дедукцію маємо: ├ F1 (F2 ... (Fm-1 (Fm G))…).
Звідси за теоремою про повноту одержуємо:
╞ F1 (F2 ... (Fm-1 (Fm G))…).
Остання формула рівносильна формулі (F1 F2 ... Fm ) G . Тоді
із тотожної істинності однієї із формул і їх рівносильності випливає, що і друга формула є тавтологією, тобто ╞ (F1 F2 ... Fm ) G .