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

 

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

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