Предикатное определение замкнутых классов

Материал из Кафедра математической кибернетики
Версия от 18:46, 31 октября 2013; Root (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович.

Программа курса

Предикаты на множестве Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): E_k . Диагонали. Операции конъюнкции и проектирования. Формулы с предикатами. Операция замыкания, замкнутые классы предикатов.

Отношение сохранения предиката функцией. Функторы Pol и Inv. Основные свойства функторов Pol, Inv.

Соответствия Галуа. Замыкания Галуа. Совпадение замкнутых классов Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): F

и

Pol(Inv(Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): F )).

Совпадение замкнутых классов Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): R

и Inv(Pol(Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): R

)).

Минимальные классы и минимальные предикаты. Эквивалентные определения минимальных предикатов. Минимальность булевых предикатов Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): x=0,\ x=1,\ x\ne y,\ x\le y,\ x_1+x_2=x_3+x_4 .

Операции декартовой степени и взятия полного прообраза, перестановочность с операциями конъюнкции и проектирования. Сохранение минимальности предиката при операциях декартовой степени и взятия полного прообраза. Минимальность предиката Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): \tau_k .

Критерий определяемости замкнутого класса конечным числом предикатов. Предикатное определение классов Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): U,\ K,\ D,\ O^m,\ I^m .

Теория Галуа для симметрической полугруппы Невозможно разобрать выражение (синтаксическая ошибка): {\bf T}_k

и симметрической

группы Невозможно разобрать выражение (синтаксическая ошибка): {\bf S}_k .

Литература

  1. Боднарчук В.Г., Калужнин Л.А., Котов В.Н., Ромов Б.А. Теория Галуа для алгебр Поста // Кибернетика. — 1969. — N 3. — С. 1—10; N 5. — С. 1—9.
  2. Марченков С.С. Замкнутые классы булевых функций. М.: Наука, 2000.
  3. Марченков С.С. Предполнота замкнутых классов в P_k: предикатный подход // Математические вопросы кибернетики, вып. 6. — 1996. — С. 117—132.

Ссылки

  • Программа курса (pdf)