Завдання №7

Булева функція задана в числовому вигляді. Побудувати таблицю істинності. Знайти:

1. СДНФ, скорочену ДНФ (номер варіанту кратний 2) або СКНФ, скорочену КНФ (номер варіанту некратний 2);

2. МДНФ (номер варіанту кратний 2) або МКНФ (номер варіанту некратний 2) , використовуючи алгоритм Квайна-Мак-Класки;

3. МКНФ та МДНФ, використовуючи діаграми Вейча.

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

Номер варіанту	Булева функція
1	f(x1,x2,x3,x4)={1,3,5,7,9,13,14,16}
2	f(x1,x2,x3,x4)={9,10,11,12,16,8,4,6}
3	f(x1,x2,x3,x4)={1,4,6,8,9,14,16}
4	f(x1,x2,x3,x4)={1,5,9,10,12}
5	f(x1,x2,x3,x4)={1,2,7,8,9,13,14
6	f(x1,x2,x3,x4)={2,6,8,10,12,14}
7	f(x1,x2,x3,x4)={1,3,5,7,9,11,13,15}
8	f(x1,x2,x3,x4)={1,4,5,8,9,12,13,16}
9	f(x1,x2,x3,x4)={3,7,8,9,14,15,16}
10	f(x1,x2,x3,x4)={2,4,6,7,12,14,15}
11	f(x1,x2,x3,x4)={1,4,7,8,9,12,15,16}
12	f(x1,x2,x3,x4)={3,7,9,11,12,16}
13	f(x1,x2,x3,x4)={3,4,12,14,16}
14	f(x1,x2,x3,x4)={7,10,14,15,16}
15	f(x1,x2,x3,x4)={2,8,9,10,13,16}
16	f(x1,x2,x3,x4)={2,3,6,7,9,10,12}
17	f(x1,x2,x3,x4)={3,4,5,13,15,16}
18	f(x1,x2,x3,x4)={6,8,11,12,15,16}
19	f(x1,x2,x3,x4)={6,7,8,10,11,12}
20	f(x1,x2,x3,x4)={1,4,5,13,16}
21	f(x1,x2,x3,x4)={4,6,8,11,14,15}
22	f(x1,x2,x3,x4)={2,3,4,8,9,13}
23	f(x1,x2,x3,x4)={2,8,11,14,15,16}
24	f(x1,x2,x3,x4)={2,8,10,12,16}
25	f(x1,x2,x3,x4)={2,3,4,10,15}
26	f(x1,x2,x3,x4)={1,2,5,7,8,13,16}
27	f(x1,x2,x3,x4)={2,3,4,5,6,14,15,16}
28	f(x1,x2,x3,x4)={1,2,3,9,10,11,12,16}
29	f(x1,x2,x3,x4)={5,6,7,8,11,13,15,16}
30	f(x1,x2,x3,x4)={1,2,3,4,6,9,11,13,16}

4 Основи алгебри логіки: висловлення, перетворення складних висловів до нормального виду, ведення доказу за допомогою методу резолюцій

Як наука логіка виникла ще у IV ст. до. н. е. у працях стародавнього філософа Аристотеля, основоположника формальної логіки. Далі ідею математизації логіки висловив німецький учений Лейбниць у XVII ст. до. н. е. Він сформулював задачу створення нової логіки, яка була б «мистецтвом обчислення». І тільки у середині ХІХ ст. ірландський учений Дж. Буль частково втілив у життя ідею Лейбниця. У його роботах та роботах Де Моргана було закладено основи булевої алґебри та алґебри логіки.

У природних умовах інформація передається за допомогою слів, об’єднанних у речення. Математична логіка вивчає та модулює тільки оповідальні речення. Наказові, окличні та питальні речення знаходяться поза сферою розгляду. Скорочені речення виключаються тому, що можуть мати подвійне значення.

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

Оповідальні речення бувають простими і складними. Складні, як правило, складаються з простих, поєднаних сполучниками, які називаються логічними зв’язками. Логічними зв’язками вважаються наступні операції:

 – заперечення;  або & – кон’юнкція;  або + –диз’юнкція;  – імплікація або логічне слідування;  або  – еквівалентність.

Логіка висловлень – це алґебраїчна структура {{0,1}, , ,  , , , 0,1}.

Атомами (елементарними висловленнями) називаються висловлення, які відповідають простим оповідальним реченням, тобто не мають складових частин.

У логіці висловлень правильно побудована формула визначається рекурсивно таким чином:

1. Атом є формула. 2. Якщо А і В – формули, то (АВ), (АВ), (АВ), (АВ), А – також формули. 3. Ніяких формул, крім породжених указаними вище, не існує.

Таблиця 4.1 – Таблиця істинності логічних зв’язок

А	В	АВ	АВ	АВ	АВ	А
0	0	0	0	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	0	0
1	1	1	1	1	1	0

Формула називається тавтологією (тотожно істинною), якщо вона набуває істинного значення на всіх наборах значень змінних.

Формула називається нездійсненною (тотожно хибною), якщо вона набуває хибного значення на всіх наборах значень змінних.

При створенні математичної логіки мали на меті побудову формальної мови для математичних міркувань і доведень. Проблема доведення у логіці полягає у пошуку формули В, яку назвемо висновком, якщо В є логічним наслідком уведених припущень А₁, А₂,…,А_n. Припущення називаються аксіомами або гіпотезами, при цьому передбачається, що вони тотожно істинні у всій розглянутій теорії. Найчастіше методом розв'язання цієї проблеми є використання правила висновку, яке допомагає отримати нові висловлення з існуючих. Процес побудови нових висловлень продовжується до отримання необхідного висновку.

Дедуктивним висновком називається висновок формули В з формули А, оснований на тому, що В є логічним наслідком А.

Найстарішими правилами виведення вважається правило відділення (Modus Ponens або скорочення припущення) та ланцюгове.

Правило відділення має вигляд: з припущень А, А В можна вивести В або (А  (А В)) В, тобто якщо засновок правильний, то правильний і наслідок з нього. Наприклад: «Якщо студент не вивчив теорію, то він не виконає завдання. Студент не вивчив теорію. Отже, студент не виконає завдання.» або «Якщо студент одержав п'ять, значить він розв’язав задачу. Студент одержав п'ять. Отже, він розв’язав задачу.».

Ланцюгове правило має вигляд . ((А В)  (ВС))  (АС). Аналог цього правила зустрічається досить часто у математиці, а тому будемо вважати його очевидним.

Розглянемо приклад 4.1. Нехай існують гіпотези

(РQ) ((Р  Q) (R  Q)); (4.1)

(R  Q)(R  S); (4.2)

РQ. (4.3)

З (4.1) та (4.3) за правилом відділення

(Р  Q)(R  Q). (4.4)

З (4.4) та (4.2) за ланцюговим правилом (Р  Q)(R  S).

Універсальним методом виведення, який використовується у логіці предикатів та у мові логічного програмування Пролог, є метод резолюцій. У ньому використовується лише одне правило виведення, яке поєднує дві формули, виконавши видалення з однієї атом А, а з другої А. Це правило основане на тавтології ╞(XA)&(YA), з якої маємо (XA),(YA)├(XY).

Для використання правила резолюцій необхідно виконати наступні дії (використовується ведення доказу від супротивного з накладанням інверсії на висновок).

1. Перетворюємо всі посилання та заперечення до вигляду КНФ (кон'юнкції єлементарних диз'юнкцій).

1.1. Виключаємо зв’язки ↔ та → за допомогою тавтологій (A↔B) = (A→B)&(B→A) та A→B = AB;

1.2. За допомогою законів Де Моргана пересуваємо заперечення у середину формул;

1.3. Використовуємо дистрибутивний закон A(B&C) = (АВ)&(АС).

2. Після використання першого кроку всі гіпотези було перетворено на кон’юнкцію диз’юнктів, можливо одночлена. Для поліпшення процесу використання правила резолюцій виписуємо кожен диз’юнкт з нового рядка.

3. Вибираємо з диз’юнктів довільні два, у яких один і той самий атом зустрічається з протилежними «знаками». Наприклад, XYZP та XPW. Використовуємо правило резолюцій для вибраних диз’юнктів: (XYZP)  (XPW)=XYZW.

4. Продовжуємо перетворення за правилом резолюцій до того часу, поки не отримаємо дві взаємно протилежні гіпотези, наприклад, Р та Р, застосувавши до яких правило резолюцій, отримуємо порожній диз’юнкт або тотожну «хибність». Порожній диз’юнкт записується □.

Приклад 4.2. Методом резолюцій довести формулу:

РQ, PR, QS ├RS.

Перетворюємо посилки до нормального вигляду

1. PQ.

2. PR.

3. QS.

Формуємо заперечення висновку та перетворюємо його до нормального вигляду (RS) =RS.

4. R.

5. S.

Виводимо порожній диз’юнкт за допомогою правила резолюцій:

6. з (2, 4) Р.

7. з (1б 6) Q.

8. з (3, 5) Q.

9. з (7, 8) □.

Отже, методом резолюцій доведено, що висновок RS є логічним наслідок з гіпотез РQ, PR, QS.