Глава III. Булевы функции
§ 1. Основные определения
Пусть В={0,1}.
Элемент
=
(x1,x2,...,xn)
Bn,
где Bn=BB...B,
называется булевым
вектором.
Функция f:BnB
называется булевой
функцией от
n переменных
x1,
x2,...,
xn,
где xi
B
(1
i
n),
и обозначается f(
)=f(x1,x2,...,xn).
Если f(
)=1,
то
называется единичным
относительно
функции f;
если f(
)=0,
то нулевым.
Для булевой функции f(x1,x2,...,xn) переменная xi, 1in, называется несущественной, если выполнено равенство: f(x1,...,xi-1,1,xi+1, ...,xn)= f(x1,...,xi-1,0,xi+1, ...,xn)
для всех значений переменных x1,...,xi-1,xi+1,...,xn. В этом случае функция f(x1,x2,...,xn) фактически не зависит от переменной xi и можно рассмотреть функцию, зависящую от n1 переменных, которая совпадает с исходной.
Две функции f1 и f2 равны между собой, если f2 может быть получена из f1 добавлением или удалением несущественных переменных (по определению).
Выпишем все возможные булевы функции одной переменной (табл. 1.1).
|
x |
1 |
2 |
3 |
4 |
Переменная х может принимать 2 значения, , в таблице 2 строки. Различных векторов длины 2, состоящих из 0 и 1, а значит, и булевых функций от 1 переменной, можно составить 22=4. |
|
0 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
1 |
Для функций 1
и 4
х
является несущественной переменной.
Эти функции называются константами,
соответственно 0 и 1. Функцию 2
называют тождественной
(2(х)
= х).
Функция 3
называется отрицанием
х (или функцией
НЕ) и обозначается
(иногда
х).
Рассмотрим булевы функции двух переменных. Их 16 (табл. 1.2). Каждая из переменных может принимать по 2 значения, , всего существует 22 = 4 различные пары (x1,x2), а значит, и строк в таблице 4. Различных векторов длины 4, состоящих из 0 и 1, можно составить 24=16.
Функции 1 и 16 константы 0 и 1, то есть функции с двумя несущественными переменными. Формально эти функции отличаются от функций 1 и 4, так как все функции в табл. 1.1 унарные операции на В, а все функции в табл. 1.2 бинарные операции на В. Однако ранее уже было принято функции, отличающиеся лишь несущественными переменными, считать равными.
Таблица 1.2
|
x1x2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Функция 2(x1,x2) называется конъюнкцией x1 и x2 ; ее обозначения: x1&x2, x1x2, x1x2, x1x2. Она равна 1, только если x1=x2=1, поэтому ее называют функцией И. Еще одно ее название логическое умножение, т.к. ее таблица совпадает с таблицей обычного умножения для чисел 0 и 1.
Функция 8(x1,x2) называется дизъюнкцией x1 и x2 ; ее обозначения: x1x2, x1+x2 . Она равна 1, если x1=1 или x2=1 (или здесь понимается в смысле хотя бы одна переменная из двух). Поэтому ее часто называют функцией ИЛИ.
Заметим, что x1&x2= min{x1,x2}, а x1x2= max{x1,x2}.
Функция 7(x1,x2) это сложение по модулю 2. Ее обозначения: x1x2, x1x2 , x1x2 . Она равна 1, когда значения ее аргументов различны, и равна 0, когда они равны; поэтому 7 иногда называют неравнозначностью.
Функция 10(x1,x2) называют эквивалентностью или равнозначностью. Ее обозначения: x1~x2 , x1x2 , x1x2. Она равна 1, когда значения ее аргументов равны, и равна 0, когда они различны. Еще 3 функции имеют свои названия:
14 (x1,x2) импликация; обозначения: x1x2 , x1x2 ; читается “если x1, то x2“;
9(x1,x2) стрелка Пирса, обозначение: x1x2 ; 15(x1,x2) штрих Шеффера; обозначение: x1|x2.
Остальные функции специальных названий не имеют и, как будет показано позднее, легко выражаются через перечисленные ранее функции.
Определим, сколько
существует булевых функций от n
переменных. Число различных наборов
(x1,x2,...,xn)
составляет 2n,
поэтому таблица, описывающая функции
n
переменных, состоит из 2n
строк. Различных векторов с 2n
компонентами,
состоящих из 0 и 1, а значит, и булевых
функций, можно составить
.
Пример.
При n
= 3 булевых
функций 256.
Функция f
называется суперпозицией
булевых функций f1,
f2,...,
fk ,
если она получается некоторой подстановкой
этих булевых функций друг в друга.
Выражение, описывающее результат этой
подстановки, называется логической
формулой,
задающей функцию f.
Например, функция 3(2
(x1,x2))
задается формулой
,
а функции 8(14
(x1,x2),
7
(x1,x2))
соответствует формула ((x1x2)
(x1x2)).
О формуле, задающей некоторую булеву
функцию, говорят, что она реализует
эту функцию.
Пример.
Формула
строится в два этапа, а формула ((x1x2)
(x1x2))
в три.