Смекни!
smekni.com

Аналіз теорії цифрових автоматів (стр. 4 из 7)

f1 (x1,x2) =x1*x2 - кон’юнкція. Замість знака “*” інколи використовують знак & або

. Цю ф-цію часто називають логічним перетворенням або логічним множенням;

f3 (x1,x2) =x1 - повторення х1;

f5 (x1,x2) =x2 - повторення х2;

f6 (x1,x2) =x1

х2 -додавання по модулю, або сума mod 2;

f7 (x1,x2) =x1

x2-диз’юнкція (логічне або);

f8 (x1,x2) =x1
х2 - функція Вебба (стрілка Пірса);

f9 (x1,x2) =x12 - еквівалентність;

f13 (x1,x2) =x1

х2 - імплікація;

f14 (x1,x2) =x1/x2 - штрих Шеффера;

f15 (x1,x2) =1 - тотожна одиниця (константа 1);

Розглянуті простіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогою узагальненої операції, що називається операцією суперпозиції. Фактично операція суперпозиції заключається в тому, що існує підстановка замість аргументів інших булевих функцій (в деякій мірі аргументів).

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

Суперпозиція булевих ф-цій представляється у виді логічних формул. Однак слід відмітити:

одна і та ж функція може бути представлена різними формулами;

кожній формулі відповідає своя суперпозиція і своя своя схема з’єднання елементів;

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

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

Для булевої алгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операції кон’юнкції і диз’юнкції (позначаються відповідно “*", “

”).

В цій алгебрі справедливі три аксіоми:

закон комутативності - x

y=y
x, x*y=y*x;
закон асоціативності - (x
y)
z=x
(y
z), (x*y) *z=x* (y*z);

закон дистрибутивності - x* (y

z) = x*y
x*z, x
y*z= (x
y) * (x
z);

Перетворення формул булевих функцій використанням тільки аксіом булевої алгебри малоефективне. Для спрощення формул використовують цілий ряд співвідношень. Приведемо деякі з них.

=
*
,
*
=
(Теореми де Моргана) (1)

x

x*y=x, x* (x
y) =x; (2)

x

x=x, x*x=x,
=x; (3)

x

y =x
y; (4)

x

=1, x*
=0; (5)

x

1=1; x*0=0; (6)

xy

x
=x, (x
y) (x
) =x; (7)

В ряді випадків, перетворення над формулами булевих функцій зручно виконувати в алгебрі Жегалкіна. Алгебра Жегалкіна включає дві двохмісні операції: кон’юнкцію і додавання за модулем 2 (*,

), а також константу 1. Тут мають місце ті ж закони:

x

y=y
x, x*y=y*x

x

(y
z) = (x
y)
z, x* (y*z) = (x*y) *z

x* (y

z) =x*y
x*z

Для спрощення формул можуть бути використані такі співвідношення:

x

0=x; x*1=x; x*0=0; x
x=0; x*x=x.

Із комутативності і асоціативності слідує, що диз’юнкція кількох змінних може виконуватися послідовно, причому порядок взяття дизьюнкції не впливає на результат. Тобто, диз’юнкція сукупності змінних може бути виражена співвідношенням

x1

x2
xn=

xi

Аналогічно для кон’юнкції


x1*x2**xn=

xi

і суми по модулю 2

x1

x2
xn=

Теореми де Моргана для кількох змінних мають вигляд:

=

=

Аналітичне представлення булевих функцій

Вище згадувалося про існування аналітичних форм представлення булевих ф-цій. Тут розглянемо універсальні (канонічні) форми представлення, які дають можливість отримати аналітичну форму безпосередньо по таблиці істиності для довільної булевої ф-ції. Ця форма в дальшому може бути спрощена. Найбільш широке поширення отримала досконала нормальна форма (ДНФ). Перед тим як перейти до вивчення, приведемо визначення конституєнти одиниці - поняття, яким будемо широко користуватися дальше.

Визначення: Конституєнтою одиниці називається функція f (x1, x2, …, xn), яка приймає значення 1 тільки на одному наборі.

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