Булева функция
Бу́лева фу́нкция (функция алгебры логики), функция, аргументы которой, равно как и сама функция, принимают значения из двухэлементного множества (обычно из множества {}). Булевы функции являются объектами дискретной математики, особенно часто они используются в математической логике, математической кибернетике и в технике. Булевы функции возникли в середине 19 в. в математических задачах логики и были названы по имени Дж. Буля.
Одной из таких задач является построение т. н. алгебры высказываний. Для этого каждому высказыванию приписывается одно из двух значений – или (играющие соответственно роль «лжи» или «истины»), и тогда основные логические связки «и», «или», «не», «если… то» можно рассматривать соответственно как «элементарные» булевы функции: . Тем самым значение любого сложного высказывания, построенного с помощью основных логических связок из заданных высказываний, является булевой функцией от значений этих высказываний. Такая булева функция представляет собой суперпозицию элементарных булевых функций, соответствующих логическим связкам, входящим в сложное высказывание. Позднее выяснилось, что язык булевых функций удобен для описания функционирования дискретных управляющих систем, таких, как контактные схемы, схемы из функциональных элементов, логические сети и др. Эти управляющие системы строятся по определённым правилам из некоторых исходных элементов подобно тому, как сложные высказывания строятся из элементарных. Правила построения указанных управляющих систем, а также функционирование исходных элементов таковы, что функционирование сложных управляющих систем может быть описано с помощью булевых функций. Эти функции используются также в некоторых задачах целочисленного программирования, которые сводятся к решению систем булевых уравнений вида
где – булева функция, . Существуют и другие возможности применения булевых функций в дискретной математике, благодаря чему изучение булевых функций представляет самостоятельный интерес.
При решении различных задач, связанных с булевыми функциями, существенны способы задания булевых функций, среди которых – таблицы, формулы, подмножества вершин -мерного единичного куба. В последнем случае каждый набор длины значений аргументов ( или ) рассматривается как вершина -мерного единичного куба, и тогда булева функция от аргументов может быть задана с помощью подмножества вершин, в которых эта функция принимает значение . Это подмножество, выписанное в виде матрицы, строками которой являются наборы значений аргументов булевой функции, называется булевой матрицей. В том случае, когда булева функция описывает функционирование управляющих систем, последнюю также можно рассматривать как средство задания булевой функции. Обычно говорят, что эта управляющая система реализует данную булеву функцию. С реализацией булевых функций теми или иными видами управляющих систем связан большой круг задач, таких, как задачи синтеза, минимизации, контроля и надёжности этих систем. В связи с различными способами задания булевых функций возникают задачи изучения метрических характеристик различных классов булевых функций и связанных с ними геометрических свойств -мерного единичного куба, а также различных алгебр булевых функций. Система всех классов булевых функций, замкнутых относительно суперпозиций, была описана Э. Постом (1941).
В некоторых случаях возникает необходимость рассматривать частичные, т. е. не всюду определённые, булевы функции, для которых перечисленные задачи имеют свою специфику.