Метод Лупанова синтеза схем

Теорема:

Любая булева функция от $n$ аргументов $f(x_1, x_2, ..., x_n)$ в базисе $B = \{\neg, \lor, \land\}$ имеет схемную сложность $size_B (f) = O\left(\frac{2^n}{n}\right)$.

Представление функции

Рис. 1. Описываемая таблица истинности, разделённая на полосы

Поделим аргументы функции на два блока: первые $k$ и оставшиеся $(n - k)$.

Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1. Строки индексируются значениями первых $k$ переменных, столбцы — значениями оставшихся $(n - k)$; таким образом, на пересечении столбца и строки находится значение функции для соответствующего набора аргументов.

Разделение на полосы

Разделим таблицу на горизонтальные полосы шириной $s$ (последняя полоса, возможно, будет короче остальных; её ширину обозначим $s'$). Пронумеруем полосы сверху вниз от 1 до $p=\left\lceil\frac{2^k}{s}\right\rceil$.

Рассмотрим независимо некоторую полосу. Заметим, что среди её столбцов при небольшом $s$ будет много повторений; введем понятие сорта столбца.

Определение:

Сорт некоторого столбца данной полосы — его класс эквивалентности по отношению поэлементного равенства столбцов данной полосы.

Число сортов столбцов $i$-й полосы обозначим как $t(i)$. Понятно, что для любой полосы $t(i) \leq 2^s$ (для последней $t(p) \leq 2^{s'}$).

Функция для одной полосы

Рис. 2. Значения, возвращаемые функцией $g_{ij}$

Пусть для некоторого $i$

• $\beta_{j}$ — произвольный столбец $i$-й полосы $j$-го сорта (точное положение столбца далее не будет иметь значения по определению сорта)
• $(\sigma_1^l, \sigma_2^l, ..., \sigma_k^l)$ — аргументы функции, соответствующие $l$-й строке $i$-й полосы.

Тогда введём булеву функцию

$g_{ij}(x_1, x_2, ..., x_k) = \begin{cases} \beta_{jl}& , \mbox{if } \exists l \in [1; s]~(x_1, x_2, ..., x_k) = (\sigma_1^l, \sigma_2^l, ..., \sigma_k^l) \\ 0&, \mbox{otherwise} \end{cases}$

Другими словами, если строка, соответствующая аргументам функции $x_1, x_2, ..., x_k$, находится в $i$-й полосе, то функция возвращает значение, записанное в столбце сорта $j$ для этой строки. Если же эта строка находится в другой полосе, то функция вернёт 0. Иллюстрация принципа работы функции $g_{ij}$ приведена на рис. 2.

Вывод исходной функции для фиксированной части параметров

Поскольку изначальный столбец $(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})$ складывается из столбцов соответствующих сортов в полосах, $f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n}) = \bigvee\limits_{i = 1}^p g_{ij_i}(x_1, x_2, ..., x_k)$, где $j_i$ — номер сорта столбца полосы $i$, являющегося соответствующей частью столбца $(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})$.

Мультиплексор и дешифратор

Для упрощения доказательства теоремы будем использовать элементы мультиплексор и дешифратор.

Определение:

Мультиплексор (англ. multiplexer) — логический элемент, получающий на вход $2^n$ булевых значений; $n$-значное число $x$ в двоичном представлении и возвращающий значение на $x$-м входе.

Определение:

Дешифратор (или демультиплексор, англ. demultiplexer) — логический элемент, получающий на вход булево значение $z$; $n$-значное число $x$ в двоичном представлении и выводящий $z$ на $x$-й из своих $2^n$ выходов. На все остальные выходы элемент выдаёт 0.

Мультиплексор слева, дешифратор справа

Можно доказать, что оба элемента представимы схемами с числом элементов $O(2^n)$ с помощью базиса $B$.

Доказательство

В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции $f(x_1, x_2, ..., x_n)$ (представление Лупанова, англ. Lupanov $(k, s)$-representation).

Для удобства поделим схему на блоки:

• Блок A — дешифратор, которому на вход подали 1 и $(x_1, x_2, ..., x_k)$ в качестве двоичного представления числа.
• Блок B — схемная реализация всех $g_{ij}$. Функцию $g_{ij}$ можно реализовать как $\bigvee\limits_{\beta_l = 1} y_{il}$, где $y_{il}$ — выдал ли дешифратор "1" на $l$-м выходе $i$-й полосы.
• Блок C — схемная реализация всех $f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)$. (здесь $\sigma_i$ - фиксированные параметры, см. п. 3.1)
• Блок D — мультиплексор, получающий на вход все $f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)$ и параметры функции $x_{k + 1}, x_{k + 2}, ..., x_n$ в качестве двоичного представления числа. Результат работы схемы — вывод мультиплексора.

Положим $s = [n - 2\log_2 n]$; $k = [\log_2 n]$. Тогда число элементов в блоках

• $L_A = O(2^k) = O(2^{\log_2 n}) = O(n)$
• $L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) \lt sp \cdot 2^s = 2^{k + s} = \frac{2^n}{n}$
• $L_C = O(p \cdot 2^{n - k}) = O\left(\frac{p}{n} \cdot 2^n\right) = O\left(\frac{2^n}{s}\right) = O\left(\frac{2^n}{n - 2\log_2 n}\right)$
• $L_D = O(2^{n - k}) = O\left(\frac{2^n}{n}\right)$

Итого, имеем схему c числом элементов $L_A + L_B + L_C + L_D = O(n) + O\left(\frac{2^n}{n}\right) + O\left(\frac{2^n}{n - 2\log_2 n}\right) + O\left(\frac{2^n}{n}\right) = O\left(\frac{2^n}{n}\right)$, откуда следует, что $size_B (f) = O\left(\frac{2^n}{n}\right)$, ч.т.д.

Ссылки

• Wikipedia — Multiplexer

Литература

• Яблонский С.В. Введение в дискретную математику — М.:"Наука", 1986 — стр. 361