Аналіз теорії цифрових автоматів
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
? зручно виконувати в алгебрі Жегалкіна. Алгебра Жегалкіна включає дві двохмісні операції: конюнкцію і додавання за модулем 2 (*,), а також константу 1. Тут мають місце ті ж закони:
xy=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.
Із комутативності і асоціативності слідує, що дизюнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, дизюнкція сукупності змінних може бути виражена співвідношенням
x1x2…xn=xi
Аналогічно для конюнкції
x1*x2*…*xn=xi
і суми по модулю 2
x1x2…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 x3f1f20 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
1
0
1
0
0
10
0
0
1
0
1
1
1
Ф-ція f1 нам відома як сума за модулем 2 трьох змінних х1х2х3. Ф-ція f2 називається мажорантною (вона приймає значення, яке приймає більшість змінних) і позначається знаком М (х1, х2, х3)
Друга відома форма носить назву “досконалої конюктивної нормальної форми" (ДКНФ). Вона будується аналогічно ДДНФ.
Визначення: Конституєнтою нуля називається функція, яка приймає значення 0 на єдиному наборі.
Конституєнта нуля записується у вигляді елементарної дизюнкції всіх змінних. Кожному набору відповідає своя конституєнта 0.
Приклад Для розглянутих вище ф-цій х1х2х3 і М (х1, х2, х3) (табл.7) побудуємо ДКНФ:
;
.
Легко побачити, що в ДДНФ можна замінити операцію дизюнкції операцією суми за модулем 2, причому рівність збережеться. Ця форма називається “досконалою поліноміальною нормальною формою” (ДПНФ). Для нашого прикладу
Якщо в ДПНФ замінити всі змінні з запереченням у відповідності з співвідношенням =1х, то отримається канонічний поліном Жегалкіна вигляду
f (x1, x2, …, xn)
=a0a1x1a2x2…anxna12x1x2a13x13…a12…nx1x2…xn,
де аi {0,1}.
Приклад: Для тих же функцій f1 і f2 знайдемо канонічний поліном Жегалкіна:
f1= (x11) (x21) x3 (x11) x2 (x31) x1 (x21) (x31) x1x2x3= x1x2x3x3x1x3x2x3x1x2x3x1x2x2x3x1x2x3x1x2x2x3x2x1x2x3x1x2x1x3x1x1x2x3=x1x2x3
Аналогічно для f2= x1x2x2x3x1x3.
В булевій алгебрі широко використовується розклад Шеннона- формула, яка дозволяє перейти від представлення функції від 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) x1f (1,0,x3,…,xn) x2f (0,1,x3,. .,xn) f (0,0,x3,…,xn)
Відмітимо, що якщо провести такий же розклад по всіх змінних, получиться ДДНФ.
Мінімізація булевих функцій
При проектуванні цифрових машин широко використовуються методи мінімізації булевих функцій, які дозволяють отримати рекомендації для побудови економічних схем цифрових машин. Загальна задача мінімізації булевих функцій формулюється так: знайти аналітичне вираження булевої функції в формі, що містить мінімально можливе число букв. Слід відмітити, що в загальній постановці дана задача поки що не розвязана, але достатньо добре досліджена в класі дизюнктивно-конюктивних нормаьних форм.
Визначення: Елементарною конюнкцією називається конюнкція кінцевого числа різних між собою булевих змінних, кожна з яких може мати, або не мати заперечення.
Визначення: Дизюнктивною нормальною формою (ДНФ) називається дизюнкція елементарних конюнкцій.
Визначення: Мінімальною дизюнктивною нормальною формою булевої функції називається ДНФ, що містить найменше число букв.
Визначення: Булева функція g (x1,x2,…,xn) називається імплікантою булевої функції f (x1,…,xn), якщо для будь-якого набору змінних, на якому g=1, справедливе f=1.
Визначення: Імпліканта g булевої ф-ції f, що є елементарною конюнкцією, називається простою, якщо ніяка частина ім