Тема 2. Булевая функция

Понятие булевой функции

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

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

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

Каждая функция определяет отображение

,

которое может быть задано таблицей 1.

Таблица 1

7=

- элементы множества декартова произведения, а - элементы множества .

Обозначим через множество всех функций алгебры логики, содержащее также константы 0 и 1.

Теорема 1. Число всех функций из множества , зависящих от переменных , равно .

Входных наборов , а выходных - Докажем это. Входные элементы – это множество , а его мощность , а набор выходных элементов – это булеан этого множества, а булеан (таблица 2).

Таблица 2

0 0 0 1 1 0 1 1		1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1	1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1	1 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1

Обратим внимание на два обстоятельства.

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

, , ,

Следовательно, уже при сравнительно небольших значениях ( ) перебор становится практически невозможнымдаже с использованием вычислительной техники.

2. С ростом числа аргументов таблица, задающая функцию, сильно усложняется. Так, например, уже при сравнительно небольшом числе аргументов, при , таблица становится громоздкой (имеет 1024 строки), а при - практически необозримой.

Введенное выше понятие функции несовершенно, поскольку оно затрудняет рассмотрение функции от большего числа аргументов. Для устранения этого недостатка введем следующее определение.

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

.

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

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

Пример 1. Проверим, является ли переменная фиктивной, для этого построим таблицу 3, используя таблицу 1.

Таблица 3

0 0
0 1
1 0
1 1

Из таблицы видно, что функции = , следовательно, переменная - фиктивная.

Пример 2.Пусть переменная является фиктивной. По таблице 1 построим новую таблицу путем вычеркивания столбца для аргумента и всех строк, где . Получим таблицу 4.

Таблица 4

0 0
0 1
1 0
1 1

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

Пример. Функции ≡ , так как функция получена путем удаления фиктивной переменной .

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

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

1. - константа 0;

2. - константа 1;

3. - тождественная функция;

4. - отрицание ( читается "не ");

5. - конъюнкция и (читается " и "). Вместо знака & употребляется знак ˙ или вообще знак опускается, т. е. пишут . Эту функцию часто называют логическим умножением;

6. - дизъюнкция и (читается " или "). Эту функцию часто называют логическим сложением;

7. - импликация и (читается "из следует "). Эту функцию часто называют логическим следованием;

8. - сложение и по mod 2;

9. или - функция Шеффера (штрих Шеффера).

10. функция Пирса (стрелка Пирса).

Заметим, что

, ,

, если .

Представим результаты перечисленных выше операций в виде таблицы 5.

Таблица 5

Условные обозначения логических элементов, выполняющих указанные операции:

а) б) в)

Пример 2.

Пусть функции, соответствующие формулам из примера 1.

1) Формула строится за три шага. Мы имеем следующие подформулы:

В таблице 6 приводятся соответствующие им функции, которые вычисляются с использованием таблицы 5. Последний столбец определяет функцию Очевидно, что

Таблица 6

0 0 0 1 1 0 1 1

Таблица 7

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

2) Функцию будем строить иным путем (также вытекающим из определения). Для каждого набора найдем (см. таблицу 7).

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