§ 6. Булевы функции (функции алгебры логики).

Каждая формула алгебры высказываний F(X₁, …, X_N) от n пропозициональных переменных X₁, X₂, …, X_n определяет некоторую функцию от n аргументов, сопоставляющую любому набору длиной n, составленному из элементов двухэлементного множества {0, 1}, единственный элемент того же множества. Этот элемент является логическим значением того составного высказывания, в которое превращается данная формула, если вместо всех ее пропозиционных переменных подставить конкретные высказывания, имеющие соответствующие значения истинности. В связи с этим вводится следующее понятие функции алгебры логики (булевой функции).

Булевой функцией (или функцией алгебры логики) от n аргументов называется любая функция f(x₁, x₂, …, x_n) от n аргументов, заданная на двухэлементном множестве {0, 1} и принимающая значение в том же множестве {0, 1}. Функцию от n переменных будем называть n- местной булевой функцией.

В отличие от алгебры и анализа, в алгебре логики число n- местных булевых функций при каждом фиксированном n конечно.

ⁿ

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

Одноместных булевых функций всего 4. Двухместных булевых функций – 16. Трехместных булевых функций уже 256. С ростом n число n – местных булевых функций быстро растет.

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

х1	x2	х1х2	х1х2	х1х2	х1х2	х1х2	х1х2	х1+х2
0 0 1 1	0 1 0 1	0 0 0 1	0 1 1 1	1 1 0 1	1 0 0 1	1 1 1 0	1 0 0 0	0 1 1 0

Эти функции называются соответственно: конъюнкция, дизъюнкция, импликация, эквиваленция, штрих Шеффера, стрелка Пирса, сложение по модулю два (или сумма Жегалкина).

Система булевых функций {f₁, f₂, …, f_n} называется полной, если любая булева функция является некоторой суперпозицией функций из этой системы (т.е. если любая булева функция может быть выражена через функции f₁, …, f_n с помощью составления сложных функций). Если же существует булева функция не представимая суперпозиция функций из данной системы функций, то данная система называется неполной.

Элементарная конъюнкция называется монотонной, если она не содержит отрицаний переменных.

Многочленом (полиномом) Жегалкина называется многочлен являющейся суммой константы 0 ли 1 и попарно различных монотонных конъюнкций.