RUS  ENG
Полная версия
ЖУРНАЛЫ // Ученые записки Казанского университета. Серия Физико-математические науки // Архив

Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 2014, том 156, книга 3, страницы 116–122 (Mi uzku1271)

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

О реализации булевых функций обобщенными $\alpha$-формулами

Л. Н. Сысоева

Кафедра дискретной математики, Московский государственный университет имени М. В. Ломоносова, г. Москва, Россия

Аннотация: Рассмотрена задача о реализации булевых функций обобщенными $\alpha$-формулами. Введено понятие обобщенной $\alpha$-формулы. Определено понятие универсального множества обобщенных $\alpha$-формул для заданного множества булевых функций. Введено понятие двойственных обобщенных $\alpha$-формул, сформулирован принцип двойственности. Показано, что для каждого $n\geq2$ для множеств $T_0(n)$ и $T_1(n)$ всех булевых функций от переменных $x_1,x_2,\dots,x_n$, сохраняющих константы 0 и 1 соответственно, существуют универсальные множества.

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

УДК: 519.95

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



© МИАН, 2024