9.5. Булева производная

Производная первого порядка от булевой функцииf по переменной x_i определяется следующим образом [9]:

=f(х₁,х₂,...,х_i-1,1,x_i+1,...,x_n)Åf(x₁,x₂,...,x_i-1,0,x_i+1,...,x_n),

где f(х₁,х₂,...,х_i-1,1,x_i+1,...,x_n) – единичная остаточная функция, получаемая в результате подстановки вместо х_i константы 1, а f(х₁,х₂,...,х_i-1,0,x_i+1,...,x_n) – нулевая остаточная функция, получаемая в результате подстановки вместо x_i константы 0.

Пример. f=х₁Úх₂.

Пример.

Пример.

Булева производная по x_i=0, если f не зависит от x_i, булева производная по x_i=1, если f зависит только от x_i.

Булева производная первого порядка определяет условия, при которых функция изменяет свое значение при изменении значения переменной x_i .

В нашем примере функция f(х₁х₂х₃) изменяет свое значение при изменении х₁, если истинна конъюнкция х₂х₃, т.е. х₂=1, х₃=1.

Пример. Определим все булевы производные функции

Итак, значение функции изменяется (функция переключается) при изменении х₁, если х₂=1 или х₃=0 ; при изменении х₂, если х₁=х₃=1 (х₁х₃=1); при изменении х₃, если х₁=1; х₂=0 .

Смешанная булева производная k-го порядка определяется путем вычисления k раз булевых производных первого порядка от булевых производных первого порядка, например [9]:

Булева производная k-го порядка равна сумме по модулю 2 всех производных первых, вторых, третьих, ..., k-х смешанных производных, и определяет условия, при которых функция изменяет значение при одновременном изменении соответствующих переменных, например:

Таким образом, f переключается при одновременном переключении х₁, х₂, когда х₃=0, либо независимо от х₃ при переключении х₁ и х₂ с 1,1 на 0,0 или с 0,0 на 1,1.

При синтезе методом каскадов оптимальное исключение переменных достигается путем анализа веса производных [9]. Вес производной по данной переменной – число конституент соответствующей переключательной функции. То есть, сначала исключается переменная, производная которой имеет максимальный вес, что означает максимальное изменение функции при изменении переменной.