Основы алгебры логики
Существует класс математических операндов, которые способны принимать только два возможных значения: истина или ложь. Такие операнды называются логическими переменными. Для работы с такими переменными существует раздел математики, называемой Булевой алгеброй или алгеброй логики. Интерпретация значений операндов в такой алгебре обычно представляет собой единицу (1,true) – «истина» или ноль (0,false) – «ложь».
Для работы с логическими операндами существуют математические операции, имеющие следующий смысл.
1) Логическая инверсия – операция «не» (обозначение \overline{X} ), основные условия:
\overline{1} = 0, \overline{0} = 1 \overline{\overline{X}} = X.
2) Логическая дизъюнкция — операция «или» (обозначения+,\cup ). Результат логической дизъюнкции равен единице, если хотя бы один из операндов равен единице, тогда: X + 0 = X, X + 1 = 1, X + \overline{X} = 1, X \cup \overline{X} = 1 .
3) Логическая конъюнкция — операция «и» (обозначения \cdot,\cap ). Результат логической конъюнкции равен 1 тогда и только тогда, когда все операнды равны 1, тогда: X \cdot 0 = 0, X \cdot 1 = X, X \cdot \overline{X} = 0, X \cap \overline{X} = 0 .
Для логических переменных действуют основные законы математики
1) переместительный (коммутативный) X + Y = Y + X или X \cdot Y = Y \cdot X
2) сочетательный (ассоциативный) X + Y + Z = X + (Y + Z) =(X + Y) + Z или X \cdot Y \cdot Z = X \cdot (Y \cdot Z) = (X \cdot Y) \cdot Z;
3) распределительный (дистрибутивный) X \cdot (Y + Z) = X \cdot Y + X \cdot Z .
При минимизации логических функций широко используются основные тождества логической алгебры
1. X \cdot Y + X \cdot \overline{Y} = X
2. X + X \cdot Y = X
3. X \cdot (X + Y) = X
4. X \cdot (\overline{X} + Y) = X \cdot Y
5. (X + Y) \cdot (X + Z) = X = Y \cdot Z
6. X \cdot \overline Y + Y = X + Y
К основным законам алгебры логики можно отнести теоремы Де Моргана:
- Отрицание дизъюнкции есть конъюнкция отрицаний \overline{X + Y} = \overline{X} \cdot \overline{Y}
- Отрицание конъюнкции есть дизъюнкция отрицаний \overline{X \cdot Y} = \overline{X} + \overline{Y}
| X | Y | \overline{X} | \overline{Y} | {X+Y} | \overline{X+Y} | {X \cdot Y} | {\overline{X \cdot Y}} | {\overline{X}+\overline{Y}} | {\overline{X}\cdot\overline{Y}} |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
Возможные логические функции двух переменных
X1 | 1 | 1 | 0 | 0 |
X2 | 1 | 0 | 1 | 0 |
| Y00 | 0 | 0 | 0 | 0 |
| Y01 | 0 | 0 | 0 | 1 |
| Y02 | 0 | 0 | 1 | 0 |
| Y03 | 0 | 0 | 1 | 1 |
| Y04 | 0 | 1 | 0 | 0 |
| Y05 | 0 | 1 | 0 | 1 |
| Y06 | 0 | 1 | 1 | 0 |
| Y07 | 0 | 1 | 1 | 1 |
| Y08 | 1 | 0 | 0 | 0 |
| Y09 | 1 | 0 | 0 | 1 |
| Y10 | 1 | 0 | 1 | 0 |
| Y11 | 1 | 0 | 1 | 1 |
| Y12 | 1 | 1 | 0 | 0 |
| Y13 | 1 | 1 | 0 | 1 |
| Y14 | 1 | 1 | 1 | 0 |
| Y15 | 1 | 1 | 1 | 1 |
Y00 – тождественный 0
Y01 – функция Пирса – отрицание дизъюнкции
Y02 – функция сравнения Х2 больше Х1
Y03 – инверсия Х1
Y04 – функция сравнения Х1 больше Х2
Y05 – инверсия Х2
Y06 – нечетность (исключающее «ИЛИ»)
Y07 – Функция Шеффера – отрицание конъюнкции
Y08 – конъюнкция «И»
Y09 – четность (инверсия исключающего «ИЛИ»исключающее «ИЛИ»)
Y10 – Х2
Y11 – функция сравнения Х1 меньше равно Х2
Y12 – Х1
Y13 – функция сравнения Х2 меньше равно Х1
Y14 – дизъюнкция «ИЛИ»
Y15 – тождественная 1
При физическом представлении двоичных переменных за параметр, эквивалентный значению переменной обычно принимают выходное напряжение операционных узлов алгебры логики — логических элементов. Логические элементы (ЛЭ) с таким соответствием называют потенциальной логикой. При объединении потенциальных ЛЭ в схемы необходимо кондуктивное (непосредственное) соединение их входов и выходов. Реактивные элементы (конденсаторы и дроссели) в соединениях могут играть лишь вспомогательную роль.
В потенциальной логике двум значениям логической переменной ставится в соответствии два уровня выходного напряжения высокий Uв и низкий Uн, причем Uв больше Uн в алгебраическом смысле.
Положительной или прямой логикой будет считаться соответствие высокого логического уровня логической единице, а низкого логического уровня – логическому нулю.
Обратное соответствие характеризует отрицательную или инверсную логику.
Существует также класс ЛЭ, у которых значение логической переменной определяется отсутствием или наличием импульса на выходе в определённый момент времени. Такая логика называется импульсной, плохо поддаётся микроминиатюризации средствами интегральной технологии и имеет ограниченное применение в жёстких условиях эксплуатации.
Основными характеристиками ЛЭ следует считать:
1) нагрузочную способность
2) потребляемую мощность
3) передаточную характеристику и значения логических уровней
4) запасы статической помехоустойчивости ЛЭ
5) динамические характеристики ЛЭ.
Нагрузочная способность ЛЭ
Нагрузочная способность ЛЭ отражает его возможности коммуникации с другими ЛЭ в процессе создания логической схемы и характеризуется коэффициентом объединения по входу M и коэффициентом разветвления по выходу N.
Коэффициент M численно равен количеству выходов однотипных ЛЭ, которые могут быть объединены со входом данного ЛЭ. Физически коэффициент M обычно совпадает с числом входов элемента. Отличие составляют «расширяемые» логические элементы, у которых физическое число входов может быть увеличено.
Коэффициент разветвления по выходу N численно равен количеству входов однотипных ЛЭ, которые могут быть объединены с выходом данного ЛЭ без потери логического соответствия.
Обычно коэффициенты M и N имеют предел 4-10.
Потребляемая мощность ЛЭ
Потребляемая мощность является одной из важнейших характеристик ЛЭ, поскольку определяет допустимую плотность упаковки ЛЭ в объёме кристалла в условиях фиксированного теплоотвода, т.е. допустимую степень интеграции. В целом потребляемая мощность подразделяется на статическую и динамическую.
Статическую составляющую Рст характеризуют мощности, потребляемые элементом:
P0 — при низком логическом уровне на выходе, и
P1 – при высоком логическом уровне на выходе.
Динамическая составляющая Рдин характеризует потребление ЛЭ при переключениях:
Р01 — при переходе из низкого логического состояния в высокое, и
Р10 — при переходе из высокого состояния в низкое.
Существует два ярко выраженных класса ЛЭ, различающиеся характером потребляемой мощности.
Для элементов первого класса статические и динамические составляющие потребляемой мощности практически эквивалентны. Элементы второго класса обладают существенным превышением динамических составляющих потребляемой мощности над статическими, поэтому для них характерна зависимость результирующего энергопотребления от тактовой частоты работы.
Передаточная характеристика ЛЭ
Передаточная характеристика ЛЭ представляет собой зависимость его выходного напряжения от медленно меняющегося напряжения входного сигнала. Для элементов неинвертирующего типа она имеет нарастающий характер, для инвертирующих элементов – спадающий.
Фундаментальным свойством, позволяющим выделить ЛЭ в отдельный класс электронных схем, следует считать свойство восстановления логического уровня, которое определяется видом передаточной характеристики логического элемента.
Свойство восстановления заключается в том, что если на вход цепи из последовательно соединённых однотипных логических элементов подан сигнал, являющийся линейной комбинацией высокого и низкого логических уровней, то цепь воспринимает этот сигнал однозначно либо как высокий, либо как низкий уровень.
Для элементов неинвертирующего типа свойства восстановления выполняются тогда, и только тогда, когда передаточная характеристика ЛЭ имеет три точки пересечения с прямой единичного усиления.
Уровни напряжений, соответствующие точкам пересечения 1,2,3 передаются в последовательной цепи без изменения.
Центральная точка пересечения получила название порогового уровня напряжения Un (напряжения меньше Un – низкий логический уровень, больше Un – высокий).
Для элементов инвертирующего типа, рассматривая два последовательно соединённых инвертирующих элемента как один неинвертирующий, можно сформулировать свойство восстановления следующим образом:
Для инвертирующих логических элементов свойство восстановления логического уровня будет выполняться тогда и только тогда, когда передаточная характеристика инвертирующего логического элемента будет иметь три точки пересечения со своим зеркальным отображением относительной прямой единичного усиления.
Координатами крайних точек пересечения при этом будут являться значения низкого и высокого логических уровней, а координаты центральной точки пересечения определят величину порогового напряжения.
Лемма: для выполнения свойства восстановления логического уровня в элементах инвертирующего типа необходимо и достаточно, чтобы передаточная характеристика элемента в точке пересечения с прямой ед. усиления имела коэффициент передачи меньше «-1» в алгебраическом смысле
Запасы статической помехоустойчивости ЛЭ.
При серийном производстве логических элементов благодаря наличию технологического разброса параметров передаточная характеристика элементов может характеризоваться разбросом, при этом, положение всех возможных передаточных характеристик ЛЭ оценивается кривой максимально допустимого положения – мажорантной MaxF и кривой минимально допустимого положения – минорантной MinF.
Запасом статической помехоустойчивости элемента считается максимально возможное напряжение помехи, которое будучи подано совместно со входным сигналом не может привести к ложному срабатыванию цепи последовательно соединенных однотипных ЛЭ.
Для цепи неивертирующих ЛЭ уровень помех при передаче низкого и высокого логических уровней могут различаться.
Запас помехоустойчивости при передаче низкого уровня ∆Uпн определяется разностью между минимальным значением порогового напряжения и максимальным значением напряжения низкого уровня, а запас при передаче высокого логического уровня ∆Uпв определяется как разность между линейным высоким уровнем и максимальным пороговым.
У элементов инвертирующего типа запасы статической помехоустойчивости ∆Uп одинаковы, поскольку они определяются поворотом зоны положения передаточных характеристик относительно прямой единичного усиления, образуя симметричную фигуру вращения.
Динамические характеристики ЛЭ
Динамические характеристики ЛЭ отражают временные параметры их работы с переключающимися входными сигналами.
Элементы неинвертирующего типа характеризуются временами распространения переднего t01 и заднего t10 фронтов импульса. Тогда время распространения фронтов будет завиcеть от количества элементов в цепи n.T^{01} =t^{01}\times n, T^{10} = t^{10}\times n
За отсчетный уровень при определении динамических характеристик используют среднее арифметическое напряжений высокого и низкого уровней.
Для элементов инвертирующего типа, поскольку каждый последующий элемент переключается в направлении, противоположном предыдущему, значение приобретает среднее время распространения t_p = (t_1+t_2)/2 , при этом T_p = t_p\times n