Логіка вивчає способи виведення висновків з припущень. Логіка спочатку виникла як частина філософії, пізніше значно розвинулася у математиці. Сьогодні вона має важливе застосування також в інформатиці.
Основа математичного уявлення про логіку – це висловлювальна логіка, в якій ми працюємо з висловлюваннями (твердження, які можуть бути або істинні, або хибні) та логічними зв’язками (та, або, заперечення). Розширенням висловлювальної логіки є предикатна логіка, в якій додатково використовуються квантифікатори (існує, для кожного).
Огляд тем з логіки, доступних на Знаємо математику:
| Тема | Опис |
|---|---|
| Логічні вислови | Усний запис логічних висловів |
| Логіка: поняття та позначення | Запис висловів за допомогою логічних зв’язок \wedge, \vee, \neg, \Rightarrow, \Leftrightarrow |
| Оцінювання логічних висловів | Оцінка правдивості логічних висловів, записаних за допомогою логічних операцій |
| Виправлення логічних висловів | Виправлення та спрощення логічного вислову за правилами роботи з логічними операціями |
| Квантифікатори | Збагачення логічних висловів квантифікаторами \exists, \forall |
| Докази | Точні математичні процедури для перевірки правильності логічних висловів |
У рамах системи Знаємо ви також знайдете логіку в інформатиці: логіка на Знаємо інформатику. Там акцент зроблений на логічні зв’язки, використовувані при програмуванні та розв’язанні логічних завдань.
ВгоруЛогіка: основні поняття
Твердження
Твердження — це судження, для якого має сенс питання, чи є воно правдивим чи неправдивим, причому може бути лише одна з цих можливостей.
Приклади тверджень:
- Місто Харків знаходиться в Україні (правдиве твердження)
- Харків є столицею України (неправдиве твердження)
- На Марсі закопано скарб (твердження, істинність якого нам невідома)
Приклади речень, які не є твердженнями: Ти голодний? Піди до крамниці за яйцями.
Логічні сполучники
| Запис | Назва | Значення |
|---|---|---|
| \neg A | заперечення | A не є правдивим |
| A \wedge B | кон’юнкція, і одночасно | A та B є правдивими одночасно |
| A \vee B | диз’юнкція, або | принаймні одне з A та B є правдивим |
| A \Rightarrow B | імплікація, якщо-то | якщо A є правдивим, то і B — правдиве |
| A \Leftrightarrow B | еквівалентність, тільки коли, тоді | тільки тоді A правдиве, коли B правдиве |
Тавтології та суперечності
Тавтологія — це формула твердження, яка завжди правдива. Приклади:
- A \vee \neg A (закон виключеного третього)
- (A \Rightarrow B) \Leftrightarrow (\neg B \Rightarrow \neg A)
Суперечність — це формула твердження, яка завжди є неправдивою. Прикладом є формула A \wedge \neg A (закон протиріччя).
Формула є виконуваною, якщо вона не є суперечністю.
ВгоруОцінка логічних виразів
Таблиця істинності логічних операцій
| A | B | A \vee B | A \wedge B | A \Rightarrow B | A \Leftrightarrow B |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Зміни логічних виразів
Переписування імплікації та еквівалентності
| Твердження | Еквівалентне твердження | |
|---|---|---|
| A\Rightarrow B | \neg A\vee B | |
| A\Rightarrow B | \neg B\Rightarrow \neg A | |
| A\Leftrightarrow B | (A\wedge B)\vee (\neg A \wedge \neg B) |
Заперечення складених тверджень
| Твердження | Еквівалентне твердження | |
|---|---|---|
| \neg (\neg A) | A | |
| \neg (A\vee B) | \neg A\wedge \neg B | |
| \neg (A\wedge B) | \neg A\vee \neg B | |
| \neg (A\Rightarrow B) | A\wedge \neg B | |
| \neg (A\Leftrightarrow B) | (\neg A\wedge B)\vee(A \wedge \neg B) |
Правила для заперечення диз’юнкції та кон’юнкції (2-й та 3-й рядок таблиці) називаються Законами де Моргана.
Аналогічні закони, як і при обчисленні з числами
Для логічних операцій \wedge, \vee також діють комутативні (1-й та 2-й рядок наступної таблиці), асоціативні (3-й та 4-й рядок) та дистрибутивні закони (5-й та 6-й рядок):
| Твердження | Еквівалентне твердження | |
|---|---|---|
| A \wedge B | B \wedge A | |
| A \vee B | B \vee A | |
| (A \wedge B) \wedge C | A \wedge (B \wedge C) | |
| (A \vee B) \vee C | A \vee (B \vee C) | |
| A \wedge (B \vee C) | (A \wedge B) \vee (A \wedge C) | |
| A \vee (B \wedge C) | (A \vee B) \wedge (A \vee C) |
Квантори
Квантифікатори
| Позначення | Поняття | Значення |
|---|---|---|
| \exists x | існуючий квантифікатор | існує x, таке що… |
| \forall x | загальний (універсальний) квантифікатор | для кожного x виконується… |
Приклади висловів з квантифікаторами
Властивість: число x парне можна виразити, як існує ціле число k таке, що x = 2\cdot k. Це можна записати як \exists k \in \mathbb{Z}: x = 2\cdot k.
Твердження Підводні човни (P) не можуть літати (L). можна записати, як \forall x: P(x) \Rightarrow \neg L(x).
У складніших висловах з кількома квантифікаторами ми маємо дбати про порядок квантифікаторів:
- \exists x\in M\ \forall y \in M: y \leq x – існує елемент у множині M, який є більшим або рівним усім іншим елементам у M, тобто вислів каже, що множина має найбільший елемент.
- \forall x\in M\ \exists y \in M: y \leq x – для кожного елемента у множині M існує елемент x, який менший або рівний X. Оскільки можна вибрати y=x, то це виконується для будь-якої множини (для просунутих: лише якщо розглядаємо множини чисел і \leq як звичайне упорядкування на числах).
\exists x\in M\ \forall y \in M: y \leq x – існує елемент у множині M, який є більшим або рівним усім іншим елементам у M, тобто вислів каже, що множина має найбільший елемент. \forall x\in M\ \exists y \in M: y \leq x – для кожного елемента у множині M існує елемент x, який менший або рівний x. Оскільки можна вибрати y=x, це виконується для будь-якої множини (для просунутих: лише якщо розглядаємо множини чисел і \leq як звичайне упорядкування на числах).
Заперечення тверджень з квантифікаторами
Під час заперечення тверджень з квантифікаторами змінюємо існуючий квантифікатор на загальний (і навпаки) і переміщуємо заперечення «всередину». Приклад:
- Не є правдою, що всі коти (К) чорні (Ч).
- \neg (\forall x: K(x) \Rightarrow C(x))
- Змінюємо загальний квантифікатор на існуючий і заперечуємо твердження.
- \exists x: \neg(K(x) \Rightarrow C(x))
- Тепер заперечуємо імплікацію за допомогою правила \neg(A \Rightarrow B) \Leftrightarrow (A \wedge \neg B).
- \exists x: K(x) \wedge \neg C(x)
- Існує кіт, який не є чорним.
