Главная | Обратная связь

НАХОЖДЕНИЕ СУЩЕСТВЕННЫХ

ПЕРЕМЕННЫХ

 

Для получения ответа на первый из поставленных вопросов нам потребуются следующие простые свойства табличного задания б.ф. f (x₁, . . . , x_n).

1.Два двоичных набора:

(s₁, . . . , s _i-1, 0,s_i+1 . . , s_n), (1)

(s₁, . . . , s_i-1, 1, s _i+1 . . , s_n) (2)

в табличном задании f(x₁, . . . , _n) соответствуют строкам, расстояние между которыми равно2^n-i.

Для того чтобы по двоичному числу, записываемому в виде последовательности (1), получить двоичное число, записываемое в виде последовательности (2), достаточно прибавить к первому числу число k, представляемое двоичной последовательностью10. . .0, имеющей n - i нулей, т.е. k = 2^n-i.

 

2.Двоичные наборы значений переменных функции f, в которых переменная x_i принимает значение 0, располагаются последовательно идущими группами по 2^n-i таких наборов в каждой группе.

Аналогичное утверждение справедливо и для двоичных наборов, в которых x_i = 1.

При этом последовательно идущие группы наборов с x_i = 0 и с x_i =1 чередуются. Кроме того, всякие две последовательно идущие группы строк с x_i = 0 и x_i = 1 при наложении совпадают всюду за исключением компоненты значений переменной x_i.

Поэтому справедлива следующая схема определения существенности переменной x_i функции f(x₁, . . . , x_n) по табличному заданию этой функции.

 

1. Разобьем последний столбец в табличном задании f на 2^i-1 последовательно идущих подстолбцов равной длины. Каждый такой столбец содержит 2^n-i+1 значений, соответствующих значениям функции на двух последовательно идущих группах наборов с равными значениями компоненты с номером i.

 

2. Если в каждом таком подстолбце верхняя половина совпадает с нижней, то x_i является несущественной переменной функции f. В противном случае переменная x_i существенна для f.

УДАЛЕНИЕ НЕСУЩЕСТВЕННЫХ

ПЕРЕМЕННЫХ

Рассмотрим второй вопрос о существенных переменных. Пусть f(x₁, . . . , x_n) Î P₂ и имеет несущественную переменную x_i. Дополнительно предположим, что n > 1.

Преобразуем табличное задание этой функции по следующим правилам:

1) удалим из таблицы все строки, соответствующие таким наборам значений переменных, в которых переменная x_i равна 1;

2) удалим из полученной таблицы столбец, соответствующий переменной x_i.

В результате будет получено табличное задание новой функции , переменные которой обозначаются символами x₁, . . . , x_i-1, x_i+1,. . . , x_n.

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

 

ОПРЕДЕЛЕНИЕ

Функции f и g называются равными, если их табличные задания совпадают с точностью до удаления несущественных переменных.

 

Равенство произвольных функций алгебры логики f и g представляется с помощью записи f = g.

 

Замечание

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

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

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

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