Спирина, М.С. Дискретная математика

чить и при задании булевой функции располагать их в виде двоич­ ных кортежей. Очевидно, что всего у булевой функции « переменных может быть 2 " аргументов, соответствующих двоичным числам от PO-Q П до LU l J , включительно. Итак, |ЯЛ| = |Д|Л= 2Л. П Определим, сколько может быть различных булевых функций « переменных. Из раздела 1.5 известно, что если \А\ = N, а |С| = к, то существует kN различных функций, действующих из А в С. Поскольку А = Вп, а С = В, то N = 2”, а к = 2. В итоге заключаем, что всего существует 2 (2<) различных булевых функций « пере­ менных. Для рассмотрения свойств булевых функций воспользуемся их геометрической интерпретацией. Поставим в соответствие различ­ ным наборам значений аргументов функции/ ( * , , х2, ..., х„) опре­ деленные точки «-мерного пространства. Тогда множеству 2" дво­ ичных наборов соответствует множество вершин «-мерного еди­ ничного куба. Припишем каждой вершине конкретное значение О или 1 , которое принимает булева функция при соответствующем наборе аргументов. Если значение функции равно 0, то точка не рисуется («выкалывается»), если значение функции равно 1 , то точка рисуется (выделяется полужирно). Такой «-мерный куб бу­ дет однозначно задавать любую булеву функцию / ( хь х2, ..., х„) с я переменными. Например, для двух переменных геометрическая интерпретация булевой функции будет на плоскости иметь вид квадрата или «двумерного куба» (рис. 4.1, а), а для трех перемен­ ных — куба в пространстве (рис. 4.1, б). Равенство функций. Как для отображений вообще, для булевых функций справедливо определение равенства функций. С учетом области определения оно будет выглядеть так: две булевы функ­ ции / и g, зависящие от « переменных, называются равными (эк­ вивалентными), если для любого х е В" справедливо соотношение ( 0 , 0 , 1 ) ( 0 , 1 ) ДО, 0,0) ( 0 , 1 , 1 ) 1 ) ( 0 , 1 , 0 ) ( 1 , 0 , 0 ) ( 1 , 1 , 0 ) 6 Рис. 4.1. Геометрическая интерпретация булевых функций: а -Д х , , х2); б — Д х ь х2, х3) 134