Алгоритмическая сложность решения некоторых задач в многозначных логиках

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

ГЛАВА I. Алгоритмическая сложность задачи выразимости
в многозначных логиках.
§ 1.1. Описание и анализ сложности алгоритма
решения задачи выразимости в алгебре логики.
§ 1.2. НР -трудность задачи выразимости
в Рк, (к^з).
Глава II. Метод построения быстрых алгоритмов
в 1^-значной логике.
Глава III. Алгоритмическая сложность задачи
распознавания полноты в Р|с
ЛИТЕРАТУРА
ВВЕЩЕНИЕ
Одной из ветвей математической логики является многозначная логика, которая в последнее время бурно развивается. Быстрое развитие многозначной логики связано с тем, что во многих областях науки и техники стали возникать задачи, для описания и решения которых потребовался аппарат математической логики с высказываниями, принимающими более двух значений. Первой работой, в которой в наиболее полной форме были, освещены результаты, относящиеся к функциональным, построениям в многозначной логике, была работа [2Ï]
Многозначная логика изучает множество Рк всех функций Кх1) Е(ь~► Ejt , где Еjt~[оД,It-l},
Одними, из важных задач, возникающих в теории функций
к- -значной логики [ к. ^ £) , являются задача о возможности выразить некоторую функцию L°)^Pk через
функции системы
1 fl (х"") , ^(Зс.11*), • • • , $т. (х*1"1) ] ,
иI , посредством
операции суперпозиции, а также задача распознавания полноты системы
1П(ха1), Ых11), ... >
функций из Рь . Сразу заметим, что вторая задача является, в некотором смысле, частным случаем первой задачи, поскольку сводится к задаче о возможности выразить некоторую функцию Шеффера в Рк через функции системы

Обе задачи часто возникают в приложениях к. -значных логик, например, в теории управляющих систем задача распознавания выразимости эквивалентна задаче о возможности синтеза некоторой функции в конечном неполном базисе
И*(г*1), 5*(а**),
а задача распознавания полноты эквивалентна задаче о возможности синтеза произвольной функции в некотором базисе
151 , ... , &(й14)}
В связи с вышесказанным, особый интерес представляет изучение поставленных задач с алгоритмической точки зрения.
Известно, что задача распознавания полноты в Р к алгоритмически разрешима [24] . Алгоритмическая разрешимость -задачи распознавания выразимости в Рк- следует из несложного обобщения алгоритма распознавания полноты в Р1с , описанного в [24] . Однако оба алгоритма являются алгоритмами переборного типа, имеющими высокую временную сложность.
Появление быстродействующих электронно-вычислительных машин усилило требования к алгоритмам, поскольку различные усовершенствования алгоритмов стали приносить существенный выигрыш во времени их работы. Поэтому, в настоящее время возникла необходимость построения алгоритмов решения задач распознавания выразимости и полноты в Рк возможно меньшей сложности. Отказ от сложных алгоритмов переборного типа потребовал при построении алгоритмов решения поставленных задач использовать более глубокие исследования в |с -значных логиках.
Американским математиком Э. Постом в И была описана структура всех замкнутых классов в , Этот результат позволяет свести задачу распознавания выразимости в Р^ к задаче распознавания принадлежности функций из различным

функцией с ошибкой в ^ и на наборах группы б* этой
функции закодировано множество /*>1
Если хотя бы одно из перечисленных условий не выполняется, то ■Ц (оо^) является функцией с ошибкой В
Доказательство. I. Пусть и функции,
которые не ЯВЛЯЮТСЯ функциями С ошибкой В $1 , И Л .
Рассмотрим наборы оСо — ( 0 , *) и = ,2Н'1)
из группы наборов бс . Эти наборы соответствуют некоторому элементу С1 множества £2 (5- и - подмножества множества Ло , а множество > либо совпадает С множеством , либо,в случае если | ,
является собственным подмножеством множества £о* , см
Если элемент /X не входит ни в множество £>1 , ни
в множество , то это означает, что
$'(£)=^(о^Ьо и j *
Но тогда и‘ ^ (о^о) = О » ^ ( см* Рис» ,
что указывает на непринадлежность элемента С1 множеству,
которое закодировано на наборах группы функции 5(*п). •
Если элемент С1 принадлежит и не принадлежит £>1 ,

поэтому см. рис. 2^(
Если элемент С1 принадлежит и не принадлежит £^
, то ?(.
Таким образом, снова
В двух последних случаях получаем, что элемент С1 принадлежит множеству, которое закодировано на группе наборов бб