Учебник по дискретной математике
Оглавлениеn1.doc (26 стр.)
Скачать Задачи
1. Доказать, что пересечение любых двух замкнутых классов замкнуто.
2. Доказать, что объединение двух замкнутых классов не всегда замкнуто.
Теорема Поста о полноте
Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов
T0,
T1,
L,
S,
M.
Доказательство. Докажем необходимость этого условия. Пусть система
N = {
f1,
f2, ...
fs, ...} полна в
Р2, покажем, что тогда она не лежит целиком в
Q, где через
Q обозначим любой из классов
T0,
T1,
L,
S,
M. Докажем от противного, пусть
N
Q, очевидно, [
N] [
Q] =
Q, но [
N] =
P2, т.к.
N – полна в
Р2, отсюда
Р2=
Q, но это не так. Необходимость доказана.
Докажем достаточность. Пусть
F = {
f0,
f1,
fL,
fm,
fs}, где
f0
T0,
f1
T1,
fL
L,
fs
S и
fm
M. Покажем, что суперпозицией функций системы
F можно получить полную систему
G = {
x1&
x2,

}.
1. Пусть
g(
x) =
f0(
x, …,
x). Тогда
g(0) =
f( 0, …, 0) = 1. Далее возможны два случая:
g(1) = 1. Тогда
g(
x) 1. Функция
h(
x) =
f1(
g(
x), …,
g(
x)) =
f1(1, …, 1) = 0, т.е.
h(
x) 0. Получили константы 0 и 1;
g(1) = 0. Тогда
g(
x) =

. По лемме о несамодвойственной функции суперпозицией над {
fs,

} можно получить одну из констант, например, 0. Тогда
f0(0, …, 0) = 1 есть другая константа.
В обоих случаях получили обе константы.
2. По лемме о немонотонной функции суперпозицией над {
fm, 0, 1} можно получить отрицание.
3. По лемме о нелинейной функции суперпозицией над {
fL, 1,

} можно получить конъюнкцию. Теорема доказана.
Следствие. Всякий замкнутый класс функций из
Р2, не совпадающий с
Р2 содержится, по крайней мере, в одном из замкнутых классов
T0,
T1,
L,
S,
M. Действительно, если
N не является подмножеством
Q, то [
N] =
P2, что неверно.