2.2.4. Существенные и несущественные переменные. Производная булевой функции первого порядка. Вес переменной

Определение. Булева функция fPn существенно зависит от переменной xi, если существует такой набор значений a1, …, ai-1, ai+1, …, an, что

В этом случае xi называют существенной переменной, в противном случае xi называют несущественной переменной.

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

где f(x1, x2, …, xi-1, 1, xi+1, …, xn) – единичная остаточная функция; f(x1, x2, …, xi-1, 0, xi+1, …, xn) – нулевая остаточная функция; - сумма по модулю 2.

Единичная остаточная функция получается в результате приравнивания переменной xi единице, нулевая – приравниванием xi нулю.

Определение. Весом производной  от булевой функции называется число конституент этой производной.

Утверждение. Чем больше вес производной  , тем больше функция f зависит от переменной xi.

Пример 50.

Определить переменную xi, по которой производная  функции

имеет минимальный (максимальный) вес, т. е. функция f(x1, x2, x3, x4, x5) зависит от нее менее (более) существенно.

Решение.

Определим вес каждой переменной, найдя сначала соответствующую производную.

Имеем

Для вычисления веса производной  зависящей от четырех переменных х2, х3, х4, х5, представим 4-мерное пространство с образующими {x2, x3, x4, x5} в виде декартова произведения двух двумерных пространств {x2, x3} {x4, x5}  с образующими {x2, x3} и {x4, x5} соответственно. Тогда производную  можно задать в виде двумерной таблицы (табл. 2.61). Вес производной  равен числу единиц в этой таблице.

Таблица 2.61 Вычисление веса производной (df/dx1) для примера 50

х2х3

х4х5

00

01

10

11

00

0

0

1

1

01

1

0

1

0

10

0

0

0

0

11

1

0

1

1

Итак,

Аналогично вычислим вес производных  (i = 2, 3, 4, 5) (табл. 2.62, 2.63, 2.64, 2.65). Имеем:

Таблица 2.62 Вычисление веса производной (df/dx2) для примера 50

х1х3

х4х5

00

01

10

11

00

0

0

0

0

01

0

1

0

1

10

0

0

1

1

11

0

1

0

0

Таблица 2.63 Вычисление веса производной (df/dx3) для примера 50

х1х2

х4х5

00

01

10

11

00

0

0

1

0

01

0

1

1

1

10

1

0

1

1

11

0

1

0

0

Таблица 2.64 Вычисление веса производной (df/dx4) для примера 50

х1х2

х3х5

00

01

10

11

00

1

0

0

0

01

1

0

0

0

10

0

1

0

0

11

1

0

0

1

Таблица 2.65 Вычисление веса производной (df/dx5) для примера 50

х1х2

х3х4

00

01

10

11

00

1

0

1

1

01

1

0

0

0

10

1

0

0

0

11

1

0

1

0

Выяснили, что минимальное значение  получено при дифференцировании функции f по переменным х2 и х4, максимальное значение  получено при дифференцировании функции f по переменной х3.