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

Булевой функцией от 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ⁿ )

Булевой функции можно придать другой смысл.

1 – истина

0 – ложь

Тогда из простых высказываний можно составить сложное.

Алгебра логики - множество высказываний и операций - одной унарной и 4 бинарных:

А₁ = ‹b, { , , , →, ~}›

: {0,1} → {0,1} - отрицание

: {0,1}² → {0,1} - конъюнкция (лог. умножение) – " и "

: {0,1}² → {0,1}- дизъюнкция (лог. сложение) - " или "

Или 1 – включено, 0 - выключено.

Тогда получаем переключательную функцию или двоичную функцию

Примеры

Параллельное и последовательное соединения

Двоичное дерево