БУЛЕВЫ ФУНКЦИИ

— функции, которые, как и их аргументы, принимают значения в области из двух элементов. В качестве этих элементов в логике математической берут значения «истинно» и «ложно», а в автоматов теории — «0» и «1». Б. ф. названы по фамилии англ. математика Дж. Буля (1815—64), работы которого положили начало развитию алгебры логики. Б. полностью определяется заданием ее значений на всех наборах значений ее аргументов, число которых равно Эти значения можно задавать, напр., в виде таблицы или в виде вектора, у которого на месте стоит значение где запись числа в двоичной системе счисления. Б. ф. можно задавать также аналитически, в виде выражений, представляющих собой суперпозиции некоторых Б. ф. (принятых за исходные) и переменных (в частности, в виде формул алгебры логики, в т. ч. дизъюнктивных и конъюнктивных нормальных форм). Амер. математик Э. Пост (1897—1954) нашел необходимые и достаточные условия полноты любой системы S Б. ф., т. е. условия выразимости любой Б. ф. с помощью суперпозиции Б. ф. из s и переменных. Э. Пост также построил все замкнутые (относительно суперпозиции) классы Б. ф. и нашел их базисы, т. е. в определенном смысле миним. подклассы таких Б. ф., через которые выражаются все Б. ф. данного класса.

Б. ф. задают также графически — на -мерном единичном гиперкубе, каждая вершина которого с координатами отмечается значением Мн-во Б. переменных с определенными на нем операциями отрицания, конъюнкции и дизъюнкции (см. Логические операции) образует свободную булеву алгебру с образующими. Любая другая булева алгебра с образующими есть гомоморфный образ алгебры Б. ф. п переменных и тем самым изоморфна алгебре классов эквивалентности, задаваемых в алгебре Б. ф. каким-нибудь отношением конгруэнтности.

Б. ф. применяют при построении контактных, релейно-контактных схем, схем из пороговых элементов, схем из т. н. функциональных элементов в некотором базисе (напр., схем из элементов, реализующих ф-ции реализуют схемно, исходя из того, что их можно представить в виде суперпозиции Б. ф. из какой-нибудь фиксированной функционально полной системы Б. ф. От сложности представления зависит сложность схемы. Это приводит к важной проблеме — минимизации булевых функций, т. е. нахождения наиболее простых их представлений.

Две Б. ф. переменных наз. ф-циями одного типа, если одну из них можно получить из другой с помощью некоторой перестановки аргументов и замены некоторых аргументов их отрицаниями. Б. ф. одного типа реализуются физически одинаковыми схемами. Число

Б. ф. переменных равно оно очень быстро растет с ростом Правда, с точки зрения схемной реализации можно ограничиться рассмотрением только типовых Б. ф. Имеется всего 402 различных типа Б. ф. четырех переменных. Но уже при число типов измеряется квадриллионами. Почти все Б. ф. допускают лишь очень сложную схемную реализацию: каждая Б. ф. переменных требует для своей схемной реализации асимптотически не менее — контактов (см. Шеннона функция). Поэтому исследуют также классы Б. ф., существенно более узкие, чем мн-во всех Б. классы Б. ф. линейных, монотонных, самодвойственных, симметрических, инвариантных, относительно инверсий некоторых аргументов, Б. ф., имеющих значение «1» на небольшом мн-ве наборов и т. д. В теории автоматов и тех. приложениях рассматривают также частичные Б. т. е. ф-ции, возможно, не определенные для некоторых значений их аргументов.

Лит.: Глушков В. М. Синтез цифровых автоматов. М., 1962 [библиогр. с. 464—469]; Яблонский C. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1966 [библиогр. с. 113-115]. В. Ф. Ностырко.