Введение к работе
. Актуальность темы.
В последние десятилетия одним из активно развивающихся разделов дискретной математики и математической кибернетики является теория функциональных систем. Ее предметом исследования выступают дискретные функции и операции над ними, позволяющие порождать из заданных функций с помощью этих операций новые функции. Такая модель возникает в целом ряде научных областей. Так, в логике из конкретных функциональных высказываний можно с помощью традиционных или обобщенных логических связок порождать новые высказывания. В алгебре, отправляясь от конкретных объектов, можно строить термальные конструкции таких объектов. В технике схемы, построенные из элементарных вычислителей, позволяют решать наперед заданные задачи, и т.д.
Содержательно функциональная система (ф.с.) представляет собой универсальную алгебру вида Я=(Р,Ш, где Р — некоторое множество функций, а П — множество операций над функциями из Р со значениями в Р [1].
Изучение функциональных систем идет в нескольких направлениях. С одной стороны изучаются конкретные ф.с, такие как итеративные алгебры функций конечно-автоматных и автоматных функций, алгебры вычислимых функций и др. С другой стороны, изучаются общего вида алгебры дискретных функций.
Укажем в этой связи работы Э.Поста[2],
С.В.Яблонского[3], А.В.Кузнецова[8], А.И.Мальцева[4],
И.Розенберга[5], В.Б.Кудрявцева[б], В.А.Буевича[7],
цитированных там авторов и др.
Конкретные ф.с, упомянутые выше, изучаются как модельные объекты, на которых'' уточняются задачи и формируется техника доказательств. Все они несут существенные черты реальных функций, отмеченные ранее.
В предполагаемом исследовании изучается новая функциональная система, которая возникает при надежностном подходе к синтезу схем из функциональных элементов и автоматов.
Как известно, реальные элементы, из которых строятся вычислительные схемы, допускают неисправности, в результате чего элементы могут реализовать не те функции,
которые им присваивались при конструировании. Тем самым и схема, построенная из таких элементов, реализует не ту функцию, которую она должна была бы реализовать. Таким образом, можно считать, что в общем случае элемент реализует сразу несколько функций, называемых нами пучком функций. То же относится и к схеме из этих элементов.
Аналогичная ситуация возникает при анализа автоматов и автоматных схем. Здесь при тестировании автоматов важно устанавливать, какой набор функций реализует автомат при вариации его состояний. Тем самым каждый элемент в автоматной схеме, как и вся схема, также выступают как пучки функций.
Подобные ситуации возникают и в других случаях, например, при рассмотрении сложных производств, иерархического административного управления и т.п.
Таким образом, возникает необходимость рассмотрения объектов в виде пучков функций с операциями над ними, индуцируемыми операциями над функциями и автоматами. Изучению таких функциональных систем и посвящено это исследование.
Цель работы.
Исследовать условия выразимости и полноты для функциональных систем пучков функций к-значной логики.
Методы исследований.
В работе используются методы дискретного анализа, теории функциональных систем и теории решеток.
Научная новизна.
В работе показано, что при любом к^2 в конечно-порожденных функциональных системах функций к-значной логики множество предполных классов конечно и описывается эффективно. Задачи о выразимости и полноте для конечных множеств пучков функций в таких функциональных системах алгоритмически разрешимы. Установлено, что при любом к^2 существуют замкнутые классы с базисом заданной конечной или счетной мощностями, а также классы без базисов. При любом ks2 решетка всех замкнутых классов континуальна.
Показано, что функциональная система всех пучков функций при к>2 является конечно-порожденной и для нее верны выше сформулированные утверждения о выразимости и полноте. Установлено существование шефферовых пучков функций и дан критерий для выявления этого свойства, из которого вытекает эффективность его проверки.
Теоретическая и практическая ценность.
Работа носит теоретический характер, однако полученные в ней результаты могут быть использованы при создании сложных вычислительных систем.
Апробация.
Результаты работы докладывались на международной конференции по интеллектуальным системам (Москва, 1993, 1994, 1995гг), на семинарах по теории автоматов на механико-математическом факультете МГУ.
Публикации.
По теме диссертации автором опубликованы пять работ, список которых приводится в конце автореферата.
Структура и объем диссертации.