Преобразуем эту формулу, используя соответствующие эквивалентности u  

Изобразим схему, соответствующую заключительной формуле

B

A

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

Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B ={1, 0}.

Функцией алгебры логики (логической функцией) или булевой функцией f(x₁,x₂,...,x_n) называется отображение f : B ⁿB, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через P_n – множество булевых функций n переменных.

Логическую функцию n переменных f(x₁,x₂,...,x_n) можно задать таблицей, в левой части которой перечислены все 2ⁿ наборов значений переменных, а в правой части – значения функции на этих наборах.

x1 x2 . . . хn-1 xn	f(x1, x2 , . . . хn-1 , xn)
0 0 . . . 0 0 0 0 . . . 0 1 0 0 . . . 1 0 . . . . . . . . . . . . . . . . 1 1 . . . 1 0 1 1 . . . 1 1	f(0,0, . . . ,0,0) f(0,0, . . . ,0,1) f(0,0, . . . ,1,0) . . . . . . . . f(1,1, . . . ,1,0) f(1,1, . . . ,1,1)

При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2ⁿ . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2ⁿ, то есть , т.е. || =.

Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1).

Пусть F={} – некоторое множество булевых функций. Его можно выбрать в качестве основного набора, называемого базисом. Формулой над базисомF (обозначается [F]) называется выражение вида [F]=, где F, а либо переменная, либо формула надF. Таким образом, всякая формула является суперпозицией базисных функций, для её представления обычно применяется форма записи с логическими операциями ~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула реализует функцию f (обозначается func  = f ). Как будет показано ниже, такая реализация не единственна.

Приведем примеры логических функций одной и двух переменных и их реализаций в виде формул.

Логических функций одной переменной четыре: две нуль-местные (₀(х), ₃(х)) – константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции – тождественная и отрицание.

x	0	1	2	3
0	0	0	1	1
1	0	1	0	1

Тождественная функция "повторяет" значение х: ₁(х)=х. Функция отрицание возвращает значение, противоположное значению х: ₂(х)=¬х.

Логических функций двух переменных шестнадцать:

х1	x2	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Рассмотрим подробнее все эти функции.

• ₀(х₁,х₂)0 и₁₅ (х₁,х₂)1.

• ₁(х₁,х₂) = х₁  х₂ . Эта функция называется ещё логическим умножением и обозначается, также, х₁х₂.

• ₂(х₁.х₂) =  (х₁х₂).

• ₃(х₁,х₂) = х₁.

• ₄(х₁.х₂) =  (х₂х₁).

• ₅(х₁,х₂) = х₂.

• ₆(х₁,х₂) = (х₁~х₂) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х₁ х₂.

• ₇(х₁.х₂) = х₁ х₂ .

• ₈(х₁.х₂) = (х₁х₂) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х₁х₂.

• ₉(х₁.х₂) = х₁~х₂ . Эту функцию называют еще равнозначностью и обозначают х₁х₂ .

• ₁₀(х₁.х₂) = _.

• ₁₁(х₁.х₂) = х₂х₁.

• ₁₂(х₁.х₂) = .

• ₁₃(х₁.х₂) = х₁х₂.

• ₁₄(х₁.х₂) = (х₁х₂) – антиконъюнкция, которая называется еще штрих Шеффера и обозначается х₁ | х₂.

Формулы, реализующие одну и ту же функцию, называются равносильными. Отношение равносильности формул является отношением эквивалентности и обозначается .

Фиктивной переменной (несущественной) функции f(x₁, . . . _, x_n) называется переменная х_i, изменение значения которой не меняет значения функции, то есть f(x₁, . . . , х_i-1, 1, x_i+1, . . . , x_n) = f(x₁, . . . , х_i-1, 0, x_i+1, . . . , x_n).

Например, в функциях ₃ и ₁₂ переменная х₂ фиктивна, а в функциях ₅ и ₁₀ фиктивна переменная х₁.

Функция f(x₁, . . . , x_n), имеющая фиктивную переменную x_i, по существу зависит от (n–1)-й переменной, т.е. представляет собой функцию g(x₁, . . . , х_i-1, x_i+1, . . . , x_n). В этом случае говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причём эти функции считаются равными.

Пусть f (x₁,  , x_n)  P_n – булева функция. Тогда функция f^*(x₁, , x_n), определенная следующим образом

f ^*(x₁, , x_n) = ,

называется двойственной к функции f.

Теорема (Принцип двойственности). Пусть F={}. Тогда, если формула [F] реализует функцию f, то формула ^* над базисом F^*={}, полученная из формулы заменой функций f_i на двойственные им функции f_i^*, реализуют функцию f ^*.