University-notes/1 курс/2 семестр/Дискретка/Билеты/15.md

Критерий Поста. Шефферовы функции

Критерий Поста

Теорема

Множество функций является полной системой тогда и только тогда, когда оно не включено ни в один из классов T_0, T_1, S, M, L.

Доказательство

Пусть A - множество функций. Допустим, что A \subseteq X, где X - один из 5 классов. По 1 курс/2 семестр/Дискретка/Билеты/9#^02f9e1 [A] \subseteq [X]

Т.к. X - замкнутый класс, то [X] = X и, следовательно, [A] \subseteq X \ne P_2 Следовательно, и A не полная система

Докажем обратное: пусть A не является подмножеством ни одного из 5 классов. Тогда в нём имеются такие функции f_1, f_2, f_3, f_4, f_5, что f_1 \notin T_0, f_2 \notin T_1, f_3 \notin S, f_4 \notin M, f_5 \notin L. Некоторые (или все) могут совпадать

Рассмотрим f_1 \notin T_0 \Rightarrow f(0, \dots 0) = 1. Рассмотрим 2 случая:

1. f_1(1, \dots, 1) = 0, тогда f_1(x, \dots, x) = \bar x

   По 1 курс/2 семестр/Дискретка/Билеты/11#Лемма, \{0, 1\} \subseteq [\{f_3, \bar x\}] По 1 курс/2 семестр/Дискретка/Билеты/14#Лемма, xy \in [\{f_5, 0, 1, \bar x\}]

   Таким образом, \bar x и xy суперпозиции из множества \{f_1, f_3, f_5\}

2. f_1(1, \dots, 1) = 1, тогда f_1(x, \dots, x) = 1 Т.к. f_2 \notin T_1, то f_2(1, \dots, 1) = 0. Значит, подставляя 1 вместо всех переменных в f_2, получим 0. Итак, \{0, 1\} \subseteq [\{f_1, f_2\}]

   По 1 курс/2 семестр/Дискретка/Билеты/12#Лемма, \bar x \in [\{f_4, 0, 1\}] По 1 курс/2 семестр/Дискретка/Билеты/14#Лемма, xy \in [\{f_5, 0, 1, \bar x\}]

   Таким образом, \bar x и xy суперпозиции из \{f_1, f_2, f_4, f_5\} В обоих случаях \set{\bar x, xy} \subseteq [\set{f_1, f_2, f_3, f_4, f_5}] \subseteq [A] Множество \set{\bar x, xy} - полная система. По 1 курс/2 семестр/Дискретка/Билеты/9#Теорема множество A - тоже полная система

Шефферовы функции

• Шефферова функция - [\{f\}] = P_2, т.е. функция, множество из одной такой функции являющееся полной системой ^27f049

Примеры

• \overline{x_1x_2 \dots x_n} при b \ge 2 Единственные Шеферовы функции от 2х переменных:
• x | y
• x \downarrow y