5.1.3. Таблиці істинності

У таблиці істин­ності формули f(p,q,r) кожному символу логічної опера­ції в формулі f(p,q,r) відповідає окремий стовпчик таблиці, останній стовпчик відповідає істинісному значенню, яке визначається даною формулою (її головною операцією). Звернемо увагу на те, що кожен стовпчик таблиці істин­ності для формули f(p,q,r) відповідає певному кроку процесу її побудови або, як кажуть, певній підформулі f(p,q,r).

Наприклад, нехай задано функцію f(p,q,r)=(q  r )(qpr).

p	q	r	p	qr	p qr	 r	pr	qpr	f(p,q,r)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 1 1 1 0 0 0 0	0 1 1 1 0 1 1 1	0 1 1 1 1 1 1 1	1 0 1 0 1 0 1 0	1 0 1 0 1 1 1 1	1 1 1 0 1 1 1 1	0 1 1 0 1 1 1 1

Часто таблицею істинності формули f(p₁, ..., p_n) називають скорочену таблицю, в якій з вищенаведеної залишають перших п стовпчиків (значень аргументів p₁, ..., p_n) і останній стовпчик.

Степінь складності таблиці істинності для формули f швидко зростає із збільшенням кількості різ­них пропозиційних букв, що входять до f. Так, при п = 3 кількість рядків таблиці дорівнює 2³ = 8, при п = 4 воно становить 2⁴= 16, при п= 5 дорівнює 2⁵= 32, а при п = 10 — вже 1024. Практично побудувати таблицю істин­ності в останньому випадку вже неможливо.

5.1.4. Тавтології і суперечності.

Означення 5.1.8. Формули алгебри висловлень f (p_1, ... , p_n), які на всіх наборах (p₁, …, p_n), тобто при всіх можливих розподілах істинісних значень пропозиційних літер p₁, ..., p_n, набувають значення 1, називають тавтологіями, тотожно істинними формулами або законами алгебри висловлень.

Приклади деяких найважливіших тавтологій:

1. p – закон подвійного заперечення.

2. p  – закон виключеного третього.

3. (p) – закон виключення суперечності.

4. p  p – закон тотожності.

5. ppp – закон ідемпотентності.

6. ppp – закон ідемпотентності.

7. (pq)( ) – закон контрапозиції.

Довести те, що формули (1)—(7) є тавтологіями, можна за допомогою таблиць істинності. Наприклад, доведемо, що формула (7) є тавтологією.

p	q	p  q				(7)
0	0	1	1	1	1	1
0	1	1	0	1	1	1
1	0	0	1	0	0	1
1	1	1	0	0	1	1

Те, що формула алгебри висловлень f є тавтологією, позначають так: ⊨ f.

Означення 5.1.9. Формулу алгебри висловлень f (p₁ , , p_n), яка набуває значення істинності 0 на всіх 2ⁿ наборах, називають суперечністю. Найпростішим прикладом суперечності є формула p.

Означення 5.1.10. Формулу алгебри висловлень, яка не є ні тавтологією, ні суперечністю, називають нейтральною. Прикладом нейтральної формули є pq.

Множини тавтологій, суперечностей і нейтральних формул попарно не перетинаються і разом становлять множину всіх формул алгебри висловлень.

Означення 5.1.11. Формулу алгебри висловлень, яка не є суперечністю, називають виконуваною.

Так, формула рр — виконувана і формула р теж виконувана при p= 0; |p|=1.

Означення 5.1.12. Висловлення називають логічно істинним (на базі алгебри висловлень) тоді і тільки тоді, коли його логічна структура є тавтологією.

Прикладом логічно істинного твердження є “Трикутник АВС — рівнобедрений або трикутник АВС — не рівнобедрений” (логічна структура цього твердження — р).