3807 БУЛЕВЫ ФУНКЦИИ

1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Понятие булевой функции
Булева  функция (другое название — функция алгебры логи-ки) — это функция, все аргументы и все значения которой принадле-жат множеству  . Булева функция с   аргументами называется  -местной. Аргументы булевой функции, заданные буквами, например  , называются буквенными аргументами или переменными. Кортеж аргументов — это упорядоченная последовательность значе-ний аргументов булевой функции.
Пример. Для 2-местной булевой функции   есть четыре кортежа аргументов:  ,  ,  ,  . •
Здесь и далее символ • означает конец примера.
Для  -местной булевой функции всего есть   кортежей аргу-ментов, т.е. она имеет   значений. Упорядоченную последователь-ность значений булевой функции при лексикографическом порядке кортежей аргументов (например,  ,  ,  ,…,  ) называем кортежем значений.
Пример. Пусть  ,  ,  ,  . Тогда имеем кортеж значений  . •
Длина кортежа — это число элементов в нем. Так как  -местная булева функция имеет   значений, длина ее кортежа значений равна  . Всего есть   кортежей длины   с элементами из множества  , поэтому всего имеется  различных  -местных булевых функций.
Способы задания булевой функции
Таблица 1.1




0    0    0
0    1    1
1    0    0
1    1    0
Способ 1. Таблица значений, например см. табл. 1.1.
Элементы кортежей аргументов в таблице записываются в лексикографическом порядке.
Способ 2. Кортеж значений. Например, кортеж значений   полностью определяет булеву функцию из табл. 1.1.
Способ 3. Десятичный номер булевой функции с указанием числа ее аргументов — это десятичное значение двоичного числа, полученного при записи кортежа значений справа налево.
Пример. Для 2-местной булевой функции из табл. 1.1 кортеж значений   записываем справа налево как двоичное число   и получаем десятичный номер 2. •
Пример. Для 3-местной булевой функции с десятичным номером 19 получим кортеж значений. Переведем десятичное число 19 в двоич-ную систему счисления:  . Записываем кортеж значений, указывая цифры этого двоичного числа справа налево и добавляя справа нулевые элементы так, чтобы кортеж имел длину  . Полу-чим  . •
Способ 4. Карта Карно . Для этой карты кортежи аргументов записываются не в лексикографическом порядке, а в последовательно-сти кодов Грея .
Последовательность кодов Грея определяется рекуррентно. Для кортежей длины 1 имеем последовательность кодов Грея  ,  . Последовательность кодов Грея для кортежей длины   получается так: записывается последовательность кодов Грея для кортежей длины  , и слева к каждому кортежу добавляется нуль; затем в обратном порядке записывается последовательность кодов Грея для кортежей длины  , и слева к каждому кортежу добавляется единица.
Пример. Имеем последовательность кодов Грея для кортежей длины 2:  ,  ,  ,  . •
Для построения карты Карно  -местной булевой функции каж-дый кортеж аргументов разделяется на два кортежа — левый и пра-вый. Они имеют равную длину при четном  ; левый кортеж имеет длину на единицу больше, чем правый, при нечетном  . Левые кортежи, расположенные в последовательности кодов Грея, соответствуют строкам карты, правые кортежи, также расположенные в последовательности кодов Грея, соответствуют столбцам карты. В карте Карно записываются соответствующие значения булевой функции.
Пример. Таблице значений (табл. 1.2) булевой функции соответ-ствует карта Карно (табл. 1.3). •
Таблица 1.2





0    0    0    0
0    0    1    1
0    1    0    1
0    1    1    0
1    0    0    1
1    0    1    1
1    1    0    0
1    1    1    1
Способ 5.  -мерный единичный куб для  -местной булевой функции. У каждой вершины такого куба указывается соответст-вующий кортеж аргументов, точками отмечаются вершины, соответствующие единичным значениям булевой функции.
1-мерный единичный куб — это единичный отрезок координатной оси. Вершины 1-мерного единичного куба — концы отрезка.
Таблица 1.3




0    1
0    0    0    1
0    1    1    0
1    1    0    1
1    0    1    1
Пример. Если  ,  , то имеем 1-мерный единичный куб на рис. 1.1. •
2-мерный единичный куб — это единичный квадрат на плоско-сти.
Пример. Если  ,  ,  ,  , то имеем 2-мерный единичный куб на рис. 1.2. •


Рис. 1.1
3-мерный единичный куб — это единичный куб в 3-мерном про-странстве.


Рис. 1.2


Рис. 1.3
Пример. Пусть 3-местная булева функция имеет значение 1 только для кортежей аргументов   и  . Тогда имеем 3-мерный единичный куб на рис. 1.3. •









На бумаге можно построить 4-мерный, 5-мерный и т.д. единич-ные кубы [3].
Способ 6. Спектр Фурье   -местной булевой функции. Запи-шем элементы кортежа значений  -местной булевой функции в виде  -компонентного вектора-столбца   (это столбец значений булевой функции в таблице значений в порядке сверху вниз или кортеж значе-ний в порядке слева направо).
Пример. Для кортежа значений   имеем  . •
Спектр Фурье  -местной булевой функции — это  -компонент¬ный вектор-столбец   с целочисленными компонентами, определяемый по формуле   прямого булева преобразования Фурье.
Здесь   — это  -местная матрица Адамара  (квадратная не-вырожденная матрица размером  ), определяемая рекуррентно:  ,  ;  .
Пример. Для 1-местной булевой функции с кортежем значений   имеем  ,  . •
Зная спектр Фурье    -местной булевой функции, можно най-ти вектор-столбец   значений этой функции через обратное булево преобразование Фурье:  . Здесь   — обратная  -местная матрица Адамара.
Способ 7. Булеву функцию можно выразить формулами через другие булевы функции, представив, например, в дизъюнктивной нор-мальной форме, в конъюнктивной нормальной форме, через полином Жегалкина (см. далее).
Существенные и несущественные переменные
Для булевой функции   переменная   называется существенной, если существуют отличающиеся только  -ми элементами два таких кортежа аргументов, для которых эта функция имеет различные значения. В противном случае   называется несущественной переменной.
Булева функция называется существенной, если все ее пере-менные существенные, и несущественной, если хотя бы одна пере-менная несущественная.
Достаточное условие существенности булевой функции: число единичных значений функции нечетное.
Необходимое и достаточное условие несущественности 1-местной булевой функции: 1-мест¬ная булева функция несущественная, если и только если все ее значения равны.
Необходимое и достаточное условие несущественности 2-местной булевой функции: 2-мест¬ная булева функция несущественная, если и только если сумма первого и последнего элементов кортежа значений функции равна сумме двух остальных элементов этого кор-тежа.
Необходимые и достаточные условия несущественности
3-местной булевой функции
3-местная булева функция несущественная, если и только если в соответствующем ей 3-мерном единичном кубе:
1) не отмечена ни одна вершина (т.е. все значения функции нулевые);
2) отмечены только две вершины на одном ребре;
3) отмечены только четыре вершины на одной грани;
4) отмечены только четыре вершины — две на одном ребре и две на параллельном ему ребре другой грани;
5) отмечены только шесть вершин — четыре на одной грани и две на одном ребре другой грани;
6) отмечены все восемь вершин (т.е. все значения функции еди-ничные).
Пример. На рис. 1.4 изображен 3-мерный единичный куб существенной 3-местной булевой функции, на рис. 1.5 — несуществен-ной. •


Рис. 1.4


Рис. 1.5