Булева функция

БУЛЕВА ФУНКЦИЯ (функция алгебры логики), функция, аргументы которой, равно как и сама функция, принимают значения из двухэлементного множества (обычно из множества {0, 1}). Булевы функции являются объектами дискретной математики, особенно часто они используются в математической логике, математической кибернетике и в технике. Булевы функции возникли в середине 19 века в математических задачах логики и были названы по имени Дж. Буля.

Одной из таких задач является построение так называемой алгебры высказываний. Для этого каждому высказыванию приписывается одно из двух значений - 0 или 1 (играющие соответственно роль «лжи» или «истины»), и тогда основные логические связки «и», «или», «не», «если... то» можно рассматривать соответственно как «элементарные» булевы функции: хΛу, x v y, x?, x—>у. Тем самым значение любого сложного высказывания, построенного с помощью основных логических связок из заданных высказываний, является булевой функцией от значений этих высказываний. Такая булева функция представляет собой суперпозицию элементарных булевых функций, соответствующих логическим связкам, входящим в сложное высказывание. Позднее выяснилось, что язык булевых функций удобен для описания функционирования дискретных управляющих систем, таких, как контактные схемы, схемы из функциональных элементов, логические сети и др. Эти управляющие системы строятся по определённым правилам из некоторых исходных элементов подобно тому, как сложные высказывания строятся из элементарных. Правила построения указанных управляющих систем, а также функционирование исходных элементов таковы, что функционирование сложных управляющих систем может быть описано с помощью булевых функций. Эти функции используются также в некоторых задачах целочисленного программирования, которые сводятся к решению систем булевых уравнений вида

f₁(х₁,..., x_n) = 0,

f_m (х₁, ... , x_n) = 0,

где f_i – булева функция, i = 1, 2, ..., m. Существуют и другие возможности применения булевых функций в дискретной математике, благодаря чему изучение булевых функций представляет самостоятельный интерес.

При решении различных задач, связанных с булевыми функциями, существенны способы задания булевых функций, среди которых - таблицы, формулы, подмножества вершин n-мерного единичного куба. В последнем случае каждый набор длины n значений аргументов (0 или 1) рассматривается как вершина n-мерного единичного куба, и тогда булева функция от n аргументов может быть задана с помощью подмножества вершин, в которых эта функция принимает значение 1. Это подмножество, выписанное в виде матрицы, строками которой являются наборы значений аргументов булевой функции, называется булевой матрицей. В том случае, когда булева функция описывает функционирование управляющих систем, последнюю также можно рассматривать как средство задания булевой функции. Обычно говорят, что эта управляющая система реализует данную булеву функцию. С реализацией булевой функции теми или иными видами управляющих систем связан большой круг задач, таких, как задачи синтеза, минимизации, контроля и надёжности этих систем. В связи с различными способами задания булевых функций возникают задачи изучения метрических характеристик различных классов булевых функций и связанных с ними геометрических свойств n-мерного единичного куба, а также различных алгебр булевой функции. Система всех классов булевых функций, замкнутых относительно суперпозиций, была описана Э. Постом (1941).

В некоторых случаях возникает необходимость рассматривать частичные, т. е. не всюду определённые, булевы функции, для которых перечисленные задачи имеют свою специфику.

Лит.: Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1966.