ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.06.2025
Просмотров: 4499
Скачиваний: 2
ГЛАВА 3
ПЕРЕКЛЮЧАТЕЛЬНАЯ
АЛГЕБРА
Цифровая техника имеет то преимущество перед аналоговой техни кой, что она основывается на относительно простой, но при этом мощной теории, на Булевой алгебре, называемой также переключа тельной алгеброй. В данной главе представлены теоретические осно вы цифровой техники. Булева алгебра может быть применена для решения почти всех возникающих при разработке цифровых схем проблем при условии выполнения технологических предпосылок, ко торые рассматриваются в главе 4.
3.1.Переключательная переменная и переключательная функция
Вцифровой технике применяют специальные переменные и функ ции. Под Булевой переменной понимают переменную, которая мо жет принимать только значения О и 1. С Булевыми переменными могут быть образованы функции. Функцию:
у = f (ж1, Х2, жз,... Хп) при Xi, у е {0,1} (3.1)
называют п-разрядной переключательной или двоичной функцией. Область значений подобной функции также определяется двоичной системой счисления с элементами О и 1. Функции могут быть опреде лены таблицами, в которых величины функций связываются с воз можными 2'^ комбинациями п входных переменных. Эти таблицы называются таблицами истинности.
Очень простая функция, которая связывает входную перемен ную X с выходной переменной у, представлена в табл. 3.1. Можно видеть, что все переключательные функции могут быть определены таблицей, в которой содержатся все входные переменные, поскольку учитывать необходимо только два элемента О и 1.
Определенную табл. 3.1 переключательную функцию у = f{x) именуют «отрицание», «дополнение» или НЕТ (NOT). В последую щем она обозначается оператором «-•» и читается «у равен не х»:
у = ^х, |
(3.2) |
3.1. Переключательная переменная и переключательная функция |
35 |
Таблица 3.1. Таблица истинности инвертора:
X У
01
10
«Отрицание» является одноразрядной переключательной функ цией, поскольку она обладает только одним входным символом. Схем ный элемент «инвертор» обозначается с помощью схемного обозна чения, представленного на рис. 3.1:
X- |
1 b |
Рис. 3.1. Схемное обозначение инвертора.
Имеются ли еще одноразрядные переключательные функции? Пу тем систематических проб находим их общим числом 4, все они све дены в табл. 3.2. Других видов одноразрядной переключательной функции у не существует. Переключательные функции ^ = О и у = 1 вырабатывают постоянные, которые не зависят от входа. Поэтому существенной ^\ля переключательной алгебры является только од норазрядная двоичная функция у = ~iX,
Таблица 3.2. Одноразрядные двоичные функции.
Таблица истинности Функции Схемное обозначение Наименование
X |
У |
||
0 |
0 |
у = о |
|
1 |
0 |
||
X |
У |
||
0 |
0 |
у = х |
|
1 |
1 |
||
X |
У |
НЕТ, |
|
0 |
1 |
у = ^х |
«дополнение», |
«отрицание», |
|||
1 |
0 |
«инверсия» |
|
X |
У |
||
0 |
1 |
у = 1 |
1 1
Глава 3. Переключательная алгебра
3.2.Двухразрядные переключательные функции.
впринципе можно образовывать произвольные двоичные функции многих входных переменных. Но оказалось практичным вначале рас сматривать только функции с одной или двумя входными перемен ными, а функции с большим количеством входных переменных сво дить к ним.
Двоичную функцию с входными переменными жо и a^i также можно определить с помощью таблицы. Комбинацию входных пе ременных хо и Ж1МОЖНО представить в виде вектора X = [a:o,:ri]. Двум входным переменным соответствуют 4 возможных входных вектора X, которые часто индицируются через их десятичные экви валенты. Так Х2 означает, что a^i = 1 и жо = О, или, выражаясь по-другому, что Х2 = [x^.xi] = [0,1].
Наряду с «отрицанием» технически возможными являются основ ные логические элементы И или ИЛИ, которые определяются табл. 3.3. Также обозначают И как AND или «конъюнкция»; ИЛИ как OR или «дизъюнкция».
Таблица 3.3. Основные логические элементы И и ИЛИ.
Таблица истинности |
ф у н к ц и и |
Схемное |
обозначение |
Наименование |
|||||
XI |
хо |
У |
|||||||
0 |
0 |
0 |
Хо |
к — |
И, |
||||
0 |
1 |
0 |
у = Хо |
Axi |
у |
AND, |
|||
XI |
|||||||||
1 |
0 |
0 |
«конъюнкция» |
||||||
1 |
1 |
1 |
|||||||
XI |
Хо |
у |
или, |
||||||
0 |
0 |
0 |
Хо |
||||||
0 |
1 |
1 |
у = xoV |
xi |
>1 |
У |
OR, |
||
XI |
|||||||||
1 |
0 |
1 |
«дизъюнкция» |
||||||
1 |
1 |
0 |
|||||||
Возникает вопрос о других возможных двухразрядных двоич ных функциях. Чтобы системно ответить на этот вопрос, можно осуществить перестановку значений входных переменных у, кото рые можно получить из четырех возможных входных векторов. В об щем случае функция y{xi^xo) может быть определена таблицей ис тинности (табл. 3.4).
На основе этой таблицы можно сделать заключение о возмож ности образования 2^ = 16 различных двоичных функций с двумя
3.2. Двухразрядные |
переключательные |
функции. |
входными переменными. Все возможные двухразрядные двоичные функции приведены в табл. 3.6. Представление двоичных функций выполнено в соответствии со стандартом DIN [43].
Таблица 3.4. Таблица истинности для двухразрядной двоичной функции.
XI |
Хо |
У |
0 |
0 |
2/(0,0) |
0 |
1 |
2/(0,1) |
1 |
0 |
2/(1,0) |
1 |
1 |
2/(1,1) |
Технически важными функциями NAND, NOR, «эквивалентность» и EXOR (также «исключительное ИЛИ», дизъюнкция) соответству ют собственные логические символы. На практике они часто реали зуются на основе специальных схем.
В этой таблице показано, что отдельные функции могут быть представлены только с помощью логических элементов AND, OR и NOT. Поэтому каждая логическая функция может быть пред ставлена с помощью этих трех логических элементов. Все двоич ные функции также могут быть представлены с помощью функции NOR, точно также и с помощью NAND. Поэтому эти функции на зывают совершенными.
Доказательство эквивалентности можно привести путем разме щения таблиц истинности. Таким образом, например, может быть доказана эквивалентность }\ля логического элемента EXOR на осно
ве AND, OR или NOT: |
|
Х{) ^ xi = (-> жо л ^i) V (хо Л -1 xi) |
(3.3) |
в табл. 3.5 вначале оцениваются оба выражения в скобках. Затем формируется логическое OR, соответствующее обоим выражениям
вскобках, и вписывается в пустую колонку. Так как последняя и предпоследняя колонки совпадают, уравнение доказано, поскольку
впоследней колонке стоит определение функции «исключительное ИЛИ» (то есть EXOR).
Таблица 3.5. Доказательство на основе таблицы истинности.
XI |
Хо |
-1^0 л ici |
а^о л -"Xi |
(-"Жо л xi) V {хо Л -ixi) |
Хо о |
xi |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0^ |
1 |
|
Глава 3. Переключательная |
алгебра |
Таблица 3.6. Двухразрядные двоичные функции: таблица истинности, представление на основе (AND, NOT, OR), логический сим вол и название функции.
Таблица |
ф у н к ц и и |
Схемное |
истинности |
Наименование |
|
обозначение |
||
Хо 1 0 1 0 |
[ 11 1 |
| o J |
|||
XI |
[0 |
|||
у |
0 |
0 |
0 |
о] |
У |
0 |
0 |
0 |
1 |
У |
0 |
0 |
1 |
0 1 |
У |
0 |
0 |
1 |
1 j |
У |
0 |
1 |
0 |
0 j |
У^ 0 |
1 |
0 |
Т] |
|
У |
0 |
1 |
1 |
0 |
У |
0 |
1 |
1 |
1 |
У |
0 |
0 |
0 I |
|
У |
0 |
0 |
1 |
|
У |
0 |
1 |
0 ] |
|
У |
0 |
1 |
1 ] |
|
У |
1 |
0 |
A\ |
|
У1 0 T]
_У_\ |
1 |
1 _o] |
у |
j j |
l] 1] |
y = 0 |
||
у = ^(xo\/ |
xi) |
|
у = |
(xo^xi) |
|
у = xo |
A-^xi |
|
y = |
^xi |
|
у = ->xo |
Axi |
|
y = ->xo |
||
у = (-1^0 |
/\xi)\/ |
|
V(xoA Ф |
xi) |
|
у= {xo<^ xi)
у= ^{xo Axi) y=:{xoAXl)
у = xo |
Axi |
|
у = |
{xo |
Axi)\/ |
V(-ixo Л xi) |
||
у = |
(xo ^ |
xi) |
y = xo |
||
у= хоУ ->xi
у= ^1
у= xi W -ixo
у= хоУ xi
2/ = l
нуль |
||||
Xo |
> 1 0 |
у |
N O R |
|
Xi |
||||
запрет |
||||
дополнение |
||||
запрет |
||||
дополнение |
||||
Xo |
= 1 — |
у |
E X O R |
|
Xl |
||||
Xo |
к ^—у |
N A N D |
||
Xl |
||||
Xo |
к — у |
AND |
1 |
|
Xl |
||||
Xo |
= — |
у |
эквивалентность |
|
Xl |
||||
идентичность |
||||
импликация |
||||
идентичность |
||||
импликация |
||||
Xo |
>1 |
У |
O R |
|
Xl |
||||
единица
3.3. Вычислительные правила
Важными для упрощения сложных функций являются вычислитель ные правила булевой алгебры. Для доказательства отдельных зако нов могут быть использованы таблицы истинности.
3.3. Вычислительные правила
Вычислительные правила булевой алгебры перечислены ниже. Переместительный (коммутативный) закон:
хо Л Xi = Ж1 Л XQ |
(3.4) |
||
хоУ xi = хгУ хо |
(3.5) |
||
Сочетательный (ассоциативный) закон: |
|||
{хо Л xi) |
/\Х2 |
= XQ Л [xi л Х2) |
(3.6) |
(жо V xi) |
Ух2 |
= х^У {Х1 V Х2) |
(3.7) |
Распределительный закон (закон дистрибутивности): |
|||
жо л (xi V Х2) = (жо Л xi) V (а^о Л Х2) |
(3.8) |
||
Хо V (xi Л Х2) = (хо V xi) Л (хо V Х2) |
(3.9) |
||
Закон поглощения (закон абсорбции): |
|||
Хо Л (хо V xi) = Хо |
(3.10) |
||
Хо V (хо Л xi) = Хо |
(3-11) |
||
Существование нейтральных элементов: |
|||
хоЛ1 =-хо |
(3.12) |
||
Хо VO = xo |
(3.13) |
||
Существование дополнительных элементов: |
|||
хоЛ-.хо==0 |
(3.14) |
||
Хо V^xo = 1 |
(3.15) |
||
Теорема Де-Моргана: |
|||
Хо Л XI = ->(-> Хо V -п xi) |
(3.16) |
||
Хо V xi = -' (-1 Хо Л -I xi) |
(3.17) |
||
На основе симметрии законов можно сделать следующие выводы. Если справедлив один закон, то справедлив и закон, который по лучают путем взаимной замены AND и OR и постоянных О и 1. По лученный таким образом закон называют дуальным законом. Как, например, законы (3.16) и (3.17) дуальны по отношению друг к другу. Аналогично обозначают функцию F', которая получилась из