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

Скачать билеты в формате PDF (123K)

Билет 1.

1. Теорема Поста о полноте в P₂.

2. Информационные деревья. Понятия д.функции и о.д.функции.

Билет 2.

1. Теорема Поста о полноте в P₂.

2. Задание д.функций каноническими уравнениями и диаграммами Мура.

Билет 3.

1. Теорема Кузнецова.

2. Теорема об отличимости двух состояний двух о.д.функций.

Билет 4.

1. Классы T_c и L. Их замкнутость и отличие от P₂.

2. Теорема Кузнецова.

Билет 5.

1. Класс M. Его замкнутость и отличие от P₂.

2. Процедура проверки на полноту конечных систем в P_k.

Билет 6.

1. Задание булевых функций с помощью д.н.ф.

2. Процедура проверки на полноту конечных систем в P_k.

Билет 7.

1. Функции k-значной логики. Существенные переменные. Равенство функций.

2. Лемма Яблонского.

Билет 8.

1. Формулы. Суперпозиции. Замыкание, его свойства. Полнота.

2. Лемма Яблонского.

Билет 9.

1. Конечная порожденность P_k.

2. Лемма о включении [Pk(x) ∪ {f}] ⊃ PE2k при k>2 и существенности f.

Билет 10.

1. Лемма о включении [Pk(x) ∪ {f}] ⊃ PE2k при k>2 и существенности f.

2. Операция суперпозиции для классов д. и о.д. функций.

Билет 11.

1. Лемма о включении [P_k(x) ∪ {f}]⊃ P^l+1_k при k>2, если f – существенная и [P_k(x) ∪ {f}]⊃ P^l_k для 1<l<k.

2. Операция обратной связи для классов д. и о.д. функций.

Билет 12.

1. Класс S. Его замкнутость и отличие от P₂.

2. Лемма о включении [P_k(x) ∪ {f}]⊃ P^l+1_k при k>2, если f – существенная и [P_k(x) ∪ {f}]⊃ P^l_k для 1<l<k.

Билет 13.

1. Теорема Жегалкина.

2. Теорема Слупецкого.

Билет 14.

1. Лемма о равенстве U(R) ∩ P_k(x₁,x₂)=R.

2. Теорема Слупецкого.

Билет 15.

1. Неполнота в P_k множества M∪ {g₁(x₁,x₂),g₂(x₁,x₂)} при неполноте M.

2. Теорема о полноте класса полиномов в P_k, k>2.

Билет 16.

1. Лемма о равенстве [P_k(x)∪ P_k^A]=P_k^|A|∪ P_k(x).

2. Теорема о полноте класса полиномов в P_k, k>2.

Билет 17.

1. Классы T_c и L. Их замкнутость и отличие от P₂.

2. Континуальность множества замкнутых классов в P_k при k>2.

Билет 18.

1. Континуальность множества замкнутых классов в P_k при k>2.

2. Операция суперпозиции для классов д. и о.д. функций.

Билет 19.

1. Задание булевых функций с помощью д.н.ф.

2. Теорема о периодичности для о.д.функций.

Билет 20.

1. Функции k-значной логики. Существенные переменные. Равенство функций.

2. Теорема о периодичности для о.д.функций.

Билет 21.

1. Формулы. Суперпозиции. Замыкание, его свойства. Полнота.

2. Теорема Мура об отличимости состояний одной о.д.функции.

Билет 22.

1. Конечная порожденность P_k.

2. Теорема Мура об отличимости состояний одной о.д.функции.

Билет 23.

1. R-множества. Процедура построения R-множеств.

2. Отсутствие конечной полной системы д.функций относительно операций суперпозиции.

Билет 24.

1. Замкнутость класса U(R).

2. Отсутствие конечной полной системы д.функций относительно операций суперпозиции.

Билет 25.

1. Лемма о равенстве U(R) ∩ P_k(x₁,x₂)=R.

2. Конечная порожденность класса д.функций с помощью операций суперпозиции и обратной связи.

Билет 26.

1. Неполнота в P_k множества M∪ {g₁(x₁,x₂),g₂(x₁,x₂)} при неполноте M.

2. Конечная порожденность класса д.функций с помощью операций суперпозиции и обратной связи.