Методи мінімізації

1. Метод безпосередніх перетворень.

2. Метод карт Карно.

1. Метод безпосередніх перетворень – це аналітичний метод спрощення логічних функцій з допомогою аксіом та законів булевої алгебри. Ефективний для кількості змінних не більшій трьох.

Приклад 1.

Y= X₃˅ X₂ ˅ X₂X₃˅ ˅X₁ = ( X₃˅X₂ ˅X₂X₃˅ )˅X₁X₂ =

= [ (X₃˅ )˅X₂(X₂˅ )]˅X₁X₂ = ( ˅X₂)˅X₁X₂ ˅ X₂ = ˅X₂ (X₁˅ )=

=X₁˅X₂ .

Приклад 2.

Y= X₃˅ X₂ ˅X₁ ˅X₁X₂X₃= ( X₃˅X₂ )˅X₁( ˅X₂X₃)= (X₂ X₃)˅ ˅X₁( )= X₁ (X₂ X₃)=X₁ X₂ X₃ – вийнятково АБО (базис).

2. Метод карт Карно

1. Заповнюють карту Карно.

Наприклад:

Х1Х2   Х3
					Х3
		Х2	Х1Х2	Х1

Закон склеювання Х1Х2˅Х1 =Х1

Тобто суть мінімізації полягає у тому, що шукають мінтерми у сусідніх клітинках, які «склеюються» за законом склеювання для диз’юнкції. У нашому випадку Х₂ при покритті приймає значення для покритих клітинок і 1 і 0 і тому цей аргумент (змінна) вилучається і зчитується як Х₁ . Об’єднують максимальне число клітинок, що містять «1» по 2, 4, 8 клітинки (2ⁿ). При цьому прагнуть, що кожна клітинка з «1» обов’язково входила в яке-небудь покриття.

Мінімізуємо за допомогою карти Карно функцію, що задана у прикладі 1.

Y= X₃˅ X₂ ˅ X₂X₃˅ ˅X₁X₂ .

Y= ˅Х₂ .

Що значно простіше.

Отже, мінімізація прямої логічної функції за допомогою карт Карно зводиться до послідовного виконання таких операцій:

1) Розміщення конституант 1 в клітинках, які відповідають мінтермам даної функції, що зображена в УДНФ;

2) Об’єднання сусідніх «1» контурами по 2, 4 або 8 клітинок;

3) Зчитування кон’юнкцій, що входять у даний контур, вилучаючи з них за законом склеювання ті змінні, які утворюють доповнення (Х_і˅ );

4) Об’єднання одержаних кон’юнкцій диз’юнкцією, яка є мінімізованою диз’юнктивною нормальною формою МДНФ заданої функції.

Приклад. Мінімізувати логічну функцію, задану таблицею істинності.

Зобразимо цю логічну функцію картою Карно і, дотримуючись правил мінімізації, отримаємо вираз мінімізованої диз’юнктивної форми (МДНФ):

рис.1.4___

Y=X₂ ˅X₃X₂˅X₃X₁X₀˅

Мінімізовану кон’юнктивну форму цієї функції одержують шляхом покриття «нулів» в карті Карно (рис.1.4)

Y=(X₃˅ )( ˅X₂˅X₀)(X₂˅X₁˅ ).

Для синтезу цифрових пристроїв вибирають ту мінімізовану форму, яка містить менше змінних.

Мінімізація частково визначених функцій

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

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

N	X2	X1	X0	Y1	Y2

x2x1 x0
			0
	1	1		Y1 1

МДНФ: Y₁=X₀

х2х1 х0
			1	Y2 1

МДНФ: Y=X₂˅X₁X₀.