Способы задания булевых функций

ê Самый прямой способ задания функции – перечисление пар (аргумент функции, значение функции). Так как значений аргументов много – 2ⁿ – то необходимо условиться, как их перечислять. Обычно это делается в лексикографическом порядке, начиная с нулевого элемента и кончая единичным, все слова помещают в столбик один под другим, а значения функции – в следующей колонке. Таким образом получается матрица из двух столбцов и 2ⁿ строк, причём первый столбец состоит из слов длины n, а второй столбец – из нулей и единиц Если необходимо задать нескольких функций, их значения перечисляются в следующих столбцах. Полученная матрица значения аргументов – значения функции называется таблицей истинности.

ê Если условиться перечислять аргументы функции числовом (лексикографическом) порядке, то вместо выписывания таблицы можно задать значения функции на последовательности аргументов (0,1,…,2^n-1), т.е. последовательностью нулей и единиц (словом) длины 2ⁿ. Такой способ задания называется заданием вектора значений функции.

ê Так как булева функция принимает только два значения 0 или 1, то для задания функции достаточно перечислить аргументы, на которых она принимает значение 1. Этот способ называется заданием носителя функции N_f ={a|f(a)=1}. Можно сделать наоборот – задать номера аргументов, на которых функция принимает значение 0. Это будет множество ={a|f(a)=0} – о, дополнение множества N_f относительно булева куба. Множества N_f и по способу задания являются классами эквивалентности.

Формулами.