Аналіз теорії цифрових автоматів (стр. 5 из 7)
f (x1, x2, …, xn) =
f (σ1, σ2, …, σn) * x1σ1, x2σ2, …, xnσn,де σi = 0,1 і
xi σi =
Ця форма і є досконала диз’юнктивна форма (ДДНФ). Замітимо, що набори, де функція f приймає значення 1, часто називають одиничними, всі решта - нульовими наборами. Виписувати в ДДНФ є зміст тільки конституєнти одиниці, відповідні одиничним наборам.
Приклад: Випишемо ДДНФ для ф-цій, заданих таблицею істиності (табл.1).
Таблиця 1
| x1 x2 x3 | f1 | f2 |
| 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 | 01101001 | 00010111 |
Ф-ція f1 нам відома як сума за модулем 2 трьох змінних х1
х2 х3. Ф-ція f2 називається мажорантною (вона приймає значення, яке приймає більшість змінних) і позначається знаком М (х1, х2, х3) Друга відома форма носить назву “досконалої кон’юктивної нормальної форми" (ДКНФ). Вона будується аналогічно ДДНФ.
Визначення: Конституєнтою нуля називається функція, яка приймає значення 0 на єдиному наборі.
Конституєнта нуля записується у вигляді елементарної диз’юнкції всіх змінних. Кожному набору відповідає своя конституєнта 0.
Приклад Для розглянутих вище ф-цій х1
х2 х3 і М (х1, х2, х3) (табл.7) побудуємо ДКНФ: 
; 
.Легко побачити, що в ДДНФ можна замінити операцію диз’юнкції операцією суми за модулем 2, причому рівність збережеться. Ця форма називається “досконалою поліноміальною нормальною формою” (ДПНФ). Для нашого прикладу
Якщо в ДПНФ замінити всі змінні з запереченням у відповідності з співвідношенням
=1х, то отримається канонічний поліном Жегалкіна виглядуf (x1, x2, …, xn)
=a0
a1x1 a2x2 … anxn a12x1x2 a13x13 … a12…nx1x2…xn,де аi
{0,1}.Приклад: Для тих же функцій f1 і f2 знайдемо канонічний поліном Жегалкіна:
f1= (x1
1) (x2 1) x3 (x1 1) x2 (x3 1) x1 (x2 1) (x3 1) x1x2x3= x1x2x3 x3 x1x3 x2x3 x1x2x3 x1x2 x2x3 x1x2x3 x1x2 x2x3 x2 x1x2x3 x1x2 x1x3 x1 x1x2x3=x1 x2 x3Аналогічно для f2= x1x2
x2x3 x1x3.В булевій алгебрі широко використовується розклад Шеннона- формула, яка дозволяє перейти від представлення функції від n-змінних до представлення функції від (n-1) - змінних:
f (x1, x2, …, xn) =x1f (1, x2, …, xn)
f (0, x2, …, xn)Співвідношення легко узагальнюється для будь-якої кількості змінних, якщо функції правої частини піддати такому ж розкладу по інших змінних. Наприклад:
f (x1, x2, …, xn) =x1 [x2f (1,1, x3, …, xn)
f (1,0, x3, …, xn)] [x2f (0,1, x3…xn) f (0,0,x3,…xn)] =x1,x2f (1,1,x3,…xn) x1 f (1,0,x3,…,xn) x2f (0,1,x3,. .,xn) 
f (0,0,x3,…,xn)Відмітимо, що якщо провести такий же розклад по всіх змінних, получиться ДДНФ.
Мінімізація булевих функцій
При проектуванні цифрових машин широко використовуються методи мінімізації булевих функцій, які дозволяють отримати рекомендації для побудови економічних схем цифрових машин. Загальна задача мінімізації булевих функцій формулюється так: знайти аналітичне вираження булевої функції в формі, що містить мінімально можливе число букв. Слід відмітити, що в загальній постановці дана задача поки що не розв’язана, але достатньо добре досліджена в класі диз’юнктивно-кон’юктивних нормаьних форм.
Визначення: Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій.