Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Комбаров Ю.А.
Уточнение нижней оценки сложности линейной функции в одном бесконечном базисе
Аннотация:
Рассматриваются схемы из функциональных элементов в базисе из обобщенных конъюнкторов (т.е. конъюнкторов с произвольным числом входов, любой вход которых может быть инвертирован). Доказано, что любая схема, реализующая линейную булеву функцию от n переменных, состоит из не менее, чем 2.125n + С элементов.
Ключевые слова:
схемы из функциональных элементов, линейная функция
