Изменения

=== Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''₂.===  * Формула над системой {''f_k''}: 1) ''f_i''- формула 2) ''f_i''(''A₁'',...…,''A_n'')-  — формула, где A- A — переменная либо формула. * Полнота системы {''f_k''}: все функции из ''P''₂ можно выразить формулами над {''f_k''}. * Замкнутый класс- класс — все формулы над функциями из класса принадлежат тому же классу. * Замкнутые классы: ''T₀'' (f(0,0...00…0)=0), ''T₁'' (f(1,1...11…1)=1), ''S'' (f(!x₁,!x₂,...…!x_n)= !f(!x₁,!x₂,...…!x_n)), ''M'' (1й набор по всем переменным >= ≥ 2го, тогда f(1го)>=≥f(2го)), ''L'' (формула над +, &, 1, 0, оно же полином Жегалкина) * Теорема о полноте: если система не входит полностью ни в одно из ''T₀'', ''T₁'', ''S'', ''M'', ''L''- то она полна. Доказывается через получение констант 0 и 1 из не входящих в ''T₀'', ''T₁'' и ''S'', из них и функции, не принадлежащей ''L''- отрицания, и из них,отрицания и функции, не принадлежащей ''M''- дизъюнкции. Подробнее- * Подробнее — в Яблонском, там много лемм. # === Алгоритм распознавания полноты систем функций ''k''-значной логики ''P_k''.===# === Теорема Слупецкого.===# === Особенности ''k''-значных логик.===# === Автоматы. Регулярные события и их представление в автоматах.===# === Эксперименты с автоматами.===# === Алгоритмическая неразрешимость проблемы полноты для автоматов.===# === Вычислимые функции. Эквивалентность класса рекурсивных функций и класса функций, вычислимых на машинах Тьюринга.===# === Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях.===