Лупановское представительство - Lupanov representation

Лупанова (k, s)-представление, названный в честь Олег Лупанов, это способ представления Булевы схемы чтобы показать, что обратная величина Эффект Шеннона. Шеннон показал, что почти все Логические функции из п переменные нуждаются в схема размером не менее 2^пп⁻¹. Обратное:

Все булевы функции п переменные могут быть вычислены с помощью схемы не более 2^пп⁻¹ + o (2^пп⁻¹) ворота.

Определение

Идея состоит в том, чтобы представить значения логической функции ƒ в таблице 2^k строк, представляющих возможные значения k первые переменные Икс₁, ..., ,Икс_k, и 2^п−k столбцы, представляющие значения других переменных.

Позволять А₁, ..., А_п - такое разбиение строк этой таблицы, что для я < п, |А_я| = s и ${\displaystyle |A_{p}|=s'\leq s}$.Позволять ƒ_я(Икс) = ƒ(Икс) если только  Икс ∈ А_я.

Кроме того, пусть ${\displaystyle B_{i,w}}$ - множество столбцов, пересечение которых с ${\displaystyle A_{i}}$ является ${\displaystyle w}$.

Смотрите также

• Учебный материал, описывающий представление Лупанова
• Дополнительный пример из того же материала курса