Булевы функции и их представления

Булевы функции от n переменных

Булевы функции В отечественной литературе их также часто называют функциями алгебры логики. названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция - константа !). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через B двухэлементное множество {0,1}. Тогда$$B^n=\underbrace{B\times B \times \ldots \times B}_{n}$$ это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x1, xn): Bn -> B . Каждый из ее аргументов xi, 1 <= i <= n , может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из Bn также может быть 0 или 1. Обозначим через $$\codecal{P}_n$$ множество всех булевых функций от n переменных. Нетрудно подсчитать их число.

Теорема 3.1. $$|\codecal{P}_n | = 2^{2^n}$$.

Доказательство.Действительно, по теореме 1.1 число функций из k -элементного множества A в m -элементное множество B равно mk . В нашем случае B={0, 1}, а A = Bn . Тогда m=2 и k= |Bn| = 2n . Отсюда следует утверждение теоремы.

Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим геометрическое и табличное представления, а также представление с помощью логических формул. В лекции 4 будет показано, как булевы функции можно представлять с помощью формул специального вида - дизъюнктивных и конъюнктивных нормальных форм и многочленов Жегалкина. Кроме того, в лекциях 1 и 2 (курс "Введение в схемы, автоматы и алгоритмы") будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений.

Геометрическое представление

Bn можно рассматривать как единичный n-мерный куб. Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы Bn при n=3,4.

При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству $$A \subseteq B_{n}$$ соответствует его характеристическая функция

Например, верхней грани куба B3 (ее вершины выделены на рисунке) соответствует функция f: f(0,0,1)=f(0,1,1)=f(1,0,1)=f(1,1,1) =1 и f(0,0,0)=f(0,1,0)=f(1,0,0)=f(1,1,0) =0. Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество Af={(x1, ..., xn)|f(x1, ..., xn)=1} вершин Bn . Например, функция, тождественно равная 0, задает пустое множество $$\varnothing \subset B^{n}$$, а функция, тождественно равная 1, задает множество всех вершин Bn .

Табличное представление

Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции f(x1, ..., xn) имеет n+1 столбец. В первых n столбцах указываются значения аргументов x1, ..., xn , а в (n+1) -ом столбце значение функции на этих аргументах - f(x1, ..., xn) .

Наборы аргументов в строках обычно располагаются в лексикографическом порядке:

$$(\alpha _{1}, \dots , \alpha _{n}) < (\beta _{1}, \dots , \beta _{n}) \Leftrightarrow$$ существует такое $$i \in [1,n]$$, что при $$j < i \alpha _{j} = \beta _{j}$$, а $$\alpha _{i} < \beta _{i}$$.

Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, $$\dots,$$ а последняя - 2n-1 .

При больших n табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблица с 1024 строками. Но для малых n оно достаточно наглядно.

Булевы функции от 1-ой и 2-х переменных

Представим вначале в табличном виде все булевы функции от 1-ой переменной. Как мы знаем, их всего четыре.

В этой таблице представлены следующие функции:

В следующей таблице представлены все 16 функций от 2-х переменных.

Многие из этих функций часто используются в качестве "элементарных" и имеют собственные обозначения.

В качестве элементарных функций будем также рассматривать 0-местные функции-константы 0 и 1.

Отметим, что функции f1(x1,x2) и f2(x1,x2) фактически не зависят от значений обоих аргументов, функции f3(x1,x2) и f4(x1,x2) не зависят от значений аргумента x2, а функции f5(x1,x2) и f6(x1,x2) не зависят от значений аргумента x1.

Определение 3.1. Функция f(x1,..., xi,..., xn) не зависит от аргумента xi, если для любого набора значений $$\sigma _{1},\dots ,\sigma _{i-1}> \sigma _{i+1},\dots , \sigma _{n}$$ остальных аргументов f имеет место равенство

Такой аргумент xi называется фиктивным. Аргументы, не являющиеся фиктивными, называются существенными.

Функции f1(x1,..., xn) и f2(x1,...,xm) называются равными, если функцию f2 можно получить из функции f1 путем добавления и удаления фиктивных аргументов.

Например, равными являются одноместная функция f3(x1) и двухместная функция f3(x1,x2) , так как вторая получается из первой добавлением фиктивного аргумента x2 . Мы не будем различать равные функции и, как правило, будем использовать для обозначения равных функций одно и то же имя функции. В частности, это позволяет считать, что во всяком конечном множестве функций все функции зависят от одного и того же множества переменных.

Формулы

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

Пусть $$\codecal{B}$$ - некоторое (конечное или бесконечное) множество булевых функций. Зафиксируем некоторое счетное множество переменных V={X1, X2, ...} . Определим по индукции множество формул над $$\codecal{B}$$ с переменными из V. Одновременно будем определять числовую характеристику $$dep(\Phi )$$ формулы $$\Phi,$$ называемую ее глубиной, и множество ее подформул.

Определение 3.2.

Каждой формуле $$\Phi (X_{1},\dots , X_{n})$$ сопоставим булеву функцию, которую эта формула задает, используя индукцию по глубине формулы.

Базис индукции. Пусть $$dep(\Phi )=0$$. Тогда $$\Phi = X_{i} \in V$$ или $$\Phi =c \in$$ $$\codecal{B}$$. В первом случае $$\Phi$$ задает функцию $$f_{\Phi }(X_{i})=X_{i}$$, во втором - функцию, тождественно равную константе c.

Шаг индукции. Пусть $$\Phi$$ - произвольная формула глубины $$dep(\Phi )= k+1$$. Тогда $$\Phi (X_{1},\dots , X_{n})= f_{i}(A_{1},\dots , A\_ m)$$, где $$f_{i} \in$$ $$\codecal{B}$$ и A1, ..., Am - формулы, для которых max1 <= i <= m{dep(Ai)}=k . Предположим (по индукции), что этим формулам уже сопоставлены функции g1(X1,..., Xn), ... , gm(X1,..., Xn) . Тогда формула $$\Phi$$ задает функцию $$f_{\Phi }(X_{1},\dots , X_{n}) = f_{i}(g_{1}(X_{1},\dots , X_{n}), \dots , g_{m}(X_{1},\dots , X_{n}))$$.

Далее мы будем рассматривать формулы над множеством элементарных функций $$\codecal{B}_e=\{ 0, 1, \neg, \wedge, \vee, \rightarrow, +, \sim,\ |, \downarrow \} $$. Все эти функции, кроме констант, называются логическими связками или логическими операциями. При этом для 2-местных функций из этого списка будем использовать инфиксную запись, в которой имя логической связки помещается между 1-ым и 2-ым аргументами. Тогда определение формулы над $$\codecal{B}_e$$ имеет следующий вид.

Определение 3.3.

Тогда выражения $$\neg \Phi _{1}$$ и $$(\Phi _{1} \hat{} \Phi _{2})$$ являются формулами. При этом $$dep(\neg \Phi _{1})=1 + dep( \Phi _{1})$$, а $$dep((\Phi _{1} \hat{} \Phi _{2}))= 1 + max \{ dep(\Phi _{1}), dep(\Phi _{2})\}$$.

В соответствии с этим определением выражения $$\Phi _{1}(X_{1},X_{2}) = \neg (X_{1} \wedge \neg X_{2})$$ и $$\Phi _{2}(X_{1},X_{2},X_{3}) = ( (X_{1} \vee \neg \neg X_{2})\to$$ $$(X_{3} \sim (X_{1} \downarrow \neg X_{2})))$$ являются формулами. Глубина $$\Phi _{1}$$ равна 3, а глубина $$\Phi _{2}$$ равна 4. Выражения же $$\neg X_{1} +( \neg X_{2} \vee X_{3})$$, $$(X_{1} \neg \wedge X_{2})$$ и (X1 + X2 + X3) формулами не являются (почему?).

Для определения функции, задаваемой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующей подформулой. Например, для формулы $$\Phi _{2}$$ функция $$f_{\Phi 2}$$ задается выделенным столбцом $$\to$$ следующей таблицы.

Булевы функции и логика высказываний

Как мы уже отметили, Дж. Буль ввел булевы функции для решения логических задач. В логике под высказыванием понимают некоторое повествовательное предложение, относительно которого можно сказать, истинно оно или ложно. Логика высказываний занимается выяснением истинности тех или иных высказываний, связью между истинностью различных высказываний и т.п.

Булевы функции могут служить полезным инструментом при решении многих логических задач.

Каждую переменную можно рассматривать как некоторое элементарное высказывание, принимающее одно из двух значений: 1 (истина) или 0 (ложь). Сложным высказываниям сооответствуют формулы, построенные из элементарных высказываний с помощью логических связок. Вычисляя значения задаваемых ими функций, можно устанавливать зависимости истинностных значений сложных высказываний от значений входящих в них элементарных высказываний. Рассмотрим следующий пример.

Пример 3.1.Пусть известно, что в дорожном проишествии участвовали три автомобиля с водителями A, B и C. Свидетели проишествия дали следующие показания:

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

Для ответа на эти вопросы введем три переменные, соответствующие следующим высказываниям: X1 : " виновен A ", X2 : " виновен B " и X3 : " виновен C ". Тогда показания 1-го свидетеля описываются формулой $$\Phi _{1}=(X_{1} \to (\neg X_{2} \vee \neg X_{3}))$$, показания 2-го свидетеля - $$\Phi _{2}= (\neg X_{3} \to (( X_{1} \vee X_{2}) \wedge \neg (X_{1} \wedge X_{2})))$$, а 3-го свидетеля - $$\Phi _{3}= ((X_{1} \wedge X_{2})\setminus vee ((X_{1} \wedge X_{3}) \vee ( X_{2} \wedge X_{3})))$$. Показаниям всех трех свидетелей соответствует конъюнкция этих формул $$\Psi = (\Phi _{1} \wedge (\Phi _{2} \wedge \Phi _{3}))$$. Составим таблицы значений для функций $$f_{\Phi i} (i=1,2,3) ,$$ а затем - для $$f_{\Psi }$$.

Из этой таблицы следует, что $$f_{\Psi }(X_{1},X_{2},X_{3})=1$$ на двух наборах: (X1=0, X2=1, X3=1) и (X1=1, X2=0, X3=1) (строки с этими наборами подчеркнуты). Поскольку в обоих случаях X3=1 , можно сделать вывод, что С является одним из виновников проишествия. Однозначно определить второго виновника полученная от свидетелей информация не позволяет, так как в одном случае им является А, а в другом - В.

Важную роль в логике играют понятия тождественно истинной и выполнимой формулы.

Определение

Булева формула $$\Phi$$ называется тождественно истинной, если она истинна при любых значениях входящих в нее переменных, т.е. функция $$f_{\Phi }$$ тождественно равна 1.

Булева формула $$\Phi$$ называется выполнимой, если существует такой набор значений переменных, на котором она истинна, т.е. функция $$f_{\Phi }$$ равна 1 хоть на одном наборе аргументов.

Как проверить тождественную истинность или выполнимость формулы $$\Phi?$$ На первый взгляд кажется, что ответ прост - построим по $$\Phi$$ таблицу для функции $$f_{\Phi }$$, и, если в столбце значений стоят только единицы, то заключаем, что $$\Phi$$ тождественно истинна, если там есть хоть одна единица, то $$\Phi$$ выполнима. К сожалению, этот способ пригоден только для формул с небольшим числом переменных. Уже для нескольких десятков и сотен переменных он не годится из-за большого размера получающейся таблицы - нетрудно подсчитать, что число 290 превосходит количество атомов во всей видимой вселенной.

В математической логике построены аксиоматические системы, позволяющие формализовать человеческие рассуждения о выводимости одних тождественно истинных формул из других (см., например, [15]). В некоторых случаях они позволяют доказать тождественную истинность достаточно длинных формул, имеющих регулярную структуру. Но в общем случае и они практически не применимы для произвольных формул с большим числом переменных.

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

Задачи

Задача 3.1. Какие подмножества вершин B4 соответствуют следующим булевым функциям:

Задача 3.2. Построить таблицы значений для следующих булевых функций:

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

$$\Psi _{1}= ((X_{1} \to \neg X_{3}) \vee (X_{2} + X_{3}))$$ ;

$$\Psi _{2} =(\neg (X_{1} | X_{2}) ~ (\neg X_{1} \wedge X_{2}))$$ ;

$$\Psi _{3} = ((X_{2} + \neg X_{3}) \wedge ((X_{1} \vee X_{2}) \to (X_{1} \sim \neg X_{3})))$$.

Задача 3.4. Назовем два набора $$\alpha =(\alpha _{1}, \dots , \alpha _{n})\in B^{n}$$ и $$\beta =(\beta _{1}, \dots , \beta _{n})\in B^{n}$$ соседними}, если они находятся в соседних строках таблицы для функции от n переменных, т.е. представляют двоичные записи чисел $$i_{\alpha }$$ и $$i_{\beta }$$, для которых $$| i_{\alpha } - i_{\beta }| = 1$$.

Найти число функций в $$\codecal{P}_n $$, которые на любой паре соседних наборов принимают

Задача 3.5. Назовем два набора $$\alpha =(\alpha _{1}, \dots , \alpha _{n})\in B^{n}$$ и $$\beta =(\beta _{1}, \dots , \beta _{n})\in B^{n}$$ противоположными}, если для всякого i $$\alpha _{i}= 1 \Leftrightarrow \beta _{i}=0$$ (и, следовательно, $$\alpha _{i}= 0 \Leftrightarrow \beta _{i}=1$$ ).

Найти число функций в $$\codecal{P}_n $$, которые на любой паре противоположных наборов принимают разные значения.

Задача 3.6. Пусть n =2k. Назовем набор $$\alpha =(\alpha _{1}, \dots , \alpha _{n})\in B^{n}$$ парным,} если для любого i=1, ..., k $$\alpha _{i} = \alpha \_ \{ k+i\}$$,т.е. $$\alpha =\alpha ^{\wedge} ' \alpha ^{\wedge}'$$ для некоторого набора $$\alpha ^{\wedge} '$$ размера k.

Найти число функций в $$\codecal{P}_n$$, которые на всех парных Наборах принимают одинаковое значение.

Задача 3.7. Администратор базы данных обнаружил, что одна или несколько из трех записей его базы A, B и C ошибочна. Он установил, что

Опишите знания администратора в виде булевой формулы. Может ли он сделать вывод, что запись B ошибочна? Можно ли достоверно утверждать, что ошибочная запись единственна?

Задача 3.8. Программист Петр использовал в своей программе три целочисленные переменные x, y и z. В определенном месте программы он поместил условный оператор:

IF (x*y >= 0)OR (x*z >= 0) THEN x=1 ELSE x=2;

Проанализировав свою программу, Петр установил, что перед выполнением этого Оператора выполнены следующие условия:

Опишите знания Петра в виде булевой формулы. Может ли он оптимизировать программу, заменив указанный условный оператор на присвоение x=1 или на присвоение x=2? Если "да", то на какое?

Задача 3.9. Комитет состоит из пяти членов. Решения принимаются большинством голосов, однако, если председатель голосует "против", то решение не принимается. Постройте формулу, зависящую от 5 переменных X1, X2,X3, X4, Y ( $$X_{i}=1 \Leftrightarrow i$$ -ый член комитета голосует "за", $$Y=1 \Leftrightarrow$$ председатель "за"), значение которой равно 1 тогда и только тогда, когда в результате голосования решение принимается.