English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

Программа курса по «Теории дискретных функций» (II поток, лектор В.Б.Кудрявцев)

 

Двузначная логика (Р2).

  1. Функции алгебры логики. Существенные переменные. Равенства функций.
  2. Элементарные функции алгебры логики и их свойства.
  3. Формулы и суперпозиции. Равенства.
  4. Замыкания, замкнутость и полнота систем булевых функций.
  5. Дизъюнктивная нормальная форма. Полнота системы {&, V, ┐, 0, 1}.
  6. Замкнутость классов T0, T1, L и их отличие от P2.
  7. Замкнутость классов S, M и их отличие от P2.
  8. Попарная невложимость классов T0, T1, L, S, M.
  9. Получение из немонотонной булевой функции с помощью констант 0 и 1 функции отрицания.
  10. Получение из несамодвойственной булевой функции с помощью функции отрицания констант 0 и 1.
  11. Получение из нелинейной булевой функции с помощью функции отрицания и констант конъюнкции.
  12. Теорема Поста о полноте в P2.
  13. Понятие базиса в замкнутом классе булевых функций. Указание всех длин базисов в P2.
  14. Понятие предполного класса в P2. Предполнота классов T0, T1, L, S, M. Отсутствие других предполных классов в P2.
  15. Большая теорема Поста о структуре замкнутых классов в P2.

 

К-значная логика (Рк).

  1. Функции k-значной логики. Существенные переменные. Отношение равенства. Элементарные функции. Класс M0.
  2. Формулы. Суперпозиции. Замыкание, его свойства. Функциональные системы k-значной логики.
  3. Полнота и выразимость для функциональных систем. Конечная порожденность Pk.
  4. R-множества. Конструктивность их описания.
  5. Замкнутость класса сохранения R-множества.
  6. Лемма о равенстве U(R)∩Pk(x1,x2)=R.
  7. Лемма о неполноте в Pk множества M∪{g1(x1, x2), g2(x1, x2)} при неполноте M.
  8. Критериальные системы в Pk. Теорема Кузнецова.
  9. Теорема о критериальности системы всех предполных классов в Pk.
  10. Алгоритм проверки на полноту конечных систем в Pk.
  11. Лемма Яблонского.
  12. Лемма о равенстве [Pk(x) ∪ PAk]=P|A|k∪ Pk(x).
  13. Лемма о включении [Pk(x) ∪ {f}] ⊃ PE2k при k>2, f – существенной функции.
  14. Лемма о включении [Pk(x) ∪ {f}]⊃ Pl+1k при k>2, f – существенной функции, 1<l<k и включении [Pk(x) ∪ {f}]⊃ Plk.
  15. Теорема Слупецкого.
  16. Теорема о полноте полиномов в Pk.
  17. Континуальность множества замкнутых классов в Pk при k>2.

 

Автоматы.

  1. Информационные деревья. Понятия д.функции и о.д.функции.
  2. Задание д.функций каноническими уравнениями и диаграммами Мура.
  3. Теорема Мура об отличимости двух состояний о.д.функции.
  4. Теорема Мура об отличимости состояний двух о.д.функций.
  5. Операция суперпозиции для классов д. и о.д. функций.
  6. Операция обратной связи для классов д. и о.д. функций.
  7. Теорема о периодичности для о.д.функций.
  8. Отсутствие конечной полной системы д.функций относительно операций суперпозиции.
  9. Конечная порожденность класса о.д.функций с помощью операций суперпозиции и обратной связи.
   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru