Способы задания булевых функций

1) Таблицей истинности.Так называется таблица, состоящая из двух частей: в левой части пересчитываются все наборы значений аргументов (булевы векторы пространства Bⁿ) в естественном порядке, т.е. по возрастанию значений чисел, представляемых этими векторами, а в первой части – значений булевой функции на соответствующих наборах.

Теорема о числе булевых функций.Число различных булевых функций, зависящих от n переменных, равно .

2) Характеристическими множествами.Так называются два множества:

M¹ (f), состоящее из всех наборов, на которых функция принимает значение 1, и M⁰ ( f ) — из всех наборов, на которых функция принимает значение 0, т.е.

M¹ (f) = {a Î B ⁿ : f (a) = 1}, M⁰ (f) = {a Î B ⁿ : f (a) = 0}.

3) Вектором значений функции:j(f) = f(0,0, ... ,0) f(0,0, ... ,1) ... f(1,1, ... ,1).

4) Матрицей Грея.Булево пространство задается матрицей Грея и наборами, на которых булева функция f(x₁, x₂, ... , x_n) принимает значение 1, отмечаются и называются точками.

Пример.

5) Интервальный способ задания.Булева функция f(x₁, x₂, ... , x_n) задается множеством интервалов I_f={I₁,I₂,…,I_k}, объединение которых образует характеристическое множество M¹(f) .

Пример: [Мажоритарная] функция может быть задана достаточным множеством I_f={I₁,I₂,I₃} интервалов:

Здесь интервалы представлены троичными векторами и изображены на матрице Грея. В отличие от предыдущих, интервальный способ задания функций многовариантен.

6) Формулами. Пример.

9. Существенные и фиктивные переменные. Алгоритмы выявления и удаления фиктивной переменной.

Булева функция f(x₁, x₂, ... , x_i , ... , x_n) существенно зависит от переменной x_i, если выполняется условие:

f (x₁, x₂, ... , x_{i -1}, 0 , x_i+1, ... , x_n) ¹ f (x₁, x₂, ... , x_{i -1}, 1 , x_i+1, ... , x_n).

В этом случае также говорят, что переменная x_i существенная, в противном случае ее называют фиктивной переменной.

Пример. Рассмотрим булеву функцию f (x₁, x₂, x₃) и исследуем ее переменные x₁ и x₃. Из таблиц истинности видно, что переменная x₁ булевой функции f (x₁, x₂, x₃) существенная, так как f (0, x₂, x₃) ¹ f (1, x₂, x₃). Переменная x₃ фиктивная, так как f (x₁, x₂, 0) = f (x₁, x₂, 1).