П. 4. Булевы функции

Названы по имени англ. математика Джорджа Буля (1815-1864), младшая дочь которого Этель Лилиан Войнич – автор романа «Овод».

Булева функция одной логической переменной.

Рассмотрим множество D, состоящее всего из двух элементов. Для простоты и определенности D = {0, 1}. Будем рассматривать числовые функции f(x), определенные на D, но не все, а те, которые принимают только два значения: 0 и 1.

Определение 28. Независимая переменная x, которая принимает всего два значения, называется двоичной, или логической переменной.

Определение 29. Функция логической переменной, принимающая только два значения, называется булевой функцией одной логической переменной (БФОЛП) или просто булевой функцией.

Для БФОЛП можно построить таблицы истинности. (и – 1, л – 0).

Примеры.

Существуют только четыре булевы функции одной логической переменной:

1. тождественная функция: f(x) = x

2. отрицание: – не x.

3. и 4) функции, отображающие множество D = {0, 1} в себя. Это постоянные

Построим их таблицы:

1)

x	f(x) = x
0	0
1	1

2)

x
0	1
1	0

3)

x	f(x) = 1
0	1
1	1

4)

x	f(x) = 0
0	0
1	0

Булева функция двух логических переменных.

Рассмотрим две логические переменные x₁ и x₂: x₁ = {0, 1}, x₂ = {0, 1}. Рассмотрим функцию f(x₁, x₂), которая каждому слову (x₁ x₂) ставит в соответствие некоторое число. Такую функцию можно назвать числовой функцией двух логических переменных.

Определение 30. Функция двух логических переменных, принимающая только два значения, называется булевой функцией двух логических переменных (БФДЛП).

Областью определения БФДЛП является множество двухбуквенных слов из алфавита {0, 1}: 00, 01, 10, 11. Если принять эти слова за координаты точек на плоскости (x₁Оx₂), то БФДЛП можем считать заданной на множестве вершин единичного квадрата, например, f(x₁, x₂) может быть равна 1 во всех вершинах, кроме вершины 01, а в этой вершине обращаться в нуль.

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

Для БФДЛП можно построить таблицы истинности. (и – 1, л – 0).

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

Примеры.

Пример 1. Таблица для конъюнкции.

x1	x2
0	0	0
1	0	0
0	1	0
1	1	1

Пример 2. Таблица для композиции f(x₁, x₂) =

x1	x2
0	0	1	1
1	0	0	0
0	1	1	1
1	1	0	1

Определение 31 (общее определение) Булева функция – функция f(x₁, x₂, …, x_n), которая по любому набору логических констант выдает логическую константу.

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

10