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

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

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

Наприклад, для булевої функції трьох змінних, 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), зазвичай називаються вхідними, а верхнє ребро - вихідним.
<center>
{|
|-
| <gallery>
SmallGraph.jpg
</gallery>|| <math>f(x_i) = {\overline {X}_i} * (f^{\overline {X}_i}) v x_i * (f^{X_i}) </math>
|}
</center>
Наприклад, якщо   f^(ẍi) = x1x2, а f^(xi) = x1vx2, то розкладання по x3 буде мати вигляд : 

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

=== Правила отримання вихідних виразів у вузлі графу ===
Нижче в таблиці представлені правила отримання вихідних виразів в вузлі графу і приведені всілякі значення вихідних виразів f(xi) в вершині xi в залежності від значень виразів на вхідних ребрах.
{| class="wikitable"  
|- 
|width="87%" | 1. Якщо на правому (прямому) і лівому (інверсному) ребрах перебувають однакові значення функцій або однакові булеві вирази, то змінна xi (по формулі розкладання) є несуттєвою і в вихідному виразі в даній вершині відсутня.

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

3. Якщо на одному з ребер стоїть 1, а на іншому булевий вираз f, то результуючий вираз являє збій диз'юнкцію вираження f  і змінної xi з інверсією, якщо f знаходиться на правому 1-ребрі, або без інверсії, якщо f знаходиться на лівому 0 -ребрі (рядки 8,9 в таблиці справа).
 || 
{| class="wikitable" style="text-align:center"
|-
! 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 називається регулярною, якщо всередині кожного ряду всі вузли мають однакові номери змінних. В іншому випадку граф-схема називається нерегулярною.

{|
|-
| style="text-align:center" |
<gallery>
StartGraph.jpg|Граф 1
</gallery>
 || На малюнку ліворуч( Граф 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 відповідає вазі <math>2^1, x1 - 2^2, x3 - 2^0</math> Таким чином, двійковий еквівалент шляху 0 1 1 (через вершини x2, x1, x3) відповідає набору з десятковим еквівалентом 5. Виходячи з цього можна сформулювати правило перестановки значення функції в таблиці істинності: для кожної вершини верхнього з переставляємих ярусів міняються місцями між собою значення функцій в підграфах на "внутрішніх" ребрах вершин нижнього з переставляємих ярусів. У розглянутому прикладі при перестановці ярусів 1 і 2 міняються місцями набори (2, 3) і (4, 5). || style="text-align:center" | <gallery>
FirstStepGraph.jpg||Граф 2
</gallery>
|}

{|
|-
| style="text-align:center" |
<gallery>
FinishGraph.jpg||Граф 3
</gallery>
||
На першому кроці переставляються яруси 1 і 2, на другому кроці - 1 і 3, на третьому 2 і 3. В результаті для кожного варіанта перестановки виходять такі функції:

{|
|-
| <math>f1(x1, x2, x3) = \overline {x1}x3 v x1 (x2 v x3); </math>
|-
| <math>f2(x2, x1, x3) = \overline {x2}x3 v x2 (x1 v x3); </math>
|-
| <math>f3(x2, x3, x1) = \overline {x2}x3 v x2 (x1 v x3); </math>
|-
| <math>f4(x3, x2, x1) = x1x2 v x3 </math>
|}
На малюнку ліворуч(Граф 3) можна побачити кінцевий вигляд графу для нашої функції.
|}
У загальному випадку складність дужкової форми залежить від порядку проходження змінних в ярусах графу. Число всіляких перестановок ярусів графу (число різних варіантів ДФ) дорівнює n!. Виходячи їх цього отримати оптимальну (мінімальну складність) ДФ простим перебором варіантів перестановок змінних в ярусах графу для n > 6 (6! = 720) практично неможливо.
Введемо кількісну оцінку оптимальності граф-схеми отримання ДФ, яку будемо називати ([[Збіжність|збіжністю]]) і позначимо S. j-я вершина i-го рангу називається збіжною, якщо <math>f^{\overline {X}_i} = f^{X_i} </math>. Відзначимо, що збіжні вершини по визначенню несуттєві
<center>
 <math>
S_{ij} = \begin{cases}
  1,  & \mbox{if } f^{\overline {X}_i} = f^{X_i} \\
  0 & \mbox{в інших випадках } 
\end{cases}
</math>
</center>

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

<center>
 <math>
S_i = \sum_{j=1}^{2^{j-1}} S_{ij}

</math>
</center>

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

<center>
 <math>
S = \sum_{j=1}^m S_i * 2^{i-1}

</math>
</center>
Певний інтерес представляє обчислення збіжності кожної змінної булевої функції за умови переміщення  її в нижній ярус графу - <math>{S^H}_i</math>. Для цього її таблиця істинності може розглядатися як одномірний масив за умови природного (x1, x2, ... xn) розташування змінних в ярусах графу (виділено червоним на малюнку "Граф 1"). Для обчислення збіжності змінної <math>x_i</math> в цих умовах порівнюються між собою значення функції в осередках масиву, віддалених один від одного на відстані <math>2^{n-i}</math> осередків, причому кожна клітинка в порівнянні бере участь тільки один раз. Для функції трьох змінних:
   при обчисленні <math>{S^H}_3</math> порівнюються осередки 0 и 1,   2 и 3,   4 и 5,   6 и 7; 
   при обчисленні <math>{S^H}_2</math> порівнюються осередки 0 и 2,   1 и 3,   4 и 6,   5 и 7; 
   при обчисленні <math>{S^H}_1</math> порівнюються осередки 0 и 4,   1 и 5,   2 и 5,   3 и 7.
Для наведених вище варіантів перестановок ярусів графу розглянутої функції f (1,3,5,6,7) = 1 збіжності S мають таке значення:

{|
|-
| 
{|
|-
| <math>f1(x1, x2, x3) = \overline {x1}x3 v x1 (x2 v x3); </math>
|-
| <math>f2(x2, x1, x3) = \overline {x2}x3 v x2 (x1 v x3); </math>
|-
| <math>f3(x2, x3, x1) = \overline {x2}x3 v x2 (x1 v x3); </math>
|-
| <math>f4(x3, x2, x1) = x1x2 v x3;  </math>
|}
|| 
{|
|-
| <math> S = 2^0 * 1 + 2^1 * 1 + 2^2 * 0 = 3;</math>
|-
| <math> S = 2^0 * 1 + 2^1 * 1 + 2^2 * 0 = 3;</math>
|-
| <math> S = 2^0 * 3 + 2^1 * 0 + 2^2 * 0 = 3;</math>
|-
| <math> S = 2^0 * 3 + 2^1 * 1 + 2^2 * 0 = 5;</math>
|}
|}
З наведених обчислень очевидно, що граф-схема з максимальною збіжністю дає мінімальну дужкову форму.

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

# Підраховуються збіжності <math>{S^H}_i</math> для кожної змінної за умови переміщення її в нижній ярус графу.
# У нижній ярус поміщається змінна <math>x_i</math> з максимальною збіжністю.
# Підраховують збіжності для решти змінних, за умови, що частина змінних вже розміщена. До наступного ярус поміщається змінна з максимальною збіжністю.
# Пункти 2, 3 повторюються до тих пір, поки всі змінні не будуть розміщені в відповідних ярусах графу.
# Записується ДФ булевої функції з застосуванням правил отримання вихідних виразів в вузлах графу.
Для даної функції  f (1,3,5,6,7) = 1  <math>{S^H}_1 = 3, {S^H}_2 = 3, {S^H}_3 = 3; </math> Таким чином в нижній ярус можна помістити x1 або x2.

Далі за умови x1 в нижньому ярусі <math>S_2 = 1, S_3 = 0;</math>

За умови x2 в нижньому ярусі <math>S_1 = 1, S_3 = 0;</math>

Отже, оптимальний порядок положення змінних в ярусах графу (від низу до верху) може бути (x2, x1, x3) або (x1, x2, x3). Нижче представлені граф-схеми, що відповідають даному порядку розташування змінних в ярусах графу.
<center>
{|
|-
| <gallery>
FinishGraph.jpg
</gallery>|| <gallery>
SecondStepGraph.jpg
</gallery>
|}
</center>

В реальності використовують більш просту процедуру отримання ДФ з більшим ступенем евристики.
# Підраховуються збіжності <math>{S^H}_i </math> для кожної змінної за умови переміщення її в нижній ярус графу. <math>{S^H}_1 = 3; {S^H}_2 = 3; {S^H}_3 = 1.</math>
# Змінні в ярусах графу (від низу до верху) розташовуються в порядку убування збіжностей <math> S^H </math>

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

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


{{Math-stub}}
{{Проблеми|refimprove=грудень 2017|стиль=грудень 2017|wikify=грудень 2017}}
{{ВП-портали|Математика|Програмування|Інформаційні технології}}

[[Категорія:Булева алгебра]]