Істинність формул

Якщо в нас є деякі атомарні висловлювання, з яких складено формулу, можна спробувати визначити, істинна ця формула чи хибна.

Істинність висловлювання

Спочатку уточнімо, що таке значення істинності висловлювання. Якщо маємо висловлювання p, ми маємо бути здатними вирішити, істинне воно чи хибне. Істинне висловлювання має значення істинності 1, а хибне — 0.

Інтерпретація (приписування значень істинності) — це правило e, яке кожному висловлюванню ставить у відповідність 0 або 1. Якщо пишемо e(p), то хочемо дізнатися істинність висловлювання p. Якщо p — це висловлювання «двічі по два — чотири», то e(p) = 1, бо це істинне висловлювання. Якщо q — це висловлювання «Остап — жінка», то e(q) = 0, бо Остап не жінка. Отже, e — функція, яка повертає, чи є висловлювання істинним.

Тут треба усвідомити, що e — не якась магічна функція, яка знає все на світі. Вона поводиться так, як ми їй скажемо. Вона не знає, чи Остап чоловік, чи жінка. На початку обчислення ми маємо оголосити, як ця функція має поводитися. Якщо ми їй скажемо, що Остап — жінка, вона поверне e(q) = 1.

Істинність логічних зв'язок

Щоб визначити істинність формули, потрібно знати, як обчислювати істинність логічних зв'язок. Тобто якщо відомі значення e(p) і e(q), яким буде значення істинності формул p ∧ q, $p \Rightarrow q$ тощо.

Кожна логічна зв'язка поводиться по-різному й використовується для різного, тому розглянемо кожну окремо.

Істинність кон'юнкції

Кон'юнкцію позначають p ∧ q і читають «p і водночас q». Для прикладу візьмімо формулу «Україна лежить у Східній Європі і водночас її столиця — Київ». Коли все це речення буде істинним?

Визначити істинність допомагає вже сама зв'язка «і водночас». Вона прямо вимагає, щоб обидва висловлювання, ліворуч і праворуч, були істинними. Отже, якщо обидва висловлювання p і q істинні, тобто e(p) = 1 і e(q) = 1, то істинна й уся кон'юнкція. В іншому випадку, коли хибне або одне з висловлювань, або обидва, уся формула хибна.

Прикладом кон'юнкції, яка не є істинною, може бути: «Дніпро — річка і водночас Дніпро тече через Польщу». Правда, що Дніпро — річка, але неправда, що він тече в Польщі, тож уся кон'юнкція не є істинною.

Наочно це записує така таблиця:

$$\begin{array}{ccc} p&q&p \wedge q\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&0 \end{array}$$

У перших двох стовпцях стоять значення істинності висловлювань p і q, а в третьому — значення істинності формули p ∧ q.

Істинність диз'юнкції

Диз'юнкцію позначають p ∨ q і читають «p або q». Приклад: «Туреччина лежить у Європі або в Азії». Коли все речення буде істинним?

У диз'юнкції нам досить, щоб істинною була принаймні одна з можливостей. Зв'язка «або» дає нам вибір: досить, щоб була істинною її ліва або права частина. Єдина невелика відмінність від звичайного мовлення в тому, що логічне «або» істинне й тоді, коли виконуються обидва висловлювання водночас. Це не зовсім звично: у побутовому мовленні ми часто вживаємо «або» як виключне, тобто «або …, або …».

Щодо цього існує класичний жарт: родина вибирає нове авто в автосалоні. Тато каже продавцеві: «Ми вирішили, що візьмемо синє або червоне авто». Продавець продав їм обидва авто. Це ілюстрація різниці між логічним і розмовним «або»: тато, імовірно, мав на увазі, що вони оберуть з цих авто рівно одне, а продавець вважав допустимим варіантом продати їм обидва.

Попереднє речення про Туреччину істинне, бо істинні обидва висловлювання. Речення «число 7 ділиться на 3 або число 7 є простим» істинне, бо сімка — просте число. Хоч на три вона не ділиться, але це нам уже не заважає. Таблиця значень істинності:

$$\begin{array}{ccc} p&q&p \vee q\\ 1&1&1\\ 1&0&1\\ 0&1&1\\ 0&0&0 \end{array}$$

Істинність імплікації

Імплікацію позначають $p \Rightarrow q$ і читають «якщо p, то q». Прикладом імплікації може бути речення «якщо ми довго гратимемо надворі в мороз, то змерзнемо». Коли це речення буде істинним?

Логічна імплікація — найпідступніша з усіх зв'язок, і навіть у побутовому мовленні її часто не розуміють та плутають з еквіваленцією. Спробуймо відповісти на питання, чи виконується водночас і обернена імплікація: $q \Rightarrow p$.

Ми знаємо, що коли ми довго граємо надворі в мороз, то змерзнемо. Чи виконується водночас, що коли ми змерзли, то довго гралися надворі в мороз? Звісно, ні: ми могли змерзнути на зупинці, чекаючи автобус, або взагалі від чогось іншого. Обернена імплікація, отже, автоматично виконуватися не мусить. Якщо виконуються і $p \Rightarrow q$, і $q \Rightarrow p$, то це еквіваленція, див. далі.

Інший приклад: «якщо завтра буде дощ, то Іван візьме з собою парасольку». А тепер скажу тобі, що Іван парасольку з собою взяв. Питання: чи йшов того дня дощ? Багато людей схильні сказати, що, звісно, так, адже Іван узяв парасольку, коли мав іти дощ. Але початкове речення побудоване не так!

Насправді Іван міг узяти парасольку з якоїсь іншої причини, про яку ми не маємо уявлення. Наприклад, він бере парасольку щоразу, коли їде до бабусі, бо вона просила її повернути. Або вирішив купити нову парасольку, а стару викинути. Усе це цілком законні причини, чому Іван міг узяти парасольку, хоча дощу могло й не бути.

Тепер ми вже можемо відповісти на питання, коли імплікація істинна. Коли обидва висловлювання істинні, імплікація точно істинна: «якщо 42 — натуральне число, то воно додатне». Обидва висловлювання істинні, тож уся імплікація істинна. Іншим прикладом може бути імплікація «якщо 42 — натуральне число, то воно від'ємне». Ця імплікація не є істинною, бо з правди ми намагаємося вивести те, що не є правдою.

Нарешті лишаються випадки, коли перше висловлювання хибне. Тоді істинність другого висловлювання нас уже не цікавить. Якщо виходити з неправди, далі можна верзти що завгодно. Це речення на кшталт «якщо 1 — від'ємне число, то ми — імператори Місяця» або «якщо Карпати — відома будівельна фірма, то сонце синє». У таких випадках імплікація автоматично істинна, бо просто виходить із неправди. Таблиця:

$$\begin{array}{ccc} p&q&p \Rightarrow q\\ 1&1&1\\ 1&0&0\\ 0&1&1\\ 0&0&1 \end{array}$$

Істинність еквіваленції

Еквіваленцію записують p ⇔ q і читають «p тоді й лише тоді, коли q». Прикладом еквіваленції може бути «число x ділиться на два тоді й лише тоді, коли воно парне». Коли все речення буде істинним?

В еквіваленції ми очікуємо, що обидва висловлювання перебувають у такому симбіозі, що або виконуються обидва, або жодне. Тобто або число x парне і водночас ділиться на два, або не виконується ні те, ні те. Не може бути випадку, щоб x було парним, але не ділилося на два.

Приклад: «Юрко читає книжку тоді й лише тоді, коли сидить на дивані». Щоб еквіваленція виконувалася, щоразу, коли Юрко сидить на дивані, він мусить читати книжку. І водночас щоразу, коли він читає книжку, він мусить сидіти на дивані. Не може статися, що він читає книжку, скажімо, в ліжку.

Еквіваленцію можна виразити за допомогою двох імплікацій. Отже, p ⇔ q можна переписати як $p \Rightarrow q$ і водночас $q \Rightarrow p$. Таблиця:

$$\begin{array}{ccc} p&q&p \Leftrightarrow q\\ 1&1&1\\ 1&0&0\\ 0&1&0\\ 0&0&1 \end{array}$$

Заперечення

Заперечення — унарна операція, її записують або штрихом p', або цим символом: $\neg p$. Заперечення заперечує початкове твердження. Якщо маємо висловлювання «Оксана — співачка», то його запереченням буде «Неправда, що Оксана — співачка» або коротше «Оксана не співачка». Практично завжди заперечення можна утворити так, що перед висловлюванням поставити «Неправда, що…».

Заперечення обертає значення істинності, тобто з 0 робить 1, а з 1 робить 0. Тож можемо записати $\neg0=1$ і $\neg1=0$.

Зверни увагу на деякі підступні речі. Нехай маємо твердження «вапно біле». Яке його заперечення? Хтось міг би подумати, що «вапно чорне», але це не так! Якщо скористатися попереднім правилом, то запереченням буде висловлювання «неправда, що вапно біле». Чи обов'язково з цього випливає, що воно чорне? Ні, воно може бути, скажімо, рожевеньким.

Таблиця всіх зв'язок

$$\begin{array}{cccccc} p&q&p \wedge q&p \vee q&p \Rightarrow q&p \Leftrightarrow q\\ 1&1&1&1&1&1\\ 1&0&0&1&0&0\\ 0&1&0&1&1&0\\ 0&0&0&0&1&1 \end{array}$$

Істинність цілої формули

Тепер ми вже вміємо визначати істинність двох висловлювань, поєднаних логічною зв'язкою. Цілу формулу обчислюємо цілком аналогічно. Якщо маємо формулу $(p \Rightarrow q) \wedge r$, то коли обчислимо формулу $(p \Rightarrow q)$, наприклад, як 1, отримаємо класичну кон'юнкцію 1 ∧ r, яку ми вже вміємо обчислювати.

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

Табличний метод

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

Нехай маємо формулу $(p \vee q) \wedge (q \Rightarrow p)$. На початку запишемо в таблицю всі пропозиційні змінні, тобто p і q, та всі комбінації їхніх значень:

$$\begin{array}{cc} p&q\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Далі допишемо стовпці для окремих підформул p ∨ q і $q \Rightarrow p$.

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Тепер обчислимо ці формули та впишемо в стовпці нулі або одиниці. У таблиці є вся потрібна інформація. Діємо так: коли обчислюємо p ∨ q у першому рядку, то замість p підставляємо 1 і замість q також 1. Так отримуємо вираз 1 ∨ 1. Значенням цього виразу знову є 1, тож у таблицю пишемо одиницю:

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Так послідовно заповнимо всю таблицю:

$$\begin{array}{cccc} p&q&p \vee q&q \Rightarrow p\\ 1&1&1&1\\ 1&0&1&1\\ 0&1&1&0\\ 0&0&0&1 \end{array}$$

Тепер лишилося обчислити цілу формулу. Позначмо її, скажімо, $\varphi=(p \vee q) \wedge (q \Rightarrow p)$. Додамо до таблиці стовпчик із $\varphi$ і обчислимо його, використавши для цього вже два попередні стовпці.

$$\begin{array}{ccccc} p&q&p \vee q&q \Rightarrow p&\varphi\\ 1&1&1&1&1\\ 1&0&1&1&1\\ 0&1&1&0&0\\ 0&0&0&1&0 \end{array}$$

Таблиця вже повна й визначає значення істинності формули в усіх можливих інтерпретаціях. Наприклад, якщо e(p) = 1 і водночас e(q) = 1, то формула істинна. Якщо ж e(p) = 0 і e(q) = 1, то формула істинною не є.

Зверни увагу, що не можна сказати «формула істинна». Таке речення не має сенсу, адже щоб сказати, що формула істинна, треба було б указати, за якої інтерпретації формула істинна. Тож можна сказати: «формула $\varphi$ істинна за інтерпретації e₁ і не є істинною за інтерпретації e₂».

Єдиний випадок, коли можна сказати, що формула істинна, — якщо вона істинна за всіх можливих інтерпретацій. Наприклад, формула $p \vee \neg p$ істинна за всіх інтерпретацій, тож можемо сказати, що формула істинна. Аналогічно для випадку, коли формула хибна за всіх інтерпретацій.

Такі формули мають особливі назви. Формулу, яка істинна за всіх інтерпретацій, називають тавтологією. Формулу, яка не виконується за жодної інтерпретації, називають суперечністю.