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

4.1. Начальные понятия

Пусть E₂ ={0,1}.

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

Определение

Всякое отображение , где n  N, называется булевской функцией.

Вместо полного наименования “булевская функция” допустимо использование сокращения  б.ф. Название является историческим и связано с близостью таких функций к исследовавшимся математиком Булем теоретико-множественным и логическим структурам. Для булевских функций применяется и другое наименование  функции алгебры логики (ф.а.л.). В настоящем пособии будет преимущественно использоваться первое наименование.

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

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

Если логическая форма U учитывает факторы F₁ , . . . , F_n, то функция истинности для значений U в зависимости от значений F₁ , . . . , F _n  это некоторая булевская функция .

Множество всех булевских функций обозначается как P₂.

Пусть . Будем использовать символы переменных x₁, . . . , x_n для обозначения первой, второй, . . . , n-й компонент двоичных наборов, являющихся элементами области определения f.

Если задан произвольный двоичный набор (₁,..., _n), то значение _i будет называться значением переменной x_i.

4.2. Табличное задание булевских функций

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

Если , то соответствующая таблица имеет вид:

x1 x2 . . . x n	f(x1 ,. . . , xn)
0 0 . . . 0	f(0 , . . . , 0)
. . .	. . .
1 2 . . . n	f(1, 2, . . , n)
. . .	. . .
1 1 . . . 1	f(1 , . . . , 1)

Приведенная таблица имеет 2ⁿ строк и n +1 столбец. В первых n элементах строк таблицы задаются все возможные наборы значений переменных x₁, . . . , x_n. Поэтому таблица имеет 2ⁿ строк. Последний элемент всякой строки содержит значение функции на наборе значений переменных этой функции, выписанном левее этого элемента в той же строке.

При этом двоичные наборы значений переменных x₁ , . . . , x_n в строках выписываются в порядке возрастания значений двоичных чисел, представляемых этими наборами. Это означает, что для задания произвольной функции f достаточно указать последний столбец табличного задания этой функции. Такой столбец является двоичным набором, содержащим 2ⁿ элементов. Следовательно, многообразие всех возможных функций алгебры логики определяется множеством всех двоичных наборов длины 2ⁿ. Поэтому существует ровно различных булевских функций . Множество всех таких б.ф. обозначается как .