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

В курсе математического анализа изучаются функции, определённые на числовой прямой или на отрезке числовой прямой или на (гипер-) плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе дискретной математики изучаться должны функции, область определения которых – дискретное множество*. Простейшим (но нетривиальным) таким множеством является множество, состоящее из двух элементов.* Так мы и приходим к понятию булевой функции.

Определение 1 (Булева функция). Булевой функцией от n аргументов называется функция f из n-ой степени множества { 0, 1 } в множество { 0, 1 }.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.

Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;W>, где W – множество всевозможных булевых функций, называется алгеброй логики.

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2n наборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

x1	x2	...	xn-1	xn	f
0	0	...	0	0	f(0,0,...,0,0)
0	0	...	0	1	f(0,0,...,0,1)
0	0	...	1	0	f(0,0,...,1,0)
0	0	...	1	1	f(0,0,...,1,1)
...	...	...	...	...	...
1	1	...	0	0	f(1,1,...,0,0)
1	1	...	0	1	f(1,1,...,0,1)
1	1	...	1	0	f(1,1,...,1,0)
1	1	...	1	1	f(1,1,...,1,1)

Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значения f(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),...,f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1). Этот набор называют вектором значений функции.

Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2n*. А их 2 в степени 2n.

Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.

Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция ``отрицание''. Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:

x	0	x	¬ x	1
0	0	0	1	1
1	0	1	0	1

Как видим, функции от некоторого числа переменных можно рассматривать как функции от большего числа переменных. При этом значения функции не меняется при изменении этих ``добавочных'' переменных. Такие переменные называются фиктивными, в отличие от остальных – существенных.

Определение 2 (Фиктивные и существенные переменные). Переменная xi называется фиктивной (несущественной) переменной функции f(x1,···,xn), если

f(x1,···,xi-1,0,xi+1,···,xn) = f(x1,···,xi-1,1,xi+1,···,xn)

для любых значений x1,···,xi-1,xi+1,···,xn. Иначе переменная xi называется существенной.

Функций от двух аргументов шестнадцать. Наиболее употребимые из этих функций (только те, которые существенно зависят от обеих переменных) мы приводим в следующей таблице:

x1	x2	x1 & x2	x1 Ъ x2	x1 Йx2	x1 Е x2	x1 є x2	x1 \| x2
0	0	0	0	1	0	1	0
0	1	0	1	1	1	0	1
1	0	0	1	0	1	0	1
1	1	1	1	1	0	1	1

Эти функции записываются как бинарные операции в инфиксной нотации. x1 & x2 называется конъюнкцией, x1 Ъ x2 – дизъюнкцией, x1 Й x2 – импликацией, x1 є x2 – эквивалентностью, x1Е x2 – суммой по модулю 2, x1 | x2 – штрихом Шеффера.

Значения 0 и 1 часто интерпретируют как ``ложь'' и ``истину''. Тогда понятным становится название функции ``отрицание'' – она меняет ``ложь'' на ``истину'', а ``истину'' на ``ложь''. Отрицание читается как ``не''. Конъюнкция читается обычно как ``и'' – действительно, конъюнкция равна 1 тогда и только тогда, когда равны 1 и первая и вторая переменная.* Кроме x1& x2 часто используют обозначение x1 Щ x2 или x1 · x2 или x1x2 или min(x1,x2). Дизъюнкция читается ``или'' – дизъюнкция равна 1 тогда и только тогда, когда равны 1 первая или вторая переменная.* Импликация выражает факт, что из x1 следует x2.* Импликацию часто также обозначают x1 ® x2.

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