Смекни!
smekni.com

Аналіз теорії цифрових автоматів (стр. 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)

Відмітимо, що якщо провести такий же розклад по всіх змінних, получиться ДДНФ.

Мінімізація булевих функцій

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

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

Визначення: Диз’юнктивною нормальною формою (ДНФ) називається диз’юнкція елементарних кон’юнкцій.