4.3.2. Удаление несущественных
ПЕРЕМЕННЫХ
Рассмотрим второй вопрос о существенных переменных. Пусть f(x1, . . . , xn) P2 и имеет несущественную переменную xi. Дополнительно предположим, что n > 1.
Преобразуем табличное задание этой функции по следующим правилам:
1) удалим из таблицы все строки, соответствующие таким наборам значений переменных, в которых переменная xi равна 1;
2) удалим из полученной таблицы столбец, соответствующий переменной xi.
В
результате будет получено табличное
задание новой функции
,
переменные которой обозначаются
символами
x1,
. . . ,
xi-1,
xi+1,
.
. . , xn.
Будем говорить, что g получается из f удалением несущественной переменной xi. Нетрудно видеть, что если известно положение несущественной переменной xi в списке переменных f, то табличное задание функции f однозначно восстанавливается по табличному заданию функции g.
Определение
Функции f и g называются равными, если их табличные задания совпадают с точностью до удаления несущественных переменных.
Равенство произвольных функций алгебры логики f и g представляется с помощью записи f = g.
Замечание
Одна из областей практической деятельности, стимулирующая интерес к изучению булевских функций, компьютерная электроника. Ей присуща явно выраженная двузначность базовых методов представления и обработки информации. Например, устройства хранения минимального объема информации могут находиться в одном из двух возможных состояний, которые абстрактно могут обозначаться с помощью символов 0 и 1, называемых битами информации.
Электронные процессы, протекающие в микросхемах процессоров это процессы преобразования входной информации в виде последовательностей битов в выходную информацию, также представляемую как последовательности битов.
Функционирование произвольной микросхемы можно рассматривать как процесс одновременного вычисления системы булевских функций, значения которых являются результатом таких вычисления и появляются на выходах микросхемы.
Переход к булевским функциям при изучении алгоритмов обработки информации в вычислительных машинах и их схемной реализации полезен, поскольку позволяет отвлечься от несущественных деталей при решении задач по проектированию и анализу микросхем.
4.4. Элементарные булевские функции
Табличное задание булевских функций не всегда удобно, поскольку уже для небольшого числа переменных размер таблицы произвольной функции таких переменных оказывается слишком большим.
Например, для функций 32 переменных, соответствующих 32 разрядным операциям процессора, такая таблица является практически необозримой. Поэтому целесообразно нахождение других форм представления б.ф., имеющих меньшие размеры.
Рассмотрим способ представления б.ф., в котором одни функции выражаются через другие. При этом некоторые б.ф., называемые элементарными функциями, выбираются в качестве базовых. Они получают собственные обозначения, а остальные функции выражаются через элементарные функции с помощью специальных операций.