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

Огляд #

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

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

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

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

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

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

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

Мотивація #

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

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

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

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

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

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

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

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

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

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

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

Приклад 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$;
• допоміжних символів — лівої та правої дужок $($ і $)$.

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

Зауваження (інші позначення). Символіка логіки не усталена повністю. На слайдах курсу заперечення записують як !p або $\sim p$, еквіваленцію — як $\sim$ чи $\Leftrightarrow$, імплікацію — як $\Rightarrow$. У Лекції 3 заперечення позначали рискою $\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 Операції та їхні таблиці істинності #

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

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

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

Заперечення $\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).

Еквіваленція $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 Аналоги природної мови #

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

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

• «$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 рекурсивно задавали множини.

Означення (правильно побудована формула). Правильно побудовані формули (ППФ, англ. 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$.

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

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

Приклад 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).

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

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

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

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

Приклад 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.

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

Твердження 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). Рівносильність формул $\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$ під засновками потрібного вигляду, хай там що конкретно означають літери. Істина передається від засновків до висновку.

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

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

• Правило відділення ($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) замінює підформулу на рівносильну їй і зберігає рівносильність усієї формули. Перше конкретизує загальний закон; друге переписує формулу, не змінюючи її істиннісного стовпчика.

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. Оґастес де Морґан, його сучасник, дав закони двоїстості. Строгу формальну мову з поняттям правильно побудованої формули запровадив Ґотлоб Фреґе (Begriffsschrift, 1879). Таблицю істинності як систематичний засіб незалежно ввели Людвіг Вітґенштайн (Tractatus, 1921) і Еміль Пост (1921); Пост також довів повноту числення висловлювань. Аксіоматичні числення гільбертівського типу постали в програмі Давида Гільберта (1920-ті), яку 1931 року обмежили теореми Курта Ґеделя про неповноту — але для логіки висловлювань повнота зберігається цілком.

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

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

• Передпольотні перевірки (preflight). Придатність файлу до друку — це велика кон’юнкція умов: «роздільність достатня $\wedge$ кольори у CMYK $\wedge$ є припуски під обріз $\wedge$ шрифти вбудовано». Файл проходить перевірку тоді й лише тоді, коли істинна вся формула; за законом де Моргана її заперечення (список помилок) — це диз’юнкція окремих порушень.
• Умовна логіка у препресі та шаблонах. Правила накладання фарб, керування оверпринтом, змінні дані у персоналізованому друку задають імплікаціями «якщо поле порожнє, то приховати блок» ($p \to \neg q$); формалізація (§5.7) прибирає двозначність природномовного технічного завдання.
• Логічні вентилі RIP та растрування. Растровий процесор і кольороподіл — це, по суті, булеві функції над пікселями (маска шару, треппінг), тобто ті самі $\wedge, \vee, \neg$ з Лекції 3, прочитані як висловлення «піксель належить формі».
• Автоматичне міркування про коректність. Перевірка, що дві версії макета еквівалентні (дають той самий друкований результат), — це питання рівносильності формул; а перевірка сумісності набору вимог замовника — це задача виконуваності (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?
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-розв’язувач.

Lectures/ODM-L05.md · 77.2 KB · updated 2026-08-04 14:32