Основы алгебры логики. Определение функции алгебры логики.

Для анализа и синтеза цифровых электронных схем широко используется математический аппарат алгебры логики, или булевой алгебры, разработанной в середине XIX в. ирландским математиком Дж. Булем. Основным понятием алгебры логики является понятие переключательной функции, или булевой функции алгебры логики (ФАЛ). Функцией алгебры логики п переменных называется такая функция, которая принимает только два возможных значения (0 или 1), как и переменные, от которых эта функция зависит. Для п переменных возможно различных значений переключательной функции f Если заданы все значений функции, то на называется полностью определенной. Если же часть значений функции f не задана, то такая функция носит название неопределенной или частично определенной.

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

Конкретная комбинация значений аргументов носит название набора. Каждый набор имеет индекс j, численно равный десятичному эквиваленту двоичного числа.

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

Таблица 15.1

j	A	B	C	F

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

Аналитическая запись функции осуществляется по таблице истинности. Непосредственно из данных таблицы находится так называемая совершенная дизъюнктивная нормальная форма булевой функции (СДНФ) по выражению

,

где – значение функции на j-м наборе; – конституента единицы, равная «1» только на одном j-м наборе; ˅ – символ логического сложения (дизъюнкции), аналогичный символу алгебраического сложения ∑.

Для записи выражений в совершенной конъюктивной нормальной форме (СКНФ) используют формулу

,

где – значение функции на j-м наборе; – конституента нуля, равная «0» только на одном j-м наборе; ˄ – символ логического произведения (конъюнкции), аналогичный символу алгебраического произведения X.

Проиллюстрируем СДНФ и СКНФ переключательной функции на примере булевой функции трех переменных, заданной таблице 15.1. Формула для любой СДНФ функции трех переменных будет иметь следующий вид:

Подставляя из таблицы значения функций … , получаем

Формула для любой СКНФ функции трех переменных будет иметь вид

Подставляя из таблицы значения функций … ,получаем

Аналогично находятся СДНФ и СКНФ любой другой булевой функции, заданной таблично.

Аналитическая запись ФАЛ, а также ее дальнейшие тождественные преобразования для получения оптимального вида опираются на следующие законы и тождества алгебры логики:

– закон двойного отрицания ;

– закон склеивания , ;

– закон поглощения ; ;

и др.

Иногда вместо аналитической формы используют запись логической функции в виде последовательностей десятичных чисел. Такая запись является аналогом таблиц истинности и СДНФ или СКНФ, но при этом является гораздо более компактной. В скобках указывают десятичные эквиваленты двоичных кодов конституент единицы или нуля, либо, что одно и то же, номера наборов функции f, в которых она принимает единичные или нулевые значения. При указании номеров наборов с единичными значениями функции перед скобкой слева указывается знак дизъюнкции ˅ или ∑, а с нулевыми значениями – знак конъюнкции ˄ или П. В качестве примера запишем функцию, заданную таблице 15.1, в виде десятичных чисел на единичных и нулевых наборах:

f(A, В, С) = ˅ (0, 2, 3, 7) = ∑ (0, 2, 3, 7);

f(A,В, С) = ˄ (1, 4, 5, 6) = П(1, 4, 5, 6).

В случае автоматизированного проектирования логических схем электронных цифровых устройств на ЭВМ удобно записывать ФАЛ в виде кубических комплексов. Такая форма в силу ограниченного числа символов позволяет формализовать запись логических функций большого числа переменных.

Для выражения ФАЛ от многих переменных достаточно иметь ограниченное число разнотипных элементарных переключательных функций, называемое системой. Как показано выше, любая функция алгебры логики может быть записана в виде СДНФ или СКНФ. Следовательно, любую функцию аргументов можно представить с помощью системы только из трех элементарных функций: инверсия, дизъюнкции и конъюнкции.

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

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