Материал: discrete_mathematics

4. Перевірити, чи є логічно еквівалентними (рівносильними)

такі твердження: Неправильно, що a тоді й тільки тоді, коли b та ¬ a тоді й тільки тоді, коли ¬ b.

Запишемо дані твердження (висловлення) формально. Матимемо відповідно: ¬ (a ~ b) і (¬ a ~ ¬ b). Таблиці істинності цих формул відрізняються, тому наведені твердження не є логічно еквівалентними (рівносильними).

У той самий час, наприклад, твердження Неправильно, що a

та b і Неправильно, що a, або неправильно, що b є рівносильни-

ми. Це один із законів де Моргана, записаний словами. ◄

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

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

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

(в) (a b) → c ≡ (a ¬ c) → ¬ b; (г) (a ~ b) (a ¬ b b) ≡ a b.

2. Довести, що формули алгебри висловлень

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

рівносильні.

3. Визначити, яка із наведених чотирьох формул рівносильна

4.Довести, що a → b ≡ ¬ b → ¬ a (закон контрапозиції).

5.Перевірити (довести або спростувати), чи має місце така рівносильність:

(а) ¬ (a ~ ¬ b) ≡ a b ¬ a ¬ b;

(б) (a c) → (b d) ≡ (a → b) (c → d); (в) a → (a ~ b) ≡ (a → b);

(г) a → (b → c) ≡ (a b) → c;

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

6. Перевірити, чи є логічно еквівалентними (рівносильними) такі пари тверджень:

32

(а) Якщо a, то b та Якщо неправильно, що b, то неправильно, що a.

(б) Якщо a, то b" та Якщо неправильно, що a, то неправильно, що b.

(в) Якщо a, то b та Неправильно, що a, і неправильно, що ← b. (г) Із a випливає b та a тільки тоді, коли b.

(д) b випливає з a та ← b – достатня умова для ← a. (е) b – необхідна умова для a та b тільки тоді, коли a.

(є) b – необхідна умова для a та ← b – достатня умова для ← a. (ж) Неправильно, що a або b та Неправильно, що a, і непра-

вильно, що b.

(з) Неправильно, що a та ←b та Неправильно, що a, або справджується b.

7. Визначити, які із висловлень логічно рівносильні:

1)Студент розв'язав цю задачу, але не склав іспит з математичної логіки.

2)Студент розв'язав цю задачу або не склав іспит з математичної логіки.

3)Неправильно, що студент не розв'язав цю задачу або склав іспит з математичної логіки.

4)Студент розв'язав цю задачу і склав іспит з математичної логіки або він не розв'язав цю задачу й не склав іспит з математичної логіки.

5)Якщо студент склав іспит з математичної логіки, то він розв'язав цю задачу.

6)Студент склав іспит з математичної логіки тоді й тільки тоді, коли він розв'язав цю задачу.

1.4.Нормальні форми логічних функцій.

Досконаладиз'юнктивнанормальнаформа(ДДНФ). Досконалакон'юнктивнанормальнаформа(ДКНФ)

У п. 1.2 описано спосіб побудови таблиці істинності для заданої пропозиційної формули, тобто побудови таблиці логічної функції, яку задає ця формула.

Не менш важливою є обернена задача: для функції, заданої таблицею, графіком, словесно тощо, визначити (побудувати)

33

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

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

Розглянемо дві такі процедури.

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

Уведемо такі позначення: для логічної змінної x вважатимемо, що x0 = ← x та x1 = x. Неважко переконатись, що для логічної змінної a B виконується xa = 1, якщо a = x (тобто якщо значення змінних a та x збігаються), а xa = 0, якщо a ≠ x.

Розглянемо довільну логічну функцію f(x, y, z) від трьох

змінних. Нехай (a1, b1, c1), (a2, b2, c2),…, (ak, bk, ck) – це всі набори значень змінних, для яких функція f істинна (тобто дорівнює

1). Тоді формула, що задає цю функцію, має вигляд:

Справді, якщо до цієї формули підставити замість x, y та z

один із наборів (ai, bi, ci) (тобто покласти x = ai, y = bi і z = ci), то рівно один із логічних доданків формули (1.1), а саме доданок

xai ybi zci , дорівнюватиме 1, i = 1, 2, …, k. Отже, значенням усієї

формули (1.1) на цьому наборі (ai, bi, ci) буде 1. Якщо ж до (1.1) підставити будь-який інший набір значень змінних (тобто набір, що не увійшов до вищезазначеного списку з k елементів), то всі доданки формули (1.1)дорівнюватимуть 0, отже, і значенням усієї формули на такому наборі буде 0.

Таким чином, обґрунтовано, що значення формули (1.1) збігається зі значенням заданої функції f(x, y, z) на будь-якому наборі (a, b, c) значень її змінних, тобто (1.1) задає (реалізує) функ-

цію f(x, y, z).

34

Формулу (1.1) називають досконалою диз'юнктивною нор мальною формою (ДДНФ) логічної функції f(x, y, z).

Операції, що входять до складу ДДНФ – це кон'юнкція, диз'юнкція та заперечення.

Приклад 1.13.

1.Побудувати ДДНФ логічної функції, таблицю істинності якої отримано у прикладі 1.7. Ця функція набуває значення 1 на наборах (0,1,1), (1,0,0) і (1,0,1), тому її ДДНФ – це

x0y1z1 x1y0z0 x1y0z1 або ←xyz x←y←z x←yz.

2.Побудувати ДДНФ логічної функції f(x, y, z) від трьох змінних, яка набуває такого самого значення, як і більшість її змін-

них (функція голосування).

Функція голосування є істинною на наборах (0,1,1), (1,0,1),

(1,1,0) та(1,1,1), тому її ДДНФ – ←xyz x←yz xy←z xyz. ◄

Алгоритм побудови ДДНФ для логічних функцій від двох, чотирьох, п'яти та більшої кількості змінних аналогічний.

Приклад 1.14.

1.Побудувати ДДНФ логічної функції f (x, y, z, u) від чотирьох змінних, яка набуває значення 1 на тих і лише тих наборах значень її змінних, у яких кількість одиниць і кількість нулів збігаються.

З умови задачі робимо висновок, що наборами, на яких функція f набуває значення 1, є такі:

(0,0,1,1), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,0,0).

Шукана ДДНФ має вигляд

x0y0z1u1 x0y1z0u1 x0y1z1u0 x1y0z0u1 x1y0z1u0 x1y1z0u0 або

←x← yzu ← xy← zu ← xyz ← u x← y ← zu x← yz ← u xy ← z ← u.

2.Побудувати ДДНФ логічної функції f (x, y, z, u, v) від п'яти змінних, яка набуває значення 1 на тих і лише тих наборах значень її змінних, у яких тільки одна зі змінних дорівнює 0.

Отже, за умовою задана функція набуває значення 1 лише на наборах (0,1,1,1,1), (1,0,1,1,1), (1,1,0,1,1), (1,1,1,0,1) та (1,1,1,1,0).

Відповідна ДДНФ:

← xyzuv x ← yzuv xy ← zuv xyz ← uv xyzu ← v.◄

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

35

Нехай (a1, b1, c1), (a2, b2, c2),…, (ak, bk, ck) – це всі набори значень змінних, для яких логічна функція f(x, y, z) хибна (набуває

Аналогічно вищенаведеним міркуванням можна обґрунтувати, що для будь-якого набору (ai, bi, ci), i = 1, 2, …, k значенням формули (1.2) буде 0, а для будь-якого іншого набору, що не увійшов до цього списку, (1.2) дорівнюватиме 1. Пропонуємо переконатись у цьому самостійно.

Формулу (1.2) називають досконалою кон'юнктивною нор мальною формою (ДКНФ) відповідної логічної функції f(x, y, z).

Приклад 1.15.

1. Побудувати ДКНФ для логічної функції f(x, y, z) із прикладу 1.7.

Ця функція набуває значення 0 на наборах (0,0,0), (0,0,1),

(0,1,0), (1,1,0) і(1,1,1), тому її ДКНФ має вигляд

(x←0 y←0 z←0) (x←0 y←0 z←1) (x←0 y←1 z←0)(x←1 y←1 z←0) (x←1 y←1 z←1) або

(x y z) (x y ← z) (x ← y z) (← x ← y z) (← x ← y ← z).

2. Визначити ДКНФ функції голосування із попереднього прикладу.

Функція голосування f(x, y, z) є хибною для наборів (0,0,0), (0,0,1), (0,1,0) і(1,0,0), тому її ДКНФ є такою:

(x y z) (x y ← z) (x ← y z) (← x y z). ◄

Аналогічно можна побудувати ДКНФ логічної функції від будь-якої іншої кількості змінних.

1.5. Логічний висновок на базі алгебри висловлень.

Несуперечність множини висловлень

Формулу B(p1, p2, …, pn) називають логічним наслідком (ло гічним висновком) із формул

A1(p1, p2, …, pn), A2(p1, p2, …, pn), …, Ak(p1, p2, …, pn)

36