Логіка висловлювань

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

Для чого потрібна логіка

Логіка — наука, що вивчає міркування, істинність, доказовість і спростовуваність. При цьому в логіці йдеться лише про форму повідомлення: нас не цікавить, що саме повідомляється, так само як не цікавлять різні психологічні тлумачення й подібні речі.

Якщо, наприклад, ми маємо речення «число 2 парне і водночас непарне», то можемо зробити висновок, що все речення хибне, адже число 2 не є непарним. Саме такими речами загалом і займається логіка.

Висловлювання

Основою логіки висловлювань, звісно, є висловлювання. Висловлюванням називають кожне розповідне речення, про яке можна визначити його значення істинності. Приклади простих висловлювань:

• Київ — столиця України.
• Натуральне число п'ять — непарне.
• HTML — мова програмування.
• Два плюс три дорівнює шести.

Усе це висловлювання. І неважливо, чи вони істинні (перші два), чи хибні (останні два). Висловлюванням не є, наприклад, питальне речення або речення, у якого не можна однозначно визначити значення істинності. Знову приклад:

• Чи буде завтра у Києві дощ?
• Зелений колір — найгарніший.

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

Класична математична логіка не дуже добре справляється з нечіткими реченнями на кшталт «Богдан високий» або «Борщ смачний». Такі висловлювання краще розглядати, наприклад, у нечіткій логіці (fuzzy logic), яка пристосована до нечіткості.

Атомарне висловлювання

У першому розділі ми розглянули висловлювання «число 2 парне і водночас непарне». Таке висловлювання можна назвати складеним, бо насправді воно поєднує два коротші висловлювання: «число 2 парне» і «число 2 непарне». Ці два висловлювання поєднані логічною зв'язкою «і», або «і водночас».

Атомарне висловлювання — це висловлювання, яке вже не можна розділити далі; у певному сенсі це найпростіше твердження. Попередні приклади висловлювань насправді були атомарними висловлюваннями:

• Київ — столиця України.
• Натуральне число п'ять — непарне.
• HTML — мова програмування.
• Два плюс три дорівнює шести.

Атомарні висловлювання далі позначатимемо малими літерами латинської абетки, як звичайно p, q, r, …, і називатимемо їх пропозиційними змінними.

Логічні зв'язки

Математична логіка зазвичай оперує певним набором логічних зв'язок. До основних належать чотири бінарні зв'язки:

• p ∧ q — кон'юнкція висловлювань, читаємо «висловлювання p і (водночас) висловлювання q»
• p ∨ q — диз'юнкція висловлювань, читаємо «висловлювання p або висловлювання q»
• $p \Rightarrow q$ — імплікація, читаємо «якщо висловлювання p, то висловлювання q»
• p ⇔ q — еквіваленція, читаємо «висловлювання p тоді й лише тоді, коли висловлювання q»

Конкретні приклади логічних зв'язок:

• У центрі Львова йде дощ і водночас світить сонце. (кон'юнкція)
• У центрі Львова йде дощ або світить сонце. (диз'юнкція)
• Піца — найсмачніша страва і футбол — найцікавіший спорт. (кон'юнкція)
• Якщо ти вип'єш склянку води, то більше не будеш спраглим. (імплікація)
• Якщо число x ділиться на чотири, то воно ділиться і на два. (імплікація)
• Оксана гарна і водночас розумна. (кон'юнкція)
• Співачки успішні тоді й лише тоді, коли вони гарні. (еквіваленція)
• Якщо не буде дощу, ми не змокнемо. (імплікація)
• Якщо корова вміє літати, то я — імператор Місяця. (імплікація)

Ми знаємо ще одну поширену логічну зв'язку: заперечення. Заперечення позначають або штрихом $p^\prime$, або символом $\neg p$.

Формула

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

Формально формулу означимо так:

• Кожна пропозиційна змінна (атомарне висловлювання) є формулою (точніше, це атомарна формула).
• Якщо A і B — формули, то й $\neg A$, (A ∧ B), (A ∨ B), $(A \Rightarrow B)$, (A ⇔ B) — формули.

Означення має сенс: у першому пункті ми кажемо, що кожне атомарне висловлювання водночас є формулою. Отже, якщо маємо два атомарні висловлювання, наприклад «У центрі Львова йде дощ» і «світить сонце», то маємо водночас і дві формули. Тепер можемо застосувати другий пункт і скласти складнішу формулу, наприклад так:

• У центрі Львова йде дощ і водночас світить сонце.
• У центрі Львова йде дощ або світить сонце.
• Якщо в центрі Львова світить сонце, то йде дощ.
• Сонце в центрі Львова світить тоді й лише тоді, коли йде дощ.

Формули, звісно, не обов'язково мають бути істинними. Тепер ми отримали ще один набір формул, тож можемо скласти ще складніші. Позначимо A = «У центрі Львова світить сонце або йде дощ.» (ми вже знаємо, що це формула) і B = «видно веселку» (припустімо, що знову в центрі Львова, щоб не повторювати це щоразу), тоді можемо утворити нові формули. Дужки в реченнях лише показують, до яких частин належить зв'язка.

• A ∧ B: (У центрі Львова світить сонце або йде дощ) і водночас (видно веселку).
• A ∨ B: (У центрі Львова світить сонце або йде дощ) або (видно веселку).
• $A \Rightarrow B$: (Якщо в центрі Львова світить сонце або йде дощ), то (видно веселку).
• A ⇔ B: (У центрі Львова світить сонце або йде дощ) тоді й лише тоді, коли (видно веселку).

Усе це формули. Тож знову можна взяти одну з цих формул і приєднати до неї ще якусь формулу. Так можна створити, наприклад, химерне речення: «Якщо в центрі Львова світить сонце або йде дощ, або видно веселку, то сонце світить або йде дощ тоді й лише тоді, коли видно веселку».

У наступній частині розглянемо істинність формул.