Условия выразимости и полноты для функциональных систем пучков функций к-значной логики тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГ6 од

Министерство общего и профессионального образования Российской Федерации Саратовский Государственный Университет им. Н.Г.Чернышевского

На правах рукописи УДК 519.95

Кудрявцев Валерий Валерьевич

Условия выразимости и полноты для функциональных систем пучков функций к-значной логики

(01.01.09 - математическая кибернетика)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Саратов - 1997

Диссертационная работа выполнена на кафедре математической

теории интеллектуальных систем механико-математического факультета Московского государственного университета им.М.В. Ломоносова

Научный руководитель

доктор физико-математических, наук доцент А. С. Подколзин

Официальные оппоненты

доктор технических наук, член-корреспондент РАЕН, профессор А.А.Сытник, кандидат физико-математических наук В. АБашмаков

Ведущая организация

Вычислительный Центр РАН

Защита диссертации состоится 1997г. в

1д час. 3 О мин, на заседании Специализированного Совета К.063.74.04 Саратовского государственного университета им. Н.Г.Чернышевского по адресу: 410071, г. Саратов, ул. Астраханская, 83, Саратовский государственный университет им. Н.Г. Чернышевского.

С диссертацией можно ознакомиться в библиотеке Саратовского государственного университета им. Н.Г.Чернышевского.

Автореферат разослан " улйсЯ^ Л 1997г.

Ученый секретарь Специализированного Совета, кандидат физико-математических наук,

доцент П.Ф.Недорезов

Общая характеристика работы. Актуальность темы.

В последние десятилетия одним из активно развивающихся разделов дискретной математики и математической кибернетики является теория функциональных систем. Ее предметом исследования выступают дискретные функции и операции над ними, позволяющие порождать из заданных функций с помощью этих операций новые функции. Такая модель возникает в целом ряде научных областей. Так, в логике из конкретных функциональных высказываний можно с помощью традиционных или обобщенных логических связок порождать новые высказывания. В алгебре, отправляясь от конкретных объектов, можно строить термальные конструкции таких объектов. В технике схемы, построенные из элементарных вычислителей, позволяют решать наперед заданные задачи, и т.д.

Содержательно функциональная система (ф.с.) представляет собой универсальную алгебру вида Я=(Р,Ш, где Р — некоторое множество функций, а £2 — множество операций над функциями из Р со значениями в Р [1].

Изучение функциональных систем идет в нескольких направлениях. С одной стороны изучаются конкретные ф.с., такие как итеративные алгебры функций конечно-автоматных и автоматных функций, алгебры вычислимых функций и др. С другой стороны, изучаются общего вида алгебры дискретных функций.

Укажем в этой связи работы Э.Поста[2], С.В.Яблонского[3], А.В.Кузнецова[8], А.И.Мальцева[4], И.Розенберга[5], В.Б.Кудрявцева[6], В.А.Буевича[7], цитированных там авторов и др.

Конкретные ф.с., упомянутые выше, изучаются как модельные объекты, на которык'' уточняются задачи и формируется техника доказательств. Все они несут существенные черты реальных функций, отмеченные ранее.

В предполагаемом исследовании изучается новая функциональная система, которая возникает при надежностном подходе к синтезу схем из функциональных элементов и автоматов.

Как известно, реальные элементы, из которых строятся вычислительные схемы, допускают неисправности, в результате чего элементы могут реализовать не те функции,

которые им присваивались при конструировании. Тем самым и схема, построенная из таких элементов, реализует не ту функцию, которую она должна была бы реализовать. Таким образом, можно считать, что в общем случае элемент реализует сразу несколько функций, называемых нами пучком функций. То же относится и к схеме из этих элементов.

Аналогичная ситуация возникает при анализа автоматов и автоматных схем. Здесь при тестировании автоматов важно устанавливать, какой набор функций реализует автомат при вариации его состояний. Тем самым каждый элемент в автоматной схеме, как и вся схема, также выступают как пучки функций.

Подобные ситуации возникают и в других случаях, например, при рассмотрении сложных производств, иерархического административного управления и т.п.

Таким образом, возникает необходимость рассмотрения объектов в виде пучков функций с операциями над ними, индуцируемыми операциями над функциями и автоматами. Изучению таких функциональных систем и посвящено это исследование.

Пель работы.

Исследовать условия выразимости и полноты для функциональных систем пучков функций к-значной логики.

Методы исследований.

В работе используются методы дискретного анализа, теории функциональных систем и теории решеток.

Научная новизна.

В работе показано, что при любом к>2 в конечно-порожденных функциональных системах функций к-значной логики множество предполных классов конечно и описывается эффективно. Задачи о выразимости и полноте для конечных множеств пучков функций в таких функциональных системах алгоритмически разрешимы. Установлено, что при любом к>2 существуют замкнутые классы с базисом заданной конечной или счетной мощностями, а также классы без базисов. При любом к>2 решетка всех замкнутых классов континуальна.

Показано, что функциональная система всех пучков функций при к>2 является конечно-порожденной и для нее верны выше сформулированные утверждения о выразимости и полноте. Установлено существование шефферовых пучков функций и дан критерий для выявления этого свойства, из которого вытекает эффективность его проверки.

Теоретическая и практическая ценность.

Работа носит теоретический характер, однако полученные в ней результаты могут быть использованы при создании сложных вычислительных систем.

Апробация.

Результаты работы докладывались на международной конференции по интеллектуальным системам (Москва, 1993, 1994, 1995гг), на семинарах по теории автоматов на механико-математическом факультете МГУ.

Публикации.

По теме диссертации автором опубликованы пять работ, список которых приводится в конце автореферата.

Структура и объем диссертации.

Диссертация состоит из введения, шести параграфов, рисунков и списка литературы. Общий объем диссертации 51 страница.

Обзор содержания диссертации.

Уточним основные понятия, чтобы иметь возможность сформулировать главные задачи и результаты работы.

Пусть £^={0,1,2,...^-!}, к>2, и Р^ - множество всех

функций { вида Е^11 Е^, где п — натуральное число. Пусть V — конечное подмножество функций из Р^ и х1,х2,-..,хт — множество всех переменных, от которых зависит хотя бы одна из функций множества V. Обозначим это множество через У(х1,х2,...,хп) и назовем п.функцией к-

значной логики. Класс всех таких п.функций обозначим через Рк,п-

На подмножествах множества Р^ п определим оператор замыкания [] следующим образом. Рассмотрим элемент Реп входами и одним выходом, приведенный на рис.1. Пусть Р — множество всех таких элементов при вариации п по всему натуральному ряду. Из этих элементов обычным образом с помощью правил отождествления входов и присоединения выходов и входов элементов без образования циклов строятся сети. Пусть Б(Р) — множество всех таких сетей и Се5(Р). Приписывая входам сети С переменные, а ее элементам — функции из Р^, получаем схему Сф из функциональных элементов, которая реализует некоторую функцию из Р^. Припишем теперь элементам из С п.функции из Рк,п-Получим схему Сфп. Тогда, фиксируя для каждого элемента функцию из приписанной ему п.функции, снова приходим к схеме Сф, которая реализует функцию из Р^- Если теперь проварьировать по всем элементам такое приписывание, то, объединяя в одно множество все функции, реализовавшиеся схемами Сф, получим п.функцию V, которую по определению реализует схема Сфп.

Заметим, что если при рассмотрении схем из функциональных элементов можно перейти к формульному представлению схем, то в случае п.ф. схем такого перехода сделать в простой форме не удается. По этой причине основным является язык п.ф. схем.

Пусть МсРк,п- Обозначим через [М]п множество всех п.функций, которые реализуются всевозможными схемами, получающимися из сетей множества БШ приписыванием их элементам п.функций из М. Нетрудно видеть, что оператор []п является замыканием множества М. Говорим, что М замкнуто, если [М]п=М. В этом случае обозначим через М пару (М,[]п), которую назовем ф.с. п.функций рода к. При М=Рк>п имеем Як,п=(Рк,п- []„).

Пусть М1,М2£Рк)П. Говорим, что М} выразимо через М2,

если М1£[М2].

Задача о выразимости состоит в описании всех таких пар (М1,М2), что М1 выразимо через М2-

Знание решетки по включению, образованной системой 2(М) всех замкнутых классов в М, позволяет решить задачу о выразимости.

Задача о полноте для ф.с. п.функций Л?=(М,[]П) состоит в описании всех таких множеств М\ М'сМ, что [М']П=М. Эта задача является частью задачи о выразимости.

Обе задачи в качестве главной своей компоненты содержат алгоритмические постановки, когда речь идет об исследовании на выразимость и полноту конечных систем п.функций.

Важный подход к решению задачи о полноте в терминах предполных классов был предложен С.В.Яблонским и А.В.Кузнецовым. Суть этого подхода состоит в следующем. Множество Е\ Е^сКЖ), называется критериальной системой (K-системой), если для любого М\ М'сМ, условие [М*]=М эквивалентно тому, что для любого К из ЕОЮ\{М} выполнено М'сК. Множество М\ М'сМ, называется предполным классом в М, если М'=[МЧ]П, MVM и при VeM\M* выполнено [M'u{V}]n=M. Множество всех предполных классов в М обозначим через ZK(M). Всякая к-система 2 содержит множество если Ф.с. М называем

правильной, если Б^Ш) образует к-систему в М. Достаточным условием правильности М является наличие в М полного конечного множества[1], при этом говорят также, что М является конечно-порожденной ф.с. В этом случае задача о полноте сводится к задаче описания предполных классов в М.

Пусть U={ui,u2,...} — алфавит переменных со значениями

из Ek, Um={ui,u2,...,um}, МбРк,п и Мт — множество всех п.функций из М, зависящих от переменных из Um. Функцию ejm(ui,u2,...,ui,...,um)=uj называем селекторной и сохраняем это название за п.функцией Vjm={eim(ui,u2,...,ui,...,um)}. Множество всех селекторных п.функций из Pkm,n обозначим через Skm,n-.

Пусть QePkm,n. Q*Pkm,n и V(xi,x2,...,xn)€Pkin. Рассмотрим сеть S, приведенную на рис.15. Будем говорить, что V сохраняет Q, если после приписывания элементу F — п.функции V, а каждому элементу Fi — произвольной

п.функции V; из Q u Skn(n. i=l,2,...,n, получаемая схема Сфп

реализует п.функцию из О. Класс всех п.функций, сохраняющих (2, обозначим через 11(0). Если и(0)2<2, то называем Я-множеством. Пусть МеЕОР^п), Ж=(М,[]П) и ш —

натуральное число. Пусть (ЭсМпРк111,!!. и О

является К-множеством. Обозначим множество всех таких О через ЯтШ). Пусть и((2,Л*)=и(С>)пМ. Класс всех и при ОеЯтШ) обозначим через и(:ЯтШ)). Пусть и(ЯтШ)) — множество всех максимальных элементов в частичном порядке, образованном множеством и(Ят(М)) по отношению включения. Обозначим через |М| мощность множества М.

к™

Пусть Рк,п(тНРкт,п1- Ясно, что Рк,п(т)= 2к -1. Пусть ^е Рк,п> обозначим через ||У|| число существенных переменных у п.функций из М. Ф.с. М называем вырожденной, если для любой п.функции V из М выполнено [№]П=М.

Теорема 4.1. Если к,т£1, МеЕ(Як,п)< Ж=(М,[]П) — невырожденная ф.с., М'сМ, |М|<оо, ||М'||=т и [М']П=М, то для М справедливы следующие положения:

1) множество й(Ят(М)) образует к-систему в М;

2) и(Лт0Ю)=2я0Ю;

3) |йО?тШ))| ^ 2Рк,пСт);

4) множество ЯтШ) описывается эффективно;

5) множество и(Ят(М)) описывается эффективно;

Теорема 4.2. Для любого к>2 задача о полноте конечных систем в конечно-порожденных ф.с. п.функций рода к алгоритмически разрешима.

Теорема 4.3. Для любого к>2 задача о выразимости для конечных систем в конечно-порожденных ф.с. п.функций рода к алгоритмически разрешима.

Пусть Ж=(М,[]П) и М'сМ. Говорят, что М' является базисом в М, если [М']П=М, но для любого М" такого, что и выполнено [М"]П*М.

Теорема 4.4. Для любого к>2 существует ф.с. п.функций М рода к, для которой выполнено точно одно из условий:

а) М имеет счетный базис;

б) М имеет базис заданной конечной мощности;

в) М не имеет базиса;

и каждое из этих свойств реализуется для некоторой ф.с. п.функций М.

Теорема 4.5. Для каждого к^2 множество £(Як>п) имеет мощность континуума.

Теорема 4.6. Ф.с. п.функций Як,п является конечно-порожденной для любого к>2.

Теорема 4.7. Для любого к>2 множество ^(Як^л;) описывается эффективно, образует к систему в и для него справедливы оценки

2^5 12,(^)1 £2р"(2)

Теорема 4.8. Для любого к>2 задачи о полноте и выразимости в для конечных систем п.функций

алгоритмически разрешимы.

П.функцию V называем Шефферовой в Р^ п, если

[{?}]п=Рк,п-

Теорема 4.9. для любых к>2 и п>3 в существует Шефферова п.функция, существенно зависящая от п переменных.

Называем множество М, МсР^д, регулярным, если [М]пэРк,п,1- Содержательно это означает, что для любой функции £ из Р^)П можно построить такую схему Спф, элементам которой будут приписаны п.функции из М, что схема Спф будет реализовывать п.функцию У={{]. Таким образом, с надежностной точки зрения из как бы ненадежных элементов строится надежная по реализации конкретной функции сеть.

Назовем множество М, МсР]^, р-предполным, если [М]П=М, МЭРк,п,1. но Для любой п.функции V из Рк,л\М

выполнено[Ми{У}]пэРк,п- Множество всех р-предполных классов обозначим через Ея,р№к,п)-

Теорема 4.10. Для любого к>2 справедливы следующие положения:

а) Рк,п,1 является р-предполным классом в Як,ш

б) ^)Р(Як)=£л(Як>п)\{Рк)П11};

в) множество М является регулярным точно тогда, когда для любого К из ЕЛ)р(Я^) выполнено МсК.

Теорема 4.11. Существует алгоритм, который при любом к>2 по любому конечному подмножеству множества Рк,п устанавливает, является ли оно регулярным.

Назовем п.функцию р-Шефферовой, если она образует регулярное множество.

Теорема 4.12. При любых к^2 и т>3 в Як д существуют р-Шефферовые п.функции, существенно зависящие от ш. переменных, при этом р-Шефферовая п.функция V является или Шефферовой, или [^}]п=Рк,п,1-

Работа состоит из введения и шести параграфов. Во введении дается краткий обзор основных результатов работы, а также очерчивается общая ситуация, связанная с проблематикой функциональных систем. В параграфе первом описывается оператор замыкания и его общие свойства. В параграфе втором приводятся основные функциональные системы дискретных функций. В параграфе третьем дается формальное введение функциональной системы пучков функций к-значной логики. В параграфе четвертом ставятся основные задачи для таких функциональных систем и формулируются главные результаты работы. В параграфе пятом доказываются вспомогательные результаты. Этот параграф является самым объемным и содержит технику достижения основных результатов. В параграфе шестом доказываются основные результаты, сформулированные в параграфе четвертом.

Основные результаты автора диссертации опубликованы в статьях [8-12].

Автор благодарит доктора физико-математических наук А.С.Подколзина за научное руководство.

Цитированная литература

Кон П. Универсальная алгебра, М., Мир, 1968.

Post Е. Two-valued iterative systems of mathematical logic, Prinston,

1941.

Яблонский C.B. Функциональные построения в к-значной логике. В кн: Труды математического института им. В.А. Стеклова, т.51, Издательство АН СССР, 1958, с.5-145.

Мальцев А. И. Итеративные алгебры и многообразия Поста. В кн: Алгебра и логика, семинар, т.5, вып.2, Новосибирск, Издательство СО АН СССР, 1966.

Rosenberg J. La structure des fonctions de plusiers variables sur un ensembl fini. Comptes Rendus Acad, Sci. Paris, 1965, v.260, p.3817-3838.

Кудрявцев В.Б. Функциональные системы, M., Издательство МГУ, 1982, с. 159.

Буевич В.А. О т-полноте в классе детерминированных функций, ДАН, 1992, т.326, №3, с.399-404.

Публикации автора по теме диссертации

Кудрявцев В.В. О функциональной системе Ptg., журнал Дискретная математика, т.З, вып.З, 1991, с.124-134. Кудрявцев В.В. Условия полноты для систем пучков функций., Проблемы теоретической кибернетики. Тезисы докладов 1Х-ой Всесоюзной конференции, 1990, ч.2.

Кудрявцев В.В. О функциональной системе Р2,п-, Тезисы всесоюзного семинара по технической диагностике., Саратов, 1990.

Кудрявцев В.В. Условия полноты для систем пучков функций алгебры логики., Сб. "Методы и системы технической диагностики".

Кудрявцев В.В. Условия выразимости и полноты для пучков готических функций., Доклады РАН., т.359, вып.1, 1998.