Висловлювання та логічні зв’язки
Класична математична логіка
Розділ 1
Основні поняття логіки висловлювань
Основні визначення
Логіка як самостійна наука виникла у IV столітті до н. е. в працях Аристотеля, який, опираючись на накопичені до нього знання, доповнив їх своїми власними й створив систему формального логічного висновку, що полягає в тому, що в міркуваннях одні пропозиції випливають з інших через певний зв'язок між їх формою і структурою незалежно від їх змісту.
Революційні наукові зворушення кінця ХІХ – початку ХХ століть торкнулися й логіки Аристотеля, шляхом реалізації ідеї Г. В. Лейбніца, запропонованої ним ще в кінці ХVII століття, про застосування в логіці математичної символіки і побудов логічних числень. Ця ідея реалізована у працях Д. Буля, Ч. С. Пірса, Ф. Л. Г. Фреге поряд із багатьма дослідженнями інших вчених.
Класична математична логіка містить два основні розділи: логіку висловлювань і логіку предикатів. Для їх побудови існують два підходи (мови), на основі яких базуються два варіанти формальної логіки: алгебра логіки і логічне числення. Між основними поняттями цих мов спостерігається взаємно однозначна відповідність, але, строго кажучи, ці терміни не є синонімами.
За своєю суттю логіка висловлювань– це наука про міркування, засновки і висновки яких складаються із висловлювань.
Означення 1.1.1. Висловлюванням називають осмислений вираз звичайної мови, якому можна приписати значення істинності.
Таким виразом може стати твердження або розповідне речення, про яке можна сказати, істинне воно чи хибне.
 |
Рисунок 1.1 – Складові частини математичної логіки
Необхідно мати на увазі, що в логіці висловлювань не існує засобів, щоб установити істинність чи хибність простого висловлювання. Якщо істинність чи хибність висловлювання не можна встановити взагалі (тобто за допомогою інших наук), то таке висловлювання не розглядається в логіці висловлювань (наприклад, наказові висловлювання, безглузді твердження).
Означення 1.1.2. Значення істинності – це абстрактний об’єкт, що ставиться у відповідність висловлюванню: істина – коли висловлювання відповідає дійсності, хибність – коли висловлювання не відповідає дійсності.
Позначають : “Істина ” – I, T (True), або 1; “Хибність” – 
, 
(False) або 0.
Приклад 1.1.1. Визначити, які із цих речень є висловлюваннями : “Дніпро впадає в Чорне море ”; “Дніпро впадає в Азовське море ”; “Хто ви?”; “Відстань від Землі до Сонця дорівнює 150 млн км ”.
Розв’язання. Перші два речення є висловлюваннями, причому перше є істинним, а друге – хибним висловлюванням. Третє речення не є висловлюванням, оскільки воно не розповідне. Четверте речення також не є висловлюванням. Його істинність або хибність залежить від потрібної точності.
Класична логіка висловлювань оперує лише двома значеннями істинності : І та Х, але не одночасно тим й іншим, тому її називають двозначною (бінарною) логікою.
Розповідні речення можуть бути простими та складними. Кожне просте речення є самостійним твердженням і не може бути розбитим на більш дрібні речення.
Означення 1.1.3. Атомом (елементарним висловлюванням) називається таке висловлювання, яке є простим розповідним реченням, тобто не має складових частин.
Для позначення атомів використовують як символи літери латинського алфавіту з індексами або без них.
Складні речення, як правило, складаються з простих речень, поєднаних сполучниками. Тобто прості речення, які представляють атоми та сполучники, є елементами словника, необхідного для формалізації природної мови за допомогою логіки висловлювання. Значення істинності складного висловлення визначається значеннями істинності його складових частин.
Алгебра висловлень цілковито абстрагується від смислового значення висловлювань, беручи до уваги лише їх предметне значення, тобто денотат, яким є такі абстрактні об'єкти, як "істина" та "хибність".
Означення 1.1.4. Інтерпретацією висловлюваньназивають приписування значень істинності атомам, із яких побудовані висловлювання.
Якщо висловлювання містить n атомів, то можна скласти 
інтерпретацій.
Означення 1.1.5. Однозначно визначеним висловлюваннямназивають висловлювання, значення істинності якого не залежить від ситуації. Наприклад , “ 33=9 ” = I. Але існують висловлювання, які можуть набувати різних значень. Наприклад, “Завтра буде сніг” може набути значення “Істина ” чи “Хибність ” залежно від конкретної ситуації.
Висловлювання та логічні зв’язки
Означення 1.2.1.Логіка висловлювань– це алгебраїчна структура á{ X, I }, 
, 
, 
, 
, ~ , X , I ñ з носієм – двійковою множиною { X : “Хибність”, I : “Істина”}, операціями – логічними зв’язками : “Ù” - кон’юнкція, “Ú” - диз’юнкція, “ ”– заперечення, “ ” – імплікація, “ ~ ” – еквівалентність і константами : X – хибність та I – істина.
У звичайній мові для утворення складного речення використовують службові слова – зв’язки : “ і ”, “ або ”,
“ неправильно, що” й інші. Наприклад, два речення “ Я поїду влітку до моря ” та “ Я поїду влітку в гори ” можна об’єднати зв’язкою “ або ” в одне складне речення “ Я поїду влітку до моря або в гори ”. Тут зв’язку “ або ” не можна приєднати ані до першого, ані до другого простого речення, вона обслуговує одночасно обидва простих речення і тому називається бінарною. Наприклад, у реченні “Неправильно, що жителів у Києві менше, ніж у Львові ” відбувається заперечення “В Києві менше жителів, ніж у Львові ”. Зв’язка “ неправильно, що … ” є унарною, тому що застосовується до одного речення. Крім розглянутих, існують зв’язки : “ якщо ”, “ якщо … то ”, “ і ”, “ тоді ”, “… тоді і тільки тоді ”, “ чи ”, “ ні ” й інші (табл. 1.2.1).
Таблиця 1.2.1 – Логічні зв’язки
| Назва | Позначення | Аналог природної мови |
| Заперечення |
| “ ні”, “ неправильно, що” |
| Диз’юнкція | Ú | “або” |
| Кон’юнкція | Ù | “і” |
| Імплікація |
| “ якщо …,то ” |
| Еквівалентність |
~ ,  , 
| “ еквівалентно”, “рівносильно”, “ тоді і тільки тоді ”, “ якщо і тільки якщо ” |
Операції , , , ~ є бінарними логічними зв’язками, а операція – унарною. Складні висловлювання, які побудовані з простих висловлювань, називають формулами,або молекулами.
Означення 1.2.2. Правила побудови формулу логіці висловлювань визначають таким:
1. Атом є формулою.
2. Якщо A і B – формули, то A B, A B, A B, A~B, A – також формули.
3. Ніяких формул, крім породжених зазначеними вище правилами, не існує.
Формули логіки висловлювань, що відповідають складним висловлюванням, набувають значень I і X залежно від значень елементарних висловлювань і логічних зв’язків, із яких вони побудовані.
Формули логіки висловлювань зручно подавати таблицями істинності, які надають значення істинності формули залежно від послідовного перебору всіх можливих значень істинності простих висловлювань, що становлять формулу (див. табл. 1.2.2).
Таблиця 1.2.2 – Таблиця істинності операцій
| A | B | A
| A B
| A B
| A B
| A~B |
| X | X | I | X | X | I | I |
| X | I | I | X | I | I | X |
| I | X | X | X | I | X | X |
| I | I | X | I | I | I | I |
Із таблиці істинності випливає, що заперечення A істинне тоді і тільки тоді, коли висловлювання A хибне. Ця унарна операція відповідає запереченню у звичайній мові, яке може мати різні синтаксичні вирази, наприклад речення “ Неправильно, що у Руслана є машина ” рівнозначне реченню “ У Руслана немає машини ”.
Висловлювання A B називають кон’юнкцією висловлювань A і B, яке істинне тоді і тільки тоді, коли істинні обидва висловлювання A і B. Ця логічна операція
відповідає у природній мові зв’язці “і”, що з’єднує два речення.
Приклад 1.2.1.Записати у вигляді формули логіки висловлювань і визначити істинне значення таких висловлювань : 1. “ 8 ділиться на 4 і 8 більше 6 ”;
2. “ 8 ділиться на 4 і 7 більше 8 ”.
Розв’язання. У цих висловлюваннях виділимо атоми. Їх три :
A – “ 8 ділиться на 4 ”,
B – “ 8 більше 6 ”,
C – “ 7 більше 8 ”.
Тоді висловлювання 1 буде відповідати формулі A B, а висловлювання 2 – формулі A С. Опираючись на те, що А, В – істинні, а С – хибне, визначимо значення висловлювань 1 і 2 :
A B = I I = I; A С = I X = X.
ВисловлюванняA Bназивають диз’юнкцією висловлювань A, B, яке дійсне тоді і тільки тоді, коли істинне хоча би одне логічне висловлювання A або B. Ця логічна операція відповідає у природній мові зв’язці “ або ”, що з’єднує два речення.
Приклад 1.2.2.Записати у вигляді формули логіки висловлювань і визначити істинні значення таких висловлювань :
1. “ 3 + 2 = 6 або 3 
2 = 6 ” ;
2. “ 4 – 2 = 3 або 4 2 = 7 ” .
Розв’язання. У поданих висловлювань виділимо атоми:
A – “ 3 + 2 = 6 ” ; B – “ 3 2 = 6 ” ;
C – “ 4 – 2 = 3 ” ; D – “ 4 2 = 7 ”
Тоді висловлювання 1 буде відповідати формулі A B, а висловлювання 2 – формулі C D. За умовою висловлювання B істинне, а висловлювання A, C, D хибні, тому : A B = X I = I; C D = X X = X.
Приклад 1.2.3.Нехай задані висловлювання : A –
“ Микола полюбляє грати у футбол ”; B – “ Микола полюбляє грати у волейбол ”; С – “ Микола полюбляє грати у теніс ”. Необхідно записати висловлювання “ Микола полюбляє грати у футбол і неправильно, що він полюбляє грати у волейбол або теніс ” у вигляді формули логіки висловлювань і побудувати відповідно до неї таблицю істинності.
Розв’язання. Висловлювання “ Микола полюбляє грати у волейбол або теніс ” можна записати у вигляді формули логіки висловлювань як B C. Висловлювання
“ Неправильно, що він полюбляє грати у волейбол або теніс ” може бути записане у вигляді формули логіки висловлювань ( B C ), оскільки заперечення застосовується до всього висловлювання, яке йде після зв’язки “ що … ”. Виходячи з цього, вихідна форма складного логічного висловлювання матиме вигляд A ( B C ).
Таблиця 1.2.3 – Таблиця істинності формули A ( B C )
| A | B | C | B C
| ( B C )
| A ( B C )
|
| X | X | X | X | I | X |
| X | X | I | I | X | X |
| X | I | X | I | X | X |
| X | I | I | I | X | X |
| I | X | X | X | I | I |
| I | X | I | I | X | X |
| I | I | X | I | X | X |
| I | I | I | I | X | X |
Із таблиці істинності складного висловлювання випливає, що лише в одному випадку це логічне висловлювання буде істинним, коли висловлювання A – істинне, а висловлювання B і C – хибні.