Минимизиране на непълно дефинирани функции

Много често, ако не в повечето случаи, работата на дадено устройство се описва с помощта на не напълно дефинирана функция, тъй като някои комбинации от входни сигнали не се доставят или са забранени.

Определение. Непълно дефинирана функция е функция за превключване, чиито стойности на някои набори от аргументи могат да бъдат произволни (т.е. равни на "0" или "1").

Определение. Нека функцията f (x1, x2. Xn) бъде недефинирана в „p“ набори от аргументи. Тогава напълно дефинирана функция ще се счита за еквивалентна на f (x1, x2. Xn), ако нейните стойности на онези кортежи, на които е дефиниран f (x1, x2. Xn), съвпадат.

Очевидно има 2 р различни функции, еквивалентни на f (x1, x2. Xn) .

Проблемът за минимизиране на f (x1, x2. Xn) се състои в избора на еквивалентен, който има най-простата форма.

Нека въведем две помощни еквивалентни функции, които поемат забранените набори от аргументи съответно стойностите 0 и 1.

ТЕОРЕМА. SDNF на непълно дефинираните f (x1, x2. Xn) съвпада с дизюнкцията на най-кратките импликанти, които обхващат съвместно всички съставни части на единството, и нито една от които не е излишна.

Нека f (x1, x2. Xn) бъде дадено под формата на следната таблица: