Логічні твердження
У цій темі ми працюємо з логічними виразами з формальним позначенням (наприклад, A або B), при цьому деякі логічні сполучення позначаються англійськими словами (and, or, not). Ця нотація поширена в інформатиці і використовується, наприклад, у багатьох мовах програмування. Розбиваємо тему на наступні підтеми:
- Логічні сполучники та таблиці істинності –значення окремих логічних сполучників, перепис із загальномовної на інформаційну нотацію (and, or, not, xor, ⇒, ⇔)
- Оцінювання логічних виразів – оцінка складених виразів, що поєднують декілька логічних сполучників
- Редагування логічних виразів – переписування до еквівалентного виразу (який виглядає інакше, але завжди має однакове значення істинності)
Ви також можете практикувати роботу з логічними твердженнями в різних нотаціях:
- Логічні твердження словами – висловлювання звичайною мовою
- Логіка на Знаємо математику – робота з висловлюваннями у математичній нотації (∧,∨,¬)
- Логічні вирази в Python – робота з логічними виразами в контексті програмування
Логічні сполучники та таблиці істинності
Значення істинності
В інформатиці ми використовуємо як взаємозамінне таке:
- 1 = true = правда
- 0 = false = неправда
Логічні сполучники
| Запис | Назва | Значення |
|---|---|---|
| not X | заперечення | X недійсний |
| X and Y | кон’юнкція, і також | X та Y дійсні водночас |
| X or Y | диз’юнкція, або | дійсним є X чи Y |
| X xor Y | ексклюзивне, або | тільки одне з X і Y є істинним |
| X \Rightarrow Y | імплікація, якщо, то | якщо дійсне X, тоді дійсне і Y |
| X \Leftrightarrow Y | еквівалентність, саме коли | X дійсне саме тоді, коли дійсне Y |
Таблиця істинності логічних операцій
| X | Y | X and Y | X or Y | X xor Y | X \Rightarrow Y | X \Leftrightarrow Y |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Оцінювання логічних виразів
Ми можемо думати про оцінку логічного виразу як про визначення його істинності чи хибності. Для простого висловлювання його оцінка відповідає його істинності, але для більш складних висловлювань з логічними сполучниками це поєднання істинності окремих підвисловлювань за допомогою сполучників.
Наприклад, сполучник and має значення істини (true, 1), якщо і тільки якщо обидва твердження є істинними.
Отже, 1 and 1 = 1, але, наприклад, 1 and 0 = 0.
Таблиця істинності логічних операцій
| X | Y | X \text{ and } Y | X \text{ or } Y | X \text{ xor } Y | X \Rightarrow Y | X \Leftrightarrow Y |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Редагування логічних виразів
Редагування логічних виразів підходить, наприклад, коли ми хочемо визначити істинність даного твердження або порівняти, чи збігаються два твердження. Для цього стануть в нагоді основні правила транскрипції.
Транскрипція основних логічних сполучників
| Твердження | Еквівалентне твердження |
|---|---|
| \text{not not } X | X |
| \text{not } (X \text{ and } Y) | (\text{not } X) \text{ or (not } Y) |
| \text{not }(X \text{ or }Y) | (\text{not } X) \text{ and (not } Y) |
Перепис імплікації, еквівалентності та операції xor
| Твердження | Еквівалентне твердження |
|---|---|
| X \Rightarrow Y | (\text{not } X) \text{ or } Y |
| X \Rightarrow Y | (\text{not } Y) \Rightarrow (\text{not } X) |
| X \Leftrightarrow Y | (X \Rightarrow Y) \text{ and } (Y \Rightarrow X) |
| X \Leftrightarrow Y | (X \text{ and } Y) \text{ or (not } X \text{ and not } Y) |
| X \text{ xor } Y | (X \text{ and not } Y) \text{ or (not } X \text{ and } Y) |
| \text{not } (X \Rightarrow Y) | X \text{ and not } Y |
| \text{not } (X \Leftrightarrow Y) | X \text{ xor } Y |
| \text{not } (X \text{ xor } Y) | X \Leftrightarrow Y |
Аналогічні закони, як і при обчисленні з числами
До логічних операцій and тa or також застосовуються комутативний (1-й і 2-й рядки наступної таблиці), асоціативний (3-й і 4-й рядки) і розподільний закони (5-й і 6-й рядки) :
| Твердження | Еквівалентне твердження |
|---|---|
| X \text{ and } Y | Y \text{ and } X |
| X \text{ or } Y | Y \text{ or } X |
| (X \text{ and }Y) \text{ and } Z | X \text{ and } (Y \text{ and }Z) |
| (X \text{ or } Y) \text{ or } Z | X \text{ or } (Y \text{ or } Z) |
| X \text{ and } (Y \text{ or } Z) | (X \text{ and } Y) \text{ or } (X \text{ and } Z) |
| X \text{ or } (Y \text{ and } Z) | (X \text{ or } Y) \text{ and } (X \text{ or } Z) |
Ви також можете знайти інші вправи з дещо іншими позначеннями на сторінці знаємо математику.
ВгоруЛогічний висновок з виразами
Логічнf послідовність за допомогою логічних виразів є формальним варіантом виведення логічних наслідків за допомогою слів.
Це процес, у якому ми отримуємо кілька логічних виразів (фактів) і виводимо з них інший вираз (висновок). Але нам не обов’язково просто робити нові висновки, ми також можемо, наприклад, спробувати вирішити, чи випливає надане твердження з інших.
Ми кажемо, що вираз виводиться (тобто випливає) із даних виразів тоді і тільки тоді, коли він справедливий у всіх випадках, у яких справедливі всі дані вирази.
Приклади
- З виразу X \text{ and } Y ми можемо зробити висновок X, тому що завжди, коли є дійсним X \text{ and } Y, має бути дійсним і X i Y, а через це є дійсним і саме X.
- З виразу X \text{ or } Y та \text{not } X ми можемо зробити висновок Y. Для того, щоб здійснювалось X \text{ or } Y, має бути дійсним X або Y, але X не може бути дійсним. Тому дійсне Y.
- З виразу X \Leftrightarrow Y та X ми можемо зробити висновок Y. Вираз X \Leftrightarrow Y стверджує, що Y завжде має те ж значення, що і X. З правдивості X ми тоді можемо виводити і правдивість Y.
