Поняття логічного слідування

Основним завданням математичної логіки є мистецтво правильних умовиводів із правильних посилок, тобто мистецтво міркування.

Одержання нових знань із уже наявних, виражених у формі висловлення, називається умовивід або міркування. При цьому вихідні висловлення, твердження називаються гіпотезами або посилками, а одержувані – висновком або логічним наслідком.

Правильним умовиводом називається таке міркування, висновок (логічний наслідок) якого є істинний щораз, коли істинні його гіпотези.

Умовивід представляють у вигляді , де

‑ гіпотези, ‑ висновок, а символ “ ” означає “отже”.

Формула B(p₁,p₂,...,p_n) є логічним слідуванням формули A(p₁,p₂,...,p_n), якщо B приймає значення 1 для всіх тих наборів значень пропозиційних змінних, для яких формула A істинна (тобто приймає значення 1); позначатимемо це AÞB.

Очевидно, що дві формули A і B є рівносильними тоді і тільки тоді, коли кожна з них є логічним слідуванням іншої, тобто A=B тоді і тільки тоді, коли AÞB і BÞA.

Формула B(p₁,p₂,...,p_n) є логічним слідуванням формул (p₁,p₂,...,p_n), … , (p₁,p₂,...,p_n), якщо B приймає значення 1 для всіх тих наборів значень пропозиційних змінних, для яких всі формули , … , приймають значення 1; позначатимемо це , … , ÞB.

Теорема. Формула B(p₁,p₂,...,p_n) є логічним слідуванням формул (p₁,p₂,...,p_n), … , (p₁,p₂,...,p_n) тоді і тільки тоді, коли тавтологією є формула , тобто

якщо , то (тавтологія)

Правильність (або істинність) побудованого умовиводу можна перевірити двома способами, а саме:

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

Властивості логічного слідування

1. Якщо і , то (властивість транзитивності).
2. Якщо і Р – довільна формула алгебри висловлень, то

(приєднання довільної формули алгебри висловлень до числа посилок не порушує даного логічного слідування).

1. Якщо і є тавтологією, то

(вилучення з числа посилок формули, яка є тавтологією, не порушує даного логічного слідування)

Схеми логічного слідування (правила виведення) в логіці висловлювань

1. Modus ponens (МР) (правило висновку): p q, p q

2. Modus tollens (МТ): p q, (tollens - заперечувальний)

3. Введення диз’юнкції: p p q;

4. Вилучення кон’юнкції: p, q p;

Похолоднішало і почав падати дощ, отже похолоднішало.

5. Правило силогізму: p q, q r p r;

Якщо сьогодні падатиме дощ, то сьогодні ми не поїдемо на пікнік. Якщо ми не поїдемо на пікнік сьогодні, то поїдемо завтра. Отже, якщо сьогодні падатиме дощ, то поїдемо на пікнік завтра.

6. Диз’юнктивний силогізм: ;

7. Резолюція: .

Множина формул (p₁,p₂,...,p_n), … , (p₁,p₂,...,p_n), називається сумісною (несуперечною), якщо існує такий розподіл істинісних значень p₁,p₂,...,p_{n, ,} при якому

Множина формул, яка не є сумісною, називається суперечною.

Множина формул (p₁,p₂,...,p_n), … , (p₁,p₂,...,p_n), називається сумісною(суперечною) тоді і тільки тоді, коли хоча б на одному наборі (на всіх наборах) значень p₁,p₂,...,p_n,, всі формули (хоча б одна з формул) набувають (набуває ) значення 1 (0).

Теорема Якщо Г – суперечна множина формул логіки висловлювань, то для довільної формули А має місце слідування