Материал: discrete_mathematics

13. Довести, що формула (a → b) (b → c) → (a → (b c)) є тавтологією. Чи буде тавтологією обернена імплікація

(a → (b c)) → ((a → b) (b → c))?

14. У різні способи показати, що дана формула алгебри висловлень не є тавтологією:

(а) (a → b) → (b → a);

(б) ((a b) → c) ~ ((a → b) → c); (в) (a ~ (b c)) ~ ((a ~ b) (a ~ c)); (г) (a → (a → b)) → (b ~ a).

15. Перевірити (довести чи спростувати), чи є наведена формула алгебри висловлень тавтологією:

(а) ((a → b) → (c → d)) → ((a → c) → (b → d)); (б) (b → (a → (b → c))) → (a → c);

(в) ((a → b) (c → b)) ~ ((a c) → b);

(г) ((a → b) (c → d)) → ((a c) → (b d)).

16. Порівняти формули A та B. Переконатись, що одна з них є тавтологією, а інша – ні:

(а) A = a → ((a → b) → b), B = (a → (a → b)) → b; (б) A = ((a → b) → (a → ¬b)) → ¬ a,

B = (a → b) → ((a → ¬b) → ¬a); (в) A = (b → c) → ((a → b) → (a → c)),

B = ((b → c) → (a → b)) → (a → c).

17.Показати, що формулаалгебри висловлень є виконуваною: (а) (a → (b → ¬c)) (a → b) (c ~ ¬b);

(б) (a → b) (a → ¬b) (b → c) (b → ¬c) (c → a) (c → ¬a); (в) (¬a b) (¬b c) (a → ¬b).

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

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

(в) (a → (b → c)) (a → b) (a ¬ c); ( (г) ¬ b a (a → b);

(д) (a ¬ a) → (b ¬ b).

19. Довести, що формула A алгебри висловлень є сильнішою за формулу B:

(а) A = (a → b) (b → c), B = a → c;

27

(б) A = (a → b) (b → c), B = a → (b c); (в) A = (a ~ b) (b ~ c), B = a ~ c;

(г) A = a → (b → c), B = (a → b) → (a → c).

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

(а) ((a b) → c) → ((a → c) (b → c)); (б) (a c b d) → ((a b) (c d)); (в) (a b c d) → ((a b) (c d)); (г) ((a ~ b) → (c ~ d)) → ((a c) ~ (b d));

(д) ((a → b) a b) ~ ((a → b) a); (е) ((← a b) (← b c) a) → ← c.

21.Чи може тавтологія містити тільки операції із множини { , }? Відповідь обґрунтувати.

22.Довести, що будь-яка формула алгебри висловлень, опе-

раціями якої є тільки операції з множини { , }, є нейтральною.

23.Довести, що довільна формула алгебри висловлень, яка містить із символів логічних операцій лише , , →, ~, є виконуваною.

24.Довести чи спростувати твердження:

(а) Із двох формул A та ← A алгебри висловлень принаймні одна – тавтологія.

(б) Якщо A та B – тавтології, то A B – тавтологія. Чи правильне обернене твердження?

(в) Якщо A та B – тавтології, то A B – тавтологія. Чи правильне обернене твердження?

(г) Якщо A та B – тавтології, то A → B – тавтологія. Чи правильне обернене твердження?

(д) Якщо формула A ~ B – тавтологія, то A та B – тавтології. Чи правильне обернене твердження?

25. Довести чи спростувати твердження:

(а) Якщо A – виконувана формула алгебри висловлень, то формула ← A є невиконуваною.

(б) Формула A невиконувана тоді й тільки тоді, коли A – суперечність.

(в) Із двох формул A та ← A алгебри висловлень хоча б одна є виконуваною.

28

(г) Якщо A та B – виконувані формули, то A B – виконувана. Чи правильне обернене твердження?

(д) Якщо A та B – виконувані формули, то A B – виконувана. Чи є правильним обернене твердження?

(е) Якщо A ~ B – виконувана формула, то A та B – виконувані. Чи правильне обернене твердження?

26. Довести твердження:

(а) Якщо A → B і ¬ B – тавтології, то ¬A – тавтологія (правило заперечення, або modus tolens).

(б) Якщо A B і ¬ A – тавтології, то B – тавтологія (правило диз'юнктивного силогізму).

(в) Якщо A → B і B → C – тавтології, то A → C – тавтологія (правило ланцюгового висновку).

(г) Якщо A → B та A → ¬ B – тавтології, то ¬A – тавтологія (метод доведення від супротивного).

27. Довести твердження:

(а) Якщо (A B) і (¬ A C) – тавтології, то (B C) – тавтологія. (б) Якщо формули (A B), (A → C) і (B → D) – тавтології, то

(C D) – тавтологія.

(в) Якщо (¬ A B) і (¬ B ¬ C) – тавтології, то (A → ¬ C) – тавтологія.

28. Відомо, що формула A → B є тавтологією, а формула A ~ B – суперечністю. Що можна сказати про формулу B → A?

29.Формула A ~ B є суперечністю. Що можна стверджувати про формули ¬ A ~ B і ¬ A ~ ¬ B?

30.Відомо, що B B → C. Чи можна стверджувати, що для

довільної формули A алгебри висловлень формула (A → B) → (A → C) є тавтологією?

31. Розставити дужки у формулах:

(а) a b → c → (a → c (b → c)); (б) a c b d → (a b) c d; (в) a b c d → a b c d;

(г) (a ~ b) → (c ~ d) → a c ~ b d;

(д) a → b a b ~ (a → b) a; (е) ¬ a b ¬ b c a → ¬ c.

32. Побудувати дерева синтаксичного аналізу для формул із завдання 31.

29

1.3.Рівносильні формули алгебри висловлень

Формули A та B алгебри висловлень називають рівносиль ними, якщо їм відповідає та сама функція істинності, тобто вони набувають однакових значень на всіх наборах значень їхніх пропозиційних змінних.

Рівносильність формул A та B позначають за допомогою знака ≡ (= або ↔): записують A ≡ B.

Рівносильні формули ще часто називають еквівалентними. Рівносильність формул можна перевірити складанням таблиць

істинності відповідних функцій і порівнюванням цих таблиць.

Рівносильним перетворенням формули A називають дію або процедуру, у результаті якої дістаємо формулу B, рівносильну формулі A.

Неважко довести (побудовою відповідних таблиць істиннос-

ті) основні тотожності (рівносильності, закони) алгебри ви

словлень.

1.(a b) c ≡ a (b c), (a b) c ≡ a (b c) – асоціативність;

2.a b ≡ b a, a b ≡ b a – комутативність;

3.a (b c) ≡ (a b) (a c), a (b c) ≡ (a b) (a c) –

дистрибутивність;

4.a a ≡ a, a a ≡ a – ідемпотентність;

5.¬ (a b) ≡ ¬ a ¬ b, ¬ (a b) ≡ ¬ a ¬ b – законидеМоргана;

6.¬ ¬ a ≡ a – закон подвійного заперечення;

7.a 0 ≡ a, a 1 ≡ a; a 1 ≡ 1, a 0 ≡ 0 – властивості елемен

тів 0 та 1;

8.a ¬ a ≡ 1, a ¬ a ≡ 0 – властивості заперечення;

9.a (a b) ≡ a; a (a b) ≡ a – правила поглинання.

Приклад 1.12.

1. Довести такі рівносильності алгебри висловлень:

Кожну із наведених рівносильностей неважко довести, побудувавши відповідні таблиці істинності для її правої і лівої частин і порівнявши ці таблиці.

Важливим висновком із цих рівносильностей є те, що операції → та ~ є надлишковими в алгебрі висловлень. Кожну підформулу, що містить такі операції, можна замінити на рівносильну їй (згідно з наведеними рівносильностями), що міститиме лише операції кон'юнкції, диз'юнкції та заперечення.

2. Використавши тотожності попередньої задачі, замінити формулу алгебри висловлень ¬ (a → b) ~ (¬ a → ¬ b) рівносильною, що містить лише операції кон'юнкції, диз'юнкції та заперечення.

Замінимо спочатку підформули, що містять символ операції →. Матимемо ¬ (¬a b) ~ (¬ ¬ a ¬ b). Використавши тотожність 4 попередньої задачі, отримаємо рівносильну формулу

(¬ ¬ (¬ a b) (¬ ¬ a ¬ b)) (¬ (¬ a b) ¬ (¬ ¬ a ¬ b)).

Застосуємо до цієї формули закон подвійного заперечення зі списку основних тотожностей алгебри висловлень. Отримаємо формулу ((¬ a b) (a ¬b)) (¬(¬ a b) ¬ (a ¬ b)). Од-

нак і після спрощення дістали рівносильну формулу, що майже вдвічі довша від початкової. Саме цим пояснюється наявність надлишкових операцій → та ~ в алгебрі висловлень.

3. Дано два складені висловлення:

1)Якщо один доданок кратний 3 і сума кратна 3, то й другий доданок кратний 3.

2)Якщо один доданок кратний 3, а другий – не кратний 3, то сума не кратна 3.

Записати ці висловлення формально й визначити, чи вони рівносильні.

Позначимо елементарні висловлення, з яких складено наве-

дені висловлення, так: a – один доданок кратний 3, b – сума кратна 3, c – другий доданок кратний 3. Відповідні формули,

що задають логічну структуру цих висловлень, є такими:

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

Побудувавши таблиці істинності для кожної із цих формул, переконаємося, що вони рівносильні.

31