Том 20, номер 4, 2013 г., Стр. 65-87

УДК 519.95
Комбаров Ю. А.
О минимальных схемах в базисе Шеффера для линейных булевых функций

Аннотация:
Рассматриваются реализации линейных булевых функций схемами из функциональных элементов в базисе Шеффера. Найдено точное значение сложности реализации неоднородной линейной функции, а также получено описание всех минимальных схем, реализующих однородную линейную функцию.
Ил. 13, библиогр. 8.

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

Комбаров Юрий Анатольевич ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские Горы, 119991 Москва, Россия
е-mail: yuri.kombarov@gmail.com

Статья поступила 24 декабря 2012 г.
Исправленный вариант — 23 апреля 2013 г.

Литература

[1] Комбаров Ю. А. О минимальных реализациях линейных булевых функций // Дискрет. анализ и исслед. операций. - 2012. - T. 19, № 3. - С. 39–57.

[2] Ложкин С. А. О структуре минимальных схем в базисе $\{\&,\vee,\neg\}$, реализующих линейную функцию // Тр. V Междунар. конф. «Дискретные модели в теории управляющих систем» (Ратмино, 26–29 мая 2003 г.). - М.: МГУ, 2003. - С. 50–51.

[3] Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: МГУ, 1984. - 136 c.

[4] Мерекин Ю. В. Нижняя оценка сложности для схем конкатенации слов // Дискрет. анализ и исслед. операций. - 1996. - T. 3, № 1. - С. 52–56.

[5] Редькин Н. П. Доказательство минимальности некоторых схем из функциональных элементов // Пробл. кибернетики. - 1970. - № 23. - С. 83–101.

[6] Редькин Н. П. О минимальной реализации линейной функции схемой из функциональных элементов // Кибернетика. - 1971. - № 6. - С. 31–38.

[7] Редькин Н. П. Дискретная математика. - М.: Физматлит, 2009. - 263 c.

[8] Cardot C. Quelques résultats sur l’application de l’algébre de Boole á la synthése des circuits á relais // Ann. Telecomm. - 1952. - Vol. 7, N 2. - P. 75–84.