Программа курса по «Теории дискретных функций» (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. Конечная порожденность класса о.д.функций с помощью операций суперпозиции и обратной связи.