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

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

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

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

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

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

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

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

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

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

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

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

* j₀(х₁, х₂) 0 и j₁₅ (х₁, х₂) 1.

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

* j₂(х₁.х₂) = Ø (х₁®х₂).

* j₃(х₁, х₂) = х₁.

* j₄(х₁.х₂) = Ø (х₂®х₁).

* j₅(х₁, х₂) = х₂.

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

* j₇(х₁.х₂) = х₁Ú х₂ .

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

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

* j₁₀(х₁.х₂) = _.

* j₁₁(х₁.х₂) = х₂®х₁.

* j₁₂(х₁.х₂) = .

* j₁₃(х₁.х₂) = х₁®х₂.

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

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

Фиктивной переменной (несущественной) функции 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).

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

Функция 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 ^*.