Скорочена диз’юнктивна нормальна форма перемикальних функцій

Уведемо поняття накриття для перемикальних функцій.

Нехай в деякому наборі аргументів  = (₁, …, _n) функція f набуває значення a₁, а функція  в цьому самому наборі – значення a₂. Це означає, що функція f у заданому наборі своїм значенням a₁ накриває значення a₂.

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

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

Якщо деяка перемикальна функція  (в окремому випадку – елементарний добуток) дорівнює нулю в тих наборах, у яких дорівнює нулю інша функція f, то вважають, що функція  входить у функцію f, тобто функція  входить у функцію f тоді, коли вона накриває нулями всі нулі функції f, а одиниці функції можуть бути накриті як нулями, так і одиницями функції . Отже, функція  має не меншу кількість нулів, ніж функція f.

Умова входження записується як   f. Константа 0 входить у будь-яку перемикальну функцію, а в константу 1 входять усі функції.

Функцію , що входить у задану функцію f, називають її імплікантою.

Простими імплікантами перемикальної функції називають терми – елементарні добутки, що самі входять у задану функцію, але жодна власна частина їх у функцію f не входить.

Власною частиною імпліканти називають терм-добуток, здобутий вилученням із нього одного або кількох співмножників. Наприклад, добуток x z має власні частини x , z, xz, x, , z.

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

Наприклад, для функції

f(x, y, z) = yz + x + x z + x

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

Теорема. Будь-яка перемикальна функція дорівнює диз’юнкції всіх своїх простих імплікант.

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

Утворення скороченої диз’юнктивної нормальної форми методом Квайна

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

В операції неповного склеювання

xy + x = x(y + ) = x

два члени xy та x склеюються за змінною y.

Операція неповного склеювання записується так:

x + xy + x = xy + x .

В операції поглинання

x + xy = x(1 + y) = x

член xy поглинається членом x. Правильна така теорема.

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

За методом Квайна необхідно виконати такі дії:

1. провести в ДДНФ функції f(x₁, …, x_n) усі можливі операції неводного склеювання конституент одиниці, внаслідок чого утворяться добутки-мінтерми (n – 1 )-го рангу. Після цього виконати операцію поглинання;

2. провести можливі склеювання членів (n – 1)-го рангу, потім поглинання і дістати кон’юнкцію (n – 2)-го рангу;

3. виконати операції склеювання членів із числом літер (n – 2)-го рангу, одержати кон’юнкцію (n – 3)-го рангу і т.д.

Приклад. Розглянемо функцію

F(x₁, x₂, x₃, x₄) = x₃x₄ + x₂ + x₂ x₄ + x₂x₃x₄ + x₁ x₄ + x₁ x₃x₄ + x₁x₂ + x₁x₂ x₄.

Мінтермами четвертого рангу тут є

x₃x₄, x₂ , x₂ x₄, x₂x₃x₄, x₁ x₄, x₁ x₃x₄, x₁x₂ , x₁x₂ x₄.

Мінтермами третього рангу служать, наприклад

x₃x₄, x₂ , x₂ x₄, x₂x₄, x₁ x₄, x₃x₄, x₂ , x₁x₂ , x₁ x₄.

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

	x3x4	x2	x2 x4	x2x3x4	x1 x4	x1 x3x4	x1x2	x1x2 x4
x3x4	1			x2x3		x3x4
x2		1	x2				x2	x2
x2 x4		x2	1	x2x4				x2 x4
x2x3x4	x3x4		x2x4	1
x1 x4					1	x1 x4		x1 x4
x1 x3x4	x3x4				x1 x4	1
x1x2		x2					1	x1x2
x1x2 x4		x2	x2 x4		x1 x4		x1x2	1
x3x4				
x2x4				
x1 x4						
x3x4						
x1 x4								
x2								

Оскільки подальше склеювання неможливе, етап визначення імплікант закінчено. Простими імплікантами є такі мінтерми: x₃x₄, x₂x₄, x₁ x₄, x₃x₄, x₁ x₄, x₂ .

Розставлення міток. На етапі розставлення міток складають таблицю, кількість рядів якої дорівнює кількості знайдених первинних імплікант функції, що мінімізується. Кількість стовпців збігається з кількістю мінтермів ДДНФ. Якщо в деякий мінтерм ДДНФ входить яка-небудь з первинних імплікант, то на перетині відповідного стовпця і рядка ставлять мітку.

Визначення суттєвих імплікант. Якщо в одному із стовпців складеної таблиці існує тільки одна мітка, то первинна імпліканта, що є у відповідному рядку, називається суттєвою. Вона не може бути вилучена з правої частини початкового рівняння, оскільки без неї не буде покриття всієї множини мінтермів заданої функції. Тому з таблиці міток виключають рядки, які відповідають суттєвим імплікантам, і стовпці мінтермів, що покриваються ними. Для функції, що розглядається, суттєвою імплікантою є x₂ . Вона покриває мінтерми x₂ , x₂ x₄, x₁x₂ , x₁x₂ x₄.

При переході до наступного етапу ці мінтерми можуть бути викреслені.

Закреслювання зайвих стовпців. Якщо в одержаній після попереднього етапу таблиці

	x3x4	x2 x3x4	x1 x4	x1 x3x4
x3x4		
x3x4				
x2x4		
x1 x4				
x1 x4			

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

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

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

Для функції, що розглядається, вибирають покриття з імплікант x₃x₄ та x₁ x₄, оскільки вони спільно покривають усі ті мінтерми, які залишилися після закреслювання зайвих стовпців. Мінімальна ДНФ для цієї функції має такий вигляд:

f(x₁, x₂, x₃) = x₃x₄ + x₁ x₄ + x₂ .