Представление булевой функции формулой логики высказываний
Определение. Булевой функцией f(x1, x2, …, xn) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.
Всякую булеву функцию от nпеременных можно задать таблицей из 2n строк, в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение 0 или 1.
Пример 31.
Для n=3 булеву функцию можно задать таблицей 17.
Таблица 17
|
№ |
x1 |
x2 |
x3 |
f(x1, x2, x3) |
|
0 |
0 |
0 |
0 |
f(0, 0, 0) |
|
1 |
0 |
0 |
1 |
f(0, 0, 1) |
|
2 |
0 |
1 |
0 |
f(0, 1, 0) |
|
3 |
0 |
1 |
1 |
f(0, 1, 1) |
|
4 |
1 |
0 |
0 |
f(1, 0, 0) |
|
5 |
1 |
0 |
1 |
f(1, 0, 1) |
|
6 |
1 |
1 |
0 |
f(1, 1, 0) |
|
7 |
1 |
1 |
1 |
f(1, 1, 1) |
Используется также задание булевой функции в виде двоичного слова, длина которого зависит от числа переменных.
Пример 32.
Пусть задана булева функция от трех переменных (табл. 18). Тогда число наборов
.
Таблица 18
|
№ набора |
х1 |
х2 |
х3 |
f |
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
2 |
0 |
1 |
0 |
1 |
|
3 |
0 |
1 |
1 |
0 |
|
4 |
1 |
0 |
0 |
1 |
|
5 |
1 |
0 |
1 |
1 |
|
6 |
1 |
1 |
0 |
0 |
|
7 |
1 |
1 |
1 |
1 |
Номера наборов всегда нумеруются, начиная с нуля, в таблице приведено стандартное расположение всех наборов функции трех переменных (обратите внимание, что каждый набор представляет собой двоичный код числа, равный номеру соответствующего набора). Первые четыре столбца одинаковы для всех булевых функций от трех переменных. Столбец значений функции задается или вычисляется.
Эту же функцию можно записать f(х1, х2, х3)=00101101.
Существует ровно 
различных булевых функций от n переменных.
Константы 0 и 1 считают нуль-местными булевыми функциями.
Утверждение. Каждой формуле логики высказываний соответствует некоторая булева функция.
Пример 33.
Построить все булевы функции, зависящие от двух переменных.
предыдущаяследующая