Производная булевой функции

Производная булевой функции (булева производная) — аналог алгебраической производной применительно к булевой функции. Широко применяется при описании и анализе дискретных динамических систем.

Определение

Как и любая булева функция, производная булевой функции принимает значения 0 или 1. В случае, если булева функция при изменении одного из её аргументов не меняет своего значения, булева производная по этому аргументу равна 0. В противном случае производная равна 1, независимо от того, как именно с (0→1 или 1→0) меняется функция при изменении аргумента 0→1.

В формальном виде определение булевой производной записывается следующим образом:

$\frac{df}{d{x}_i}=f(x_i=0)\oplus f(x_i=1),$

где $\oplus$ — операция «исключающее или» (суммирование по модулю 2).

История

Начало развития дифференциального исчисления булевых функций относится к 50-м годам XX в. В отличие от производной непрерывной функции, которая основана на понятии предельного перехода, в основе булевой производной лежит понятие изменения функции при изменении её аргументов.

Свойства булевой производной

• $\frac{d(const)}{dx}=0;$

• $\frac{d}{dx}\left(\frac{df}{dx}\right)=0;$

• $\frac{d}{d{x}_i}\left(\frac{df}{d{x}_j}\right)=\frac{d}{d{x}_j}\left(\frac{df}{d{x}_i}\right);$

• $\frac{d\overline{f}}{dx}=\frac{df}{dx};$

• $\frac{d}{dx}(f\oplus g)=\frac{df}{dx}\oplus \frac{dg}{dx};$

• $\frac{d}{dx}(f\cdot g)=f\frac{dg}{dx}\oplus g\frac{df}{dx}\oplus \frac{df}{dx}\frac{dg}{dx};$

• $\frac{d}{dx}(f\vee g)=\overline{f}\frac{dg}{dx}\oplus \overline{g}\frac{df}{dx}\oplus \frac{df}{dx}\frac{dg}{dx};$