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

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

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

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

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

Автоматы.

1. Информационные деревья. Понятия д.функции и о.д.функции.
2. Задание д.функций каноническими уравнениями и диаграммами Мура.
3. Теорема Мура об отличимости двух состояний о.д.функции.
4. Теорема Мура об отличимости состояний двух о.д.функций.
5. Операция суперпозиции для классов д. и о.д. функций.
6. Операция обратной связи для классов д. и о.д. функций.
7. Теорема о периодичности для о.д.функций.
8. Отсутствие конечной полной системы д.функций относительно операций суперпозиции.
9. Конечная порожденность класса о.д.функций с помощью операций суперпозиции и обратной связи.