Вопросы к коллоквиуму по Pk, курс "Теория дискретных функций" (II поток)

Скачать список вопросов в формате PDF (90K)

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. Лемма о включении [Pk(x) ∪ {f}] ⊃ PE2k при 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.