Курсовая работа: Аналіз теорії цифрових автоматів

f₀ (x₁ ,x₂ ) =0 - тотожній нуль (константа 0);

f₁ (x₁ ,x₂ ) =x_1* x₂ - кон’юнкція. Замість знака “_* ” інколи використовують знак & або . Цю ф-цію часто називають логічним перетворенням або логічним множенням;

f₃ (x₁ ,x₂ ) =x₁ - повторення х₁ ;

f₅ (x₁ ,x₂ ) =x₂ - повторення х₂ ;

f₆ (x₁ ,x₂ ) =x₁ х₂ -додавання по модулю, або сума mod 2;

f₇ (x₁ ,x₂ ) =x₁ x₂ -диз’юнкція (логічне або);

56

f₈ (x₁ ,x₂ ) =x₁ ?₂ - ??????? ????? (??????? ϳ???);

f₉ (x₁ ,x₂ ) =x₁ ~х_{2 -} еквівалентність;

f₁₃ (x₁ ,x₂ ) =x₁ х₂ - імплікація;

f₁₄ (x₁ ,x₂ ) =x₁ /x₂ - штрих Шеффера;

f₁₅ (x₁ ,x₂ ) =1 - тотожна одиниця (константа 1);

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

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

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

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

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

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

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

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

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

закон комутативності - xy=yx, x_* y=y_* x;

57

????? ?????????????? - (xy) z=x (yz), (x_* y) _* z=x_* (y_* z);

закон дистрибутивності - x_* (yz) = x_* yx_* z, xy_* z= (xy) _* (xz);

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

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

xx_* y=x, x_* (xy) =x; (2)

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

xy =xy; (4)

x=1, x_* =0; (5)

x1=1; x_* 0=0; (6)

xyx =x, (xy) (x ) =x; (7)