Елементи математичної логіки; булеві функції; логіка висловлювань

📌 Про що ця тема

Тут перевіряють уміння працювати з висловлюваннями — реченнями, про які можна сказати «істина» або «хиба», — та будувати з них складені вирази за допомогою логічних операцій. Ключові поняття: логічне висловлювання, логічні операції (НЕ, І, АБО), таблиця істинності, булева функція.

📖 Головне

• Висловлювання — твердження, яке є або істинним (1, true), або хибним (0, false). «Київ — столиця України» істинне; «2>5» хибне. Питання й накази висловлюваннями не є.

• Логічні змінні позначають буквами (A, B, X). Вони набувають лише двох значень: 0 або 1.

• Заперечення (НЕ, інверсія, not, ¬A, Ā): міняє значення на протилежне. НЕ(1)=0, НЕ(0)=1.

• Кон’юнкція (І, логічне множення, and, A∧B): істинна ЛИШЕ коли обидва операнди істинні. Схоже на множення: 1∧1=1, решта 0.

• Диз’юнкція (АБО, логічне додавання, or, A∨B): істинна, коли ХОЧА Б ОДИН операнд істинний. Хибна лише 0∨0=0.

• Виключне АБО (xor, ⊕): істинне, коли значення РІЗНІ. 1⊕0=1, 1⊕1=0.

• Імплікація (A→B, «якщо A, то B»): хибна лише коли A=1, B=0. В інших випадках істинна.

• Еквіваленція (A↔B): істинна, коли значення ОДНАКОВІ.

• Пріоритет операцій: спершу НЕ, потім І, потім АБО. Дужки змінюють порядок.

• Таблиця істинності — перелік усіх комбінацій значень змінних і результату. Для n змінних — 2ⁿ рядків.

• Булева функція — функція від логічних змінних, що повертає 0 або 1; задається формулою або таблицею істинності.

• Закони: подвійне заперечення НЕ(НЕ A)=A; закони де Моргана НЕ(A∧B)=НЕ A ∨ НЕ B і НЕ(A∨B)=НЕ A ∧ НЕ B.

🔢 Як це працює на прикладі

Побудуємо таблицю для F = НЕ A ∨ B (це те саме, що A→B).

A=0, B=0: НЕ A=1, 1∨0=1

A=0, B=1: НЕ A=1, 1∨1=1

A=1, B=0: НЕ A=0, 0∨0=0

A=1, B=1: НЕ A=0, 0∨1=1

Отже F=0 лише у третьому рядку — збігається з імплікацією.

Приклад 2: обчислимо (A∧B)∨НЕ C при A=1, B=0, C=0.

A∧B = 1∧0 = 0; НЕ C = 1; 0∨1 = 1. Відповідь: 1.

⚠️ Типові помилки

• Плутають І та АБО: кон’юнкція — це «множення» (істина лише коли все істинне), диз’юнкція — «додавання».

• Забувають пріоритет: у A∨B∧C спершу виконують B∧C, а не зліва направо.

• Невірно рахують рядки таблиці: для 3 змінних це 2³=8, а не 6.

• Помиляються в імплікації: вважають її хибною при A=0; насправді хибна лише 1→0.

• Застосовують де Моргана без заміни операції: НЕ(A∧B) ≠ НЕ A ∧ НЕ B — знак обов’язково міняється.

🎯 Що завчити напамʼять

• Кон’юнкція=1 лише при 1∧1. Диз’юнкція=0 лише при 0∨0.

• Імплікація A→B=0 лише при 1→0.

• Xor=1 при різних, еквіваленція=1 при однакових.

• Кількість рядків = 2ⁿ.

• Пріоритет: НЕ → І → АБО.

• Закони де Моргана.

🧠 Перевір себе

1. Скільки рядків у таблиці істинності для 4 змінних?

2. Чому дорівнює 0→1?

3. Спрости НЕ(A∨B) за де Морганом.

4. Обчисли (1∨0)∧НЕ 1.

Відповіді: 1 — 2⁴=16; 2 — 1 (істина); 3 — НЕ A ∧ НЕ B; 4 — (1)∧0 = 0.