# Лекція 5. Математична логіка

## Огляд

Дискретна математика — це передусім наука про **строгі міркування**: майже кожне
твердження цього курсу ми не просто проголошуємо, а **доводимо**. Але щоб говорити про
доведення чесно, треба спершу мати мову, якою можна точно записати самі твердження та
правила, за якими з одних тверджень дозволено виводити інші. Такою мовою є
**математична логіка**, а її найпростіший, базовий поверх — **логіка висловлювань**
(пропозиційна логіка) — і є темою цієї лекції.

Логіка висловлювань — це, по суті, та сама двоелементна алгебра, яку ми вивчали в
[Лекції 3](ODM-L03.md) про **булеві операції**, але побачена під іншим кутом — під кутом
*істини та смислу*, а не суто символьних перетворень. Там, де в булевій алгебрі стояли
біти $1$ і $0$, тут стоятимуть значення **істина** (І) і **хиба** (Х); де там писали
операції $\cdot$ і $+$, тут писатимуть $\wedge$ («і») та $\vee$ («або»); закони, яким
вони підпорядковані (комутативність, дистрибутивність, де Морган), — ті самі. Це не
приблизна аналогія, а точна відповідність: логіка висловлювань *є* двоелементною
булевою алгеброю, прочитаною семантично. Тому все, що ви вже вмієте спрощувати в булевих
виразах, негайно переноситься сюди.

Навіщо будувати *формальну* мову для таких буденних слів, як «і», «або», «якщо»? З трьох
причин, і кожна — наскрізна тема курсу:

- **Точність.** Природна мова багатозначна: «або» буває включним і виключним, «якщо»
  часто плутають з «тоді й лише тоді». Формальна мова змушує кожне речення мати рівно
  одну структуру та рівно одне значення істинності за кожної інтерпретації.
- **Механізація.** Щойно смисл зведено до скінченного перегляду таблиці, перевірити
  правильність міркування, коректність схеми чи сумісність обмежень може вже *машина*.
  Звідси беруть початок автоматичне доведення теорем, SAT-розв'язувачі та верифікація
  апаратного й програмного забезпечення.
- **Основа для доведень.** Кожне доведення, яке ви писатимете далі, — пряме, від
  супротивного, за випадками — є дисциплінованим способом установити саме ті *смислові*
  зв'язки, які означено тут. Не можна сказати, що доводить доведення, поки не сказано,
  що *означають* його твердження.

> **Про два поверхи логіки.** Логіка висловлювань оперує *цілими* реченнями як
> неподільними атомами: «Дніпро впадає в Чорне море» — один атом, і його внутрішня
> будова («Дніпро», «впадає») її не цікавить. Цього замало, щоб виразити міркування на
> кшталт «усі люди смертні; Сократ — людина; отже, Сократ смертний»: тут суттєве слово
> «усі» та внутрішня структура «$x$ — людина». Такі засоби — предикати та квантори
> $\forall, \exists$ — вивчає **логіка предикатів** у [Лекції 6](ODM-L06.md). Ця лекція —
> необхідний фундамент під неї.

У цьому розділі ми послідовно вводимо поняття **висловлення**, будуємо **алфавіт і
зв'язки** алгебри висловлювань, означуємо кожну операцію її **таблицею істинності**,
учимося **інтерпретувати** та **формалізувати** речення, класифікуємо формули на
**тавтології, суперечності й нейтральні**, означуємо **логічний наслідок** і, нарешті,
переходимо від *семантики* (істина, таблиці) до *синтаксису* доведення — **правил
виводу** та **числення висловлювань**. Кілька ключових фактів (означальні таблиці,
теорема про дедукцію, коректність правил відділення й від'ємної форми) ми **доводимо**.

---

## 5.1 Висловлення та їхні значення істинності

### Мотивація

Будь-яке міркування складається з тверджень, кожне з яких ми вважаємо або правильним,
або неправильним, і сполучників між ними. Щоб міркувати точно, треба спершу відокремити
речення, які взагалі *можуть* бути істинними чи хибними, від тих, до яких поняття
істинності незастосовне. Це й робить перше означення.

> **Означення (висловлення).** **Висловленням** (**висловлюванням**, англ. *statement*,
> *proposition*) називають розповідне (оповідальне) речення, яке є або **істинним**, або
> **хибним** — але не одночасно і не жодним із двох.

Два можливі значення утворюють крихітну **множину значень істинності**
$\{\text{істина}, \text{хиба}\}$, яку ми позначатимемо $\{\text{І}, \text{Х}\}$ або, у
дусі [Лекції 3](ODM-L03.md), $\{1, 0\}$. Важливо не *чи знаємо ми зараз*, яке саме
значення має речення, а те, що воно *має* рівно одне з двох. Речення «існує нескінченно
багато простих чисел-близнюків» — цілком правильне висловлення, хоча на час написання
цих рядків ніхто не знає, істинне воно чи хибне.

Розгляньмо речення, з яких традиційно починають курс логіки (вони — просто зі слайдів):

- «**Дніпро впадає в Чорне море.**» — висловлення; воно **істинне**.
- «**Дніпро впадає в Азовське море.**» — висловлення; воно **хибне**.
- «**Яке сьогодні число?**» — **не** висловлення: це запитання, йому не можна приписати
  ні І, ні Х.

Реченнями, що висловленнями **не є**, зокрема, бувають:

- **запитання** — «Котра година?»;
- **накази (спонукання)** — «Зачини двері.»;
- **оклики** — «Який холод!»;
- **парадоксальні самопосилальні речення** — «Це речення хибне.» Якби воно було
  істинним, то було б хибним, а якби хибним — істинним; йому несуперечливо не можна
  приписати жодного значення, тож воно взагалі лежить поза межами висловлень. (Це
  **парадокс брехуна**; сама потреба обережно виключати такі речення — одна з причин,
  чому важливий формальний синтаксис.)

### Відкриті речення (пропозиційні функції)

Тонший випадок — речення «**$X$ ділиться на $5$**» зі слайда. Само по собі воно не має
сталого значення істинності: воно залежить від $X$. Висловленням воно стає лише після
того, як $X$ дістане конкретне значення: для $X = 15$ — істинне, для $X = 8$ — хибне.

> **Означення (відкрите речення).** Речення з вільною змінною, значення істинності якого
> залежить від того, що підставлено замість змінної, називають **відкритим реченням**
> (**пропозиційною функцією**, **предикатом**).

Логіка висловлювань розглядає лише *закриті* речення з визначеним значенням; відкриті
речення разом із кванторами «для всіх» ($\forall$) та «існує» ($\exists$), потрібними,
щоб їх «закрити», — предмет [Лекції 6](ODM-L06.md).

> **Приклад 5.1 (класифікація).** Визначимо тип кожного речення.
> (а) «$7$ — просте число.»
> (б) «Передайте, будь ласка, сіль.»
> (в) «$n^2 \ge 0$ для цілого $n$.»
> (г) «Чи йде дощ?»
> (ґ) «$x + 3 = 10$.»
>
> **Розв'язання.** (а) висловлення, **істинне**. (б) **не** висловлення (наказ). (в)
> висловлення, **істинне**: змінну $n$ зв'язано зворотом «для цілого $n$», тож речення в
> цілому робить визначене (істинне) твердження. (г) **не** висловлення (запитання). (ґ)
> **відкрите речення** — істинне при $x = 7$ і хибне інакше; висловленням стає лише після
> фіксації $x$.

> **Типова помилка (незнання проти відсутності значення).** Не плутайте «*ми не знаємо
> значення істинності*» з «*речення не має значення істинності*». Гіпотеза Ґольдбаха —
> висловлення (рівно одне з двох значень), хоча її статус відкритий. Натомість «$x+3=10$»
> справді не має значення істинності, доки не задано $x$, — це об'єкт іншого роду,
> відкрите речення.

---

## 5.2 Атомарні та складені висловлення

Речення бувають простими й складеними. Просте речення не розкладається на менші
висловлення; складене збирають із простих за допомогою сполучників.

> **Означення (атом).** **Атом** (**атомарне**, **елементарне висловлення**) — це просте
> оповідальне речення, що не містить жодної логічної зв'язки і не розкладається на менші
> висловлення. Атоми — неподільні «цеглинки» мови; їх позначають **пропозиційними
> змінними**: малими $p, q, r, s, \dots$ або великими $P, Q, R, S, \dots$

> **Означення (складене висловлення).** **Складеним** (**молекулярним**) висловленням
> називають висловлення, побудоване з атомів за допомогою **логічних зв'язок**.

Означальна риса всієї мови вловлюється одним принципом.

> **Принцип істиннісної функційності.** Значення істинності складеного висловлення
> **повністю** визначається значеннями істинності його атомів разом зі змістом зв'язок —
> і **нічим більше**.

Це справжнє обмеження, і саме воно робить теорію обчислюваною. Зв'язка «і» дає лише
правило комбінування значень; їй байдуже, *про що* атоми, чи пов'язані вони за змістом,
чи один спричиняє інший, чи взагалі йдеться про одне й те саме. Складене «$2+2=4$ **і**
Київ — місто» істинне з тієї самої причини, що й «трава зелена **і** сніг білий»: обидві
частини істинні. Природна мова інколи «протягує» додатковий смисл (порядок подій у «вона
відчинила двері й вийшла»), але логіка висловлювань свідомо його відкидає.

> **Приклад 5.2.** «Петро запізнювався» — атом, позначмо його $P$. «Петро запізнювався і
> Петро перевищив швидкість» — складене висловлення $P \wedge Q$, де $Q$ — атом «Петро
> перевищив швидкість». Ціле речення не несе жодного власного значення понад те, що дають
> $P$, $Q$ і зв'язка $\wedge$. (До цього прикладу ми повернемося в §5.7.)

---

## 5.3 Алфавіт і зв'язки алгебри висловлювань

Щоб перетворити ці ідеї на числення, зафіксуймо точний **алфавіт** мови — скінченний
набір символів, з яких будують формули.

> **Означення (алфавіт алгебри висловлювань).** Алфавіт складається з:
> - **пропозиційних змінних** $p, q, r, \dots$ (зліченний запас атомів);
> - **логічних зв'язок** $\neg,\ \wedge,\ \vee,\ \to,\ \leftrightarrow$;
> - **допоміжних символів** — лівої та правої дужок $($ і $)$.

Логіка висловлювань використовує п'ять стандартних зв'язок. **Заперечення** — **унарна**
(діє на одну формулу); решта чотири — **бінарні** (сполучають дві).

| Зв'язка | Символ | Читається | Значення |
|---|:--:|---|---|
| **Заперечення** | $\neg p$ | «не $p$» | інвертує значення |
| **Кон'юнкція** | $p \wedge q$ | «$p$ і $q$» | істинне, коли істинні обидві |
| **Диз'юнкція** | $p \vee q$ | «$p$ або $q$» | істинне, коли істинна хоч одна |
| **Імплікація** | $p \to q$ | «якщо $p$, то $q$» | хибне лише при $p=$І, $q=$Х |
| **Еквіваленція** | $p \leftrightarrow q$ | «$p$ тоді й лише тоді, коли $q$» | істинне, коли значення збігаються |

> **Зауваження (інші позначення).** Символіка логіки не усталена повністю. На слайдах
> курсу заперечення записують як `!p` або $\sim p$, еквіваленцію — як $\sim$ чи
> $\Leftrightarrow$, імплікацію — як $\Rightarrow$. У [Лекції 3](ODM-L03.md) заперечення
> позначали рискою $\overline{p}$. Ми в цій лекції дотримуємося набору
> $\neg,\wedge,\vee,\to,\leftrightarrow$, але корисно впізнавати всі варіанти. Ще одна
> корисна зв'язка — **виключне «або»** $p \oplus q$ («рівно одне з двох»), до якого ми
> повернемося в §5.4.

**Термінологія імплікації.** У записі $p \to q$ висловлення $p$ називають
**засновком** (**антецедентом**, **умовою**), а $q$ — **висновком** (**консеквентом**,
**наслідком**). З однієї імплікації будують ще три формули з тих самих атомів; уміти їх
розрізняти конче потрібно:

- **обернена** (конверсія): $q \to p$;
- **протилежна** (інверсія): $\neg p \to \neg q$;
- **контрапозиція** (протилежна до оберненої): $\neg q \to \neg p$.

> **Типова помилка (імплікація $\ne$ обернена).** Умовне речення **не** рівносильне ні
> своїй оберненій, ні протилежній. «Якщо йде дощ, то земля мокра» ($p \to q$) не
> випливає з «якщо земля мокра, то йшов дощ» (обернена — могли ввімкнути поливалку). Проте
> воно **рівносильне** своїй контрапозиції «якщо земля не мокра, то дощу не було» — цей
> факт ми доведемо в §5.8 і постійно вживатимемо як правило виводу в §5.10.

---

## 5.4 Операції та їхні таблиці істинності

Кожну зв'язку **означують** тим, як вона обчислює значення істинності. Найпрозоріший
спосіб задати цю функцію — **таблиця істинності**: усі можливі набори значень атомів
разом зі значенням результату. Наведена нижче таблиця — це означення всіх п'яти операцій
(вона ж — таблиця зі слайда «Інтерпретація висловлювань»).

![Означальна таблиця істинності п'яти логічних операцій: заперечення, кон'юнкція, диз'юнкція, імплікація, еквіваленція](img/l05_truth_ops.png)

| $A$ | $B$ | $\neg A$ | $A \wedge B$ | $A \vee B$ | $A \to B$ | $A \leftrightarrow B$ |
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
| Х | Х | І | Х | Х | І | І |
| Х | І | І | Х | І | І | Х |
| І | Х | Х | Х | І | Х | Х |
| І | І | Х | І | І | І | І |

> **Зауваження (порядок рядків).** Рядки впорядковано так, що Х передує І, а пари
> $(A,B)$ читаються як двійкові числа з $\text{Х}=0$, $\text{І}=1$, зростаючи:
> $00, 01, 10, 11$. Годиться будь-який фіксований порядок; важлива лише сталість, і ми
> дотримуватимемося цього до кінця лекції. Це той самий порядок, у якому в
> [Лекції 3](ODM-L03.md) виписували таблиці булевих функцій.

Прочитаймо кожен стовпчик як означення й водночас коментар до природної мови.

**Заперечення $\neg A$** інвертує значення: істинне робить хибним і навпаки. Природномовні
відповідники: «не», «неправильно, що».

**Кон'юнкція $A \wedge B$** істинна **лише** тоді, коли істинні *обидва* члени. Логічно
«але» — це теж $\wedge$: «іде дощ, **але** світить сонце» — просто кон'юнкція $p \wedge q$.
Українське «але» сигналізує про контраст, але істиннісно контрасту не існує.

**Диз'юнкція $A \vee B$** хибна лише тоді, коли хибні *обидва* члени; отже, вона
**включна** — істинна й тоді, коли істинні обидва.

> **Зауваження (включне проти виключного «або»).** Українське «або» інколи **виключне**
> («суп або салат, але не обидва»). Це вже *інша* зв'язка — **виключне «або»**
> $A \oplus B$, істинне рівно тоді, коли істинний рівно один член. Через основні операції:
> $$ A \oplus B \;\equiv\; (A \vee B) \wedge \neg(A \wedge B) \;\equiv\; (A \wedge \neg B) \vee (\neg A \wedge B). $$
> Коли меню каже «суп або салат», мають на увазі $\oplus$; коли стипендію призначають
> «студентам, що вивчають математику або інформатику», мають на увазі $\vee$ (подвійна
> спеціалізація теж підходить). Який зміст обрано — питання перекладу, а не логіки.

**Імплікація $A \to B$** хибна **в єдиному випадку** — коли засновок $A$ істинний, а
висновок $B$ хибний; в усіх інших випадках вона істинна. Зокрема, коли засновок $A$
хибний, імплікація $A \to B$ істинна **тривіально** (**пусто-істинна**), хай там яке $B$:
речення «якщо Місяць зроблено із сиру, то $2+2=5$» — *істинна* імплікація. Імплікація
вловлює образ «$B$ гарантовано щоразу, коли $A$», а не «$A$ спричиняє $B$».

> **Типова помилка (пусто-істинність).** Рядок $A=$Х дає $A \to B =$І незалежно від $B$.
> Студенти часто вважають таку імплікацію «неповною» чи «беззмістовною» — але за
> означенням вона істинна. Саме цей рядок робить коректним доведення тверджень про
> порожню множину (як-от $\varnothing \subseteq A$ в [Лекції 1](ODM-L01.md)).

**Еквіваленція $A \leftrightarrow B$** істинна рівно тоді, коли $A$ і $B$ мають *однакове*
значення. Її можна розкласти на дві імплікації (це доведемо в §5.8):
$A \leftrightarrow B \equiv (A \to B) \wedge (B \to A)$.

### Пріоритет зв'язок

Щоб не громадити дужок, домовляються про **пріоритет** (від найвищого, що зв'язує
найщільніше, до найнижчого):

$$
\neg \;\succ\; \wedge \;\succ\; \vee \;\succ\; \to \;\succ\; \leftrightarrow .
$$

Наприклад, $\neg p \vee q \to r$ читається як $((\neg p) \vee q) \to r$. Бінарні зв'язки
за домовленістю асоціюють **праворуч**, тож $p \to q \to r$ означає $p \to (q \to r)$.

> **Типова помилка (асоціативність $\to$).** Праворучна асоціація — це *домовленість про
> скорочення*, а не логічний закон: формули $(p \to q) \to r$ і $p \to (q \to r)$
> **не рівносильні** (їхні таблиці різняться). У сумніві — **ставте дужки**.

---

## 5.5 Аналоги природної мови

Найперша практична навичка логіки — упізнавати, яку зв'язку ховає той чи той зворот живої
мови. Наведена таблиця (зі слайда «Аналоги природної мови») зіставляє кожну операцію з
типовими українськими зворотами.

![Таблиця відповідності логічних операцій зворотам природної мови](img/l05_analogues.png)

| Операція | Звороти природної мови |
|---|---|
| **Еквіваленція** $\leftrightarrow$ | еквівалентно; рівносильно; тоді й тільки тоді; якщо і тільки якщо; необхідно й достатньо |
| **Імплікація** $\to$ | якщо …, то …; тільки якщо; звідси; достатньо, щоб; необхідно, щоб |
| **Кон'юнкція** $\wedge$ | і; та; а також; обидва; хоча; але; проте |
| **Диз'юнкція** $\vee$ | або; чи; один із двох; принаймні одне |
| **Заперечення** $\neg$ | не; неправильно, що; неправда, що |

Кілька зворотів заслуговують окремої уваги, бо саме на них найчастіше спотикаються.

- «$p$ **тільки якщо** $q$» — це $p \to q$, а **не** $q \to p$. Зворот каже, що $p$ може
  справдитися *лише за обставин*, коли справджується й $q$.
- «$p$, **якщо** $q$» — навпаки, $q \to p$.
- «$q$ **необхідно** для $p$» — це $p \to q$; «$p$ **достатньо** для $q$» — теж $p \to q$.
- «$A$, **якщо не** $B$» (зворот «$A$, окрім випадку $B$») — це $\neg B \to A$, рівносильно
  $B \vee A$.
- «**ні** $p$, **ні** $q$» — це $\neg p \wedge \neg q$, рівносильно $\neg(p \vee q)$.

> **Приклад 5.3 (місце заперечення).** Розгляньмо два схожі звороти:
> «**не обидва** $p$ і $q$» $= \neg(p \wedge q)$ — хоч одне хибне;
> «**і не** $p$, **і не** $q$» $= \neg p \wedge \neg q$ — хибні обидва.
> Це різні формули: перша істинна при $p=$І, $q=$Х, а друга — ні. За законом де Моргана
> перша дорівнює $\neg p \vee \neg q$ — зверніть увагу на «*або*».

> **Типова помилка (підміна «і»↔«або» після «не»).** У побутовій мові кажуть «не можна
> мати й тістечко, і морозиво», маючи на увазі «щонайбільше одне» — логічно
> $\neg(c \wedge m)$, тобто $\neg c \vee \neg m$. Українське «і» лишається, а правильний
> переклад містить «або». Завжди перекладайте *смисл*, а закон де Моргана узгодить його зі
> словами.

---

## 5.6 Формули та їхня інтерпретація

### Правильно побудовані формули

Перш ніж питати, що формула *означає*, треба точно сказати, які саме рядки символів
*є* формулами. Це роблять **рекурсивно** — так само, як у [Лекції 1](ODM-L01.md)
рекурсивно задавали множини.

> **Означення (правильно побудована формула).** **Правильно побудовані формули** (ППФ,
> англ. *well-formed formulas*) логіки висловлювань означують рекурсивно:
> 1. **(база)** кожна пропозиційна змінна $p, q, r, \dots$ є ППФ (атом);
> 2. **(заперечення)** якщо $\varphi$ — ППФ, то $(\neg \varphi)$ — ППФ;
> 3. **(бінарні зв'язки)** якщо $\varphi$ і $\psi$ — ППФ, то $(\varphi \wedge \psi)$,
>    $(\varphi \vee \psi)$, $(\varphi \to \psi)$, $(\varphi \leftrightarrow \psi)$ — ППФ;
> 4. **(замикання)** нічого іншого ППФ не є.

Отже, $((p \to q) \wedge (\neg r))$ — правильно побудована формула, а рядки $p\,q\to$,
$\;\wedge p$, $(p \to \to q)$ — ні. На практиці зовнішні дужки та дужки навколо заперечення
опускають, а решту відновлюють за пріоритетом зі §5.4; тож зазвичай пишуть просто
$(p \to q) \wedge \neg r$.

### Дерево формули та головна зв'язка

Кожній ППФ відповідає **дерево формули** (**синтаксичне дерево**, дерево розбору): листки —
атоми, внутрішні вузли — зв'язки, а піддерева кожної зв'язки — це дерева її безпосередніх
підформул. Зв'язку в **корені** — застосовану *останньою* — називають **головною зв'язкою**.
Визначити головну зв'язку — *ключовий* крок читання й обчислення формули, бо вона задає
найзовнішню структуру.

![Дерево формули (P → Q) → ¬S із головною зв'язкою (другою імплікацією) у корені](img/l05_parse_tree.png)

> **Приклад 5.4.** У формулі $(P \to Q) \to \neg S$ головна зв'язка — **друга**
> імплікація; її ліве піддерево — $P \to Q$, праве — $\neg S$. Дерево:
>
> ```
>            →            ← головна зв'язка
>          /   \
>         →     ¬
>        / \     \
>       P   Q     S
> ```
>
> Порівняйте: у $\neg(p \wedge q)$ головна зв'язка — $\neg$, застосоване до всієї
> кон'юнкції; а в $\neg p \wedge q$ головна зв'язка — $\wedge$ (бо $\neg$ зв'язує щільніше),
> з лівим піддеревом $\neg p$ і правим $q$.

### Інтерпретація та обчислення таблиці

> **Означення (інтерпретація).** **Інтерпретацією** (**оцінкою**, **набором значень**)
> називають функцію
> $$ v : \{\text{пропозиційні змінні}\} \to \{\text{І}, \text{Х}\}, $$
> що приписує значення істинності кожному атому.

Оскільки зв'язки істиннісно функційні, інтерпретація атомів *однозначно змушує* значення
кожної побудованої з них формули: обчислюємо значення знизу вгору деревом формули, від
листків до кореня, застосовуючи на кожному вузлі означальну таблицю зі §5.4. Формула з $n$
різними атомами має рівно $2^n$ інтерпретацій (кожен атом незалежно набуває двох значень) —
це і є рядки її **таблиці істинності**.

**Як будувати таблицю складеної формули.** Заводять по стовпчику на кожну **підформулу**,
упорядковуючи їх за деревом (спершу атоми, останньою — головна зв'язка); кожен стовпчик
обчислюють з попередніх за базовою таблицею.

> **Приклад 5.5 (дві змінні).** Побудуємо таблицю для $(p \to q) \wedge \neg q$ (головна
> зв'язка — $\wedge$):
>
> | $p$ | $q$ | $p \to q$ | $\neg q$ | $(p \to q) \wedge \neg q$ |
> |:--:|:--:|:--:|:--:|:--:|
> | Х | Х | І | І | **І** |
> | Х | І | І | Х | **Х** |
> | І | Х | Х | І | **Х** |
> | І | І | І | Х | **Х** |
>
> Виділений останній стовпчик — значення всієї формули за кожної з $2^2 = 4$
> інтерпретацій. Формула істинна лише при $p = q = \text{Х}$.

> **Приклад 5.6 (три змінні, вісім рядків).** Побудуємо таблицю формули
> $(P \to Q) \to \neg S$ — тієї, чиє дерево ми малювали в Прикладі 5.4. Проміжні стовпчики
> — $P \to Q$ і $\neg S$; головна зв'язка — зовнішня імплікація.
>
> | $P$ | $Q$ | $S$ | $P \to Q$ | $\neg S$ | $(P \to Q) \to \neg S$ |
> |:--:|:--:|:--:|:--:|:--:|:--:|
> | Х | Х | Х | І | І | **І** |
> | Х | Х | І | І | Х | **Х** |
> | Х | І | Х | І | І | **І** |
> | Х | І | І | І | Х | **Х** |
> | І | Х | Х | Х | І | **І** |
> | І | Х | І | Х | Х | **І** |
> | І | І | Х | І | І | **І** |
> | І | І | І | І | Х | **Х** |
>
> Формула хибна рівно в тих рядках, де $S=$І, а імплікація $P \to Q$ істинна. Мішаний
> стовпчик означає, що формула **нейтральна** (див. §5.8).

![Побудова таблиці істинності складеної формули (P → Q) → ¬S за проміжними стовпчиками](img/l05_compound_tt.png)

---

## 5.7 Формалізація висловлювань

**Формалізація** (**символізація**, **переклад**) — це заміна атомів змінними, а
сполучникових слів — символами. Це місток між живою мовою й обчислюваною логікою.

Метод складається з трьох кроків:

1. Виокремити **атомарні** висловлення й приписати кожному змінну. За змоги обирайте
   атоми *стверджувальними* (нехай $p$ = «двері відчинені», а не «двері зачинені»), щоб
   заперечення проступали явно.
2. Знайти **сполучникові слова** («і», «або», «якщо…, то», «не», «тільки якщо», …) та
   зіставити їм зв'язки за таблицею §5.5.
3. Визначити **групування** (область дії зв'язок) — саме цей крок вимагає розуміння змісту
   — і розставити дужки.

![Формалізація речення про Петра: виокремлення атомів P, Q, S та побудова формули (P → Q) → ¬S](img/l05_formalize.png)

> **Приклад 5.7 (речення про Петра — зі слайда).** Формалізуймо речення
> «*Оскільки Петро запізнювався, він перевищив швидкість і тому не є слушним водієм.*»
>
> Атоми:
> - $P$ — «Петро запізнювався»;
> - $Q$ — «Петро перевищив швидкість»;
> - $S$ — «Петро є слушним (розважливим) водієм».
>
> Речення стверджує: *якщо* (запізнення спричинило перевищення швидкості, тобто $P \to Q$),
> *то* Петро не є слушним водієм ($\neg S$). Формалізація:
> $$ (P \to Q) \to \neg S. $$
> Це саме та формула, дерево і таблицю якої ми вже розібрали у Прикладах 5.4 і 5.6.

Переклад не механічний: слова-підказки скеровують його, але область дії та групування
потребують читання наміру речення. Особливо підступне місце «не».

> **Приклад 5.8 (звороти «тільки якщо», «якщо і тільки якщо»).** Нехай $e$ = «відвідувач
> заходить», $t$ = «відвідувач має квиток».
> «Заходити можна, **тільки якщо** є квиток» $= e \to t$.
> «Заходити можна **тоді й лише тоді, коли** є квиток» $= e \leftrightarrow t$.
> Друге речення сильніше: воно додатково обіцяє вхід кожному з квитком.

> **Приклад 5.9 (складене міркування у формулу).** «Якщо програма компілюється й тести
> проходять, то ми розгортаємо реліз; ми не розгорнули; тести пройшли. Отже, програма не
> скомпілювалася.» Атоми $c$ = «компілюється», $t$ = «тести проходять», $d$ =
> «розгортаємо». Засновки: $(c \wedge t) \to d,\; \neg d,\; t$. Висновок: $\neg c$. Чи
> *правильне* це міркування — з'ясуємо в §5.9.

---

## 5.8 Типи формул: тавтологія, суперечність, нейтральна

Дивлячись лише на **останній стовпчик** таблиці істинності формули, кожну формулу
відносять рівно до одного з трьох класів (це поділ зі слайда «Типи формул»).

> **Означення.**
> - **Тотожно істинна** формула (**тавтологія**, **загальнозначуща**) — істинна за
>   **кожної** інтерпретації (останній стовпчик суцільно І). Позначають $\models \varphi$.
>   Приклад: $p \vee \neg p$ (**закон виключеного третього**).
> - **Тотожно хибна** формула (**суперечність**, **суперечлива**, **нездійсненна**) —
>   хибна за **кожної** інтерпретації (останній стовпчик суцільно Х). Приклад:
>   $p \wedge \neg p$.
> - **Нейтральна** формула (**незагальнозначуща**, **несуперечлива**, **виконувана, але не
>   тавтологія**) — істинна за одних інтерпретацій і хибна за інших. Приклад: $p \to q$, а
>   також $(P \to Q) \to \neg S$ із Прикладу 5.6.

![Класифікація формул за останнім стовпчиком таблиці: тавтологія (усі І), суперечність (усі Х), нейтральна (мішана)](img/l05_classify.png)

Ці класи **розбивають** множину всіх формул: кожна формула належить рівно до одного з них.
Пов'язані вони запереченням.

> **Твердження 5.10 (двоїстість тавтологія — суперечність).** Формула $\varphi$ — тавтологія
> тоді й лише тоді, коли $\neg\varphi$ — суперечність; і $\varphi$ — суперечність тоді й
> лише тоді, коли $\neg\varphi$ — тавтологія.
>
> *Доведення.* За означенням заперечення для кожної інтерпретації $v$ маємо: $\neg\varphi$
> істинне при $v$ $\iff$ $\varphi$ хибне при $v$. Тому: $\varphi$ — тавтологія $\iff$
> $\varphi$ істинне за всіх $v$ $\iff$ $\neg\varphi$ хибне за всіх $v$ $\iff$ $\neg\varphi$
> — суперечність. Друге твердження випливає із застосування першого до $\neg\varphi$ й
> закону подвійного заперечення $\neg\neg\varphi \equiv \varphi$. $\blacksquare$

> **Зауваження (виконуваність).** Формулу називають **виконуваною**, якщо *хоч одна*
> інтерпретація робить її істинною (останній стовпчик містить хоч одне І). Отже,
> виконувані — це тавтології та нейтральні формули разом; невиконувані — точно
> суперечності. Задача «чи виконувана дана формула?» називається задачею **SAT** і є
> однією з центральних у теорії складності: це перша задача, для якої доведено
> **NP-повноту** (теорема Кука — Левіна, 1971). Таблиця істинності завжди її розв'язує, але
> має $2^n$ рядків, тож для великих $n$ потрібні розумніші **SAT-розв'язувачі**.

Тавтології — це саме ті формули, що виражають **логічні закони**. Пересвідчимося на
прикладі, що потрібен нам далі.

> **Приклад 5.11 (закон контрапозиції — тавтологія).** Покажемо, що
> $(p \to q) \leftrightarrow (\neg q \to \neg p)$ — тавтологія.
>
> | $p$ | $q$ | $p \to q$ | $\neg q \to \neg p$ | $(p \to q) \leftrightarrow (\neg q \to \neg p)$ |
> |:--:|:--:|:--:|:--:|:--:|
> | Х | Х | І | І | **І** |
> | Х | І | І | І | **І** |
> | І | Х | Х | Х | **І** |
> | І | І | І | І | **І** |
>
> Останній стовпчик суцільно І, отже, формула — **тавтологія**. Заразом два внутрішні
> стовпчики збіглися: це означає, що $p \to q \equiv \neg q \to \neg p$ (рівносильність
> імплікації та її контрапозиції — той факт, який ми обіцяли у §5.3).

> **Зауваження (зв'язок із [Лекцією 3](ODM-L03.md)).** Рівносильність формул
> $\varphi \equiv \psi$ (однакові останні стовпчики) — це рівно те саме, що рівність
> булевих функцій із Лекції 3, з $\text{І}/\text{Х}$ замість $1/0$. Усі закони булевої
> алгебри (комутативність, дистрибутивність, де Морган, поглинання, $p \to q \equiv
> \neg p \vee q$) виконуються й тут; відображення $\text{І}\mapsto 1,\ \text{Х}\mapsto 0$ —
> ізоморфізм двоелементної булевої алгебри й алгебри висловлювань. Тому спрощувати логічні
> формули можна тими самими перетвореннями, що й булеві вирази.

---

## 5.9 Логічний наслідок

Тепер точно означимо, що означає «висновок *випливає* із засновків» — центральне поняття
правильного міркування (слайд «Логічний наслідок»).

> **Означення (логічний наслідок, семантичне слідування).** Формула $B$ є **логічним
> наслідком** формул $A_1, \dots, A_n$, що записують
> $$ A_1, \dots, A_n \models B, $$
> якщо **кожна** інтерпретація, яка робить істинними *всі* засновки $A_1, \dots, A_n$,
> робить істинним і $B$. Рівносильно: немає жодної інтерпретації (жодного
> **контрприкладу**), що справджує всі засновки, але спростовує $B$.

Зокрема, за одного засновка $A \models B$ означає «кожна модель $A$ є моделлю $B$».
Наступна теорема зводить будь-яке питання про наслідок до питання про **тавтологію** — і
саме тому єдиної процедури (таблиці істинності) досить, щоб перевіряти правильність
міркувань. Це і є ті «тотожно істинні формули $A \to B$ та $A_1 \wedge \dots \wedge A_n
\to B$», що фігурують на слайді.

> **Теорема 5.12 (про дедукцію).** Нехай $A_1, \dots, A_n$ і $B$ — формули. Тоді
> $$ A_1, \dots, A_n \models B \quad\Longleftrightarrow\quad \text{формула } (A_1 \wedge A_2 \wedge \dots \wedge A_n) \to B \text{ — тавтологія.} $$
>
> *Доведення.* Позначмо $\Phi = A_1 \wedge \dots \wedge A_n$. Для будь-якої інтерпретації
> $v$ маємо: $\Phi$ істинне при $v$ $\iff$ $v$ справджує всі засновки.
>
> ($\Rightarrow$) Нехай $A_1, \dots, A_n \models B$; візьмемо довільну $v$. Якщо $\Phi$
> хибне при $v$, то імплікація $\Phi \to B$ істинна (хибний засновок). Якщо ж $\Phi$
> істинне при $v$, то $v$ справджує всі засновки, тож за означенням наслідку $B$ істинне
> при $v$, і знову $\Phi \to B$ істинне. Отже, $\Phi \to B$ істинна за кожної $v$ — це
> тавтологія.
>
> ($\Leftarrow$) Нехай $\Phi \to B$ — тавтологія; нехай $v$ справджує всі засновки, тобто
> $\Phi$ істинне при $v$. Оскільки імплікація $\Phi \to B$ істинна, а її засновок
> істинний, то істинним мусить бути й висновок: $B$ істинне при $v$. Отже, кожна модель
> засновків є моделлю $B$, тобто $A_1, \dots, A_n \models B$. $\blacksquare$

**Перевірка правильності таблицею.** Щоб перевірити $A_1, \dots, A_n \models B$, будують
одну таблицю й **переглядають лише рядки, де істинні всі засновки**; міркування правильне
тоді й лише тоді, коли в кожному такому рядку істинний і висновок.

> **Приклад 5.13 (правило відділення — правильне).** «Якщо йде дощ, то земля мокра. Іде
> дощ. Отже, земля мокра.» Нехай $p$ = «іде дощ», $q$ = «земля мокра». Засновки
> $p \to q,\; p$; висновок $q$.
>
> | $p$ | $q$ | $p \to q$ | $p$ | $q$ |
> |:--:|:--:|:--:|:--:|:--:|
> | Х | Х | І | Х | Х |
> | Х | І | І | Х | І |
> | І | Х | Х | І | Х |
> | І | І | І | **І** | **І** |
>
> Обидва засновки істинні лише в останньому рядку, і там висновок $q$ теж істинний.
> Контрприкладу немає $\Rightarrow$ міркування **правильне**. Це — modus ponens (§5.10).

> **Приклад 5.14 (ствердження висновку — неправильне).** «Якщо йде дощ, то земля мокра.
> Земля мокра. Отже, іде дощ.» Засновки $p \to q,\; q$; висновок $p$. У рядку $p=$Х, $q=$І
> обидва засновки істинні ($p \to q =$І, $q =$І), а висновок $p =$Х. Це контрприклад, тож
> $\{p \to q,\ q\} \not\models p$ — міркування **неправильне**, попри поверхову схожість із
> Прикладом 5.13. (Це поширена хиба «ствердження консеквента».)

> **Приклад 5.15 (повернення до релізу з Прикладу 5.9).** Засновки $(c \wedge t) \to d,\;
> \neg d,\; t$; висновок $\neg c$. Припустимо, всі засновки істинні: $\neg d$ дає $d=$Х;
> $t$ дає $t=$І. Якби $c$ було І, то $c \wedge t =$І, і перший засновок змусив би $d=$І —
> суперечність із $d=$Х. Отже, $c=$Х, тобто $\neg c=$І. Кожна модель засновків справджує
> висновок — міркування **правильне**. За Теоремою 5.12 це те саме, що тавтологічність
> формули $\big((c \wedge t) \to d\big) \wedge \neg d \wedge t \to \neg c$.

---

## 5.10 Дедуктивний висновок і правила виводу

Досі ми *обчислювали* істинність (це **семантика**: таблиці, $\models$). Тепер перейдемо
до *виведення* — до **синтаксису** доведення, де формули не «істинні» чи «хибні», а
механічно **перетворюються за правилами**, наче ходи у грі. Це і є **дедуктивний
висновок** зі слайдів.

> **Означення (дедуктивний висновок, формальне виведення).** **Виведенням** формули $B$ із
> засновків $\Gamma = \{A_1, \dots, A_n\}$ (записують $\Gamma \vdash B$) називають
> скінченний занумерований список формул, що закінчується на $B$, у якому кожен рядок — це
> або засновок, або результат застосування **правила виводу** до попередніх рядків. Кожен
> рядок супроводжують **обґрунтуванням**: назвою правила й номерами використаних рядків.

Знак $\vdash$ («виводиться», *синтаксичне* поняття) — двійник знака $\models$
(«випливає», *семантичне* поняття). Найважливіша ідея лекції:

> **Кожне правило виводу — це тавтологія в іншому вбранні.** Правило «з $A_1, \dots, A_n$
> вивести $B$» **коректне** (сумлінне) рівно тоді, коли імплікація
> $A_1 \wedge \dots \wedge A_n \to B$ — тавтологія (Теорема 5.12).

Через цю відповідність достатньо *один раз* пересвідчитися (таблицею чи алгеброю), що
певна імплікація — тавтологія, і далі можна *завжди* вживати відповідне правило як дозвіл
дописати $B$ під засновками потрібного вигляду, хай там що конкретно означають літери.
Істина *передається* від засновків до висновку.

Наведена таблиця містить стандартні пропозиційні правила зі слайда «Правила дедуктивних
висновків». Середній стовпчик дає назви введення/видалення (українська традиція),
останній — тавтологію-гаранта; будь-яку з них можна перевірити таблицею істинності.

![Таблиця правил виводу: назва, схема «засновки ⊢ висновок» та тавтологія-гарант](img/l05_inference.png)

| Правило | Засновки | Висновок | Тавтологія-гарант |
|---|---|---|---|
| **Введення диз'юнкції** (приєднання) | $A$ | $A \vee B$ | $A \to (A \vee B)$ |
| **Введення кон'юнкції** (об'єднання) | $A,\; B$ | $A \wedge B$ | $(A \wedge B) \to (A \wedge B)$ |
| **Видалення диз'юнкції** (диз'юнктивний силогізм) | $A \vee B,\; \neg A$ | $B$ | $\big((A \vee B) \wedge \neg A\big) \to B$ |
| **Видалення кон'юнкції** (спрощення) | $A \wedge B$ | $A$ | $(A \wedge B) \to A$ |
| **Контрапозиція імплікації** | $A \to B$ | $\neg B \to \neg A$ | $(A \to B) \leftrightarrow (\neg B \to \neg A)$ |
| **Правило відділення** (modus ponens) | $A,\; A \to B$ | $B$ | $\big(A \wedge (A \to B)\big) \to B$ |
| **Від'ємна форма відділення** (modus tollens) | $A \to B,\; \neg B$ | $\neg A$ | $\big((A \to B) \wedge \neg B\big) \to \neg A$ |
| **Гіпотетичний силогізм** | $A \to B,\; B \to C$ | $A \to C$ | $\big((A \to B) \wedge (B \to C)\big) \to (A \to C)$ |

Кілька зауваг про найважливіші правила.

- **Правило відділення** ($A,\ A \to B \therefore B$) — робоча конячка всіх доведень; його
  звуть «відділенням», бо воно «відділяє» $B$ від імплікації. Майже кожне пряме доведення
  — це ланцюжок відділень.
- **Від'ємна форма відділення** (modus tollens) поширює хибність *назад*: якщо висновок
  хибний, то й засновок мусить бути хибним. Це двигун доведення контрапозицією.
- **Видалення диз'юнкції** (диз'юнктивний силогізм) — усунення варіантів: «це $A$ або $B$;
  це не $A$; отже, $B$».
- **Введення кон'юнкції** має «тривіальну» тавтологію-гарант $(A \wedge B) \to (A \wedge B)$
  — вона істинна вже тому, що будь-яка імплікація виду $X \to X$ є тавтологією; правило
  просто дозволяє з двох окремо доведених формул скласти їхню кон'юнкцію.

Доведімо коректність двох центральних правил безпосередньо — таблицею істинності.

> **Твердження 5.16 (коректність правила відділення).** Формула
> $\big(A \wedge (A \to B)\big) \to B$ — тавтологія.
>
> *Доведення.*
>
> | $A$ | $B$ | $A \to B$ | $A \wedge (A \to B)$ | $\big(A \wedge (A \to B)\big) \to B$ |
> |:--:|:--:|:--:|:--:|:--:|
> | Х | Х | І | Х | **І** |
> | Х | І | І | Х | **І** |
> | І | Х | Х | Х | **І** |
> | І | І | І | І | **І** |
>
> Останній стовпчик суцільно І. Зауважте: єдиний рядок, де засновок
> $A \wedge (A \to B)$ істинний, — останній, і там $B$ теж істинне, як і провіщає
> Теорема 5.12. $\blacksquare$

> **Твердження 5.17 (коректність від'ємної форми, modus tollens).** Формула
> $\big((A \to B) \wedge \neg B\big) \to \neg A$ — тавтологія.
>
> *Доведення.*
>
> | $A$ | $B$ | $A \to B$ | $\neg B$ | $(A \to B) \wedge \neg B$ | $\neg A$ | ціле $\to$ |
> |:--:|:--:|:--:|:--:|:--:|:--:|:--:|
> | Х | Х | І | І | І | І | **І** |
> | Х | І | І | Х | Х | І | **І** |
> | І | Х | Х | І | Х | Х | **І** |
> | І | І | І | Х | Х | Х | **І** |
>
> Останній стовпчик суцільно І, тож правило коректне. Єдиний рядок з істинним засновком —
> перший, і там $\neg A$ істинне. $\blacksquare$

Зібравши правила разом, будують **виведення**. Кожен рядок обґрунтовано якимось правилом
із таблиці, тож остання формула вважається доведеною із засновків.

> **Приклад 5.18 (повне виведення).** Покажемо, що
> $\{\,p \to q,\ \ q \to r,\ \ \neg r,\ \ p \vee s\,\} \vdash s$.
>
> | № | Формула | Обґрунтування |
> |---|---|---|
> | 1 | $p \to q$ | засновок |
> | 2 | $q \to r$ | засновок |
> | 3 | $\neg r$ | засновок |
> | 4 | $p \vee s$ | засновок |
> | 5 | $p \to r$ | гіпотетичний силогізм, 1, 2 |
> | 6 | $\neg p$ | від'ємна форма відділення (modus tollens), 5, 3 |
> | 7 | $s$ | видалення диз'юнкції, 4, 6 |
>
> Кожен крок дозволено правилом, тож рядок 7 установлено: $s$ випливає з чотирьох
> засновків. $\blacksquare$

> **Типова помилка (порядок і точність збігу).** Рядок можна обґрунтовувати лише рядками
> *вище* нього. І правило мусить збігатися зі схемою *точно*: щоб застосувати відділення,
> на попередніх рядках потрібні і $A$, і ціла імплікація $A \to B$; мати $A$ та $B \to A$
> — не підстава ні для чого.

---

## 5.11 Правило підстановки

Крім правил, що комбінують *цілі* формули, потрібне правило, яке дозволяє **конкретизувати**
доведену схему — підставити замість атома довільну формулу (слайд «Правило підстановки»).

> **Означення (правило підстановки).** Нехай $F_1$ — формула логіки висловлювань, а $A$ —
> **атомарна** формула (пропозиційна змінна), що входить у $F_1$; запишімо $F_1$ як
> $F_1(A)$, щоб підкреслити входження $A$. Нехай $F_2$ — довільна формула. Тоді $F_1(F_2)$
> — формула, отримана заміною **всіх** входжень $A$ у $F_1$ на $F_2$. **Правило:** якщо
> $F_1(A)$ — тавтологія (теорема числення), то й $F_1(F_2)$ — тавтологія (теорема).

Ключове слово — «**всіх**»: підстановка має бути **однорідною**.

> **Приклад 5.19.** З тавтології $A \vee \neg A$ (закон виключеного третього), підставивши
> $A := (p \wedge q)$, дістаємо тавтологію $(p \wedge q) \vee \neg(p \wedge q)$.

> **Типова помилка (неоднорідна підстановка).** Заміна лише *деяких* входжень руйнує
> тавтологічність. З тавтології $A \to A$, замінивши тільки *перше* $A$ на $p \wedge q$,
> дістанемо $(p \wedge q) \to A$ — а це вже **не** тавтологія (хибна при $p=q=$І, $A=$Х).

> **Зауваження (підстановка проти заміни рівносильним).** Розрізняйте два різні правила.
> **Правило підстановки** (тут) замінює *атом* $A$ на *довільну* формулу $F_2$ і зберігає
> тавтологічність. **Правило заміни** (яким ми користувалися, спрощуючи булеві вирази в
> [Лекції 3](ODM-L03.md)) замінює *підформулу* на *рівносильну* їй і зберігає рівносильність
> усієї формули. Перше конкретизує загальний закон; друге переписує формулу, не змінюючи її
> істиннісного стовпчика.

---

## 5.12 Числення висловлювань

Зібравши мову (§5.3, §5.6), поняття тавтології (§5.8) та правила виводу (§5.10–5.11), ми
можемо описати логіку висловлювань як **формальне числення** (слайди «Обчислення
висловлювань»). Це суто *синтаксичний* погляд: теореми породжують маніпуляцією символами,
не звертаючись до значень істинності.

> **Означення (числення висловлювань).** **Численням висловлювань** називають трійку:
> - **Мова** — множина всіх правильно побудованих формул логіки висловлювань (§5.6).
> - **Аксіоми** — обрана множина загальнозначущих (тотожно істинних) формул, узятих за
>   відправні точки.
> - **Правила виводу** — закони, за якими з наявних формул дістають нові.
>
> **Теоремою** числення називають будь-яку формулу, отриману з аксіом скінченним числом
> застосувань правил виводу.

Один із класичних варіантів — **числення гільбертівського типу** над зв'язками
$\{\neg, \to\}$ (решту зв'язок уводять як скорочення: $p \vee q := \neg p \to q$,
$p \wedge q := \neg(p \to \neg q)$ тощо). Його три схеми аксіом:

$$
\textbf{A1:}\quad A \to (B \to A),
$$

$$
\textbf{A2:}\quad \big(A \to (B \to C)\big) \to \big((A \to B) \to (A \to C)\big),
$$

$$
\textbf{A3:}\quad (\neg B \to \neg A) \to (A \to B),
$$

а правил виводу лише два — **правило відділення** (modus ponens) та **правило
підстановки** (§5.10–5.11). Саме така мінімальна конфігурація стоїть на слайді-прикладі:
мова над $\{\text{І}, \text{Х}\}$, аксіоми — загальнозначущі формули, правила висновку —
відділення й підстановка.

> **Приклад 5.20 (виведення тотожності $A \to A$).** Формула $A \to A$ очевидно
> загальнозначуща, але покажемо, що вона — *теорема* числення, тобто виводиться з аксіом
> самими правилами.
>
> | № | Формула | Обґрунтування |
> |---|---|---|
> | 1 | $\big(A \to ((A \to A) \to A)\big) \to \big((A \to (A \to A)) \to (A \to A)\big)$ | A2, підстановка $B := A \to A,\ C := A$ |
> | 2 | $A \to \big((A \to A) \to A\big)$ | A1, підстановка $B := A \to A$ |
> | 3 | $\big(A \to (A \to A)\big) \to (A \to A)$ | відділення, 1, 2 |
> | 4 | $A \to (A \to A)$ | A1, підстановка $B := A$ |
> | 5 | $A \to A$ | відділення, 3, 4 |
>
> Отже, $\vdash A \to A$. $\blacksquare$

Чому це числення «правильне»? Дві глибокі метатеореми пов'язують синтаксис ($\vdash$) із
семантикою ($\models$):

- **Коректність (несуперечність):** якщо $\vdash \varphi$, то $\models \varphi$ — з аксіом
  правилами не вивести нічого, крім тавтологій (числення *не бреше*).
- **Повнота (теорема Поста, 1921, для логіки висловлювань):** якщо $\models \varphi$, то
  $\vdash \varphi$ — кожну тавтологію *можна* вивести (правил *досить*).

Разом вони означають, що для логіки висловлювань $\vdash$ і $\models$ **збігаються**:
вивідність і загальнозначущість — те саме відношення, до якого підходять із двох боків
(семантичного й синтаксичного). Саме тому правила виводу зі §5.10 водночас *надійні* й
*достатні* для всіх семантичних фактів цієї лекції. (Доведення обох метатеорем виходить за
межі курсу.)

> **Історична довідка.** Алгебраїчне трактування логіки започаткував **Джордж Буль**
> (*«Математичний аналіз логіки»*, 1847), звівши міркування до обчислень над $0$ і $1$ —
> звідси й «булева алгебра» [Лекції 3](ODM-L03.md). **Оґастес де Морґан**, його сучасник,
> дав закони двоїстості. Строгу формальну мову з поняттям правильно побудованої формули
> запровадив **Ґотлоб Фреґе** (*Begriffsschrift*, 1879). **Таблицю істинності** як
> систематичний засіб незалежно ввели **Людвіг Вітґенштайн** (*Tractatus*, 1921) і **Еміль
> Пост** (1921); Пост також довів повноту числення висловлювань. Аксіоматичні числення
> гільбертівського типу постали в програмі **Давида Гільберта** (1920-ті), яку 1931 року
> обмежили теореми **Курта Ґеделя** про неповноту — але для *логіки висловлювань* повнота
> зберігається цілком.

---

## Застосування у видавництві та поліграфії

Логіка висловлювань — це мова умов, перевірок і автоматики, тож вона прямо описує задачі
фаху:

- **Передпольотні перевірки (preflight).** Придатність файлу до друку — це велика
  кон'юнкція умов: «роздільність достатня $\wedge$ кольори у CMYK $\wedge$ є припуски під
  обріз $\wedge$ шрифти вбудовано». Файл проходить перевірку тоді й лише тоді, коли істинна
  вся формула; за законом де Моргана її заперечення (список помилок) — це диз'юнкція
  окремих порушень.
- **Умовна логіка у препресі та шаблонах.** Правила накладання фарб, керування
  оверпринтом, змінні дані у персоналізованому друку задають імплікаціями «якщо поле
  порожнє, то приховати блок» ($p \to \neg q$); формалізація (§5.7) прибирає двозначність
  природномовного технічного завдання.
- **Логічні вентилі RIP та растрування.** Растровий процесор і кольороподіл — це, по суті,
  булеві функції над пікселями (маска шару, треппінг), тобто ті самі $\wedge, \vee, \neg$
  з [Лекції 3](ODM-L03.md), прочитані як висловлення «піксель належить формі».
- **Автоматичне міркування про коректність.** Перевірка, що дві версії макета
  еквівалентні (дають той самий друкований результат), — це питання рівносильності формул;
  а перевірка сумісності набору вимог замовника — це задача виконуваності (SAT) зі §5.8.
- **Валідні висновки в редакційних правилах.** Ланцюжки правил стилю («якщо це цитата, то
  курсив; це не курсив; отже, це не цитата») — це modus tollens; уміння відрізнити його від
  хибного «ствердження висновку» (Приклад 5.14) убезпечує від псевдологічних приписів.

---

## Підсумок

- **Висловлення** — розповідне речення з визначеним значенням істинності зі
  $\{\text{І}, \text{Х}\}$. Запитання, накази, оклики, парадокси та **відкриті речення**
  («$X$ ділиться на $5$») висловленнями не є.
- **Атоми** — неподільні прості речення (пропозиційні змінні); **складені** висловлення
  будують зв'язками $\neg, \wedge, \vee, \to, \leftrightarrow$ і вони **істиннісно
  функційні**: значення залежить лише від значень атомів і зв'язок.
- Кожну операцію означує **таблиця істинності**. Ключові факти: $\vee$ **включне**;
  $A \to B$ хибне **лише** при $A=$І, $B=$Х (пусто-істинне при $A=$Х); $A \to B$ рівносильне
  своїй **контрапозиції**, але не оберненій чи протилежній.
- Звороти живої мови зіставляють зі зв'язками (**аналоги природної мови**); «тільки якщо»
  $= \to$, «тоді й лише тоді» $= \leftrightarrow$, «ні…, ні…» $= \neg(\cdot \vee \cdot)$.
- **ППФ** означують рекурсивно; пріоритет $\neg \succ \wedge \succ \vee \succ \to \succ
  \leftrightarrow$ і дужки задають єдине **дерево формули** з **головною зв'язкою**.
  **Інтерпретація** атомів однозначно змушує значення формули; таблиця має $2^n$ рядків.
- **Формалізація** — переклад речення у формулу (приклад про Петра: $(P \to Q) \to \neg S$).
- Кожна формула — **тавтологія** (тотожно істинна), **суперечність** (тотожно хибна) або
  **нейтральна** (виконувана, але не тавтологія).
- **Логічний наслідок** $A_1, \dots, A_n \models B$: кожна модель засновків є моделлю
  висновку; за **теоремою про дедукцію** це рівносильне тавтологічності
  $A_1 \wedge \dots \wedge A_n \to B$.
- **Правила виводу** — тавтології у вбранні схем: введення/видалення $\wedge$ і $\vee$,
  контрапозиція, **правило відділення** (modus ponens), **від'ємна форма** (modus tollens),
  **гіпотетичний силогізм**. **Правило підстановки** замінює атом довільною формулою
  (однорідно!) зі збереженням тавтологічності.
- **Числення висловлювань** = мова + аксіоми + правила виводу; для логіки висловлювань
  синтаксична вивідність $\vdash$ і семантичне слідування $\models$ **збігаються**
  (коректність і повнота).

## Вправи

### Для розігріву

1. Визначте, які з речень є висловленнями, а для висловлень укажіть значення істинності,
   якщо воно відоме: (а) «$13$ — просте число»; (б) «Розв'яжіть рівняння $x^2 = 4$»; (в)
   «$x^2 = 4$»; (г) «Кожне парне число, більше за $2$, є сумою двох простих»; (ґ) «Яка
   гарна обкладинка!».
2. Побудуйте таблицю істинності формули $p \to (q \vee \neg p)$ і класифікуйте її
   (тавтологія / суперечність / нейтральна).
3. Заперечте, оберніть, візьміть протилежну та контрапозицію до речення «Якщо число
   ділиться на $6$, то воно ділиться на $3$». Яка з чотирьох формул гарантовано має те саме
   значення істинності, що й початкова?

### Стандартні

4. Розставте всі дужки за пріоритетом і вкажіть головну зв'язку: (а) $\neg p \vee q \to r$;
   (б) $p \wedge \neg q \leftrightarrow r \vee s$; (в) $\neg(p \to q) \wedge r$.
5. Формалізуйте, увівши позначення атомів: (а) «Я піду на пробіжку, якщо не піде сніг»;
   (б) «Увійти можна тільки якщо є перепустка»; (в) «Не працює ні принтер, ні сканер».
6. Побудуйте таблицю істинності формули $(p \leftrightarrow q) \to (p \wedge q)$ і
   класифікуйте її. За яких інтерпретацій вона хибна?
7. Доведіть таблицею істинності коректність **гіпотетичного силогізму**, тобто що
   $\big((A \to B) \wedge (B \to C)\big) \to (A \to C)$ — тавтологія.
8. Перевірте, чи правильне міркування: «Якщо кеш прогрітий, то запит швидкий. Запит не
   швидкий. Отже, кеш не прогрітий». Яке це правило виводу?

### Підвищеної складності

9. Наведіть повне виведення $s$ із засновків $\{\,p \wedge q,\ \ p \to r,\ \ q \to t,\ \
   (r \wedge t) \to s\,\}$, обґрунтовуючи кожен рядок правилом виводу.
10. Спираючись лише на закони рівносильності (без таблиці, цитуючи кожен крок), спростіть:
    (а) $\neg(p \vee \neg q)$; (б) $(p \to q) \wedge (p \to \neg q)$. Який зв'язок результат
    (б) має з булевими перетвореннями з [Лекції 3](ODM-L03.md)?
11. Використавши правило підстановки, виведіть із тавтології $A \vee \neg A$ формулу
    $(p \to q) \vee \neg(p \to q)$. Поясніть, чому заміна лише одного входження $A$ дала б
    хибний результат.
12. У численні гільбертівського типу (аксіоми A1–A3, правила відділення й підстановки)
    побудуйте виведення формули $A \to A$, докладно вказавши кожну підстановку. (Це
    Приклад 5.20; відтворіть його самостійно, не підглядаючи.)
13. Формула має $n$ різних атомів. (а) Скільки рядків має її таблиця істинності? (б)
    Поясніть, чому перевірка виконуваності (SAT) таблицею непрактична вже при $n = 60$,
    навівши приблизну кількість рядків. (в) Одним реченням скажіть, що робить інакше
    SAT-розв'язувач.