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

Означення 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)

Те, що формулаалгебри висловлень 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. Висловлення називають логічно істинним (на базі алгебри висловлень) тоді і тільки тоді, коли його логічна структура є тавтологією.

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