Математика в Internet |
Логіка це наука про способи доведень. Ми розглянули доведення в логіці Буля, які будувалися на
відношенні еквівалентності. Дві логічні функції вважалися еквівалентними, якщо вони давали на
відповідних наборах аргументів однакові значення нулів та одиниць.
В логіці висловлювань всі доведення будуються на відношенні порядку, тобто відношенні між
причиною та наслідком. Окремі ланцюги доведення зв'язані символом імплікації "", проте при
доведенні використовують символ"". Символ""називають об'єктивним, а""- суб'єктивним, або
метасимволом. Аналогічно: замість об'єктивної кон'юнкції""будемо використовувати суб'єктивний
символ метакон'юнкції - ",", а замість об'єктивної диз'юнкції""- суб'єктивну метадиз'юкцію -
";". Тоді твердження, що вимагає доведення в логіці висловлювань можна оформити у виді
причинно-наслідкового відношення.
,
де - причина (посилка);
А - наслідок (висновок).
Читається: "Якщо посилки - істинні, то наслідок А теж істинний".
Щоб не переплутати об'єктивні висловлювання з суб'єктивними, істинність яких треба встановити
домовимося речення типу називати клаузами - метареченнями, в яких використовуються відношення
порядку, оформлені через символ метаімплікації.
Відомо, що відношення порядку задовольняє трьом законам:
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. .
ЗМІСТ |