EN|RU

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

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

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

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

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

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

 © Институт математики им. С. Л. Соболева, 2015