Булевы функции

Переменные , способные принимать лишь два значения: 0 и 1, называются двоичными или булевыми переменными. Из n булевых переменных можно образовать всего 2ⁿ не совпадающих между собой наборов вида . Геометрически эти наборы изображаются точками n-мерного евклидова пространства. Которые можно рассматривать как вершины n-мерного ед иничного куба; одна из этих вершин находится в начале координат.

Функции от любого конечного числа булевых переменных, способные принимать лишь два значения 0 и 1 – булевы фукции. Имеется точно различных булевых функций от n переменных.

Существует взаимно однозначное соответствие между булевыми функциями n переменных и логическими высказываниями с n логическими переменными.

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

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

Класс абстрактных систем. Описываемых булевыми функциями, может быть выделен из множества абстрактных систем общего вида при помощи дополнительных ограничений, налагаемых на множества Т – моментов времени функционирования, Z – состояний системы, X и Y – выходных и выходных сигналов, а так же операторы переходов и выходов H и G.

Пусть - конечные множества. Закодируем каждое из (а так же ) двоичными числами. Тогда ,

будут представлять собой наборы булевых переменных, соответствующих разрядам двоичных чисел. Выберем фиксированную пару . Не ограничивая области, можно ввести рассуждения относительно сиситем без последствия для, для которых операторы переходов H и выходов G имеют вид и соответственно. Пусть теперь для выбранных и каждое представляется в виде булевой функции вида

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

во множество Z при фиксированных . Если для всех пар можно записать аналогичные совокупности булевых функций, мы придем к отображению прямого произведения во множество Z или, другими словами, к оператору переходов H некоторой системы . Аналогично, пусть для выбранных каждое , представляется в видебулевой функции вида . Множество совокупностей булевых функций , соответствующих всем , описывает оператор выходов рассматриваемой системы

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