Аналіз теорії цифрових автоматів
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
я з допомогою n-мірного куба. В геометричному смислі кожний двійковий набір =<>, {0,1} є n-мірний вектор, визначаючий точку n-мірного прстору. Виходячи з цього, вся множина наборів, на яких визначена ф-ція n змінних, представляється вершинами n-мірного куба. Відмічаючи точками вершини куба, в яких функція приймає одиничне значення (або нульове), одержимо геометричне представлення функції. Наприклад, булева функція, задана табл.1, геометрично представляється 3-мірним кубом
При аналітичному способі булева функція задається формулами, тобто аналітичними виразами, побудованими на основі операцій булевої алгебри. Аналітичний спосіб задання булевих функцій займає особливе місце в проектуванні цифрових машин. Фактично, всі перетворення над булевими ф-ціями, необхідні для побудови цифрових машин, ведуться на аналітичному рівні.
Розглянемо області визначення булевоі ф-ції. Як уже відмічалось, між двійковими наборами і двійковими числами існує взаємнооднозначна відповідність. Отже, існує 2n різних наборів двійкових змінних.
Таким чином, областю визначення булевої ф-ції n змінних при матричному способі задання являється множина всіх можливих двійкових довжин n наборів, а при геометричному способі задання множина всіх вершин n-мірного одиничного куба.
Булеву ф-цію, визначену на всіх своїх наборах, називають повністю визначеною. Булеву ф-цію n змінних називають неповністю визначеною, або частинною, якщо вона визначена не на всіх двійкових наборах довжини n. Неповністю визначена булева ф-ція не попадає під визначення, дане на початку глави, але при довільному довизначенні (на всіх наборах, на яких вона не визначена) ця невідповідність знімається.
Існує не більше як 2n різних булевих функцій n змінних. До цього висновку легко прийти, користуючись простими комбінаторними міркуваннями, і згадавши, що на кожному із 2n наборів функції можуть приймати два значення.
Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 5, де
f0 (x) =0 - тотожній нуль (константа 0);
f1 (x) =x - тотожна ф-ція;
f2 (x) = - заперечення x (інверсія);
f3 (x) =1 - тотожна одиниця (константа 1).
Ф-ції двох змінних представлені в табл.6.
Найбільш часто використовуються такі:
f0 (x1,x2) =0 - тотожній нуль (константа 0);
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) =x1x2-дизюнкція (логічне або);
f8 (x1,x2) =x1х2 - функція Вебба (стрілка Пірса);
f9 (x1,x2) =x1~х2 - еквівалентність;
f13 (x1,x2) =x1х2 - імплікація;
f14 (x1,x2) =x1/x2 - штрих Шеффера;
f15 (x1,x2) =1 - тотожна одиниця (константа 1);
Розглянемо найбільш використовувані булеви ф-ції однієї і двох змінних. Ф-ції однієї змінної представлені таблиці 5, де
f0 (x) =0 - тотожній нуль (константа 0);
f1 (x) =x - тотожна ф-ція;
f2 (x) = - заперечення x (інверсія);
f3 (x) =1 - тотожна одиниця (константа 1).
Ф-ції двох змінних представлені в табл.6.
Найбільш часто використовуються такі:
f0 (x1,x2) =0 - тотожній нуль (константа 0);
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) =x1x2-дизюнкція (логічне або);
f8 (x1,x2) =x1х2 - функція Вебба (стрілка Пірса);
f9 (x1,x2) =x1~х2 - еквівалентність;
f13 (x1,x2) =x1х2 - імплікація;
f14 (x1,x2) =x1/x2 - штрих Шеффера;
f15 (x1,x2) =1 - тотожна одиниця (константа 1);
Розглянуті простіші булеві ф-ції дозволяють будувати нові булеви ф-ції з допомогою узагальненої операції, що називається операцією суперпозиції. Фактично операція суперпозиції заключається в тому, що існує підстановка замість аргументів інших булевих функцій (в деякій мірі аргументів).
Зауважимо, що суперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиція ф-цій двох аргументів дає можливість будувати функції будь-якої кількості аргументів.
Суперпозиція булевих ф-цій представляється у виді логічних формул. Однак слід відмітити:
одна і та ж функція може бути представлена різними формулами;
кожній формулі відповідає своя суперпозиція і своя своя схема зєднання елементів;
між формулами представлення булевих ф-цій і схемами, які їх реалізують, існує взаємнооднозначна відповідність.
Очевидно, що серед схем, які реалізують дану функцію є найбільш проста. Пошук логічної формули, що відповідає цій схемі, предствляє великий практичний інтерес, а перетворення формул булевих функцій грунтується на використанні співвідношень булевої алгебри.
Для булевої алгебри визначена одна одномісна (унарна) операція, дві двохмісні (бінарні) операції конюнкції і дизюнкції (позначаються відповідно “*", “”).
В цій алгебрі справедливі три аксіоми:
закон комутативності - xy=yx, x*y=y*x;
закон асоціативності - (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)
В ряді випадків, перетворення над формулами булевих функці?/p>