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

2.1. Функции и константы алгебры логики

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

2.2. Несущественные переменные и равенство функций

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

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

Несущественные переменные удаляются следующим образом:

Сначала строится таблица значений функции . Затем перебираются пары строк аргументов, на которых значения функции совпадают, и отмечается -й элемент строк вида

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

Пример

. Здесь обозначает остаток от деления на 2. Составим таблицу значений:

	x1	x2	x3	f
1	0	0	0	0
2	0	0	1	1
3	0	1	0	0
4	0	1	1	1
5	1	0	0	1
6	1	0	1	0
7	1	1	0	1
8	1	1	1	0

Строку 1 сравниваем со строками, в которых . Отмечаем элементы 2-го столбца строк 1 и 3. То же самое проделываем с остальными строками. Отмечаем элементы 2-го столбца строк 2 и 4, 5 и 7, 6 и 8. Поскольку все элементы столбца 2 отмечены, то – несущественная переменная. Вычеркивая второй столбец, получаем таблицу значений некоторой функции , равной :

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

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

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

и не имеет фиктивных элементов.