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

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Лупановское представительство»  – Новости  · газеты  · книги  · ученый  · JSTOR (Декабрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Эта статья может требовать уборка встретиться с Википедией стандарты качества. Конкретная проблема: Неполное определение Пожалуйста помоги улучшить эту статью если вы можете. (Август 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Лупанова (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}$.

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

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