Булева функция.

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

Функции алгебры логики (ФАЛ) называются также булевыми функциями, двоичными функциями и переключательными функциями.

Булевой функцией описываются преобразования некоторым устройством входных сигналов в выходные. Пусть устройство f имеет n входов x₁, x₂, … ,x_n на которые может подаваться (1) или не подаваться (0) ток и один выход, на котором ток есть (1) или (0). Таким образом, значение переменной x_i = 1 интерпретируется как поступление тока на i-й вход, а x_i = 0 - как не поступлении тока. Значение на выходе устройства f(δ₁,δ₂, … ,δ_n) = 1, означает ток на выходе при заданном входе и f(δ₁,δ₂, … ,δ_n) = 0 - тока на выходе нет.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству {0, 1}. Множество {0, 1} мы будем в дальнейшем обозначать через B.

Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;W>, где W – множество всевозможных булевых функций, называется алгеброй логики.

В дискретной математике большую роль играют конечные функции.

Конечной функцией называют отображение одного конечного множества в другое.

Важный класс таких функций образуют булевы функции.

Булева функция (от n переменных) - это произвольное отображение вида

f: Bⁿ → B, B={0,1};

Булева функция определена на множестве всех n-элементных последовательностей (n-элементных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.

Булева константа - это индивидная константа с областью значений {0,1}. Таким образом, существует две булевы константы: 0 и 1. По определению принимается, что каждая булева константа есть также булева функция от 0 переменных (нульарная операция).

Булево переменное - это индивидное переменное с областью значений {0,1}, т.е. это переменное, которое может принимать только два значения: 0 и 1.

Тогда булева функция f: {0,1}ⁿ → {0,1} задается y = f(x₁, . . . , x_n), в которой каждое булево переменное x_i(i = 1, . . .,n) и функция f принимают два возможных значения: 0 и 1.

Переменные x₁, . . . , x_n называют - переменными булевой функции f.

Кортеж из множества {0,1}ⁿ называется набором значений переменныхx₁, . . . , x_n . Мощность этого множества 2ⁿ

Число функции f: M → N равно N^M(2в степени 2ⁿ)