О нижних оценках сложности схем в базисе антицепных функций

Антицепной функцией называется характеристическая функция антицепи в булевом кубе. Множество всех антицепных функций образует бесконечный полный базис. В работе изучается сложность реализации булевых функций схемами в этом базисе. Доказаны нижние оценки порядка корень из n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных.

Авторы

Подольская О.В.

Тэги

антицепная функция булевы схемы линейные функции функции голосования леммы доказательства бесконечный базис

Тематические рубрики

Прикладные науки. Медицина. Технология

Предметные рубрики

Физико-математические науки

В этом же номере:

Моделирование движения железнодорожного экипажа при вкатывании гребня колеса на рельс с использованием подхода Дирака, О сложности реализации линейной булевой функции в базисе Шеффера, ...

Резюме по документу**

Антицепной функцией называется характеристическая функция антицепи в булевом кубе. <...> Множество всех антицепных функций образует бесконечный полный базис. <...> В работе изучается сложность реализации булевых функций схемами в этом базисе. <...> Доказаны нижние оценки порядка корень из n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных. <...> Антицепной функцией называется характеристическая функция антицепи в булевом кубе. <...> Множество всех антицепных функций образует бесконечный полный базис. <...> В работе изучается сложность реализации булевых функций схемами в этом базисе. <...> Доказаны нижние оценки порядка корень из n для сложности реализации линейной функции, функции голосования и почти всех функций от n переменных. <...>

** - вычисляется автоматически, возможны погрешности

Похожие документы:

Похожие документы из РУАЭСТ
|
Похожие документы из Руконт

О нижних оценках сложности схем в базисе антицепных функций

Помощь:

Участники: