► Для цього за допомогою індексів занумеруємо порядок виконання операцій у даній формулі, як було зроблено у прикладі
1.5(1). Матимемо:
(((a →4 (¬1b)) →7 (b 6 ((¬2c) →5 a))) ~8 (¬3a)).
Підставимо замість пропозиційних змінних a, b, c задані вище значення, дістанемо
(((1 →4 (¬11)) →7 (1 6 ((¬20) →5 1))) ~8 (¬31)).
Обчисливши операції 1, 2 та 3, дістанемо вираз
(((1 →4 0) →7 (1 6 (1 →5 0))) ~8 0),
який після обчислення операцій4 та5 набуде вигляду
((0 →7 (1 6 0)) ~ 8 0).
Результатом операції 6 є 0, отже, матимемо ((0 →7 0) ~8 0).
Після виконання операції 7 дістанемо (1 ~ 8 0). Останній вираз має значення 0. Таким чином, значенням даної формули на наборі (1,1,0) буде 0. Аналогічні обчислення можна виконати й для решти семи наборів значень змінних a, b, c. ◄
Функцію f називають функцією істинності для формули A або відповідного складеного висловлення. Для функції істинності f можна побудувати таблицю істинності (табл. 1.3). Традиційно набори значень змінних розташовують у цій таблиці в лексикографічному порядку (див. розд. 2).
p1 p2 ... |
pn–1 pn |
f (p1, p2, ..., pn–1, pn) |
Таблиця 1.3 |
0 0 ... |
0 0 |
f (0, 0, ..., 0, 0) |
|
0 0 ... |
0 1 |
f (0, 0, ..., 0, 1) |
|
0 0 ... |
1 0 |
f (0, 0, ..., 1, 0) |
|
0 0 ... |
1 1 |
f (0, 0, ..., 1, 1) |
|
......................... |
|
..................... |
|
1 1 ... |
1 0 |
f (1, 1, ..., 1, 0) |
|
1 1 ... |
1 1 |
f (1, 1, ..., 1, 1) |
|
Приклад 1.7. Побудувати таблицю істинності для формули із попереднього прикладу.
► У першому рядку кожного стовпця останньої таблиці записано вираз (підформулу) і номер відповідної операції. Наприклад, запис (a→(1)) (4) означає, що результатом операції із номером 4 є імплікація значення пропозиційної змінної a та результату операції з номером 1, а запис ((4)→(6)) (7) означає, що результатом операції з номером 7 є імплікація значення операції із номером 4 і результату операції із номером 6 тощо..
17
a b c |
(¬ b) |
(¬ c) (2) |
(¬ a) (3) |
(a → (1)) (4) |
((2) → a) (5) |
(b (5)) (6) |
((4) → (6)) (7) |
((7) ~ (3)) (8) |
|
(1) |
|||||||||
|
|
|
|
|
|
|
|
||
0 0 0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 0 1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
0 1 0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
0 1 1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 0 0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
1 0 1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
|
1 1 0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
1 1 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
◄
18
Формулу алгебри висловлень A(p1, p2, …, pn) називають тав тологією, коли їй відповідає функція істинності, що тотожно до-
рівнює 1. Те, що формула A є тавтологією, позначають як |
|
A. |
, |
||
Тавтології ще |
називають тотожно істинними |
|
|
||
або законами алгебривисловлень. |
формулами |
|
|||
|
|
|
|
||
Наведемо приклади деяких важливих тавтологій: |
|
|
|
|
|
(p (¬ p)) |
(закон виключення третього); |
|
|
|
|
(¬ (p (¬ p))) |
(закон виключення суперечності); |
|
|
|
|
(p → p) |
(закон тотожності). |
|
|
|
|
Переконатись у тому, що ці формули є тавтологіями, можна за допомогою відповідних таблиць істинності.
Іноді перевірку того, що певна формула є тавтологією, вико-
нують за допомогою способу відшукання контрприкладу (або методу від супротивного). Пояснимо його на прикладах.
Приклад 1.8.
1. Перевірити, чи є тавтологією формула
A = (((a → ¬b) (b → (a c))) (¬ c → ¬ a)) → (a ¬ c).
► Припустимо, що формула A не є тавтологією. Тоді принаймні на одному наборі значень формула A набуває значення 0. Спробуємо відшукати цей набір. Оскільки останньою (головною) операцією формули A є імплікація, то її консеквент має дорівнювати нулю, а антецедент – одиниці. Консеквент (a ¬ c) дорівнює нулю, коли a = 0 та c = 1. Звідси (a → ¬ b) = 1 та (¬ c → ¬ a) = 1. Залишилось з'ясувати, чи може за цих умов вираз (b → (a c)) дорівнювати одиниці. Відповідь позитивна (для b = 0). Отже, ми знайшли набір (0, 0, 1), на якому формула A набуває значення 0, тобто відшукали контрприклад, який свідчить, що формула A не є тавтологією. ◄
2. У разі, коли при спробі відшукати контрприклад для певної формули A отримуємо суперечність, можемо стверджувати, що A – тавтологія.
Наприклад, треба перевірити на тавтологічність формулу
B = (((a → ¬ b) (b → (a c))) (¬ c → ¬a)) → (a ¬ b),
яка є дещо зміненим варіантом попередньої формули A.
► Діючи саме у такий спосіб, матимемо: a = 0 і b = 1, звідки
(a → ¬ b) = 1, (¬ c → ¬ a) = 1, однак (b → (a c)) = 0, що су-
19
перечить припущенню (b → (a c)) = 1. Отже, формула B є тавтологією. ◄
Якщо формула A → B є тавтологією, то кажуть, що формула
A сильніша ніж B, а формула B слабша ніж A.
Формула алгебри висловлень A(p1, p2, …, pn), яка набуває значення 0 на всіх наборах (a1, a2, …, an) значень своїх пропозиційних змінних, називається суперечністю, або тотожно хиб
ною формулою.
Формулу, що не є ні тавтологією, ні суперечністю, називають
нейтральною.
Множину всіх формул алгебри висловлень розбивають на тавтології, суперечності та нейтральні формули.
Формулу, яка не є суперечністю, називають виконуваною,
інакше – невиконуваною.
Приклад 1.9.
1. Показати, що формула алгебри висловлень
(a → (b → ¬ b)) (a → c) (a ¬ c)
є виконуваною.
Для будь-якого набору значень змінних, у якому a = 1 та c = 0, підформула (a ¬ c), а отже, і вся формула набуватиме значення 1, тому ця формула є виконуваною.
2. Довести, що формула A = (a → c) (b → c) алгебри висловлювань є сильнішою за формулу B = (a b) → c.
Для доведення слід відомим способом переконатись, що формула A → B є тавтологією.
3. Визначити, чи є формула алгебри висловлень
((a b) → c) → ((a → c) (b → c))
тавтологією, суперечністю або нейтральною.
За допомогою таблиці істинності або методом відшукання контрприкладу для формули можна переконатись, що ця формула є тавтологією.
4. Чи може суперечність містити тільки операції із множини { , , ~, →}? Відповідь обґрунтувати.
Припустимо, що така формула-суперечність існує. Підставимо замість усіх її пропозиційних змінних значення 1. Усі підформули цієї формули містять тільки операції з множини { , , ~, →}, тому всі вони, отже, і вся формула набуватимуть
20
значення 1 (див. табл. 1.2). Це суперечить нашому припущенню про те, що ця формула є суперечністю. Звідси доходимо висновку, що такої суперечності бути не може.
5. Довести чи спростувати таке твердження: якщо A та B – тавтології, то A B – тавтологія. Чи правильне обернене твердження?
Оскільки A та B – тавтології, то на кожному наборі значень їхніх пропозиційних змінних ці формули набуватимуть значення 1, отже, формула A B також дорівнюватиме 1. Тому наведене твердження є істинним.
Обернене твердження не справджується. Наприклад, якщо A
– тавтологія, а B – суперечність, то A B буде тавтологією, але при цьому не виконуватиметься умова, що A та B – тавтології.
6. Довести чи спростувати таке твердження: якщо A → B – виконувана формула, то A та B – виконувані. Чи правильне обернене твердження?
Це твердження хибне. Наприклад, якщо A – суперечність (тобто не є виконуваною формулою), а B – довільна формула, то A → B буде тавтологією (тобто буде виконуваною формулою).
Обернене твердження справджується. Якщо A та B – виконувані формули, то принаймні на одному наборі значень пропозиційних змінних формула B набуватиме значення 1. Тоді на цьому наборі формула A → B також дорівнюватиме 1, а отже, буде виконуваною.
7. Довести твердження: якщо A та A → B – тавтології, то B – тавтологія (правило висновку, або modus ponens (МР)).
Припустимо, що формула B не є тавтологією. Тоді на якомусь наборі значень пропозиційних змінних формула B набуватиме значення 0. На цьому самому наборі формула A набуватиме значення 1, а формула A → B дорівнюватиме 0, а це суперечить припущенню, що A → B – тавтологія. Отже, припустивши, що формула B не є тавтологією, ми дійшли суперечності, тому справджується, що B – тавтологія.
8.Відомо, що формула A → B є тавтологією, а формула A ~ B
–нейтральна. Що можна сказати про формулу B → A?
Із умов задачі випливає, що існує такий набір значень пропозиційних змінних, на якому формула B набуватиме значення 1, а формула A – значення 0 (на цьому наборі формула A ~ B дорів-
21