Мінімізація логічних функцій за таблицями Дейча

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

Таблиці Дейча для трьох і чотирьох змінних мають такий вигляд:

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

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

Приклад 1. Знайти мінімальну ДНФ функції

.

Розв’язання

	у
х	1		1	1
	1	1		1

Будуємо таблицю Вейча, позначивши в ній конституенти одиниці даної функції

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

У результаті отримаємо, що мінімізована функція має вигляд:

Приклад 2. Знайти мінімальну КНФ функції

Розв’язання

Будуємо таблицю Дейча, позначивши в ній конституенти нуля даної функції.

	у
х			0	0
	0	0		0

У результаті об’єднання отримаємо, що мінімізована функція має вигляд: