13 514
правок
Изменения
→Теория функциональных систем
== Теория функциональных систем ==
Берётся снова из {{Скачать|Яблонский - Введение в дискретную математику.djvu}}.
==== Проблема полноты. Теорема о полноте систем функций двузначной логики ''P''<sub>2</sub> ====
* Замкнутые классы: ''T<sub>0</sub>'' (f(0,0…0)=0), ''T<sub>1</sub>'' (f(1,1…1)=1), ''S'' (f(!x<sub>1</sub>,!x<sub>2</sub>,…!x<sub>n</sub>) = !f(!x<sub>1</sub>,!x<sub>2</sub>,…!x<sub>n</sub>)), ''M'' (1й набор по всем переменным ≥ 2го, тогда f(1го)≥f(2го)), ''L'' (формула над +, &, 1, 0, оно же полином Жегалкина)
* Теорема о полноте: если система не входит полностью ни в одно из ''T<sub>0</sub>'', ''T<sub>1</sub>'', ''S'', ''M'', ''L'' — то она полна. Доказывается через получение констант 0 и 1 из не входящих в ''T<sub>0</sub>'', ''T<sub>1</sub>'' и ''S'', из них и функции, не принадлежащей ''L''- отрицания, и из них, отрицания и функции, не принадлежащей ''M'' — дизъюнкции.
==== Алгоритм распознавания полноты систем функций ''k''-значной логики ''P<sub>k</sub>'' ====
* Полнота, замкнутость- см'''Т. на 1(один) вопрос выше=) * Теорема: ''' существует алгоритм анализа системы на полноту. («в лоб»)<br /> '''Док-во: пошагово ''' строим мн-ва функций от 2х переменных, подставляя в функции из нашей системы либо функции от 2х переменных с предыдущего шага, либо просто переменную x<sub>1</sub> или x<sub>2</sub>. Так как функций k-значной логики у нас конечное количество, то рано или поздно множество окажется замкнутым. Если оно совпадает со всеми функциями 2х переменных- переменных — то система полна, иначе нет. * Предыдущий результат с практической т.з. бесполезен, ибо задолбаешься так проверять=) Поэтому мы сначала введем понятие функции, сохраняющей множество (см. опять же предыдущий вопрос, только тут не 0 и 1, а произвольные множества- множества — причем замкнутость класса, сохраняющего множество, есть всегда, независимо от того, какое это множество), а потом! мы докажем теорему Мы докажем…* '''Т.''' (о функциональной полноте) , Кузнецова! ) про то, что и в k-значной логике можно построить аналоги 5 классов из бинарной(см. теорему о полноте на 1 вопрос выше), то есть если система полностью не вложена ни в 1 из них- то она полна. * И все равно нам это не поможет, потому что такие классы задолбаешься строить(вроде бы для 3 и 4-значной логики сделали, для остальных- остальных — нишмагли, но тут не уверен). Поэтому придумали теорему Слупецкого…
==== Теорема Слупецкого ====
* …которая в обобщенном виде гласит, что если система содержит все функции 1й переменной, принимающие не более k-1 значений (в необобщенном виде — просто все функции 1й переменной), то для полноты н. и д., чтобы она содержала еще существенную (то есть зависящую от 2+ переменных) функцию, принимающую k значений. Подробнее про док-во — в Яблонском, там несколько длинных (по доказательству) лемм.
* Это уже хорошо, но всех функций 1й переменной, принимающих не более k-1 значений, все равно очень много. Поэтому проще искать «базисы» для таких функций, примеры см. в Яблонском, с.64-65.
==== Особенности ''k''-значных логик ====
* В бинарной логике каждый замкнутый класс имеет конечный базис; всего их счётное число; всякую функцию можно записать полиномом.
* А в k-значной — нифига.
* '''Т.''' (Янова) для всякого k≥3 в P<sub>k</sub> {{exists}} замкнутый класс, не имеющий базиса.
* '''Т.''' (Мучника) для всякого k≥3 в P<sub>k</sub> {{exists}} замкнутый класс, имеющий счётный базис.
* '''Т.''' для всякого k≥3 в P<sub>k</sub> {{exists}} континуум различных замкнутых классов.
* '''Т.''' система полиномов в P<sub>k</sub> полна ⇔ k — простое число.
==== Автоматы. Регулярные события и их представление в автоматах ====
==== Алгоритмическая неразрешимость проблемы эквивалентности слов в ассоциативных исчислениях ====
* Берётся из {{Файл:Мальцев - Алгоритмы и рекурсивные функции.djvu}}, стр. 254.
* '''Опр.''' ассоциативного исчисления (набор замен); эквивалентные слова.
* '''Т.''' (Пост, Марков) {{exists}} ассоциативное исчисление с алгоритмически неразрешимой проблемой эквивалентности слов.
== Комбинаторный анализ и теория графов ==
