RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1993, том 5, выпуск 3, страницы 125–149 (Mi dm698)

Реализация некоторых систем булевых функций схемами из двувходовых элементов

К. А. Зыков


Аннотация: В работе рассматриваются системы булевых функций, удовлетворяющие некоторому ограничению на взаимное расположение существенных переменных. Для таких систем доказана нижняя оценка сложности схем из функциональных элементов в базисе из всех двуместных булевых функций. Полученная оценка имеет вид $(4k-3)$, где число входов схемы равно числу выходов схемы и равно $2k$. Приведен пример системы линейных булевых функций, для которой указанная нижняя оценка является точной.

УДК: 519.714

Статья поступила: 19.10.1992



Реферативные базы данных:


© МИАН, 2024