18 Лекция. Элементы алгебры логики. Основные типы логических элементов интегральных микросхем. Параметры логических элементов
18.1 Элементы алгебры логики
Устройства автоматики с цифровыми узлами используют импульсные сигналы с двумя фиксированными уровнями напряжения: уровень “низкого” напряжения “Low”, и уровень “высокого” напряжения “High”.
Математическим аппаратом для анализа и синтеза таких устройств служит “алгебра логики”. “0” и “1”– это состояния переменных, функций, - но не числа. Алгебра логики – это алгебра состояний, но не чисел; ее основные действия отличны от алгебры чисел.
Так как в алгебре логики переменные могут быть только “0” или “1”, то каждой переменной ставится в соответствие обратная (инверсная): если x = 0, то `х = 1; если х = 1, то `х = 0. Переменная `х читается НЕ х.
В алгебре логики действуют правила (аксиомы) (без выводов,которые даются в дисциплине «мат. логика и теория алгоритмов»).
1 Логическое сложение (дизъюнкция):
х + (или) 0 = х; х + 1 = 1; х + х = х; х +`х = 1.
2 Логическое умножение (конъюнкция):
х × (и) 0 = 0; х × 1 = х; х × х = х; х ×`х = 0.
3 Инверсия:
;
.
Законы алгебры логики.
1 Переместительный (коммутативный):
х + y = y + x; x × y = y × x.
2 Сочетательный (ассоциативности):
x + y + z = (x + y) + z = x + (y + z);
x × y × z = (x × y) × z = x × (y × z).
3 Распределительный (дистрибутивности):
x × (y + z) = x × y + x × z.
Тождества.
1 x × y + x ×`y = x;
2 x + x × y = x;
3 x × (x + y) = x;
4 x × (`x + y) = xy;
5 (x + y) × (x + z) = x + y × z;
6 x×`y + y = x + y.
Законы инверсии для логического сложения и умножения (теоремы де Моргана):
1)
;
2)
.
Логические функции: они записываются различными сочетаниями операций сложения и умножения переменных. Для практики, с позиции удобства синтеза схем, используют записи:
а) в
виде суммы произведений
– дизъюнктивная
нормальная форма
(ДНФ):
;
б) в виде произведения сумм – конъюнктивная нормальная форма (КНФ): x×(x + y) ×(y + z)×(`x + y + z).
Инверсия любой функции, записанной в ДНФ, дает замену записи на КНФ:
F= x +`yz + x`yz; `F=`x(y +`z)(`x + y +`z).
Логические функции наиболее наглядно представляются таблицей истинности, в которой для каждой комбинации значений переменных указывается значение функции.
Основные системы счисления. Число может иметь различные формы выражения. Привычная нам система построения чисел – это числа в десятичном коде: число состоит из десятичных разрядов. В каждом разряде может быть 10 различных состояний, которым соответствуют цифры от 0 до 9. Эта система является позиционной: “вес” цифры зависит от ее позиции.
В двоичной системе число тоже состоит из разрядов, но в каждом разряде есть два возможных состояния: «0» и «1». Для неё числа из натурального ряда имеют вид по таблице 18.1.
Таблица 18.1 – Числа из натурального ряда в двоичной системе счисления
-
Натуральные числа
Номера двоичных разрядов и весовые коэффициенты
5
4
3
2
1
24
23
22
21
20
0
0
0
0
0
0
1
0
0
0
0
1
2
0
0
0
1
0
3
0
0
0
1
1
4
0
0
1
0
0
5
0
0
1
0
1
9
0
1
0
0
1
Общее выражение числа в двоичной системе:
,
где
-
состояния в i-м
разряде; i-номер
разряда.
В такой же форме можно записать число в десятичной системе:
,
где аi
=
0, 1, 2 … 9
состояние в i-м
разряде.
Для любых систем счисления:
,
где аi - состояние в i-м разряде, h - основание системы счисления; i – номер разряда; hi-1 – весовой коэффициент разряда; 0 £ а i£ (h – 1).
Двоично-десятичная система – в ней кодируется не всё число N, а каждый отдельно взятый десятичный разряд:
,
где j – номер десятичного разряда.
Здесь сохраняется преимущество двоичной системы – возможность реализации на элементах с двумя состояниями и преобразование в десятичный код более простыми дешифраторами.
Максимальное число, которое может быть получено в двоичной системе при данном количестве разрядов: Nmax = 2n - 1.