|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Минимальные контактные схемы для характеристических функций сфер
Н. П. Редькин МГУ им. М.В. Ломоносова
Аннотация:
В работе исследуется сложность реализации контактными схемами характеристических функций сфер. Под характеристической функцией сферы с центром в вершине $\tilde\sigma=(\sigma_1,\ldots,\sigma_n)$, $\sigma_1,\ldots,\sigma_n\in\{0,1\}$, подразумевается булева функция $\varphi^{(n)}_{\tilde\sigma}(x_1,\ldots,x_n)$, обращающаяся в единицу на всех тех и только тех наборах значений, каждый из которых отличается от набора $\tilde\sigma$ ровно в одном разряде. Устанавливается, что для реализации $\varphi^{(n)}_{\tilde\sigma}(\tilde x)$ контактной схемой необходимо и достаточно $3n-2$ контактов.
Ключевые слова:
булева функция, контактная схема, минимальная схема.
Статья поступила: 28.11.2019
Образец цитирования:
Н. П. Редькин, “Минимальные контактные схемы для характеристических функций сфер”, Дискрет. матем., 32:3 (2020), 68–75; Discrete Math. Appl., 31:6 (2021), 403–408
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1601https://doi.org/10.4213/dm1601 https://www.mathnet.ru/rus/dm/v32/i3/p68
|
|