Синтез комбинационной логической схемы 19 (19)

Логические основы микропроцессорной техники

Аксиомы и теоремы алгебры логики

Алгеброй логики называется любое множество элементов, на котором заданы операции над элементами и аксиомы (правила), которым подчиняются эти операции.

Булева алгебра базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с двоичными переменными. Аксиомы определяют свойства операций и отношения операций между собой. Каждая аксиома представлена в двух видах, что вытекает из принципа двойственности логических операций, согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять логическую 1 на 0 и 0 на 1, а знак «» на «» и «» на «» (табл. 1).

Таблица 1 Аксиомы алгебры логики

Двоичные переменные	Конъюнкция	Дизъюнкция
Х=0, если Х1 и Х=1, если Х0	00=0	11=1
Отрицание	10=01=0	01=10=1
	11=1	00=0

Законы булевой алгебры вытекают из аксиом и также имеют две формы выражения: для конъюнкции и дизъюнкции (правильность законов проверяется путем подстановки 0 и 1 вместо соответствующих значений переменных). Законы алгебры логики используются для преобразования логических выражений в целях их минимизации, упрощения схемного решения или приведения к основному базису (табл. 2).

Таблица 2 Законы алгебры логики

№	Наименование закона	Логическое выражение
		Конъюнкция	Дизъюнкция
1	Переместительный
2	Сочетательный	x1(x2x3)=(x1x2)x3 =x1x2x3	x1(x2x3)=(x1x2)x3 =x1x2x3
3	Повторения (тавтологии)	xx=x	хх=х
4	Обращения	Если х1=х2, то
5	Двойной инверсии
6	Нулевого множества	x0=0		х0=х
7	Универсального множества	x1=х		х1=1
8	Дополнительности
9	Распределительный	х1(x2x3) = x1x2х1x3		x1(x2x3) = (x1x2)(x1x3)
10	Поглощения	х1х1х2 = х1		х1(x1x2) = х1
11	Склеивания
12	Инверсии (Де Моргана)

Для обработки цифровых сигналов используются цифровые устройства, построенные на базе логических элементов. Действие цифровых устройств можно описать функциональными зависимостями между величинами на его входах и выходах.

Для проектирования и реализации цифровых устройств используется алгебра логики (булева алгебра), которая рассматривает логические переменные (высказывания, утверждения, аргументы) и функциональные связи между переменными. Функционирование цифровых (дискретных) устройств основано на использовании двоичной системы счисления, оперирующей только двумя цифрами: ноль (ложь) и единица (истина). Цифры 0 и 1 не выражают количественных соотношений и являются не числами, а символами, которые отражают два состояния: выключено/включено, разомкнуто/замкнуто, не горит/горит и т.д.

Логической переменной называется величина, которая может принимать только два значения – 0 или 1. Переменные можно объединить знаком логической функции Y=f(Х₁,Х₂,...,Х_n), которая отражает зависимость выходных переменных от входных. Логической функцией называется функция, которая, как и ее переменные, тоже может принимать только два значения – 0 или 1.

Основными функциями алгебры логики являются функции двух переменных Y=f(Х₁,Х₂). Различные комбинации значений входных переменных в логических функциях называются наборами. Функция является полностью заданной, если указаны ее значения для всех 2ⁿ наборов (n – количество переменных).

Для двух переменных существует 2²=4 набора входных переменных, которым соответствует 4²=16 логических функций (так как функция может принимать два значения), из которых выделяют три основные функции.

К основным относятся три логические функции: конъюнкция, дизъюнкция и инверсия. С помощью основных функций можно создать цифровые устройства, выполняющие любые сколь угодно сложные функции (включая микропроцессор).

Логические функции могут задаваться аналитически Y=f(X₁,X₂) и с помощью таблицы истинности.

Логические функции реализуются с помощью релейно-контактных схем (РКС) и логических элементов (ЛЭ).

На рис. 1 показана таблица истинности конъюнкции, реализация ее на релейно-контактной схеме и логическом элементе 2И.

Конъюнкция (операция И, логическое умножение) означает, что функция Y= X₁ И X₂=X₁X₂ истинна тогда, когда истинны оба высказывания Х₁ и Х₂. Например для РКС это значит, что электрическая цепь «mn» будет замкнута, если нажаты контакты Х1 и Х2 и по катушке реле К1 будет протекать электрический ток.

а б с

Рис. 1. Логическая функция конъюнкция Y=X₁X₂: а - таблица истинности; б - релейно-контактная схема; с - логический элемент 2И

На рис. 2 показана таблица истинности дизъюнкции и реализация ее на релейно-контактной схеме и логическом элементе 2ИЛИ.

Д изъюнкция (операция ИЛИ, логическое сложение) означает, что функция Y= X₁ ИЛИ X₂=X₁VX₂ истинна, если истинно хотя бы одно из высказываний Х₁ или Х₂.

Например, для РКС это значит, что электрическая цепь mn будет замкнута, если нажаты контакты Х1 или Х2.

а б с

Рис. 2. Логическая функция дизъюнкция Y=X₁VX₂: а - таблица истинности; б - релейно-контактная схема; с - логический элемент 2ИЛИ

На рис. 3 показана таблица истинности инверсии и реализация ее на релейно-контактной схеме и логическом элементе НЕ.

И нверсия (операция НЕ, логическое отрицание) означает, что функция Y=(НЕ X) = истинна, если высказывание Х ложно, и наоборот. Например, для РКС это значит, что электрическая цепь mn будет замкнута, если контакт Х не нажат, и наоборот.

а б с

Рис. 3. Логическая функция инверсия Y=X: а - таблица истинности;

б - релейно-контактная схема; с - логический элемент НЕ

Рассмотрим пример описания технического устройства с помощью выражений алгебры логики. Предположим, в техническом объекте имеется электродвигатель, который управляет рабочими органами, выполняющими технологические операции. Двигатель М можно включать двумя различными кнопками S₁ или S₂, и только в том случае, если закрыт защитный кожух К и не сработал датчик температуры D (например, перегрев двигателя). В этом случае включение двигателя описывается функцией

(1)

Заменим названия логических операций И, ИЛИ, НЕ на логические знаки

.

(2)

Заменим технические обозначения S₁, S₂, К и D на символы входных и выходных переменных

.

(3)

Кроме основных операций алгебры логики важное значение имеют более сложные функции, такие как И-НЕ (штрих Шеффера), ИЛИ-НЕ (стрелка Пирса) и сумма по модулю два (исключающее ИЛИ, логическая неравнозначность). Эти функции также определяются через основные функции алгебры логики.

В интегральных микросхемах, изготавливаемых по полупроводниковой технологии, используются базовые логические элементы И-НЕ (штрих Шеффера) и ИЛИ-НЕ (стрелка Пирса).

На рис. 4 показана таблица истинности функции штрих Шеффера и реализация ее на логическом элементе 2И-НЕ. Операция 2И-НЕ означает, что функция Y=X₁/X₂, ложна если истинны оба высказывания Х₁ и Х₂.

а б

Рис. 4. Логическая функция штрих Шеффера Y=X1/Х2:

а - таблица истинности; б - логический элемент 2И-НЕ

На рис. 5 показана таблица истинности функции стрелка Пирса и реализация ее на логическом элементе 2ИЛИ-НЕ. Операция ИЛИ-НЕ означает, что функция Y=X₁↑X₂ ложна, если истинно хотя бы одно из высказываний Х₁ или Х₂.

б

Рис. 5. Логическая функция стрелка Пирса Y=X1/Х2:

а - таблица истинности; б - логический элемент 2ИЛИ-НЕ

На рис. 6 показана таблица истинности функции сумма по модулю два и логический элемент. Функция Y=X₁X₂ истинна, если оба высказывания неравнозначны, и ложна, если оба высказывания равнозначны.

а б

Рис. 6. Логическая функция сумма по модулю два Y=X₁X₂:

а - таблица истинности; б - логический элемент

Функция сумма по модулю два играет очень важную роль в теории переключательных функций. Она используется для построения двоичных сумматоров, выполняющих арифметические операции, решения логических уравнений и создания кодов, повышающих достоверность при передаче и хранении информации (контроль паритета).

Законы алгебры логики используются для преобразования логических выражений с целью их минимизации, упрощения схемного решения или приведения к базису И-НЕ.

Например, логическое выражение (3) содержит конъюнкции, дизъюнкции и инверсии. Для построения комбинационной логической схемы необходимо использовать логические элементы трех типов: И, ИЛИ , НЕ.

Для приведения логического выражения (3) к базису И-НЕ необходимо выполнить ряд преобразований:

• поставить двойную инверсию (в соответствии с законом двойной инверсии) над выражением в скобках, содержащим знак дизъюнкции

.

(4)

• выражение в скобках (4) преобразовать по закону Де Моргана

.

(5)

Выражение (5) содержит только знаки конъюнкции и инверсии и может быть реализовано на базовых логических элементах одного типа: И-НЕ.