Основные классы булевых функций.

{, &, V, ~, →, ∆, /, ↓ }

{ ∆, /, ↓ } – добавочные.

1 класс. Р₀ - класс булевых функций сохраняющие const 0.

это означает, что f(x_1, ..., x_n) при x_i=0, 1≤ i≤ n, то f(0...0) должно быть равно 0.

– мощность. Р₀ = {f │ f (0, …, 0) = 0}

Р₁ - класс булевых функций сохраняет const 1.

это означает, что f(x₁,..., x_n) при x_i=1 равно 1.

– мощность. Р₁ = {f │ f (1, …, 1) = 1}

2 класс. S - класс самодвойственных булевых функций.

Функция f* называется двойственной по отношению к f(x₁,..., x_n), если имеет место следующее равенство

Функция является само двойственной, если

Функция является само двойственной, если при взятии отрицания всех переменных и плюс ко всему отрицание самой функции мы получим исходную функцию.

3 класс L - класс линейных функций.

Функция f(x₁,..., x_n) является линейной, если она представлена в виде полинома.

полином Жегалкина:

где C_i = const.

Пример линейной функции.

f(x₁, x₂)=x₁∆ x₂.

4 класс. М – монотонные функции.

Возьмем 2 набора (кортежа) одной размерности

Набор x¹ не меньше набора x², если для всех x_i выполняется

, если

где 1=1, 0=0, 1=1, 1> 0 =>

Если => наборы не сравнимые.

Функция f является монотонной, если в рассмотренных наборах имеется такое условие:

5 класс симметричных функций S

функция f(x₁,..., x_n) является симметричной если она сохраняет свое значение при любой перестановке аргумента.

f(x₁,..., x_n)↔ f(y₁,..., y_n)

где y₁,..., y_n – любая перестановка переменных.

Если взять функции одного(из данного) класса и применить к ним операции подстановки и суперпозиции, то получатся функции только данного класса.

Критерий Поста-Яблонского.

(критерий полноты системы булевых функций).

Для того, чтобы {f₁,..., f_m} – система функций была полной, необходимо и достаточно, чтобы она содержала хотя бы 1 функцию:

- Не сохраняющую нуль ()

- Не сохраняющую единицу ()

- Не являющуюся самодвойственной ()

- Не являющуюся линейной ()

- Не являющуюся монотонной ()

Примеры полных систем:

1) {, &, V }

2) {, & }

3) { / }

4) { ↓ }

5) { ∆, &, const f(0) }