13 515
правок
Изменения
→Теория функциональных систем
== Теория функциональных систем ==
==== Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub> ====
* Формула над системой {''f<sub>k</sub>''}: 1) ''f<sub>i</sub>''- формула 2) ''f<sub>i</sub>''(''A<sub>1</sub>'',…,''A<sub>n</sub>'') — формула, где A — переменная либо формула.
* Подробнее — в Яблонском, там много лемм.
==== Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>'' ====
==== Теорема Слупецкого ====
==== Особенности ''k''-значных логик ====
==== Автоматы. Регулярные события и их представление в автоматах ====
==== Эксперименты с автоматами ====
==== Алгоритмическая неразрешимость проблемы полноты для автоматов ====
==== Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга ====
==== Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях ====
== Комбинаторный анализ и теория графов ==
