<<
>>

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

Определение. Булева функция fÎPn существенно зависит от переменной 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) – нулевая остаточная функция; A - сумма по модулю 2.

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

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

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

Пример 50.

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

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

Решение.

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

Имеем

х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

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

Итак,

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

х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

х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

Таблица 64

х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

Таблица 65

х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.

<< | >>
Источник: Лекции - Дискретная математика. 2016

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

  1. 4.2 Аппроксимативная оценка корреляционной функции
  2. §21. Производная сложной функции
  3. Производная сложной функции.
  4. Производная обратных функций.
  5. Производные и дифференциалы высших порядков.
  6. Свойства производной векторной функции скалярного аргумента.
  7. Обыкновенные дифференциальные уравнения.
  8. Линейные однородные дифференциальные уравнения в частных производных первого порядка.
  9. 14. Дифференциал функции. Производные и дифференциалы высших порядков.
  10. 15. Понятия производного. Дифференцируемость функции.
  11. 19. Производная обратной функции. Производные высших порядков.
  12. А. СУЩЕСТВЕННОЕ И НЕСУЩЕСТВЕННОЕ (DAS WESENTLICHE UND DAS UNWESENTLICHE)
  13. Производная сложной функции
  14. 2.6. Частные производные первого порядка
  15. Контрольные вопросы
  16. Производная сложной функции
  17. Многочлен Ньютона с конечными разностями