ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.16. АКСІОМАТИЧНИЙ МЕТОД ДОВЕДЕННЯ В ЛОГІЦІ ВИСЛОВЛЮВАНЬ

      Логіка це наука про способи доведень. Ми розглянули доведення в логіці Буля, які будувалися на відношенні еквівалентності. Дві логічні функції вважалися еквівалентними, якщо вони давали на відповідних наборах аргументів однакові значення нулів та одиниць.

В логіці висловлювань всі доведення будуються на відношенні порядку, тобто відношенні між причиною та наслідком. Окремі ланцюги доведення зв'язані символом імплікації "", проте при доведенні використовують символ"". Символ""називають об'єктивним, а""- суб'єктивним, або метасимволом. Аналогічно: замість об'єктивної кон'юнкції""будемо використовувати суб'єктивний символ метакон'юнкції - ",", а замість об'єктивної диз'юнкції""- суб'єктивну метадиз'юкцію - ";". Тоді твердження, що вимагає доведення в логіці висловлювань можна оформити у виді причинно-наслідкового відношення.

,

де - причина (посилка);

А - наслідок (висновок).

Читається: "Якщо посилки - істинні, то наслідок А теж істинний". Щоб не переплутати об'єктивні висловлювання з суб'єктивними, істинність яких треба встановити домовимося речення типу називати клаузами - метареченнями, в яких використовуються відношення порядку, оформлені через символ метаімплікації.

Відомо, що відношення порядку задовольняє трьом законам:

1. - закон рефлексивності;

2. якщо , то ; закон антисиметричності;

3. якщо і , то - закон транзитивності.

Причому, якщо і , то .

Клауза - це формальний запис речення, яке необхідно довести. Якщо замість букв в ній підставити об'єктивні висловлювання, вона наповнюється конкретним змістом і уже називається семантикою або легендою.

      Наприклад: (клаузи).

Якщо прийняти {Петро студент}, B={складання екзамену}, то клаузи перетворюються в легенду. "Якщо Петро студент, то він буде складати екзамен".

Довільну клаузу можна записувати в різних еквівалентних формах. Наприклад, може бути записана:



або , і т.д.

      Проте клауза має деякі переваги, так вона використовується в мові логічного програмування ПРОЛОГ, її називають хорнівською, причому довільну клаузу можна звести до хорнівського виду. Якщо символ метаімплікації "|-" хорнівської клаузи змістити в крайнє ліве положення, вона перетворюється в тавтологію, в крайнє праве положення - в протиріччя.

- тавтологія, чи

- протиріччя.

      Як і в логіці Буля в логіці висловлювань існують аксіоматичний, конструктивний методи доведення.

      Аксіоматичний метод побудови доведення полягає в тому, щоб на основі незалежних систем аксіом довести справедливість довільної клаузи. Доведення будується, як уже було сказано, на основі відношення порядку, тобто логіка висловлювань є розширенням логіки Буля і всі тотожності логіки Буля автоматично стають справедливими клаузами логіки висловлювань, тобто закони комутативності, асоціативності, дистрибутивності, нуля та одиниці стають аксіомами в логіці висловлювань. Для відношення порядку запишемо клаузу- "якщоістинне, то джерелом цієї істинності може бути, що завгодно, наприклад", або після перетворень"якщо раніше було відомо, що- істинне, то істинністьне може проявитися так, що стане хибним" або "істинність одного висловлювання не впливає на істинність другого висловлювання". Елементарна клауза відома з часів Арістотеля, грає важливу роль в логіці висловлювань, носить назву modus ponehs - правило відділення. Якщо в процесі доведення складної клаузи її звести до клаузи modus ponehs то доведення закінчилося.

      Історично першою системою аксіом класичної логіки була так звана система Фреге:

1. ;

2. ;

3. ;

4. ;

5. ;

      Перша аксіома є аксіомою порядку, 3-5 аксіоми логіки Буля, що записані у формі клауз.

Доведемо другу аксіому.

.

Виконаємо елементарні перетворення:

.

Скористаємося modus ponens .



Ще раз скористаємося modus ponens , прийдемо до аксіоми порядку

Розглянемо приклад.

      Приклад 11. Довести істинність клаузи аксіоматичним методом:

.

Доведення:

1. ,

2. ,

3. ,

4. ,

5. .

ЗМІСТ