Курсовая работа: Аналіз теорії цифрових автоматів
x
y=yx, x*y=y*x
x (yz) = (xy) z, x* (y*z) = (x*y) *z
x* (yz) =x*yx*z
Для спрощення формул можуть бути використані такі співвідношення:
x0=x; x*1=x; x*0=0; xx=0; x*x=x.
Із комутативності і асоціативності слідує, що диз’юнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, диз’юнкція сукупності змінних може бути виражена співвідношенням
x1
x2 … xn =
xi
Аналогічно для кон’юнкції
x1* x2* …* xn =
xi
і суми по модулю 2
x1 x2 …xn =
Теореми де Моргана для кількох змінних мають вигляд:
= 
=
Аналітичне представлення булевих функцій
Вище згадувалося про існування аналітичних форм представлення булевих ф-цій. Тут розглянемо універсальні (канонічні) форми представлення, які дають можливість отримати аналітичну форму безпосередньо по таблиці істиності для довільної булевої ф-ції. Ця форма в дальшому може бути спрощена. Найбільш широке поширення отримала досконала нормальна форма (ДНФ). Перед тим як перейти до вивчення, приведемо визначення конституєнти одиниці - поняття, яким будемо широко користуватися дальше.
Визначення: Конституєнтою одиниці називається функція f (x1 , x2 , …, xn ), яка приймає значення 1 тільки на одному наборі.
Якщо згадати, що диз’юнкція рівна 1, коли хоча б одна з змінних приймає значення 1, то можна легко виразити, будь-яку булеву функцію як диз’юнкцію конституєнт одиниці, які відповідають тим наборам, на яких функція рівна 1. В більш загальному вигляді це можна записати таким чином:
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 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 К-во Просмотров: 367
Бесплатно скачать Курсовая работа: Аналіз теорії цифрових автоматів
|