Пост

1.

Полнота множества функций. Замыкание
множества функций. Понятие замкнутого
класса функций. Важнейшие замкнутые
классы: Т0 (класс функций, сохраняющих
константу 0), Т1 (класс функций
сохраняющих константу 1), S (класс
самодвойственных функций), L (класс
линейных функций), М (класс монотонных
функций). Теорема Поста.

2.

Виды функций
*
Функция f
называется двойственной функцией f
,
(
x
,
x
,..,
x
)
(
x
,
x
,..,
x
)
1
2
n
1
2
n
*
*
x
y
,
f
x
y
x
y
если f
= f(
(
x
,
x
,..,
x
)
x
,..,
x
). Например, f
1
2
n
1
n
Функция называется самодвойственной, если
*
).
f
x
,
f
x
x
f f*
(например,
Функция называется линейной, если ее полином Жегалкина имеет первую
степень.
Функция называется монотонной, если для любых
f
()
f
()
.
следует, что

3.

O Пусть - K f1 , f 2 , , f m конечная система
булевых функций. Функция f называется
суперпозицией функций f1 , f 2 , , f m , если f
может быть получена одним из следующих
способов:
O Переименованием некоторой переменной xj
какой-либо функции fi;
O Подстановкой некоторой функции fi вместо
x f K
любой переменной xj, j n
.
O Множество К булевых функций называется
замкнутым, если вместе с функциями из
этого множества оно содержит все их
суперпозиции.

4.

Основные замкнутые классы
булевых функций
O Класс функций, сохраняющих 0 (Т0, где f(0,0,0..,0)=0).
O Класс функций, сохраняющих 1 (Т1, где f(1,1,1..,1)=1).
O Класс самодвойственных функций
(T* = S = {f | f = f *}).
O Класс линейных функций (TL = L = {f | f - линейная
функция}).
O Класс монотонных функций (T<= M =
{f | f ( ) f ( ) )}.

5.

Основными шефферовскими
функциями являются:
O Штрих Шеффера x | y (и не) ( x y );
O Стрелка Пирса
x y (или не) ( x y );
O Сложение по модулю два x+y.

6.

O Система булевых функций называется
полной, если любая булева функция может
быть выражена через функции f1 , f 2 ,.., f m с
помощью суперпозиций.
O Теорема Поста: Для того чтобы система
булевых функций была полной, необходимо
и достаточно, чтобы для каждого из классов
Т0, Т1, S, L, M нашлась функция, не
принадлежащая этому классу.
O Полные системы: , , , , ,1 .