RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2019, номер 6, страницы 51–55 (Mi vmumm3641)

Краткие сообщения

Квазиуниверсальный булев автомат с четырьмя константными состояниями

Л. Н. Сысоева

Национальный исследовательский университет "Высшая школа экономики", г. Москва

Аннотация: Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и $n$ входами, т.е. автоматами, такими, что в любом из состояний функция выхода совпадает с одной из булевых констант $0$ или $1$, зависящих от $n$ переменных, $n\ge1$. Построен пример инициального булева автомата с минимальным количеством константных состояний и $n$ входами, реализующего максимальное возможное число булевых функций от $n$ фиксированных переменных, при $n\ge3$.

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

УДК: 519.716.32

Поступила в редакцию: 31.10.2018


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2019, 74:6, 241–245

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


© МИАН, 2024