4.3.Существенная зависимость функций от переменных определение

Булевская функция f (x₁ , . . . , x_n) существенно зависит от переменной x_i если:  ₁, . . . ,  _i-1 , ,  _{i +1} . . , _n  E₂

(f(₁, . . . , _i-1, 0,  _{i +1} . . , _n)  f (₁, . . . , _i-1, 1, _{i +1} . . , _n)).

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

Переменная, которая не является существенной переменной б.ф. f, называется несущественной переменной для f. Нетрудно видеть, что x_i  несущественная переменная функции f, если:

 ₁, . . . ,  _i-1, ,  _{i +1} . . , _n  E₂

(f(₁, ... ,  _i-1, 0, _{i +1}, … , _n) = f(₁, ..., _i-1, 1, _{i +1}, …, _n)).

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

Для лучшего понимания явления существенности переменных рассмотрим следующие два вопроса:

1) как по заданной функции из P₂ можно просто определить ее существенные и несущественные переменные?

2) если некоторая переменная булевской функции несущественна, то в каком смысле эта б.ф. является функцией меньшего числа переменных?

4.3.1. Нахождение существенных

ПЕРЕМЕННЫХ

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

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

(₁, . . . ,  _i-1, 0, _i+1 . . , _n), (1)

(₁, . . . , _i-1, 1,  _i+1 . . , _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.