105

Глава 3

Булевы функции (БФ)

3.1 Определения и примеры

Определение. Булевы константы 0 и 1 образуют булево множество B = f0; 1g: Булева переменная – переменная, которая может принимать значение из B:

Булева функция (БФ) n переменных – это отображение

f : Bn 7!B:

Булеву функцию можно представить в виде

y= f(x1; x2; : : : ; xn);

вкотором каждая булева переменная xi и функция f могут принимать одно из двух возможных значений 0 или 1: Зна-

чение функции соответствует набору значений переменных ha1 ¢ ¢ ¢ ; ani 2 Bn, где ai есть фиксированное значение пере-

менной xi, ai 2 f0; 1g;

f(a1; ¢ ¢ ¢ ; an):

106 Глава 3. Булевы функции (БФ)

Булев вектор (набор) ha1 ¢ ¢ ¢ ; ani 2 Bn будем изображать в виде последовательности значений булевых переменных (компонент вектора) без скобок и запятых (для сокращения записи) a1a2 ¢ ¢ ¢ an: Длина вектора – число его компонент, а вес вектора – число единиц в нем.

Пример 3.1. Длина вектора ~a = a1a2a3a4a5 = 10101 равна 5, а его вес – 3. J

Теорема 3.1 jBnj = 2n (число различных векторов длины n равно 2n).

До к а з а т е л ь с т в о .

Векторы упорядочены отношением доминирования 4: для

~

векторов ~a = a1 : : : an; b = b1 : : : bn;

Векторы разных размерностей нельзя сравнивать по отношению доминирования.

Булев вектор можно рассматривать как двоичное представление целого неотрицательного десятичного числа. Если компоненты вектора ~a = a1 : : : an интерпретировать как числа 0 и 1, то десятичное число a 2 f0; 1; : : : ; 2n ¡ 1g есть

Xn

a = ai ¢ 2n¡i:

i=1

Например, вектор ~a = 1011 представляет число

1 ¢ 23 + 0 ¢ 22 + 1 ¢ 21 + 1 ¢ 20 = 8 + 0 + 2 + 1 = 11:

В десятичном представлении векторы упорядочены в линейном порядке.

Множество всех булевых функций n переменных обозначим

Pn = ffjf : f0; 1gn 7!0f; 1gg:

Теорема 3.2

jPnj = 22n :

Д о к а з а т е л ь с т в о . Число булевых векторов длины n (число n-кортежей над двухэлементным множеством f0; 1g)

равно 2n. В свою очередь, jPnj есть число 2n-кортежей над f0; 1g, то есть jPnj = 22n :

Булеву функцию можно представить таблицей с 2n строками и n + 1 столбцами. В первых n столбцах перечисляются наборы значений аргументов a1 : : : an в лексикографическом порядке (по возрастанию чисел,

представленных векторами, от 0 до 2n¡1), а в (n+1)-м столбце

– значения функции для этих аргументов.

Таблица 3.1. Табличное представление БФ

Слева в таблице добавлен столбец с десятичными номерами векторов.

Если интерпретировать элементы множества f0; 1g как истинностные значения "ложь” и "истина” некоторых высказываний, то булеву функцию можно считать некоторым сложным высказыванием. При этом истинностное значение f зависит от истинностных значений переменных.

С другой стороны, булеву функцию можно считать n- арной операцией на множестве f0; 1g. Таким образом, понятие логических операций :; ^; _; !; $ является частным случаем общего понятия логической операции. Таблицу, представляющую булеву функцию, можно считать таблицей истинности этой операции.

Примеры 3.3. 1. При n = 0 булевых функций две (220 = 21): константа 0 и константа 1.

2. Булевы функции одной переменной.

При n = 1 число булевых функций равно 4 (221 = 22):

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

f0(x) – 0, нуль;

f1(x) – тождественная функция;

f2(x) – : x,отрицание, инверсия (другие обозначения: x;¹ » x);

f3(x) – 1, единица.

3. Булевы функции двух переменных.

При n = 2 число булевых функций равно 16 (222 = 24):

Таблица 3.3. Булевы функции двух переменных

Обозначения и названия некоторых функций двух переменных:

f0 – 0, нуль;

f1 – x1 ^ x2, конъюнкция (другие обозначения: &; ¢);

f6 – x1 © x2, исключающее "или”, сложение по модулю 2; f7 – x1 _ x2, дизъюнкция, ( другое обозначение +);

f8 – x1 # x2, стрелка Пирса;

f9 – x1 $ x2, эквиваленция (другие обозначения: »; ´); f13 – x1 ! x2, импликация (другие обозначения: ¾; )); f14 – x1jx2, штрих Шеффера;

f15 – 1, единица.

4. Мажоритарная функция (функция голосования, принимает значение 1, если "за” проголосовало большинство).

Таблица 3.4. Мажоритарная функция

Булевы функции с числом переменных n 6 2 называются

элементарными.

Область определения БФ n переменных множество Bn = f0; 1gn можно интерпретировать геометрически как булев n-мерный куб (гиперкуб). Вершинами гиперкуба являются n-мерные булевы векторы, упоря-

доченные отношением доминирования. Гиперкуб, как упорядоченное множество, можно представить с помощью диаграммы Хассе. Булевой функции ставится в соответствие то подмножество A µ Bn вершин куба, на которых функция равна 1:

Пример 3.4.

Рис. 3.1. Булевы гиперкубы.

Мажоритарной функции соответствует множество

f011; 101; 110; 111g на трехмерном кубе, сложению по модулю 2 – множество f01; 10g на двухмерном кубе. Функции 0 соответствует пустое множество ?, а функции 1 – множество всех вершин гиперкуба Bn: J

Представление вектором значений. Так как множество векторов упорядочено от 0 до 2n ¡ 1, то для представления функции достаточно задать значения функции в этом порядке.

Пример 3.5. Мажоритарная функция трех переменных задается вектором 00010111, сложение по модулю 2 (функция двух переменных) – вектором 0110.

Можно также перечислить десятичные номера тех векторов, на которых булева функция принимает значение 1: Для мажоритарной функции трех переменных f = f3; 5; 6; 7g; для сложения по модулю 2 (функции двух переменных) – f = f1; 2g: J

Представление Определение. Суперпозицией булевых

БФ формулами функций f0 и f1; : : : ; fm называется функция

f(x1; : : : ; xn) = f0(f1(x1; : : : ; xn); : : : ; fm(x1; : : : ; xn)):

Выберем некоторое подмножество функций n переменных x1; : : : ; xn