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

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

Определение

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

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

${\frac {df}{dx_{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}{dx_{i}}}\left({\frac {df}{dx_{j}}}\right)={\frac {d}{dx_{j}}}\left({\frac {df}{dx_{i}}}\right);$

• ${\frac {d{\bar {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)={\bar {f}}{\frac {dg}{dx}}\oplus {\bar {g}}{\frac {df}{dx}}\oplus {\frac {df}{dx}}{\frac {dg}{dx}};$