Том 19, номер 3, 2012 г., Стр. 39-57

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

Аннотация:
Рассматриваются реализации линейных булевых функций схемами из функциональных элементов в классическом базисе (конъюнкция, дизъюнкция и отрицание). Установлено, что все минимальные схемы, реализующие линейные функции в этом базисе, имеют определенную блочную структуру.
Ил. 10, библиогр. 10.

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

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

Статья поступила 28 июня 2011 г.
Исправленный вариант — 18 августа 2011 г.

Литература

[1] Комбаров Ю. А. О минимальных реализациях линейных булевых функций схемами из функциональных элементов в базисе {$x \to y, \overline{x} \And y$} // Тр. VIII междунар. конф. «Дискретные модели в теории управляющих систем» (Москва, 6–9 апреля 2009 г.). — М.: МАКС Пресс, 2009. — C. 145–149.

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

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

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

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

[6] Редькин Н. П. О минимальных и асимптотически минимальных схемах для некоторых индивидуальных булевых функций // Мат. IX междунар. семинара «Дискретная математика и её приложения», посвящённого 75-летию со дня рождения академика О. Б. Лупанова (Москва, 18–23
июня 2007 г.). — М.: Изд-во мех.-мат. фак. МГУ, 2007. — С. 11–19.

[7] Редькин Н. П. О минимальной реализации двоичного сумматора // Проблемы кибернетики. — 1981. — № 38. — C. 181–216.

[8] Шкребела И. С. О сложности реализации линейных булевых функций схемами из функциональных элементов в базисе {$x \to y, \overline{x}$} // Дискрет. математика. — 2003. — Т. 15, № 4. — С. 100–112.

[9] Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986. — 384 c.

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