О минимальной реализации оператора совпадения булевых наборов

Н. П. Редькин

МГУ имени М. В. Ломоносова

Аннотация: Исследуется сложность реализации оператора совпадения $R_n(\tilde x,\tilde y)$ двух $n$-разрядных булевых наборов $\tilde x=(x_1,\dots,x_n)$ и $\tilde y=(y_1,\dots,y_n)$, который обращается в единицу тогда и только тогда, когда $\tilde x=\tilde y$. Устанавливается, что минимальная схема из функциональных элементов для $R_n(\tilde x,\tilde y)$ в базисе $\{x\&y,\overline x\}$ содержит $8n-1$ элементов.

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

УДК: 519.714.7

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

DOI: 10.4213/dm1847