Основные понятия алгебры логики

Алгебра логики основана на аксиомах:

• 1) третьего не дано: Х_= 0, если X ^ 1, и X = 1, если X ^ 0;
• 2) отрицание, «НЕ»: 0 = 1,1 = 0;
• 3) конъюнкция, логическое умножение, «И»: 0л0 = 0, 1л1 = 1,1л0 = = 0 Л 1 = 0, или в другой форме записи 0−0 = 0, 1−1 = 1, 1−0 = 01 = 0;
• 4) дизъюнкция, логическое сложение, «ИЛИ»: lvl = l, 0v0 = 0, 0vl = - 1 V 0 — 1, или 1 + 1−1, 0 + 0−0.0 + 1−1+0−1.

Первая аксиома задает рассмотрение только двоичных чисел, остальные — операции алгебры логики.

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

Функцией алгебры логики (булевой функцией) п переменных называют функцию F (x_;), однозначно сопоставляющую каждому конкретному набору значений 0 или 1 переменных одно из двух значений 0 или 1 самой функции.

Для одной переменной, которая может принимать два значения, можно применить только одну функцию инверсии: F_x(x₀) = х₀. Эта операция осуществляется с помощью цифрового элемента — инвертора.

Функция конъюнкции (операция И). Это функция, которая принимает значение, равное единице, если все входящие в нее переменные равны единице. Также эту функцию называют логическим умножением:

Цифровой элемент, осуществляющий эту функцию, называется элементом И.

Функция дизъюнкции (операция ИЛИ). Это функция, которая принимает значение, равное нулю, если все входящие в нее переменные равны нулю. Также эту функцию называют логическим сложением:

Цифровой элемент, осуществляющий эту функцию, называется элементом ИЛИ.

Любая функция алгебры логики п переменных может быть задана таблично, если перечислить все возможные наборы переменных x_i и указать соответствующие им значения функции F (x_t). Такая таблица называется таблицей истинности.

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

• 1. Выбрав из таблицы истинности все наборы переменных, при которых функция принимает значение, равное единице, можно для каждого из наборов записать соответствующую конъюнкцию, а затем связать все конъюнкции между собой операцией логического сложения (ИЛИ). Если переменная принимает в таблице значение, равное единице, то в аналитической записи содержится сама переменная. Если переменная принимает в таблице значение, равное нулю, то в выражение аналитической записи входит инверсия переменной. Такая форма записи получила название дизъюнктивной нормальной формы (ДНФ).
• 2. Выбрав из таблицы истинности все наборы переменных, при которых функция принимает значение, равное нулю, можно для каждого из наборов записать соответствующую дизъюнкцию, а затем связать все дизъюнкции между собой операцией логического умножения (И). Если переменная принимает в таблице значение, равное нулю, то в аналитической записи содержится сама переменная. Если переменная принимает в таблице значение, равное единице, то в выражение аналитической записи входит инверсия переменной. Такая форма записи получила название конъюнктивной нормальной формы (КНФ).

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

• 1) X = ХГ,
• 2) х + х = х;
• 3) х + х = 1;
• 4) х + 1 = 1;
• 5) х + 0 = х,
• 6) х-х = х;
• 7) х-х = 0;
• 8) х-1 =х;
• 9) х-0 = 0;
• 10) х⁷]/ = х + у
• 11) х + у = х-у;
• 12) х + х-у = х;
• 13) х-(х + у) —х
• 14) (х + у) —(х + у)=х;
• 15) х-у + х-у = х.

Выражения 10 и 11 называют теоремой де Моргана (теоремой двойственности), выражения 12 и 13 — теоремой слияния (поглощения), а выражения 14 и 15 — теоремой склеивания.

Пример 5.2.1.

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

Таблица 5.2.1

Таблица истинности для примера 5.2.1.

Решение

Используя дизъюнктивную нормальную форму, выбираем из таблицы все строки, в которых функция принимает значение, равное единице. В каждом наборе перемножаем переменные, добавляя функцию отрицания для переменных, равных нулю (табл. 5.2.2).

Выражение для логической функции можно записать с помощью функции логического сложения:

Составление ДНФ к примеру 5.2.1.

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

Используя конъюнктивную нормальную форму, выбираем из таблицы все строки, в которых функция принимает значение, равное нулю. В каждом наборе суммируем переменные, добавляя функцию отрицания для переменных, равных единице (табл. 5.2.3).

Таблица 5.2.3

Составление КНФ к примеру 5.2.1.

Выражение для логической функции можно записать с помощью функции логического умножения:

Произведем минимизацию полученной функции. Продублируем некоторые сомножители для удобства и воспользуемся законом склеивания (свойство 14):

Другим способом составления логической функции и ее минимизации является составление карты Карно. В программах схемотехнического моделирования (например, EWB) имеется блок Logic Converter, с помощью которого автоматически производятся подготовка логической функции, но таблице истинности, ее минимизация и синтез логической схемы, реализующей функцию.

Упражнение 5.2.1

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