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

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

Обозначим множество {0;1} через , т. е. . Булевой функциейот n аргументов называется отображение функция f из n-ой степени множества во множество

Т.е. .

Напомним, что -это множество наборов a = (a1,a2,... ),где ={0,1}, i=1,2…n.

Переменные булевых функций могут принимать только значения 0 или 1 и называются булевыми переменными.

Булев вектор это последовательность булевых констант.

Примеры: α=a1a2…a6=010101, β = b1b2…b8= 11110000.

Множество всех булевых функций от любого числа аргументов часто обозначается P₂, а от n аргументов — P₂(n).

Каждая булева функция n-арности определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2ⁿ. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно:

.

Теорема (о числе булевых функций от аргументов). Число различных булевых функций от аргументов равно .

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

Выясним сначала, сколько существует различных наборов , составленных из нулей и единиц, значений для аргументов . Покажем, что это число равно . Доказательство будем вести методом математической индукции по числу . В самом деле, для имеется всего два набора значений переменного . Это 0 и 1. Так что для число наборов равно . Предположим, что для аргументов имеется точно различных наборов , составленных из 0 и 1, значений для к аргументов. Тогда среди всевозможных различных наборов значений для аргумента имеется, согласно предположению индукции, точно наборов вида и точно наборов вида . Следовательно, всего будет различных наборов. Тем самым доказано с помощью индукции утверждение о числе различных наборов.

Например, булевы функции 1 переменной

,