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

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

Определение

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

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

${\displaystyle {\frac {df}{dx_{i}}}=f(x_{i}=0)\oplus f(x_{i}=1),}$

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

История

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

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

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

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

• ${\displaystyle {\frac {d}{dx_{i}}}\left({\frac {df}{dx_{j}}}\right)={\frac {d}{dx_{j}}}\left({\frac {df}{dx_{i}}}\right);}$

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

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

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

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

Примечания

1. Шевелев Ю.П. Дискретная математика. Ч. 1: Теория множеств. Булева алгебра. — Томский гос. ун-т систем управления и радиоэлектроники, 2003. — 118 с. Архивировано 2 июля 2015 года. Архивированная копия  (неопр.). Дата обращения: 1 ноября 2014. Архивировано 2 июля 2015 года.