Бульові функції, Детальна інформація

Нехай F позначає множину всіх можливих функцій деякої алгебри функцій A з операцією суперпозиції.

Означення. Множина функцій S називається передповним класом алгебри A, якщо (S((F і за будь-якої функції f з множини F\S набір S({f} є повним: (S({f}(=F.

Критерій Поста. Нехай S1, S2, … – усі передповні класи алгебри функцій F. Множина функцій M є повною тоді й тільки тоді, коли для кожного передповного класу Si множина M містить f(M\Si.

Приймемо це твердження без доведення.

Пост також дослідив передповні класи алгебри бульових функцій. Їх виявилося лише 5. Це множини всіх функцій:

що зберігають сталу 0,

що зберігають сталу 1,

самодвоїстих,

лінійних,

монотонних.

Означимо вказані функції.

Означення. Функція f(n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.

Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.

Наприклад, тотожна функція f(x)=x зберігає сталі 0 і 1, функція f(x)=(x не зберігає жодної.

****Двоїста до …

Означення. Функція f(n) є самодвоїстою, якщо для всіх пар протилежних наборів вона приймає на них протилежні значення:

f(n)((1, (2, …, (n) = ****f(n)((1, (2, …, (n) зберігає сталу 0, якщо на нульовому наборі має значення 0: f(n)(0, 0, …, 0)=0.

Означення. Функція f(n) зберігає сталу 1, якщо на одиничному наборі має значення 1: f(n)(1, 1, …, 1)=1.

Неважко переконатися, що множини означених функцій, позначені відповідно T0, T1, S, L, M, є замкненими класами.

Список рекомендованої літератури

Виленкин Н.Я. Популярная комбинаторика.–М.: Наука, 1975.

Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.–М.: Наука, 1973.

Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики.–М.: Наука, 1982

Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование.–К.: Наукова думка, 1988.

Ершов Ю.Л., Палютин Е.А., Математическая логика.–М.:Наука, 1979.

Карри Х.Б. Основания математической логики.–М.: Мир, 1969.

Клини С.К. Математическая логика.– М.: Мир, 1973.

Колмогоров А.Н. Фомин С.В. Элементы теории функций и функционального анализа.–М.: Наука, 1981.

Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.–М.:Энергоатомиздат, 1988.

Курош А.Г. Лекции по общей алгебре.–М.: Наука, 1973.