Классы булевых функций

Множество всех булевых функций P₂ является замкнутым классом (Почему?). Общее их число всех булевых функций n переменных равно его мощности . Из множества этих функций выделяют некоторые классы (подмножества).

1. Булева функция f сохраняет константу 0, если

f(0, 0, …, 0) = 0

Множество всех булевых функций, сохраняющих константу 0, образует класс .

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

Доказательство. Булева функция, принадлежащая классу K₀, на наборе <0, 0, …, 0> принимает значение равное 0, но таких наборов 2ⁿ – 1, следовательно общее число таких функций .

2. Булева функция f сохраняет константу 1, если

f(1, 1, …, 1) = 1

Множество всех булевых функций, сохраняющих константу 1, образует класс .

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

Доказательство. Булева функция, принадлежащая классу K₁, на наборе <1, 1, …, 1> принимает значение равное 1, но таких наборов 2ⁿ – 1, следовательно общее число таких функций .

3. Булева функция называется двойственной функцией к функции f и обозначается f*.

ZB. По определению , т.е. функция является двойственной к функции .

Рассмотреть, что происходит с таблицей истинности.

Замечание. Замена кортежей соответствует переворачиванию таблицы.

Булева функция называется самодвойственной, если она совпадает с двойственной себе функцией f = f*.

ZB. Класс самодвойственных булевых функций: 1. ; 2. .

Множество всех самодвойственных булевых функций, образует класс .

Теорема. Число всех самодвойственных булевых функций равно .

Доказательство. Любую булева самодвойственную функция, принадлежащая классу S, можно определить на половине наборов, т.е. 2^n-1, следовательно, общее число таких функций .

4. Булева функция f называется линейной функцией, если она может быть записана в следующем виде , где .

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

Теорема. Число всех линейных булевых функций равно .

Доказательство. Имеется всего 2ⁿ⁺¹ различных наборов значений коэффициентов c_k. следовательно, общее число таких функций .

5. Набор значений переменных не меньше набора , если для всех j = 1, 2, …, n. В этом случае пишут , в противном случае наборы называются несравнимыми.

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

.

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

Число всех монотонных булевых функций оценивается асимптотически:

, где А – некоторая константа.

Теорема (Пост-Яблонского).

Для того чтобы множество N булевых функций было полной системой, необходимо и достаточно найти для каждого из пяти замкнутых классов Поста K₀, K₁, S, M, L функцию из N, которая ему не принадлежит.

ZB. Рассмотрим множество из одной функции Шеффера . Это - полная система. Согласно теореме Поста эта единственная функция должна не принадлежать ни одному из классов Поста.

1. ; вывод

2. вывод

3. вывод

4. вывод

5. вывод