Программа курса по «Теории дискретных функций» (II поток, лектор В.Б.Кудрявцев)
Двузначная логика (Р2).
- Функции
алгебры логики. Существенные переменные. Равенства функций.
- Элементарные
функции алгебры логики и их свойства.
- Формулы
и суперпозиции. Равенства.
- Замыкания,
замкнутость и полнота систем булевых функций.
- Дизъюнктивная
нормальная форма. Полнота системы {&, V, ┐,
0, 1}.
- Замкнутость
классов T0, T1, L
и их отличие от P2.
- Замкнутость
классов S, M и их отличие от P2.
- Попарная
невложимость классов T0, T1, L,
S, M.
- Получение
из немонотонной булевой функции с помощью констант 0 и 1 функции
отрицания.
- Получение
из несамодвойственной булевой функции с помощью функции отрицания констант
0 и 1.
- Получение
из нелинейной булевой функции с помощью функции отрицания и констант
конъюнкции.
- Теорема
Поста о полноте в P2.
- Понятие
базиса в замкнутом классе булевых функций. Указание всех длин базисов в P2.
- Понятие
предполного класса в P2.
Предполнота классов T0, T1, L,
S, M. Отсутствие других предполных классов в P2.
- Большая
теорема Поста о структуре замкнутых классов в P2.
К-значная логика (Рк).
- Функции k-значной логики. Существенные
переменные. Отношение равенства. Элементарные функции. Класс M0.
- Формулы. Суперпозиции. Замыкание, его свойства.
Функциональные системы k-значной логики.
- Полнота и выразимость для функциональных систем.
Конечная порожденность Pk.
- R-множества.
Конструктивность их описания.
- Замкнутость класса сохранения R-множества.
- Лемма о равенстве U(R)∩Pk(x1,x2)=R.
- Лемма о неполноте в Pk множества M∪{g1(x1, x2), g2(x1,
x2)} при неполноте M.
- Критериальные системы в Pk. Теорема
Кузнецова.
- Теорема о критериальности системы всех предполных
классов в Pk.
- Алгоритм проверки на полноту конечных систем в Pk.
- Лемма Яблонского.
- Лемма о равенстве [Pk(x) ∪ PAk]=P|A|k∪ Pk(x).
- Лемма о включении [Pk(x) ∪ {f}] ⊃
PE2k при
k>2, f – существенной функции.
- Лемма о включении [Pk(x) ∪ {f}]⊃
Pl+1k при k>2, f – существенной функции, 1<l<k и включении [Pk(x) ∪ {f}]⊃ Plk.
- Теорема Слупецкого.
- Теорема о полноте полиномов в Pk.
- Континуальность множества замкнутых классов в Pk
при k>2.
Автоматы.
- Информационные деревья. Понятия д.функции и о.д.функции.
- Задание д.функций каноническими уравнениями и диаграммами Мура.
- Теорема Мура об отличимости двух состояний о.д.функции.
- Теорема Мура об отличимости состояний двух о.д.функций.
- Операция суперпозиции для классов д. и о.д. функций.
- Операция обратной связи для классов д. и о.д. функций.
- Теорема о периодичности для о.д.функций.
- Отсутствие конечной полной системы д.функций относительно операций суперпозиции.
- Конечная порожденность класса о.д.функций с помощью операций суперпозиции и обратной связи.
|
|