Билеты к экзамену по курсу "Теория дискретных функций" (II поток, лектор В.Б.Кудрявцев)
Скачать билеты в формате PDF (123K)
Билет 1.
1. Теорема Поста о полноте в P2.
2. Информационные деревья. Понятия д.функции и о.д.функции.
Билет 2.
1. Теорема Поста о полноте в P2.
2. Задание д.функций каноническими уравнениями и диаграммами Мура.
Билет 3.
1. Теорема Кузнецова.
2. Теорема об отличимости двух состояний двух о.д.функций.
Билет 4.
1. Классы Tc и L. Их замкнутость и отличие от P2.
2. Теорема Кузнецова.
Билет 5.
1. Класс M. Его замкнутость и отличие от P2.
2. Процедура проверки на полноту конечных систем в Pk.
Билет 6.
1. Задание булевых функций с помощью д.н.ф.
2. Процедура проверки на полноту конечных систем в Pk.
Билет 7.
1. Функции k-значной логики. Существенные переменные. Равенство
функций.
2. Лемма Яблонского.
Билет 8.
1. Формулы. Суперпозиции. Замыкание, его свойства. Полнота.
2. Лемма Яблонского.
Билет 9.
1. Конечная порожденность Pk.
2. Лемма о включении [Pk(x) ∪ {f}] ⊃ PE2k при
k>2 и существенности f.
Билет 10.
1. Лемма о включении [Pk(x) ∪ {f}] ⊃ PE2k при
k>2 и существенности f.
2. Операция суперпозиции для классов д. и о.д. функций.
Билет 11.
1. Лемма о включении [Pk(x) ∪ {f}]⊃ Pl+1k при
k>2, если f - существенная и [Pk(x) ∪ {f}]⊃
Plk для 1<l<k.
2. Операция обратной связи для классов д. и о.д. функций.
Билет 12.
1. Класс S. Его замкнутость и отличие от P2.
2. Лемма о включении [Pk(x) ∪ {f}]⊃ Pl+1k при
k>2, если f - существенная и [Pk(x) ∪ {f}]⊃
Plk для 1<l<k.
Билет 13.
1. Теорема Жегалкина.
2. Теорема Слупецкого.
Билет 14.
1. Лемма о равенстве U(R) ∩ Pk(x1,x2)=R.
2. Теорема Слупецкого.
Билет 15.
1. Неполнота в Pk множества M∪
{g1(x1,x2),g2(x1,x2)} при неполноте M.
2. Теорема о полноте класса полиномов в Pk, k>2.
Билет 16.
1. Лемма о равенстве [Pk(x)∪ PkA]=Pk|A|∪ Pk(x).
2. Теорема о полноте класса полиномов в Pk, k>2.
Билет 17.
1. Классы Tc и L. Их замкнутость и отличие от P2.
2. Континуальность множества замкнутых классов в Pk при k>2.
Билет 18.
1. Континуальность множества замкнутых классов в Pk при k>2.
2. Операция суперпозиции для классов д. и о.д. функций.
Билет 19.
1. Задание булевых функций с помощью д.н.ф.
2. Теорема о периодичности для о.д.функций.
Билет 20.
1. Функции k-значной логики. Существенные переменные. Равенство
функций.
2. Теорема о периодичности для о.д.функций.
Билет 21.
1. Формулы. Суперпозиции. Замыкание, его свойства. Полнота.
2. Теорема Мура об отличимости состояний одной о.д.функции.
Билет 22.
1. Конечная порожденность Pk.
2. Теорема Мура об отличимости состояний одной о.д.функции.
Билет 23.
1. R-множества. Процедура построения R-множеств.
2. Отсутствие конечной полной системы д.функций относительно
операций суперпозиции.
Билет 24.
1. Замкнутость класса U(R).
2. Отсутствие конечной полной системы д.функций относительно
операций суперпозиции.
Билет 25.
1. Лемма о равенстве U(R) ∩ Pk(x1,x2)=R.
2. Конечная порожденность класса д.функций с помощью операций
суперпозиции и обратной связи.
Билет 26.
1. Неполнота в Pk множества M∪
{g1(x1,x2),g2(x1,x2)} при неполноте M.
2. Конечная порожденность класса д.функций с помощью операций
суперпозиции и обратной связи.
| 
