Материал: discrete_mathematics

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

нюватиме 0, а формула A → B – 1), а також існує такий набір, на якому обидві формули A та B набуватимуть однакових значень (на цьому наборі обидві формули A ~ B та A → B дорівнюватимуть 1). Тоді на першому із цих наборів формула B → A дорівнюватиме 0, а на другому вона дорівнюватиме 1. Отже, формула

B→ A – нейтральна.

9.Відомо, що B A → ¬ A. Що можна сказати про формулу A?

Формула A є суперечністю. Якщо припустити, що формула A не є суперечністю, то вона виконувана, тобто принаймні на одному наборі значень пропозиційних змінних формула A набуватиме значення 1. Тоді на цьому наборі формула A → ¬ A дорівнюватиме 0, що суперечить умові задачі. ◄

Порядок виконання операцій у формулі визначається за до-

помогою дужок. Задля зменшення їх кількості випускають зовнішні дужки й запроваджують такий порядок (пріоритет) виконання операцій у разі відсутності дужок: ¬, , , →, ~ (за спаданням). Часто у формулах алгебри висловлень випускають знак кон'юнкції і замість a b записують ab.

Для визначення порядку виконання операцій у формулі пріоритету операцій не достатньо. Потрібно ще вказувати для однакових операцій, групуються вони зліва направо чи справа наліво. Наприклад, операції та групуються зліва направо, а операція → – справа наліво. Тому для формули a b c дужки розставляємо таким чином: ((a b) c), для формули a → b → a дужки розставляємо так: (a → (b → a)). Зазначимо, що для операцій та порядок групування не є суттєвим, але для операції → він є важливим. Тому для формули a → b → a при групуванні дужок справа наліво отримаємо формулу (a → (b → a)), яка не еквівалентна попередній формулі (a → (b → a)). Переконайтесь у цьому самостійно. Для операції еквівалентності групування не використовують.

Приклад 1.10. Розставитидужки у формулі: a → b → ¬ b a → c a ¬ c.

► Починаємо із пошуку операцій найвищого пріоритету й беремо відповідну підформулу в дужки. Тут операцією з найви-

22

щим пріоритетом є заперечення. Воно зустрічається двічі. Отримуємо формулу

a → b → (¬ b) a → c a (¬ c).

Наступна за пріоритетом операція – це . Така операція має два аргументи. Беремо відповідні підформули в дужки:

a → b → ((¬b) a) → c (a (¬ c)).

Далі виокремлюємо підформулу з операцією . Дістали a → b → ((¬b) a) → (c (a (¬ c))).

Наступна за пріоритетом операція – імплікація →. Однак тут треба врахувати порядок групування, тому отримуємо остаточний результат:

(a → (b → (((¬ b) a) → (c (a (¬ c)))))). ◄

Структура формули. Розстановка дужок у формулі вказує не лише на порядок виконання операцій, а фактично задає її структуру. Тут важливими є поняття головної операції у формулі та її аргументів.

Приклад 1.11. Проаналізувати структуру формули

(a → (b → (((¬ b) a) → (c (a (¬ c))))))

із прикладу 1.10.

► Головною буде перша імплікація (позначаємо головну операцію зірочкою *). Маємо такий запис:

( a →* (b → (((¬b) a) → (c (a (¬ c)))))).

Далі аналізуємо підформули. Підформули

a та (b → (((¬ b) a) → (c (a (¬ c)))))

задають перший і другий аргументи цієї операції. Для другої підформули головною буде перша імплікація, тобто

(b →* (((¬ b) a) → (c (a (¬ c))))).

Далі, у підформулі

(((¬ b) a) → (c (a (¬ c))))

головною є імплікація, тому отримуємо

(((¬b) a) →* (c (a (¬c)))).

Аргументами є підформули

Продовжуючи таким чином, підійдемо до найпростіших підформул a , b, c.

Структуру формули часто подають деревом синтаксичного аналізу формули. У ньому дужки не вказують. Для проаналізованої формули дерево синтаксичного аналізу має вигляд:

c

Наведене дерево дає наочне уявлення про порядок виконання операцій, оскільки спочатку виконуються операції, записані внизу дерева, а потім ті, які йдуть вище. ◄

Проблема розв'язності в алгебрі висловлень – це задача знаходження алгоритму, за допомогою якого для будь-якої формули A алгебри висловлень можна визначити, є A тотожно істинною (тавтологією), чи ні.

Для алгебри висловлень цю проблему можна, зокрема, роз- в'язати такими двома способами:

1) побудувати таблицю істинності для формули A й перевірити, чи складається стовпчик значень A лише з одиниць;

24

2) застосувати спосіб відшукання контрприкладу. Аналогічно можна сформулювати й розв'язати проблему роз-

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

Завдання для самостійної роботи

1. Визначити, чи є наведена послідовність символів формулою алгебри висловлень:

(а) (((x → y) (¬z)) ~ ((¬x) → (y → x)));

(б) (((¬x) ~ ((¬y) + 1)) → (x 5y)); (в) (((¬y) ~ (x (¬z))) → ((¬ y) x)); (г) (((((x → y) ~ (¬z)) x) (¬ y))).

2.Виписати всі підформули даної формули: (а) (((x → (¬ y)) (¬z)) ~ ((¬ x) → (x z)));

(б) ((((y (¬ z)) → (y z)) ~ ((¬ y) x)); (в) ((z → (¬ y)) ((¬x) (¬(y (¬ x)))));

(г) (((¬x y) (x ~ ((¬y) → x)).

3.Занумерувати послідовність виконання операцій у формулі:

(а) (((y ~ (¬ z)) (¬ x)) → ((¬ z) ~ (x y)));

(б) (((x → (¬ y)) → (y ((¬ z) → x))) ~ (¬ x)).

4.Занумерувати послідовність виконання операцій у формулі

зурахуванням їхніх пріоритетів:

(а) (a → ¬ b) (¬ a ~ c) b (c → ¬ (a ~ b));

(б) (a → ¬ ((b c) ¬ a)) → (¬ c b) a ~ ¬ (a → ¬ b).

5. Знайти значення істинності формули:

(а) (a ~ b) ((¬ c → b) (¬ a c) (a ¬ b)) при a = 0, b = 1, c = 0;

(б) ((b → a) (¬ c (a ~ ¬ b))) → (a (d ¬ b)) при a = 1, b = 1, c = 0, d = 1;

(в) ¬ a (a ~ c) (¬ b (¬ c → a)) при a = 1, b = 0, c = 1.

6. Знайти значення істинності складеного висловлення:

(а) Якщо ми успішно складемо іспити (a), то поїдемо відпочивати до моря (b), і ми або успішно складемо іспити, або здійснимо турпохід у Карпати (c) тоді й тільки тоді, коли погода

25