RUS  ENG
Полная версия
ЖУРНАЛЫ // Доклады Российской академии наук. Математика, информатика, процессы управления // Архив

Докл. РАН. Матем., информ., проц. упр., 2020, том 495, страницы 65–68 (Mi danma136)

Эта публикация цитируется в 1 статье

МАТЕМАТИКА

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

К. А. Попков

Институт прикладной математики им. М.В. Келдыша Российской академии наук, Москва, Россия

Аннотация: Введено понятие равномерной ширины контактной схемы. Для каждой булевой функции найдено минимально возможное значение равномерной ширины реализующей ее контактной схемы. Конструктивно доказано, что оно не превосходит 3. Установлено также, что для почти всех булевых функций от $n$ переменных это значение равно 3.

Ключевые слова: контактная схема, булева функция, равномерная ширина.

УДК: 519.714.22

Статья представлена к публикации: Б. Н. Четверушкин
Поступило: 01.09.2020
После доработки: 01.09.2020
Принято к публикации: 03.10.2020

DOI: 10.31857/S2686954320060132


 Англоязычная версия: Doklady Mathematics, 2020, 102:3, 502–504

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


© МИАН, 2024