О P-множествах автономных функций

• Автор: Родин, Александр Алексеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 91 с. : ил.

Содержание

ВВЕДЕНИЕ

Глава 1. О континуальности числа предполных классов, содержащих

Р—множество

1.1. Доказательство теоремы 1.

Глава 2. Алгоритмы распознавания полноты систем, содержащих

Р—множества

2.1. Принятые обозначения

2.2. Порождающее множество содержит тождественную функцию и обе константы

2.2.1. Проверка эффективности условий теоремы 2.

2.2.2. Доказательство теоремы 2.
2.2.3. Следствия из теоремы 2.
2.3. Порождающее множество содержит тождественную функцию и одну из констант
2.4. Порождающее множество содержит тождественную функцию
2.4.1. Критерий А-полноты
2.4.2. Система М содержит константную функцию
2.4.3. Система М содержит функцию задержки
2.5. Порождающее множество не содержит тождественную функцию
2.6. Эффективный критерий А-выразимости для систем, содержащих
Р—множества
Глава 3. Полные системы в Р—множествах
3.1. Порождающее множество содержит обе константы
3.2. Порождающее множество содержит тождественную функцию и отрицание
СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ
Одной из важных проблем, рассматриваемых в дискретной математике и математической кибернетике, является проблема полноты для функциональных систем. Функциональная система (ф.с.) представляет собой множество функций и множество операций над этими функциями. Проблема полноты для ф.с. состоит в описании всех таких подмножеств функций, используя которые с помощью операций ф.с. можно выразить все принадлежащие ф.с функции.
С точки зрения алгебры, ф.с. могут рассматриваться как вариант универсальных алгебр. Существенной особенностью ф.с., выделяющей их из общего класса универсальных алгебр, является содержательная связь ф.с. с реальными кибернетическими моделями управляющих систем и отображение важнейших характеристик таких моделей: функционирования, правил построения более сложных систем из заданных, описания функционирования сложных систем по функционированию их компонент.
Центральное место среди ф.с. принадлежит итеративным ф.с., представляющим собой множество дискретных функций с операциями итерации — суперпозиции, обратной связи, а также их модификаций [21], [28]. В свою очередь, итеративные ф.с. могут быть разделены на два типа: истинностные ф.с. и последовательностные ф.с. В первом случае функции, принадлежащие ф.с., вычисляются без использования, а во втором — с использованием "памяти".
Важнейшим примером истинностных и последовательностных ф.с. являются к—значная логика с одной стороны и ф.с. автоматных функций с другой. Для к—значных логик (ф.с. Р*,) основная проблема в теории итеративных ф.с. — проблема полноты, была решена. В 1921 г. Э. Постом была полностью описана структура замкнутых классов в двузначной логике. Это описание, изложенное в виде монографии в 1941 году [4], по существу эквивалентно решению проблемы полноты для произвольных двузначных логик, в которых в качестве операций выступают операции суперпозиции. Для произвольного к > 3 усилиями многих авторов ( С.В. Яблон-

существенно зависящая не менее, чем от двух переменных, и достижимое из ^‘ по некоторому набору
(31(^)> I 9т{А))
По доказанному выше, функции а.-л.
Вд91 , ■ - - , Вддт ,
будут существенно зависеть не более, чем от одной переменной. Тогда существует такие
01, ... , а/с € Е2,

/ф,'1 (а 1. ... ,а/с), ... ,Едят(а1, ... ,а/с) ^ Я(д,),
поскольку состояние г/(‘ не является локально существенным. Это означает, что при подаче на вход функции ю, находящейся в этом состоянии, набора а = (а^ ... ,а,к), функция /1 покидает компоненту, в которой содержится д[‘. Обратно в эту компоненту функция /г не может вернутся, что следует из определения компоненты. Рассмотрим набор
у1 = Ла= (Агаи ... , Акак).
Ясно, что
Яг $ и{Ь,фк(д1(^1),... ,дт(ъ)),ЯН),з,д).
т.к. функция /г при таких начальных значениях входных данных уже побывала в компоненте, где лежит вышла из нее и обратно вернутся уже не может. Если в иЗ(ф‘ (31(71),... , дт(ъ)), Я11)) содержится еще какое-либо существенное состояние функции /г, действуем таким же образом. Состояний второго типа конечное число, поэтому рано или поздно получим такой набор В, что иЗ(фн(д(В),... , дт(В)), д'1) не содержит ни одного существенного состояния функции /г. Это означает, что со-