Література

1. Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцькиц Г.М., Печорін М.К. Основи дискретної математики. – К.: Наукова думка, 2002. – С.6-15.

2. Кужель О.В. Елементи теорії множин і математичної логіки. – К.: Рад. школа, 1977. – С. 4-24.

3. Новиков Ф.А. Дискретная математика для програмистов. – СПб.: Питер, 2002. – С.19-32.

4. Федосеева Л.И. Дискретная математика: Учеб.-практич. пособие. – Пенза: Изд-во Пенз. технол. ин-та, 1998. – С. 3-30.

Тема 4.3. Мінімізація формул булевих функцій у класі диз'юнктивних нормальних форм

Як було встановлено вище, довільна булева функція може бути представлена формулою в ДНФ і КНФ, причому таке подання неоднозначно. Рівносильними перетвореннями можна одержати формулу, що містить менше число входжень змінних. Наприклад, дві різні формули: f₁(x₁, x₂) = x₁V x₁&x₂ V x₂ і f₂(x₁, x₂) = x₁ V x₂ рівносильні, тому що в силу 2-го закону поглинання (Рівносильність 6б з розділу 4.3) x₁ V x₁&x₂  x₁.

Але у формулі f₁(x₁, x₂) утримується чотири входження змінних, а у формулі f₂(x₁, x₂) – два.

Визначення 4.3.1 ДНФ називається мінімальною, якщо вона містить найменше загальне число входжень змінних серед всіх рівносильних їй ДНФ.

Визначення 4.3.2 Імплікантом булевої функції f(x₁, x₂, ... , x_n) називається елементарна кон’юнкція С, не рівна тотожно 0, така що C V f f. Відзначимо, що будь-яка кон’юнкція будь-який ДНФ у силу закону ідемпотентності (рівносильність 5б) є імплікантом цієї функції.

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

Приклад 4.3.1.

Для функції x&yVx&zVx&y&z  x&(yVz) кон’юнкції x&y й x&z – прості імпліканты, а x&y&z – імплікант, але не простій.

Визначення 4.3.3. Диз'юнкція всіх простих імплікантов булевої функції f називається скороченої ДНФ функції f.

Для знаходження скороченої ДНФ використається наступний алгоритм, в основі якого лежить метод Квайна.

Алгоритм 4.3.1. (Алгоритм Квайна побудови скороченої ДНФ).

Крок 1. Знаходимо для даної булевої функції f її формулу F, що перебуває в ДДНФ.

Крок 2. Знаходимо всі прості імпліканты функції f. Для цього всі елементарні кон’юнкції формули F попарно порівнюємо між собою. Якщо дві елементарні кон’юнкції такі, що вони мають вигляд C&x_i і C&x_i, те виписуємо кон’юнкцію С. Це є наслідком 1-го закону розщеплення (склеювання) (рівносильність 7а). Кон’юнкція С містить n - 1 входження змінних. Елементарні кон’юнкції, для яких відбулося склеювання, позначаємо. Після побудови всіх кон’юнкцій, що включають n - 1 входження змінних, знову порівнюємо їх попарно, робимо, якщо можливо, склеювання, виписуємо отримані кон’юнкції з n - 2 членів, позначаємо що склеюються кон’юнкції з n - 1 членів і т.д. Процес закінчується, коли подальше склеювання неможливо. Всі непомічені елементарні кон’юнкції є простими імплікантами. Їхня диз'юнкція дасть нам формулу F₁, рівносильну F, що перебуває в ДНФ і складається із простих імплікантов, тобто скорочену ДНФ.

Приклад 4.3.2.

Знайдемо скорочену ДНФ функції:

f(x₁, x₂, x₃) = (x₂x₃) ~(x₁Vx₂).

1. Крок 1 був виконаний раніше. ДДНФ формули f(x₁, x₂, x₃) є формула

F(x₁, x₂, x₃) = x₁&x₂&x₃V x₁&x₂&x₃ V x₁&x₂&x₃ V x₁&x₂&x₃.

2. Попарно порівнюємо всі 4 тричленні кон’юнкції (всіх порівнянь C= 6) і застосовуємо, де це можливо, закон склеювання:

x₁&x₂&x₃V x₁&x₂&x₃ = x₂&x₃.

x₁&x₂&x₃ V x₁&x₂&x₃ = x₁&x₂.

x₁&x₂&x₃ V x₁&x₂&x₃ = x₁&x₃.

Отже, на першому етапі одержали 3 двочленні кон’юнкції:

x₂&x₃, x₁&x₂, x₁&x₃.

Всі тричленні кон’юнкції виявилися позначеними.

Попарно порівнюємо всі 3 двочленні кон’юнкції (всіх порівнянь 3) і зауважуємо, що склеювання неможливо.

У результаті одержимо скорочену ДНФ формули f:

F₁(x₁, x₂, x₃) = x₂&x₃ V x₁&x₂ V x₁&x₃.

На практиці для побудови скороченої ДНФ зручніше користуватися модифікованим методом Квайна - Мак-Класки. Цей метод складається в автоматизації процесу склеювання. Розберемо цей метод на конкретному прикладі.

Алгоритм 4.3.2. (Алгоритм Квайна - Мак-Класки побудови скороченої ДНФ).

Крок 1. Складемо таблицю значень булевої функції (якщо функція задана формулою в ДДНФ, то в силу зауваження до алгоритму 4.3 це завжди можна зробити)

Для нашого приклада така таблиця вже складена - це таблиця 4.4.

Очевидно, у силу алгоритму 4.3, ця функція має наступну формулу в ДДНФ:

f(x₁, x₂, x₃) = x₁&x₂&x₃V x₁&x₂&x₃ V x₁&x₂&x₃ V x₁&x₂&x₃.

Крок 2. Випишемо набори змінних, на яких функція приймає значення 1, причому ці набори впорядкуємо по групах так, що в кожну групу входять набори з однаковим числом одиниць. Нехай A_i – група наборів змінних, таких, що кожен набір містить i одиниць, і функція на цьому наборі змінних приймає значення, рівне одиниці.

Групи A₀ (де всі змінні нулі, а значення функції дорівнює 1) немає.

Група A₁ (де одна змінна одиниця, інші нулі, і значення функції дорівнює 1):

1 0 0

Група A₂:

0 1 1

1 0 1

Група A₃:

1 1 1

Крок 3. Робимо попарне порівняння наборів змінних, вхідних у сусідні групи. Якщо при цьому порівнянні виявляться два набори, які відрізняються тільки в одному розряді, то замість них записується один набір, у якому замість незбіжних розрядів ставиться “ – “ (прочерк). Після всіх можливих порівнянь із попереднього списку викреслюються всі набори, які брали участь в утворенні хоча б одного набору із прочерком. Формуються два масиви наборів: набори із прочерками (масив P) і невикреслені (масив R).

Ці дії відповідають склеюванню кон’юнкцій і зменшенню числа входжень змінних.

Для нашого приклада при порівнянні груп A₁ й A₂:

замість (1 0 0) і (1 0 1) одержимо (1 0 -);

При порівнянні груп A₂ й A₃:

замість (0 1 1) і (1 1 1) одержимо (- 1 1);

замість (1 0 1) і (1 1 1) одержимо (1 - 1);

Після цього етапу масив R порожній, тому що всі набори брали участь в утворенні наборів із прочерками, а масив P = P(1) включає наступні набори:

(1 0 -);

(- 1 1);

(1 - 1).

Далі розглянемо набори із прочерками. Вони знову попарно рівняються між собою. При цьому має сенс порівнювати лише набори, у яких прочерк коштує в співпадаючих розрядах. Якщо порівнювані набори відрізняються друг від друга тільки в одному розряді, то виписуємо набір із двома прочерками (старим і новим). Після всіх попарних порівнянь із множини наборів з одним прочерком викреслюються всі набори, що мають один прочерк і брали участь в утворенні набору із двома прочерками. Набори з одним прочерком, що не брали участь в утворенні наборів із двома прочерками, містяться в масив R.

Для нашого приклада попарне порівняння наборів з одним прочерком не приводить до утворення наборів із двома прочерками.

Далі розглянемо набори із двома прочерками і т.д. Процес припиняється, якщо на черговому кроці всі розглянуті набори попадають в R. Неважко переконатися, що кожному набору з R відповідає простий імплікант, причому одиниці відповідає змінна, взята без заперечення, нулю – змінна, взята із запереченням, а прочерку – відсутність відповідної змінної. Скорочена ДНФ є диз'юнкція цих простих імплікантов.

Для нашого приклада процедура порівняння закінчується після формування наборів з одним прочерком. Масив R після цього включає набори:

(1 0 -);

(- 1 1);

(1 - 1).

Скорочена ДНФ має вигляд:

f(x₁, x₂, x₃) = x₂&x₃ V x₁&x₂ V x₁&x₃.

Далі процес знаходження мінімальної ДНФ зводиться до відкидання деяких простих імплікантов.

Визначення 4.3.4. Простий імплікант називається істотним (ядровим) імплікантом, якщо його видалення зі скороченої ДНФ функції приводить до ДНФ, що не рівносильна вихідної ДНФ.

Побудова мінімальної ДНФ зводиться до відкидання несуттєвих імплікантов зі скороченої ДНФ.

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

Приклад 4.3.3.

Елементарна кон’юнкція x₁&x₂ покриває елементарні кон’юнкції x₁&x₂&x₃ і x₁&x₂&x₃, але не покриває елементарні кон’юнкції x₁&x₂&x₃ й x₁&x₂&x₃.

Знаходження мінімальної ДНФ складається у виборі таких простих імплікантов зі скороченої ДНФ, які в сукупності покривають всі елементарні кон’юнкції ДДНФ і містять мінімальне число входжень змінних. Така ДНФ рівносильна ДДНФ, тому що в силу визначення її значення на деякому наборі змінних збігаються зі значеннями ДДНФ.

Розглянемо наступний алгоритм знаходження мінімальної ДНФ.

Алгоритм 4.3.3. (Алгоритм побудови мінімальної ДНФ за допомогою таблиці покриттів).

Крок 1. Складання таблиці покриттів.

Для даної функції

f(x₁, x₂, ... , x_n) = A_i B_j, m k,

де A_i -елементарні кон’юнкції, що входять у ДДНФ, i = 1, 2, ..., k, k n, а B_j – прості імпліканти скороченої ДНФ, j = 1, 2, ... ,m, m k, побудуємо таблицю покриттів, число рядків якої дорівнює числу отриманих простих імплікантів, а число стовпців – числу елементарних кон’юнкцій у ДДНФ. Якщо в деяку елементарну кон’юнкцію входить який-небудь простий імплікант, то на перетині відповідного стовпця і рядка ставиться мітка (наприклад, “ * “).

Крок 2. Виділення стовпців, що містять одну мітку.

Якщо в яких-небудь стовпцях складеної таблиці є тільки одна мітка, то рядка, у яких коштують ці мітки, визначають прості імпліканты, які не можуть бути виключені зі скороченої ДНФ, тому що без них не може бути отримане покриття всіх елементарних кон’юнкцій ДДНФ. Вони є істотними й обов'язково входить у мінімальну ДНФ. Тому з таблиці покриттів виключаються рядки, що відповідають істотним імплікантам, і стовпці елементарних кон’юнкцій ДДНФ, покрывемые цими істотними імплікантами.

Крок 3. Викреслення зайвих стовпців.

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

Крок 4. Викреслення зайвих істотних імплікантів.

Якщо після викидання деяких стовпців у результаті кроку 3, у таблиці з'являються рядки, у яких немає жодної мітки, то прості імпліканты, що відповідають цим рядкам, виключаються з подальшого розгляду, тому що вони не покривають оставшиеся в розгляді елементарні кон’юнкції ДДНФ.

Крок 5. Вибір мінімального покриття істотними імплікантами.

Вибирається така сукупність рядків (тобто істотних імплікантов), щоб вони покривали всі стовпці, що залишилися (елементарні кон’юнкції ДДНФ). При декількох можливих варіантах перевага віддається варіанту покриття з мінімальним загальним числом входження змінних.

Приклад 4.3.4.

Продовжимо попередній приклад.

1. Становимо таблицю покриттів. Для формули, булевої функції зі ДДНФ:

f(x₁, x₂, x₃) = x₁&x₂&x₃V x₁&x₂&x₃ V x₁&x₂&x₃ V x₁&x₂&x₃

ми одержали рівносильну їй скорочену ДНФ:

F₁(x₁, x₂, x₃) = x₂&x₃ V x₁&x₂ V x₁&x₃.

Кожної елементарної кон’юнкції x₁^s1&x₂^s2&...&x_n^sn, (x_i ^si = x_i, якщо s_i = 0 й x_i^si = x_i, якщо s_i = 1, i = 1, 2, ... ,n), що входить у ДДНФ, можна зіставити набір змінних з нулів й одиниць. Цей набори ідентифікують стовпці. Кожному простому імпліканту зі скороченої ДНФ також можна зіставити набір з нулів, одиниць і прочерків, де 0 означає, що змінна береться із запереченням, 1 – змінна береться без заперечення, “ – ” – змінна відсутній. Для нашого приклада одержимо наступну таблицю (таблиця 4.6) з 4 стовпців, що відповідають 4 елементарним кон’юнкціям ДДНФ F(x₁, x₂, x₃, x₄) і 3 рядків, що відповідають 3 простим імплікантам скороченої ДНФ F₁(x₁, x₂, x₃, x₄).

Таблиця 4.6

	011	100	101	111
–11	*			*
10–		*	*
1–1			*	*

2. Виділяємо стовпці, що містять одну мітку – це 1-ий і 2-ий стовпці. Імплікант x₂&x₃ (йому відповідає 1-а рядок) є істотним. Він покриває дві елементарні кон’юнкції ДДНФ: x₁&x₂&x₃ й x₁&x₂&x₃ (їм відповідають 1-ий і 4-ий стовпці). Імплікант x₁&x₃ (йому відповідає 2-а рядок) теж є істотним. Він покриває дві елементарні кон’юнкції ДДНФ: x₁&x₂&x₃ і x₁&x₂&x₃ (їм відповідають 2-ий й 3-ій стовпці).

Всі зазначені рядки (1-ую й 2-ую) і стовпці (1-ий, 2-ий, 3-ій й 4-ий) викреслюємо з таблиці покриттів. Після цього всі елементи таблиці виявляться викресленими. Отже, два істотних імпліканта x₂&x₃ і x₁&x₃ покривають всі елементарні кон’юнкції ДДНФ.

Отже, мінімальна ДНФ для нашої функції має вигляд:

F₂(x₁, x₂, x₃) = x₂&x₃ V x₁&x₂ .

Розглянемо ще один приклад знаходження мінімальної ДНФ булевої функції.

Приклад 4.21.

Нехай булева функція задана таблицею

Таблиця 4.7

x1 x2 x3 x4	f(x1, x2, x3, x4)
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 0

Застосуємо спочатку алгоритм Квайна - Мак-Класки для знаходження скороченої ДНФ.

Очевидно, у силу алгоритму 4.3, дана функція має наступну формулу в ДДНФ:

F(x₁, x₂, x₃, x₄) = x₁&x₂&x₃&x₄ V x₁&x₂ &x₃ &x₄ V x₁&x₂&x₃&x₄ Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄Vx₁&x₂&x₃&x₄.

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

Групи A₀ немає.

Група A₁:

0 1 0 0

Група A₂:

0 0 1 1

0 1 0 1

1 0 1 0

1 1 0 0

Група A₃:

0 1 1 1

1 0 1 1

1 1 0 1

Групи A₄ немає.

Робимо попарне порівняння наборів змінних, вхідних у сусідні групи.

При порівнянні груп A₁ й A₂:

замість (0 1 0 0) і (0 1 0 1) одержимо (0 1 0 -);

замість (0 1 0 0) і (1 1 0 0) одержимо (- 1 0 0);

При порівнянні груп A₂ й A₃:

замість (0 0 1 1) і (0 1 1 1) одержимо (0 - 1 1);

замість (0 0 1 1) і (1 0 1 1) одержимо (- 0 1 1);

замість (0 1 0 1) і (0 1 1 1) одержимо (0 1 - 1);

замість (0 1 0 1) і (1 1 0 1) одержимо (- 1 0 1);

замість (1 0 0 1) і (1 0 1 1) одержимо (1 0 - 1);

замість (1 0 0 1) і (1 1 0 1) одержимо (1 - 0 1);

замість (1 1 0 0) і (1 1 0 1) одержимо (1 1 0 -).

Після цього етапу масив R порожній, тому що всі набори брали участь в утворенні наборів із прочерками, а масив P = P(1) включає наступні набори:

(0 1 0 -);

(- 1 0 0);

(0 - 1 1);

(- 0 1 1);

(0 1 - 1);

(- 1 0 1);

(1 0 - 1);

(1 - 0 1);

(1 1 0 -).

Тепер попарно рівняються між собою набори із прочерками. Набори з одним прочерком, що не брали участь в утворенні наборів із двома прочерками, містяться в масив R.

Для нашого приклада

замість (0 1 0 -) і (1 1 0 -) одержимо (- 1 0 -);

замість (- 1 0 0) і (- 1 0 1) одержимо (- 1 0 -)

Після цього етапу в масив R попадають набори, що не брали участь в утворенні наборів із двома прочерками:

(0 - 1 1);

(- 0 1 1)

(0 1 - 1);

(1 0 - 1);

(1 - 0 1);

Масив P(2) складається з набору із двома прочерками:

(- 1 0 -).

Набір із двома прочерками один і процедура порівняння закінчується. Тому всі набори з P(2) попадають у масив R, що після цього включає набори:

(0 - 1 1);

(- 0 1 1)

(0 1 - 1);

(1 0 - 1);

(1 - 0 1);

(- 1 0 -).

Скорочена ДНФ має вигляд:

F₁(x₁, x₂, x₃, x₄) = x₁&x₃&x₄ V x₂&x₃&x₄ V x₁&x₂&x₄ V x₁&x₂&x₄ V x₁&x₃&x₄ x₂&x₃.

Знайдемо тепер мінімальну ДНФ за допомогою таблиці покриттів (алгоритм 4.7).

Становимо таблицю покриттів.

Для нашого приклада одержимо наступну таблицю (таблиця 4.8) з 8 стовпців, що відповідають 8 елементарним кон’юнкціям ДДНФ F(x₁, x₂, x₃, x₄) і 6 рядків, що відповідають 6 простим імплікантам скороченої ДНФ F₁(x₁, x₂, x₃, x₄).

Таблиця 4.8

	0011	0100	0101	0111	1001	1011	1100	1101
0-11	*			*
-011	*					*
01-1			*	*
10-1					*	*
1-01					*			*
-10-		*	*				*	*

Виділяємо стовпці, що містять одну мітку – це 2-ий й 7-ий стовпці. Обоє цих стовпця визначають той самий імплікант x₂&x₃ (йому відповідає 6-а рядок), що є істотним. Він покриває наступні чотири елементарні кон’юнкції ДДНФ: x₁&x₂&x₃&x₄, x₁&x₂&x₃&x₄, x₁&x₂&x₃&x₄, x₁&x₂&x₃&x₄ (їм відповідають 2-ий, 3 - ий, 7 - ой й 8 - ой стовпці). Всі зазначені рядки й стовпці викреслюємо з таблиці покриттів. Після цього таблиця прийме вид:

Таблиця 4.9

	0011	0111	1001	1011
0-11	*	*
-011	*			*
01-1		*
10-1			*	*
1-01			*

В отриманій таблиці немає однакових стовпців. В отриманій таблиці немає порожніх рядків. Вибираємо таку сукупність істотних імплікантов, що покриває всі стовпці й містить найменша кількість букв. Для нашої таблиці це імпліканти x₁&x₃&x₄ і x₁&x₂&x₄ (1 - ий і 4 - ий рядки таблиці 4.9), тому що вони покривають всі стовпці, що залишилися.

Итак, мінімальна ДНФ для нашої функції має вигляд:

F₂(x₁, x₂, x₃, x₄) = x₁&x₃&x₄ V x₁&x₂&x₄ V x₂&x₃ .