3. Дві властивості логічного наслідку.

Теорема 5.3. Відношення логічного наслідку між формулами алгебри висловлень має наступні властивості:

а) ╞ , для i = 1, 2, …, т (рефлексивність відношення логічного наслідку) ;

б) якщо ╞ для j = 1, 2, …, р і ╞, то ╞ (транзитивність відношення логічного наслідку).

4. Логічний наслідок і рівносильність формул.

Теорема 5.4. Дві формули алгебри висловлень рівносильні тоді й тільки тоді, коли кожна із них є логічним наслідком іншої: FH  H F.

Наслідок. Якщо деяка формула є тавтологією, то і будь-який її логічний наслідок також є тавтологією. Символічно це можна записати так: ╞ F, F╞ H  ╞ H.

Доведення. Необхідність. Дано: . За означенням рівносильності обидві формули і для довільних конкретних висловлень перетворюються в висловлення і , які одночасно або істинні або хибні. Отже, кожне із висловлень → і → істинне для будь-яких висловлень . Це означає, що ╞→ і ╞→, звідки й випливає ╞ і ╞ .

Достатність. Дано: ╞ і ╞. Тоді ╞→ і ╞→. Оскільки формули → й → завжди перетворюються в істинні висловлення, то і їх кон’юнкція (→) (→) є формулою, яка завжди перетворюється істинне висловлення, тобто ╞ (→) (→). Але (→) (→) ↔. Отже ╞↔, а значить.

Наслідок. Якщо деяка формула є тавтологією, то і будь-який її логічний наслідок також є тавтологією. Символічно це можна записати так: ╞ F, F╞ H  ╞ H.

Лекція 6 План

1. Правила логічного висновку.

2. Знаходження наслідків з даних посилок.

3. Знаходження посилок для даного наслідку.

1. Правила логічного висновку

Розглянемо приклади структур правильного мислення, тобто, правила за якими із істинних посилок отримують істинні висновки.

Нехай маємо тавтологію ╞ (P (P → Q)) → Q.

За теоремою 5.2. маємо: F, F G ╞ G. Одержану схему, або правило виводу називають правилом modus ponens.

Правило 6.1 {modus ponens): .

Зміст цього правила такий. Якщо формули, що стоять над рискою тавтології, то й формула, що стоїть під рискою також тавтологія.

Використовуючи тавтологію одержуємо наступне правило modus tollens.

Правило 6.2 (modus tollens): .

Розглянуті правила дозволяють в істинній імплікації F → G із істинності посилки F робити висновок при істинність висновку G, а із хибності наслідку G  про хибність посилки F.

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

Правило 6.3 (введення кон’юнкції): .

Правило 6.4 (вилучення кон’юнкції): , .

Правило 6.5( введення диз’юнкції): , .

Правило 6.6 (контрапозиція): .

Правило 6.7 (силогізм або ланцюговий висновок): .

Правило 6.8 (перестановка посилок): .

Правило 6.9 (об’єднання й роз’єднання посилок):

, .

Правило 6.10 (розширена контрапозиція): .

Аналогічно формулюються й інші правила

На правила виведення можна дивитися з двох точок зору. По-перше, кожне з них є твердженням наступного типу: Формула, записана під рискою, є логічним наслідком усіх формул, записаних над рискою. По-друге, кожне із цих правил можна розглядати як правило одержання нових тавтологій із тих, що вже маємо.

Розглянемо ще один спосіб перевірки логічного наслідку.

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

З’ясуємо, чи виконується логічний наслідок

╞ .

Нехай існують такі конкретні висловлення A, B, C, що = 1, = 1, = 1, але = 0. Тоді з останнього співвідношення маємо = 0, = 0, що не суперечить співвідношенню = 1. Далі, співвідношення = 1 дає = 0 (так як = 0). Нарешті, обчисливши при заданих значеннях А, В і С значення , впевнюємося що воно рівне 1, а це знаходиться в повній відповідності з припущенням. Отже, приходимо до висновку: якщо висловлення А, В, С такі, що = = = 0, то при підстановці X = A, Y = B, Z = C формули-посилки приймуть значення 1, а формула X Z прийме значення 0. Звідси випливає, що формула X Z не вивідна з формул .