1.2. Висловлювання та логічні зв’язки

Означення 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 – хибні.