39. Булевы функции, способы их задания. Представления булевых функций формулами.

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

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

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

Булева функция f(x₁,…,x_n) полностью задается своей таблицей истинности. В каждой строке таблицы задается сначала набор значений переменных (δ₁,…,δ_n), а затем значение функции на этом наборе.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то говорят, что формула φ представляет функцию f.

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо наборов, на которых она принимает значение 1.

Вектором значений булевой функции f(x₁,…,x_n) называется упорядоченный набор всех значений функции f, при котором значений упорядочены по лексикографическому порядку множества аргументов {0,1}ⁿ.

Отметим, что поскольку всего имеется 2ⁿ наборов нулей единиц, то существует ровно булевых функций от n переменных.

Наборы 0 и 1 можно представить в виде вершин n-мерных кубов или в виде вершин 2-дерева.

Функция f называется суперпозицией функций g(y₁,..,y_n) и h₁(x₁,…,x_n),…,h_m(x₁,…,x_n), если f(x₁,…,x_n)=g(h₁(x₁,…,x_n),…,h_m(x₁,…,x_n)).

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

Опишем булеву алгебру β_n функцией алгебры логики от n переменных. В качестве носителя рассмотрим множество . Отношение ≤ на множестве B_n определим по следующему правилу: для любого набора значений X=(δ₁,…,δ_n). Пересечением называется такая функция h , что h(X)=min{f(X),g(X)} на любом наборе X=(δ₁,…,δ_n). Объединением называется такая функция h, чтоh=max{f(X),g(X)} на любом наборе X. Дополнение функции f определяется следующим образом: . В качестве 0 рассмотрим функцию, являющуюся константой 0, а в качестве 1 возьмем константу 1. Система образует булеву алгебру функций от n переменных (алгебру булевых функций).