Индуктивное построение формулы
Пусть \(\text{Б}=\{\varphi_{1},\ldots,\varphi_b\}\) — базис булевых функций, а \(X=\{x_{1},x_{2},\ldots \}\) — множество переменных. Любая \(x_j\) является тривиальной формулой глубины 0. Если \(\varphi_i\) имеет арность \(k_i\) и \(F_{1},\ldots,F_{k_i}\) — формулы глубин \(q_{1},\ldots,q_{k_i}\), то
\(F=\varphi_i(F_{1},\ldots,F_{k_i})\)
является формулой глубины \(D(F)=1+\max (q_{1},\ldots,q_{k_i})\) и реализует функцию \(\varphi_i(f_{1},\ldots,f_{k_i})\), где \(f_j\) реализуется \(F_j\).1
Формулы, появившиеся в процессе такого построения, называются подформулами. Если одна и та же запись подформулы встречается в разных местах, каждое место считается отдельным позиционным вхождением.
Эквивалентность
Графически совпадающие формулы рассматриваются как изоморфные. Более широкое отношение — функциональная эквивалентность: F′ и F″ эквивалентны, если реализуют равные булевы функции. Равенство \(F'=F''\) в таком случае является тождеством. Именно эта идея лежит в основе последующих эквивалентных преобразований формул.1
Функционалы сложности
L(F) — число вхождений функциональных символов, то есть операций из базиса. R(F) — число вхождений символов переменных. D(F) — глубина формулы. В древовидном представлении R равно числу листьев, L — числу внутренних вершин, а D — глубине корня.1
Эти меры фиксируют разные аспекты реализации. L отражает общий объём операций, D — длину критического пути вычисления, а R показывает, сколько раз входные переменные используются в записи формулы. Поэтому оптимальность формулы всегда нужно связывать с конкретным функционалом.