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

Теория

Булева функция — отображение f: Bn → B, где B — некоторая булева алгебра. Наибольший интерес — двухэлементная алгебра B. Табличный способ задания булевой функции. Примеры – функции одной и двух переменных. Вектор значений булевой функции. Аналитический способ. Язык булевой алгебры: тройка (P, C, F ) (переменные, константы, функциональные символы). Интерпретация языка: сопоставление каждому функциональному символу арности n конкретной булевой функции от n аргументов. Синтаксическое дерево. Подформулы и значение формулы. Неоднозначность соответствия формул и функций. Эквивалентность функций и эквивалентность формул. Теорема о замене подформулы эквивалентной и теорема о замене переменной в эквивалентных формулах. Замыкание множества булевых функций. Замкнутые и полные множества функций.

Пусть задана булева алгебра (B, {∨, ∧,  }). Булева функция — это отображение f: Bn → → B, т.е. функция от n переменных, область изменения каждой из которых есть сама алгебра, причем значениями функции также являются элементы булевой алгебры. Мы остановимся на простейшем случае, имеющем наибольший интерес, когда B — это двухэлементная алгебра B. В этом случае каждый аргумент функции принимает два возможных значения 0 и 1 и сама функция принимает лишь два тех же значения. Подобная функция представляет собой отображение f: Bn → B. Комбинируя такие функции, можно получить любое отображение вида F: Bn → Bm, а в конечном счете булевы функции нескольких переменных для любой конечной булевой алгебры.

*Диаграмма Хассе — изображение в виде неориентированного графа конечного упорядоченного множества. При этом ребрами соединяются вершины, связанные отношением доминирования, причем вершина, изображенная ниже, предшествует расположенной выше.

Таблица 1.1. Булевы функции

Нетрудно подсчитать количество возможных булевых функций вида f: Bn → B: это количество равно 22n (по формуле YX, где X количество элементов области определения, а Y — количество элементов области значений). Поскольку и область определения, и область значений конечны, булевы функции удобно зада- вать с помощью таблиц. Элементы области опре- деления — n-мерные векторы, которые можно рас- сматривать как двоичные записи целых неотрица- тельных чисел от 0 до 2n − 1. Таблица, определя- ющая булеву функцию, может выглядеть следую- щим образом (табл. 1.1). В качестве примера приведем таблицы булевых функций одного переменного (табл. 1.2) и семи наиболее важных функций двух переменных (табл. 1.3).


Таблица 1.2 - 1.3. Булевы функции

Отметим, что булева функция n переменных представляет собой n-арную операцию на булевой алгебре B. В частности, функции двух переменных — это бинарные операции, для которых обычно используют инфиксную форму записи. Так, для функций приведенных в табл. 1.3, ис- пользуют следующие названия и символы операций:

f1(x1, x2) = x1 ∨ x2 = x1 + x2 — дизъюнкция;

f2(x1, x2) = x1 ∧ x2 = x1 · x2 — конъюнкция;

f3(x1, x2) = x1 ⊕ x2 — сложение по модулю 2;

f4(x1, x2) = x1 → x2 — импликация;

f5(x1, x2) = x1 ∼ x2 — эквивалентность;

f6(x1, x2) = x1 | x2 — штрих Шеффера (”не и“);

f7(x1, x2) = x1 ↓ x2 — стрелка Пирсона (”не или“).

Функции f11 и f2 — базовые операции булевой алгебры B, т.е. сложение и умножение (или, по-другому, решеточное объединение и пересечение), но в теории булевых функции традиционно предпочитают названия, указывающие на связь с математической логикой. Сложение по модулю 2 — альтернатива дизъюнкции, превращающая полукольцо B в поле Z2. Штрих Шеффера и стрелка Пирсона — это отрицания соответственно конъюнкции и дизъюнкции, т.е.

x1 |x2 = x1 ∧x2, x1 ↓x2 = x1 ∨x2.

Инфиксная форма записи и представление штриха Шеффера и стрелки Пирсона с помощью операций булевой алгебры указывает еще на один способ представления булевых функций — аналитический. Вообще говоря, любая алгебраическая система содержательна, если для нее удается создать такие формы записи операций и их последовательностей, для которых воз- никают многообразные способы преобразования выражений. Речь идет о понятии ”формула“.

Формула интуитивно понимается как запись с помощью определенного языка некоторой последовательности действий над объектами алгебраической системы.

В самом общем смысле под языком понимают следующее. Рассмотрим некоторое непустое конечное множество V , элементы которого будем называть символами. Произвольные последовательности символов называются словами или цепочками. Слова могут быть любой длины. Вводится специальное слово нулевой длины. Множество всех слов обозначим V ∗. Это множество можно представить как объединение всех декартовых степеней множества V (нулевой, содержащей слово нулевой длины, первой со словами длины 1, второй со словами длины 2 и т.д.). Язык — это некоторое подмножество в V ∗, т.е. некоторый фиксированный набор слов, составленных с помощью элементов множества V , которое называют алфавитом языка.

Конкретный язык формируется правилами, по которым из всех слов, составленных с помощью данного алфавита, выбираются ”правильные“ или допустимые слова. В нашем случае словами должны быть правильно записанные формулы булевой алгебры, а символами — символы переменных, знаков операций и элементов алгебры. Язык формул можно построить в рамках данного выше понятия формального языка. Однако, упрощая изложение, мы снимем ограничение конечности алфавита языка*, полагая, что алфавит может быть счетным множе- ством. Строго формальный математический язык можно ввести следующим образом.

Пусть дана тройка объектов (P, C, F), где P — счетное множество, элементы которого мы будем называть булевыми переменными; C — счетное множество символов, используемых для обозначения элементов алгебраической системы (в данном случае двух элементов 0 и 1 алгебры B), которые мы будем называть константами; F — счетное множество функциональных символов, каждый из которых имеет натуральную характеристику — арность.

Понятие формулы в рассматриваемом языке вводится индуктивно, т.е. указываются кон- кретные способы построения правильных формул на основе уже построенных формул. Базис индукции — изначальный набор элементарных формул, под которыми мы будем понимать элементы множества P ∪ C. Шаг индукции описывает, как из уже построенных формул получаются новые: если X1, X2, . . . , Xn — формулы и f ∈ F — функциональный символ арности n, то f(X1, X2, . . . , Xn) — формула. Кратко сказанное можно сформулировать так:

1) элементы множества P ∪ C — формулы;

2) если X1, X2, . . . , Xn — формулы и f ∈ F — функциональный символ арности n, то f(X1,X2,...,Xn) — формула

Первый пункт определения — базис индукции. Второй (и последующие, если они есть) определяет правила построения новых формул из уже построенных. Это шаг индукции.

В данном случае под алфавитом следует понимать объединение P ∪ C ∪ F, к которому добавлены еще три служебных символа: две круглые скобки и запятая. Но заметим, что при таком подходе нарушается требование конечности алфавита. Мы сознательно идем на такое нарушение, чтобы не усложнять язык формул. Язык булевой алгебры — это множество всех правильно составленных формул.

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

Индуктивное определение формулы позволяет корректно составлять сами формулы, как последовательности символов, но не придает им какого-либо смысла. Чтобы наполнить формулы смыслом, необходимо каждому функциональному символу сопоставить конкретную операцию соответствующей арности (конкретную булеву функции с соответствующим количеством аргументов). Другими словами, необходимо задать отображение множества F в множество всех булевых функций, при котором арность функционального символа совпадает с арностью операции. Кроме того, необходимо фиксировать смысл символов, предназначенных для обозначения констант, т.е. задать отображение множества C в алгебру B. Два указанных отображения составляют интерпретацию языка.

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

Следует учесть еще одно обстоятельство. Общепринятым является запись бинарных опе- раций не в виде f(x1,x2), а в виде x1 f x2 (как правило, со специальным символом операции). Поэтому в наш язык следует ввести символы инфиксных операций, а в качестве шага индукции ввести дополнительное правило:

3) если X1 и X2 — формулы, то и слова (X1 +X2), (X1 ·X2), (X1 ⊕X2), (X1 →X2), (X1 ∼ X2), (X1 | X2), (X1 ↓ X2) являются формулами.

При использовании инфиксной формы записи бинарных операций в формулах оказывается большое количество пар скобок, что затрудняет восприятие таких формул. Скобки нужны для того, чтобы однозначно определить последовательность шагов, которые приводят от элементарных формул к конечной формуле. Чтобы сократить количество скобок и сделать формулы более читаемыми, используют правило приоритетов, согласно которому каждой бинарной операции с инфиксной формой записи присваивается приоритет — некоторое натуральное число. Сперва выполняются операции с большим приоритетом, затем с меньшим. Среди операций с одинаковым приоритетом в первую очередь выполняется та, знак которой находится левее. Мы будем использовать инфиксную форму на практике, как более привычную и удобную, но в теоретических рассуждениях с целью упрощения ограничимся лишь префиксной формой записи операций.

Рассматривая различные множества F функциональных символов и различные их интерпретации, мы можем строить различные схемы построения формул, которые различаются набором базовых функций. Например, в качестве базовых могут рассматриваться три базовые операции булевой алгебры: сложение, умножение и отрицание, но могут быть и другие варианты (например, сложение по модулю 2 и умножение — базовые операции в Z2).

Любая корректная формула либо элементарная, либо получена в результате шага индукции, т.е. с помощью функционального символа f и некоторого набора формул X1, ..., Xn. Каждая из формул Xi в свою очередь либо элементарная формула, либо получена с помощью своего функционального символа fi и некоторого набора формул XI1, . . . , Xini и т.д. Двигаясь от конечной формулы, мы за конечное число шагов придем к элементарным формулам — переменным и константам. Представленный анализ формулы называется синтаксическим. Его результаты можно представить в виде ориентированного дерева. Корень дерева — сам формула, вершины глубины 1, формулы Xi и т.д. Каждому листу дерева соответствует переменная или константа. Вершинам, не являющимся корнем соответствуют формулы, которые входят как составная часть в анализируемую формулу. Они называются подформулами.

Пример 1.1. Рассмотрим формулу f1(f2(x1, x2), f3(x2), f4(x1, f2(x3), x4)). Эта формула получена с помощью функционального символа f1 арности 3. Подформулами глубины 1 являются f2(x2), f3(x2) и f4(x1,f2(x3),x4). Первая из них имеет подформулу — переменную x2, вторая имеет также одну подформулу — переменную x2, а третья — уже три подформулы: первая и третья — переменные x1 и x4, вторая подформула — сложная подформула f2(x3). В резуль- тате получаем дерево синтаксического анализа, представленное на рис. 1.2. Высоту дерева (в данном случае 3) называют сложностью формулы.

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


Рис. 1.2. Булевы функции

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

В формулу, как правило, входят переменные (булевы переменные). Но есть формулы, в которых элементарные составляющие — все константы. Такие формулы имеют определенное значение, соответствующее конкретному объекту алгебраической системы (т.е. в нашем случае 0 и 1). Если в формулу входят переменные, то ее значение не определено. Однако если в формуле заменить каждую переменную константой (т.е. дать переменной конкретное значение), получим новую формулу, имеющую значение. Таким образом, каждому набору значений переменных, входящих в формулу, соответствует конкретное значение формулы.

Это обстоятельство позволяет рассматривать формулу как форму записи функции. Однако надо иметь в виду, что с помощью одной и той же формулы можно задавать различные функции. Например, формула x−t определяет функции f(x,t = x−t и f(t,x) = x−t, а также, например, функцию f (x, y, t) = x − t.

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

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

На практике мы часто пользуемся эквивалентными преобразованиями. Например, если f1 — булева функция из табл. 1.3, то f1(x1,x2) = f1(x2,x1). Знак равенства означает, что формулы задают одну и ту же функцию, т.е. эквивалентны. Вообще говоря, знак равенства в данном контексте рассматривается как знак тождества, т.е. формулы дают одно и то же значение при любых значениях входящих в равенство переменных. Если состав переменных слева и справа один и тот же, то тождество как раз и означает, что левая и правая части задают одну и ту же функцию. Однако возможно и такое равенство x ⊕ x = 0, также верное при любых значениях неизвестных. Но в левую часть входит переменная x, а в правой части вообще стоит константа. Левая часть задает функцию двух переменных, а правая часть — нульарную операцию (кон- станту). Надо либо отказаться признать такое равенство, либо установить эквивалентность каких-либо функций. Второе более удобно.

Две формулы* Φ[x1,...,xn] и Ψ[y1,...,ym] с наборами переменных x1, ..., xn и y1, ..., ym соответственно назовем эквивалентными, если равенство Φ[x1, . . . , xn] = Ψ[y1, . . . , ym] остается верным при любых значениях всех переменных. Если наборы переменных не совпадают, то значение одной из формул или обеих не зависит от значений некоторых переменных. Такие переменные назовем фиктивными. Переменную, не являющуюся фиктивной, будем называть существенной. У двух эквивалентных формул существенные переменные должны быть общими, хотя часть общих переменных может быть и фиктивными.

*Использование квадратных скобок подчеркивает, что это не обозначение функции. Здесь имеется в виду формула, обозначенная как Φ, все переменные которой входят в указанный список переменных.

Теорема 1.1. Если формулы Φ[x1, . . . , xn] и Ψ[y1, . . . , ym] эквивалентны, то замена в каждой из них всех вхождений какой-либо из переменных произвольной формулой приведет к двум новым формулам, эквивалентным между собой.

◀ Объединим списки переменных у формул и напишем равенство

Φ[z1,...,zk] = Ψ[z1,...,zk].

Предположим, что все вхождения переменной zk заменены формулой ∆[u1, . . . , ul]. Получим формулы Φ [z1,...,zk−1,u1,...,ull] и Ψ [z1,...,u1,...,ul]. Обозначения исходят из того, что переменные формулы ∆ не входят в формулы Φ и Ψ. На самом деле это допущение несущественно и служит лишь упрощению рассуждений.

Задав произвольные значения переменным z1, . . . , zk−1, u1, . . . , ul, мы получим для переменной zk значение ∆(u1, . . . , ul). Проверка равенства значений двух формул равносильна проверке исходного равенства, в котором в качестве значения переменной zk взято ∆(u1, . . . , ul). Поскольку исходное равенство верно, то и после подстановки равенство останется верным.

Теорема 1.2. Если в формуле заменить одну из подформул эквивалентной, то новая фор- мула будет эквивалентна исходной.

◀ Пусть дана формула Φ[x1,...,xn], в которую входит подформула Ψ[x1,...,xn] (мы можем считать, что подформула включает все переменные исходной формулы, рассматривая недостающие как фиктивные). Заменим подформулу Ψ новой переменной z, которая не входит в список x1, . . . , xn. Получим новую формулу Γ[x1, . . . , xn, z], связь которой с исходной формулой можно записать в виде

Φ[x1,...,xn] = Γ[x1,...,xn,z]Дискретная математикаz=Ψ [x1,...,xn]

Замена формулы Ψ[x1, . . . , xn] эквивалентной формулой Ψ [x1, . . . , xn] приведет к новой формуле

Γ[x1,...,xn,z]z=Ψ [x1,...,xn]

Надо показать, что при любых значениях неизвестных верно равенство

Γ[x1,...,xn,z] z=Ψ[x1,...,xn] = Γ[x1,...,xn,z] z=Ψ[x1,...,xn]

Но нетрудно заметить, что, задавая значения неизвестных, мы в силу эквивалентности формул Ψ и Ψ получим один и тот же набор значений переменных в формуле Γ. Значит, в обеих частях равенства мы получим одно и то же значение.

В функции f(x1,...,xn) назовем i-й аргумент фиктивным аргументом, если значение функции не зависит от значения этого аргумента, т.е. функции

f(x1,...,xi−1,0,xi+1,...,x1) и f(x1,...,xi−1,1,xi+1,...,xn)
совпадают. Вместо двух этих равных друг другу функций можно рассмотреть функцию

f(x1,...,xi−1,xi+1,...,xn) = f(x1,...,xi−1,0,xi+1,...,xn),

у которой количество аргументов на единицу меньше. Такое преобразование назовем удалением фиктивного аргумента.

Возможно и противоположное преобразование — введение фиктивных переменных, а именно:

gˆ(x1,...,xi−1,xi,xi+1,...,xn) = g(x1,...,xi−1,xi+1,...,xn).

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

Нетрудно проверить, что введенное отношение на множестве булевых функций действительно является отношением эквивалентности. Точно так же на множестве все булевых формул эквивалентность (в смысле равенства значений при любых значениях переменных) — это отношение эквивалентности.

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

Пусть F — некоторое множество функций. Его замыканием назовем множество [F] всех булевых функций, которые представимы формулами с базисом F (формулами над множеством F). Если замыкание множества F совпадает с F, то это множество называется замкнутым. Множество F называется полным, если его замыкание совпадает с множеством всех булевых функций.

Термин ”полный базис“ как раз и означает, что любую булеву функцию можно записать аналитически, используя в качестве исходных функции базиса. Замыкание множества — совокупность всех функций, которые могут быть представлены формулами над этим множеств. Замкнутое множество F — такое множество, которое не может быть расширено добавлением функций, представимых формулами над F.

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

1) [∅] = ∅;
2) [[X]] = [X];
3) X ⊂ [X];
4) [X] ∪ [Y ] ⊂ [X ∪ Y ].

Первое свойство носит формальный характер. Второе вытекает из конечности процедуры построения любой формулы: достаточно, следуя по дереву синтаксического анализа, последова- тельно заменять функции из [X] их формулами над X. Третье и четвертое свойства очевидны.

Из четвертого свойства вытекает, что если X ⊂ Y , то [X] ⊂ [Y ]. Действительно, включение X ⊂ Y равносильно равенству X ∪ Y = Y. Если X ⊂ Y, то в силу свойства 4 заключаем, что [X] ∪ [Y] ⊂ [X ⊂ Y] = [Y]. Следовательно,[X] ⊂ [Y].

Из указанных свойств замыкания вытекает следующее утверждение.

Теорема 1.3. Если F — полное множество булевых функций, каждая из которых представима формулой над множеством G, то и G — полное множество.

◀ Так как каждая функция из F есть формула над G, то F ⊂ [G]. Из свойств замыкания вытекает, что

[F] ⊂ [[G]] = [G].

Но поскольку [F] совпадает с множеством всех булевых функций, то и [G] совпадает с множеством всех булевых функций, т.е. G — полный базис. ▶