Мінімізація булевих функцій за допомоги дужкових форм

Загальні питання мінімізації

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

Наприклад, для булевої функції трьох змінних, f (1,3,5,6,7) = 1, 6-а і 7-а кон'юнкції мають вигляд: x1x2ẍ3, x1x2x3. За дистрибутивним законом: x1x2ẍ3 v x1x2x3 = x1x2 (ẍ3 v x3) = x1x2. Таким чином, дві кон'юнкції, що містять несуттєву змінну, замінюються однією, в якій суттєва змінна відсутня.

У кубічному вигляді склеювання має наступну інтерпретацію: 1 1 0 U 1 1 1 = 1 1 X, що відповідає кон'юнкції x1x2. Наведемо основні визначення, використовувані при мінімізації булевих функцій.

Число змінних, що входять в елементарну кон'юнкцію (для ДНФ) або в елементарну диз'юнкцію (для КНФ) називається її рангом. В основі будь-яких методів мінімізації лежить операція склеювання. Дві елементарні похідні одного рангу (для ДНФ) або елементарних сум одного рангу (для КНФ) склеюються, якщо вони різняться лише з однією змінною. Операція Аx v Aẍ = A називається повним склеюванням, а операція Аx v Aẍ = A v Аx v Aẍ - неповним склеюванням (для ДНФ).

Операція (А v x)• (A v ẍ) = A називається повним склеюванням, а операція (А v x) • (A v ẍ) = A• (А v x)• (A v ẍ) – неповним склеюванням (для КНФ).

Наприклад, повне склеювання (x1 v x2 v x3)• (x1 v x2 v ẍ3) = x1 v x2 ; неповне склеювання x1x2x3 v x1x2ẍ3 = x1x2 v x1x2x3 v x1x2ẍ3 .

Мінімізація булевих функцій за допомогою дужкових форм

Якщо розглядати схемну реалізацію булевих функцій, представлених у вигляді ДНФ або КНФ, то, без урахування інверсій, вони представляють собою дворівневі схеми І-АБО (АБО-І). Але в реальній схемотехніці подібні схеми зустрічаються досить рідко. Зазвичай загальні частини різних імплікант на основі дистрибутивного закону "виносяться за дужки", в результаті чого виходить багаторівнева схема, аналітичний запис якої прийнято називати дужковою формою (ДФ). Іноді в літературі операція "винесення за дужки" називається факторизацією або виділенням загальних частин. В даному підрозділі описується структура і отримання дужкових форм булевих функцій на основі ДНФ, але абсолютно аналогічні викладки застосовні і до КНФ. Наприклад, для функції чотирьох змінних f (11, 13, 14, 15) = 1, ДНФ має вигляд f = x1x2x3 v x1x2x4 v x1x3x4. Якщо в перших двох імплікантах винести за скобки x1x2, то отримаємо дужкову форму f = x1x2 (x3 v x4) v x1x3x4, котра містить на дві букви (два входи) менше, ніж вихідна ДНФ. Даній дужковій формі відповідає трирівнева схема. Для безпосереднього запису ДФ булевої функції зазвичай використовують першу формулу розкладання:

f (x1, x2, ...xi,... xn) = ẍi • f (x1, x2, ...0, ... xn) v xi • f (x1, x2, ...1,... xn);

Для наочності часто використовують графічну форму представлення розкладання по змінній xi. При цьому кожне розкладання по змінної xi є вузол граф-схеми, всередині якого записується змінна, по якій проводиться розкладання. Нижнє ліве ребро (позначається "0") відповідає функції f^(ẍi), а нижнє праве ребро (позначається "1") - функції f^(xi). Вихід вузла (верхнє ребро) відповідає результуючої функції f(xi). При цьому якщо f є деякий булевий вираз, то його доцільно укладати в дужки. Звідси і випливає результуюче вираз у вигляді ДФ. Мінлива xi називається суттєвою для функції f, якщо f^(ẍi) ≠ f^(xi). В іншому випадку змінна вважається фіктивною. Нижче показана графічна інтерпретація розкладання функції f по змінній xi і запис результуючого виразу. Нижні ребра вузла (вершини) графу (на малюнку помічені 0 і 1), зазвичай називаються вхідними, а верхнє ребро - вихідним.

$f(x_{i})={{\overline {X}}_{i}}*(f^{{\overline {X}}_{i}})vx_{i}*(f^{X_{i}})$

Наприклад, якщо f^(ẍi) = x1x2, а f^(xi) = x1vx2, то розкладання по x3 буде мати вигляд :

                            f (x3) = x1x2ẍ3 v x3(x1 v x2)

Правила отримання вихідних виразів у вузлі графу

Нижче в таблиці представлені правила отримання вихідних виразів в вузлі графу і приведені всілякі значення вихідних виразів f(xi) в вершині xi в залежності від значень виразів на вхідних ребрах.

1. Якщо на правому (прямому) і лівому (інверсному) ребрах перебувають однакові значення функцій або однакові булеві вирази, то змінна xi (по формулі розкладання) є несуттєвою і в вихідному виразі в даній вершині відсутня. 2. Якщо на одному з ребер стоїть 0, а на іншому булевий вираз f, то результуючий вираз являє збій кон'юнкцію вираження f і змінної xi з інверсією, якщо f знаходиться на лівому 0-ребрі, або без інверсії, якщо f знаходиться на правому 1 - ребрі (рядки 6,7 в таблиці справа). 3. Якщо на одному з ребер стоїть 1, а на іншому булевий вираз f, то результуючий вираз являє збій диз'юнкцію вираження f і змінної xi з інверсією, якщо f знаходиться на правому 1-ребрі, або без інверсії, якщо f знаходиться на лівому 0 -ребрі (рядки 8,9 в таблиці справа).

f^(ẍi) f^(xi) f(xi) 0 1 0 1 0 1 1 0 0 1 xi ẍi f f 0 f 1 f 0 f 1 f f ẍi ˑ f xi ˑ f xi v f ẍi v f

Алгоритм побудови графів

Граф-схема отримання дужкової форми для перемикаючої функції n змінних складається з n ярусів. Яруси нумеруються знизу вгору числами від 1 до n, при цьому кожен ярус (ряд) відповідає змінній xi, i = 1,n. У кожному ряду міститься 2^(n-1) вершин. Число можливих шляхів від входів першого ряду до вершини граф-схеми дорівнює числу вхідних наборів даної функції (2^n). Граф-схема для функції f називається регулярною, якщо всередині кожного ряду всі вузли мають однакові номери змінних. В іншому випадку граф-схема називається нерегулярною.

Граф 1

На малюнку ліворуч( Граф 1) показана графічна інтерпретація отримання дужкової форми булевої функції трьох змінних f (1,3,5,6,7) = 1. Змінні в ярусах графу розташовуються в природному порядку (x1, x2, x3) від старших розрядів до молодших. У нижній частині малюнка в рамці показана таблиця істинності цієї функції (виділено червоним), а нижче наведені відповідні номери наборів в десятковому еквіваленті. Двійковий еквівалент шляху (складений з 0 і 1, що позначають вхідні ребра вузлів графу) від вершини верхнього ярусу графу до відповідного значення функції (блакитне поле) вказує номер відповідного двійкового набору (порядок проходження розрядів - x1, x2, x3). Наприклад, шлях 0 1 1 (через вершини x1, x2, x3) відповідає номеру набору 3, що підтверджується його десятковим еквівалентом.

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

На малюнку праворуч (Граф 2) показана графічна інтерпретація перестановки вершин в ярусах графу для даної функції f (1,3,5,6,7) = 1. На даному малюнку переставлені змінні в першому і другому ярусах графу (тепер порядок проходження розрядів в довічним еквіваленті x2, x1, x3). Але, незважаючи на перестановку, вагова значимість розрядів в двійковому еквіваленті не змінюється, тобто x2 відповідає вазі $2^{1},x1-2^{2},x3-2^{0}$ Таким чином, двійковий еквівалент шляху 0 1 1 (через вершини x2, x1, x3) відповідає набору з десятковим еквівалентом 5. Виходячи з цього можна сформулювати правило перестановки значення функції в таблиці істинності: для кожної вершини верхнього з переставляємих ярусів міняються місцями між собою значення функцій в підграфах на "внутрішніх" ребрах вершин нижнього з переставляємих ярусів. У розглянутому прикладі при перестановці ярусів 1 і 2 міняються місцями набори (2, 3) і (4, 5).

Граф 2

Граф 3

На першому кроці переставляються яруси 1 і 2, на другому кроці - 1 і 3, на третьому 2 і 3. В результаті для кожного варіанта перестановки виходять такі функції: $f1(x1,x2,x3)={\overline {x1}}x3vx1(x2vx3);$ $f2(x2,x1,x3)={\overline {x2}}x3vx2(x1vx3);$ $f3(x2,x3,x1)={\overline {x2}}x3vx2(x1vx3);$ $f4(x3,x2,x1)=x1x2vx3$ На малюнку ліворуч(Граф 3) можна побачити кінцевий вигляд графу для нашої функції.

У загальному випадку складність дужкової форми залежить від порядку проходження змінних в ярусах графу. Число всіляких перестановок ярусів графу (число різних варіантів ДФ) дорівнює n!. Виходячи їх цього отримати оптимальну (мінімальну складність) ДФ простим перебором варіантів перестановок змінних в ярусах графу для n > 6 (6! = 720) практично неможливо. Введемо кількісну оцінку оптимальності граф-схеми отримання ДФ, яку будемо називати (збіжністю) і позначимо S. j-я вершина i-го рангу називається збіжною, якщо $f^{{\overline {X}}_{i}}=f^{X_{i}}$. Відзначимо, що збіжні вершини по визначенню несуттєві

$S_{ij}={\begin{cases}1,&{\mbox{if }}f^{{\overline {X}}_{i}}=f^{X_{i}}\\0&{\mbox{в інших випадках }}\end{cases}}$

Збіжністю змінної xi (ярусу графу) називається сума збіжності всіх $m=2^{i-1}$ вершин i-го ярусу графу (рахуючи зверху).

$S_{i}=\sum _{j=1}^{2^{j-1}}S_{ij}$

Збіжністю граф-схеми називається сумма збіжностей усіх ярусів графу з урахуванням вагомо значимості (номера) кожного з ярусів графу ( i=1,n ).

$S=\sum _{j=1}^{m}S_{i}*2^{i-1}$

Певний інтерес представляє обчислення збіжності кожної змінної булевої функції за умови переміщення її в нижній ярус графу - ${S^{H}}_{i}$. Для цього її таблиця істинності може розглядатися як одномірний масив за умови природного (x1, x2, ... xn) розташування змінних в ярусах графу (виділено червоним на малюнку "Граф 1"). Для обчислення збіжності змінної $x_{i}$ в цих умовах порівнюються між собою значення функції в осередках масиву, віддалених один від одного на відстані $2^{n-i}$ осередків, причому кожна клітинка в порівнянні бере участь тільки один раз. Для функції трьох змінних:

  при обчисленні ${S^{H}}_{3}$ порівнюються осередки 0 и 1,   2 и 3,   4 и 5,   6 и 7; 
  при обчисленні ${S^{H}}_{2}$ порівнюються осередки 0 и 2,   1 и 3,   4 и 6,   5 и 7; 
  при обчисленні ${S^{H}}_{1}$ порівнюються осередки 0 и 4,   1 и 5,   2 и 5,   3 и 7.

Для наведених вище варіантів перестановок ярусів графу розглянутої функції f (1,3,5,6,7) = 1 збіжності S мають таке значення:

$f1(x1,x2,x3)={\overline {x1}}x3vx1(x2vx3);$ $f2(x2,x1,x3)={\overline {x2}}x3vx2(x1vx3);$ $f3(x2,x3,x1)={\overline {x2}}x3vx2(x1vx3);$ $f4(x3,x2,x1)=x1x2vx3;$

$S=2^{0}*1+2^{1}*1+2^{2}*0=3;$ $S=2^{0}*1+2^{1}*1+2^{2}*0=3;$ $S=2^{0}*3+2^{1}*0+2^{2}*0=3;$ $S=2^{0}*3+2^{1}*1+2^{2}*0=5;$

З наведених обчислень очевидно, що граф-схема з максимальною збіжністю дає мінімальну дужкову форму.

Так як завдання мінімізації булевих функцій відноситься до числа NP-повних задач, то отримання мінімальної ДФ (точне рішення цієї задачі) можливо тільки в результаті повного перебору n! варіантів розташування змінних в ярусах графів. Тому на практиці використовують різні евристичні процедури отримання ДФ. При використанні критерію збіжності можна з достатнім ступенем точності отримати оптимальну дужкову форму, але обчислити S для всієї граф схеми цілком можна тільки виконавши обчислення ДФ в (n-1) ярусах графу. Практично для n > 10 реалізувати такий підхід досить важко. Однією з евристичних процедур отримання ДФ може бути наступна:

1. Підраховуються збіжності ${S^{H}}_{i}$ для кожної змінної за умови переміщення її в нижній ярус графу.
2. У нижній ярус поміщається змінна $x_{i}$ з максимальною збіжністю.
3. Підраховують збіжності для решти змінних, за умови, що частина змінних вже розміщена. До наступного ярус поміщається змінна з максимальною збіжністю.
4. Пункти 2, 3 повторюються до тих пір, поки всі змінні не будуть розміщені в відповідних ярусах графу.
5. Записується ДФ булевої функції з застосуванням правил отримання вихідних виразів в вузлах графу.

Для даної функції f (1,3,5,6,7) = 1 ${S^{H}}_{1}=3,{S^{H}}_{2}=3,{S^{H}}_{3}=3;$ Таким чином в нижній ярус можна помістити x1 або x2.

Далі за умови x1 в нижньому ярусі $S_{2}=1,S_{3}=0;$

За умови x2 в нижньому ярусі $S_{1}=1,S_{3}=0;$

Отже, оптимальний порядок положення змінних в ярусах графу (від низу до верху) може бути (x2, x1, x3) або (x1, x2, x3). Нижче представлені граф-схеми, що відповідають даному порядку розташування змінних в ярусах графу.

В реальності використовують більш просту процедуру отримання ДФ з більшим ступенем евристики.

1. Підраховуються збіжності ${S^{H}}_{i}$ для кожної змінної за умови переміщення її в нижній ярус графу. ${S^{H}}_{1}=3;{S^{H}}_{2}=3;{S^{H}}_{3}=1.$
2. Змінні в ярусах графу (від низу до верху) розташовуються в порядку убування збіжностей $S^{H}$

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

Список використаної літератури

• Автоматизовані системі управління та прилади автоматики. Випуск 59. Харків. 1981. 73-77с.