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

Функцией алгебры логики или булевой функцией называется функция n переменных если аргументы функции являются булевыми переменными (т.е. ), и функция может принимать только два значения: 0 или 1. Таким образом, булева функция Булевы функции называются также переключательными функциями. Каждая комбинация значений аргументов булевой функции называется набором. Для функции n переменных количество разных наборов равно 2 ⁿ.

Булева функция задается таблицей истинности:

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

Функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Функция f ₁ называется тождественной функцией и обозначается через x. Функция f ₂ называется отрицанием x и обозначается .

Рассмотрим часто используемые булевы функции двух аргументов. Эти функции определены на четырех наборах.

Приведем обозначения и названия этих функций. Функция f ₃ называется конъюнкцией x ₁ и x ₂ и обозначается x ₁× x ₂. Функция f ₄ называется дизъюнкцией x ₁ и x ₂ и обозначается . Функция f ₅ называется суммой по модулю 2 и обозначается . Функция f ₆ называется импликацией и обозначается (читается x ₁ влечет x ₂). Функция f ₇ называется эквивалентностью и обозначается x ₁ ~ x ₂ (читается x ₁ эквивалентно x ₂). Функция f ₈ называется штрихом Шеффера и обозначается x ₁ |x ₂ (читается не x ₁ и x ₂).

С помощью операции суперпозиции из этих элементарных функций можно построить функции большего числа аргументов. Заметим, что булеву функцию можно однозначно определить перечислением всех наборов, на которых она принимает значение 1.

Функция существенно зависит от переменной x_i, если для любых значений . В противном случае переменная x_i - фиктивная. Наборы, отличающиеся значением только одной переменной x_i, называются соседними.