Важнейшие замкнутые классы

Введем следующие классы функций (классы Поста):

; ;

класс самодвойственных функций;

класс монотонных функций (функция называется монотонной);

класс линейных функций ( называется линейной).

Лемма. Классы замкнуты.

Доказательство. а) Рассмотрим функцию , где . Покажем, что . Действительно,

.

Следовательно, класс замкнут.

б) Аналогично предыдущему доказывается замкнутость класса .

в) Пусть , где самодвойственные функции. Тогда , т. е. . . Следовательно, класс замкнут.

г) Пусть , где .

Возьмем два набора и значений переменных . Они определяют наборы значений переменных причем . Так как , то

.

Тогда . Функция , поэтому . Отсюда

.

Следовательно, класс замкнут.

д) Класс замкнут, так как линейное выражение, составленное из линейных выражений, является линейным.

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

Доказательство. Так как , то существует набор такой, что .

Рассмотрим функцию . Пусть

.

Тогда

Следовательно, константа 0 или 1.

Замечание. Если , то вместо подставляем , если же то .

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

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

Доказательство. Если , то найдутся два набора значений переменных и такие, что и .

и каждый следующий набор получается из предыдущего изменением ровно одной координаты.

Так как , то в этой цепочке найдутся два соседних набора переменных и такие, что и . Пусть эти наборы различаются в - ой координате:

.

Рассмотрим функцию

.

Имеем

Поскольку, , то .

Замечание. Для проверки на монотонность функции , заданной своим вектором значений , нужно сначала разделить его две равные части и .

Лемма (о нелинейной функции). Если , то из нее путем подстановки констант , и функций и , а также, быть может, инвертированием , можно получить функцию .

Доказательство. Возьмем полином Жегалкина для :

.

В силу нелинейности полинома в нем найдется член, содержащий не менее двух множителей. Без ограничения общности можно считать, что среди этих множителей присутствуют и . Тогда можно преобразовать полином следующим образом:

,

где в силу единственности полинома .

Пусть таковы, что . Тогда

,

где – константы, равные или . Рассмотрим функцию , получаемую из следующим образом:

.

Очевидно, что

.

Следовательно, .

Лемма. Классы Поста попарно различны.

Доказательство. Для доказательства леммы приведем функции, лежащие в классах, но так, чтобы классы взаимно не поглощались. Рассмотрим функции и построим таблицу принадлежности классам. В таблице будем ставить «+», если функция принадлежит классу, и «–» в противном случае.

0	+	–	–	+	+
1	–	+	–	+	+
	–	–	+	–	+

Если бы какие-нибудь два класса совпадали, то совпадали бы и соответствующие столбцы таблицы. Так как они не совпадают, делаем вывод о попарном различии классов.

Теорема Поста (о полноте). Для того чтобы система функций была полной необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов .

Доказательство. Необходимость. Пусть система полна. Тогда . Допустим, что содержится целиком в каком-либо из классов Поста (обозначим его через ), т.е. . В этом случае . Отсюда , что невозможно.

Достаточность. Пусть не содержится целиком ни в одном из пяти классов Поста. Выделим из нее подсистему функций. , где , и на ее основе построим полную систему.

1. При помощи построим функции (константы) 0 и 1 или функцию .

Разберем отдельно два случая:

(а) ;

(б) .

(а) Рассмотрим функцию . Из цепочки равенств следует, что .

(б) В этом случае для функции получаем , т.е. .

Аналогичным образом, используя функцию , строим константу 0 или функцию .

Итак, нами построены либо функция , либо обе константы 0 и 1. или

2. Если построена , то с помощью и , применяя лемму о несамодвойственной функции, строим константы 0 и 1.

Если есть обе константы 0 и 1, то .с помощью функций 0, 1 и , используя лемму о немонотонной функции, можно построить .

3. При помощи 0, 1, и , применяя лемму о нелинейной функции, строим функцию .

Система полная. Значит, и полная. Отсюда следует полнота системы . Теорема доказана.

Следствие 1. Из всякой полной системы можно выделить полную подсистему, содержащую не более пяти функций.

Это утверждение можно усилить, а именно, имеет место.

Лемма. Из всякой полной системы можно выделить полную подсистему, содержащую не более четырех функций.

Доказательство. Так как , то либо либо . Тогда полная система будет состоять из функций либо .

Пример 1. Определить количество функций классов и , зависящих от переменных .

Решение. Вектор значений функции имеет вид , т.е. определено только значение на нулевом

наборе переменных, свободных же . Следовательно, . Аналогично вычисляется количество функций класса .

Пример 2. Определить количество самодвойственных функций, зависящих от переменных.

Решение. Функция принимают противоположные значения на противоположных наборах переменных. Поэтому для ее задания достаточно задать первую половину ее вектора значений . Следовательно, количество самодвойственных функций, зависящих от переменных, равно .

Пример 3. Определить количество линейных функций, зависящих от переменных .

Решение. Различных линейных функций от переменных столько же, сколько различных векторов , т.е. . Задачи для самостоятельного решения.

1. Перечислить все самодвойственные функции от двух переменных.

2. Выяснить, является ли самодвойственной функция :

а) ;

б) ;

в) .

3. Выяснить, является ли самодвойственной функция , заданная векторно:

а) ; б) ;

в) ;

г) .

4. Определить, какие из переменных функций следует заменить на , а какие на с тем, чтобы получить константу:

а) ; б) ;

в) ; г) .

5. Выяснить при каких функция :

а) ;

б) ;

в) .

6. Перечислить все линейные функции от двух переменных.

7. Представив функцию полиномом, выяснить, является ли она линейной:

а) ;

б) ;

в) .

8. Выяснить, является ли линейной функция , заданная векторно:

а) ; б) ;

в) ; г) .

9. Подставляя на места переменных нелинейной функции функции из множества , получить хотя бы одну из функций :

а) ;

б) ;

в) ;

г) .

10. Найти число линейных функций ,

а) существенно зависящих в точности от переменных;

б) удовлетворяющих условию .

11. Выяснить, принадлежит множеству функция :

а) ;

б) .

12. Выяснить, при каких функция :

а) ;

б) .

13. Приведите все монотонные функции от двух переменных.

14. Выяснить, является ли монотонной функция :

а) ;

б) ;

в) ;

г) .

15. Выяснить, является ли монотонной функция , заданная векторно:

а) ; б) ;

в) ; г) .

16. Для немонотонной функции указать два соседних набора и значений переменных таких, что и :

а) ;

б) ;

в) .

17. Выяснить при каких функция монотонна:

а) ; б) .

18. Подсчитать число функций, зависящих от переменных и принадлежащих множеству :

а) ; б) ; в) ;

г) ; д) ; е) .

19. Выяснить, полна ли система функций :

а) ;

б) ;

в) ;

г) ;

д) ;

е) . Ответы

1. . 2. а) ; б) ; в) . 3. а) ;

б) ; в) ; г) . 4. а) заменить на , на или наоборот; б) существуют две пары наборов таких, что : (010) – (101) и (011) – (100). В первом случае заменив на , а на получим константу 0; во втором заменив на , а на получим константу 1; в) получим константу 1, заменив, например, на , а на получим константу 0; во втором заменив на , а на ; г) существуют три пары наборов таких, что : (0011) – (1100), (0100) – (1011) и (0110) – (1110). Можем координаты, соответствующие 0 в первом наборе каждой пары заменить на , а соответствующие 1 – на . 5. а) при нечетных ; б) – в) при всех . 6. . 7. а) ; б) ; в) . 8.а) ; б) ; в) ; г) . 9. а) ; б) ; в) ;

г) . 10. а) б) . 11. а) ;

б) . 12. а) при нечетных ; б) при всех и . 13. . 14. а) ; б) ; в) ; г) . 15. а) ; б) ; в) ; г) . 16. а) , ; б) , или ; , или ;

в) , .

17. а) при , при б) при и при всех . . 18. а) ; б) ; в) ; г) ; д) ; е) . 19. а) Нет. . б) Нет. . в) Нет. . г) Да. д) Да. е) Нет. .