автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Функциональная полнота и выразимость в классе квазимонотонных функций на конечной полурешетке

Введение.

1. Основные понятия.

1.1. Проблема полноты и выразимости в замкнутых классах конечнозначных функций.

1.2. Замкнутые классы вР^и отношения на Ь.

1.3. Классы функций на верхней полурешетке.

1.4. Выводы.

2. Функциональная полнота в классах квазимонотонных и монотонных функций на полурешетке подмножеств двухэлементного множества.

2.1. Некоторые отношения на Ег.

2.2. Одноместные функции в 02.

2.3. Г2-полнота в классе М%.

2.4. Полнота в классе Мг.

2.5. Классы Слупецкого в 02.

2.6. Критерий полноты в классе 02.

2.7. Выводы.

3. Полнота в классе квазимонотонных функций на произвольной полурешетке.

3.1. Инвариантность отношений на множествах Фь, (2ь.

3.2. Отношение ру.

3.3. Предполные Ф^-классы в 0ь.

3.4. Тест квазимонотонности.

3.5. Выводы.

4. Выразимость минимальных функций в классе монотонных функций.

4.1. /¿-полнота в Ml.

4.2. Отношение сводимости наборов и Г£-предполные Г£(1)-классы в ML

4.3 Случай L= Ёк.

4.4. Выводы.

5. Слабая полнота в классе квазимонотонных функций.

5.1. Инвариантность на и Р/1) отношений.

5.2. Некоторые отношения на!.

5.3 Критерий полноты.

5.4. Некоторые следствия из теоремы 5.1.

5.5. Выводы.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Основу математического аппарата для логического проектирования дискретных управляющих систем (дискретных автоматов) составляет такой раздел дискретной математики, как конечнозначная логика. Ее средства позволяют описывать статическое поведение автомата (при фиксированном входном состоянии). Однако, при описании динамического (вызываемого асинхронным изменением компонент входного состояния) поведения автомата возникают трудности, обусловленные явлением состязаний между асинхронно изменяющимися компонентами его состояний. В монографии [1] показано, что динамическое поведение дискретных автоматов может быть адекватно и с заданной точностью описано средствами полурешеточно упорядоченных алгебр. При таком описании каждое из множеств входных, выходных и внутренних состояний автомата, функционирующего в динамическом режиме, образует структуру полурешетки, то есть частично упорядоченного множества, в котором для каждой пары элементов существует точная верхняя грань. Отношение порядка на множестве состояний интерпретируется как отношение сравнения состояний по степени их неопределенности, обязанной явлению состязаний. В связи с этим научный интерес представляет изучение функций, определенных и принимающих значения на полурешетках. Важнейшими классами таких функций являются классы монотонных, квазимонотонных и минимальных точечных функций. Минимальными точечными функциями обладают реальные физические элементы (транзисторы, резисторы, вентили и т.д.), монотонные функции принадлежат комбинационным схемам, построенным из них, а квазимонотонные функции реализуются такими схемами, в связи с чем актуальна задача функциональной полноты в указанных классах функций. Квазимонотонные функции реализуются монотонными, а те, в свою очередь, реализуются минимальными точечными функциями, поэтому актуальна задача выразимости минимальных точечных функций в классах монотонных и квазимонотонных функций. В связи с задачами о полноте и выразимости представляет интерес структура замкнутых классов квазимонотонных и монотонных функций, в особенности интересны предполные классы квазимонотонных и монотонных функций и максимальные замкнутые подмножества монотонных функций, не содержащие всех минимальных точечных функций, т.е. такие, в которых отсутствует хотя бы одна минимальная точечная функция.

Первый результат, относящийся к проблеме полноты в классе квазимонотонных функций на конечных полурешетках, получен в [1], где описана система квазимонотонных функций на полурешетке подмножеств трехэлементного множества со свойствами П-полноты и независимости. В дальнейшем [3-6] были построены некоторые конечные системы квазимонотонных функций на полурешетке подмножеств конечного множества, обладающие теми или иными свойствами выразимости. Однако ни теоремы о функциональной полноте, ни общих критериев полноты, подобных тем, что известны для множества Р^ всех функций &-значной логики, для классов монотонных и квазимонотонных функций на полурешетках не установлено.

Цель работы. Настоящая работа посвящена решению проблемы функциональной полноты в классах квазимонотонных и монотонных функций на конечной полурешетке и проблемы выразимости множества минимальных точечных функций в классе всех монотонных функций на конечной полурешетке. Ставятся следующие задачи: (1) установить критерии полноты в классах квазимонотонных и монотонных функций на конечной полурешетке и критерий выразимости множества минимальных точечных функций в классе всех монотонных функций на конечной полурешетке; (2) ответить на вопрос об алгоритмической разрешимости рассматриваемых проблем полноты и выразимости; (3) эффективно описать предполные классы монотонных и квазимонотонных функций на конечных полурешетках и максимальные классы монотонных функций, не содержащие всех минимальных точечных функций.

Научная новизна и выносимые на защиту положения. В диссертационной работе получены следующие основные результаты:

1. Доказаны критерии полноты в классах квазимонотонных и монотонных функций на полурешетке подмножеств двухэлементного множества и критерии выразимости множества минимальных точечных функций в классе монотонных функций на той же полурешетке.

2. Установлены критерии полноты в классе квазимонотонных функций на конечной верхней полурешетке относительно суперпозиции с множеством слабо существенных функций и относительно суперпозиции с множеством несущественных функций; установлен критерий выразимости множества минимальных точечных функций в классе монотонных функций на конечной верхней полурешетке относительно суперпозиции с множеством несущественных минимальных точечных функций.

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

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

Все перечисленные результаты являются новыми.

Методы исследования. В работе использовались элементы теории частично упорядоченных множеств, конечных полурешеток, средства и методы дискретной математики, а именно таких ее разделов, как конечнозначная логика и теория Галуа для алгебр Поста.

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

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

Апробация работы. Результаты диссертации обсуждались на совместных семинарах кафедр математической логики и проектирования, защиты информации и криптографии и программирования Томского государственного университета, докладывались на VI Международной конференции студентов, аспирантов и молодых ученых «Современная техника и технологии» (Томск, 1999), на Городской конференции по приборостроению, посвященной 40-летию полета Гагарина в космос (Томск, 2000), на конференции, посвященной 70-летию Сибирского физико-технического института им. акад. В. Д. Кузнецова при ТГУ (Томск, 1998), на третьей всероссийской конференции с международным участием «Новые информационные технологии в исследовании дискретных структур» (Томск, 2000), на Международной конференции «Дискретный анализ и исследование операций» (Новосибирск, 2000), на Седьмом Международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ, 2001), на семинаре кафедры математической кибернетики МГУ (2001).

Работа выполнена в соответствии с планами НИР Томского госуниверситета по единому заказ-наряду и по Федеральной целевой программе "Интеграция" при поддержке грантом РФФИ № 98-01-00288.

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

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

5.5. Выводы

В данной главе решена задача о слабой полноте (т.е. о полноте со всеми одноместными функциями) в классе квазимотонных функций на конечной верхней полурешетке. Указана конечная критериальная система в классе квазимонотонных функций для случая суперпозиции со всеми одноместными функциями (теорема 5.1) и, таким образом, установлены конечная порождае-мость класса квазимонотонных функций (теорема 5.2) и алгоритмическая разрешимость проблем полноты в нем. Доказано (следствие 1 из теоремы 5.1), что в зависимости от вида полурешетки L в классе Qi может содержаться любое конечное число классов Слупецкого (предполных Ql^-классов).

ЗАКЛЮЧЕНИЕ

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

1) критерий полноты и описание предполных классов квазимонотонных функций на полурешетке подмножеств двухэлементного множества (теорема 2.4);

2) критерий полноты и описание предполных классов в классе монотонных функций на той же полурешетке (теорема 2.2);

3) критерий выразимости минимальных точечных функций в классе монотонных функций и описание максимальных классов монотонных функций, не содержащих множества минимальных точечных функций (теорема 2.1);

4) критерии полноты в классе квазимонотонных функций на конечной полурешетке при суперпозиции со всеми слабо существенными функциями (теорема 3.1) и при суперпозиции с одноместными функциями (теорема 5.1);

5) описание предполных классов квазимонотонных функций, содержащих все слабо существенные функции (теорема 3.2);

6) критерий выразимости минимальных точечных функций в классе всех монотонных функций на произвольной конечной полурешетке при суперпозиции с одноместными минимальными точечными функциями (теорема 4.1 и теорема 4.2);

1. Агибалов Т.П. Дискретные автоматы на полурешетках. - Томск: Изд-во Том. ун-та, 1993- 227 с.

2. Агибалов Г.П Квазимонотонные функции и их минимизация // Кибернетика. -1989. №2. - С.111-113.

3. Агибалов Г.П. Свойства замыканий некоторых классов функций на полурешетке подмножеств конечного множества // Проблемы теоретической кибернетики. Тезисы докладов XI Международной конференции. М., 1996. - С.4.

4. Агибалов Г.П. О полных системах функций на полурешетке подмножеств конечного множества // Всесибирские чтения по математике и механике. Т.1. Математика. Томск: Изд-во Том. ун-та, 1997. - С.148-149.

5. Агибалов Г.П. О полных системах операций и синтезе схем для квазимонотонных функций на конечных полурешетках // Новые информационные технологии в исследовании дискретных структур. Екатеринбург: УрО РАН, 1998. - С.149-152.

6. Агибалов Г.П. Канонические формы и полные системы квазимонотонных функций на конечных полурешетках // Международная Сибирская конференция по исследованию операций . Материалы конференции. Новосибирск: Изд-во Института математики СО РАН, 1998. - С.118.

7. Алексеев В.Б., Вороненко Л.Л. О некоторых замкнутых классах в частичной двузначной логике // Дискретная математика. 1994 - Т.6, №4.

8. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука. Физматлит, 1997. - 368 с.

9. Боднарчук В.Г., Калужнин Л.А., Котов В.Н., Ромов Б.А. Теория Галуа для алгебр Поста // Кибернетика. 1969 - №3. - С. 1-10; №5. - С. 1-9.

10. Гаврилов Г.П. Индуктивное представление булевых функций и конечная порождаемость классов Поста // Алгебра и логика. 1984. - Т. 23, № 1.-С.3-26.

11. Гаврилов Г.П. Функциональные системы дискретной математики. -М.:Из-во МГУ, 1985.

12. Гниденко В.М. Нахождение порядков предполных классов в 3-значной логике // Проблемы кибернетики. Вып. 8.-М.:Физматгиз, 1962.-С.341-346.

13. Захарова Е.Ю. Критерий полноты системы функий из И Проблемы кибернетики. -1967. №18. - С.5-10.

14. Захарова Е.Ю., Кудрявцев В.Б., Яблонский С.В. О предполных классах в ¿-значной логиках // Доклады АН СССР. 1969. - Т.186, №3 - С.509-12.

15. Кудрявцев В.Б. О функциональных системах автоматов // Дискретная математика. 1997. - Т.7., №4. - С. 3-28.

16. Кузнецов A.B. Алгебра логики и ее обобщения // Яновская С.А. Математическая логика и основания математики. Матиематика в СССР за сорок лет. Т. 1. М.:Физматгиз, 1959.-С.13-120.

17. Кузнецов A.B. О средствах для обнаружения невыполнимости и невыразимости. Логический вывод. М.:Наука, 1979.-С.5-33.

18. Кузнецов A.B. Структуры с замыканием и критерии функциональной полноты // Успехи матем. наук. 1961. - Т. XVI, №2(98). - С.201-202.

19. Линдон Р.К. Тождества в двузначных исчислениях // Кибернетический сборник. 1960. - №.1. - С.234-45.

20. Линдон Р.К. Тождества в конечных алгебрах // Кибернетический сборник. 1960. - №.1. - С.246-53.

21. Ло Чжукай. Максимальные замкнутые классы в множестве частичных функций многозначной логики //Кибернетический сборник. Сер. Новая. 1988.- №25. С.131-141.

22. Мальцев А.И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. - Т.5, №2. - С.5-24.

23. Мальцев А.И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ, 1976.

24. Макаров A.B. О гомоморфизмах функциональных систем многозначных логик // Математические вопросы кибернетики. Вып.4.- М.: Наука. 1992. - С. 5-24

25. Марченков С.С. Замкнутые классы булевых функций. М.: Физматлит, 2000. - 128 с.

26. Марченков С.С. Инварианты классов Поста // Фундаментальная и прикладная математика-1998 -Т.4, №4.-С.1385-1404.

27. Марченков С.С. К существованию конечных базисов в замкнутых классах булевых функций // Алгебра и логика. 1984. - Т.23, №1.-С. 88-99.

28. Марченков С.С. Основные отношения S-классификации. функций многозначной логики // Дискретная математика. 1996. - Т.8, №1. — С.99-128.

29. Марченков С.С. О выразимости функций многозначной логики в некоторых логико-функциональных языках // Дискретная математика.-1999.-T.il, №4.-С.110-126.

30. Марченков С.С. О классах Слупецкого в системах Р/х. .хР/ // Дискретная математика. 1992. - Т.4, №3. - С.135-148.

31. Марченков С.С. О предполных классах в декартовых произведениях Р2 и Р3 // Дискретная математика. 1994. - Т.6, №2. - С.21-42.

32. Марченков С.С. Предполнота замкнутых классов в Р^: предикатный подход // Математические вопросы кибернетики. Вып. 6.- М.:Наука, 1996.-С.117-132.

33. Марченков С.С. S-классификации функций многозначной логики // Дискретная математика. 1997. - Т.9, №.3. - С. 125-152.

34. Марчеиков С.С. О-предполные классы многозначной логики // Дискретный анализ и исследование операций. 1996. - Т.З, № 3. - С.47-70.

35. Марченков С.С., Угольников А.Б. Замкнутые классы булевых функций. -М.:Из-во ИПМ АН СССР, 1990.

36. Мещанинов Д.Г. О первых ¿/-разностях функций &-значной логики // Математические вопросы кибернетики. Вып.7.-М.:Наука, 1998.-С.265-280.

37. Мещанинов Д.Г. О замкнутых классах Аг-значных функций, сохраняющих первые ¿/-разности // Математические вопросы кибернетики. Вып. 8.-М.:Наука, 1999- С.219-230.

38. Михеева Е.А.Минимальные классы в трехзначной логике // Сборник трудов семинара по дискретной математике и ее приложениям / Под редакцией чл.-корр. РАН О.Б.Лупанова М.: Изд-во механико-математического факультета МГУ, 1998.-С.114-116.

39. Михеева Е.А. О минимальных классах в многозначных логиках // Методы дискретного анализа в решении комбинаторных задач. Вып.45. Новосибирск: ИМ СО АН СССР, 1987.

40. Михеева Е.А. Построение в Рз класса, не имеющего конечного базиса // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции.Часть II. М.:Изд-во механико-матем.ф-та МГУ, 1999. - С. 161.

41. Михеева Е.А. Построение в Рк максимальных классов, не имеющих конечных базисов // Дискретная математика. 1998 - Т. 10, вып. 2. - С. 137-159.

42. Мурский В.Л. Существование в трехзначной логике замкнутого класса сконечным базисом, не имеющего конечной полной системы тождеств // Доклады АН СССР. 1965. - Т.163, №4. - С.815-18.

43. Нгуен Ван Хоа. Об ¿-эквивалентности систем функций в многозначной логике // Алгебра и логика. 1988. - Т.27, №1. - С.37-47.

44. Нгуен Ван Хоа. О семействах замкнутых классов &-значной логики, сохраняемых всеми автоморфизмами // Дискретная математика. 1993. -Т. 5, №4.-С.87-108.48.0ре О. Теория графов. М.:Наука, 1969.

45. Ремизов А.Б. О надструктуре замкнутого класса полиномов по модулю к II Дискретная математика. 1989. - Т.1, №.1, -С.3-15.

46. Риге Ж. Бинарные отношения, замыкания, соответствия Галуа // Кибернетический сборник. Вып. 7 М.:Мир, 1963 -С. 129-186.

47. Ромов Б.А. Алгоритм решения проблемы полноты в классе векторных функциональных систем // Математические системы сложных систем-Киев: Ж АН УССР, 1973.-С.151-155.

48. Ромов Б.А. О решетке подалгебр прямых произведений алгебр Поста конечной степени // Математические системы сложных систем.-Киев: ИК АН УССР, 1973.-С.156-168.

49. Ромов Б.А. О полноте на квадрате функций алгебры логики и в системе РкхР1 II Кибернетика. 1987. - №4. - С.9-14.

50. Ромов Б.А. Об одной серии максимальных подалгебр прямых произведений алгебр конечнозначных логик // Кибернетика. 1989. - №3. - С. 11-16.

51. Ромов Б.А. О максимальных подалгебрах алгебры частичных функций многозначной логики // Кибернетика. -1980. №1. - С.28-36.

52. Ромов Б.А. Алгебры частичных функций и их инварианты // Кибернетика. 1981. -№2. - С.1-11.

53. Ромов Б.А. О продолжениях не всюду определенных функций многозначной логики // Кибернетика. 1987. - №3. - С.27-34.

54. Ромов Б.А. О проблеме полноты в алгебре частичных функций многозначной логики // Кибернетика. 1990. - № 1. С. 102-106.

55. Саломаа А. Некоторые критерии полноты для множеств функций многозначной логики // Кибернетический сборник. 1964. - №.8. - С.7-32.

56. Сафин K.JI. Идеалы итеративных алгебр // Сибирский математический журнал, Ноябрь декабрь. - 1995. - Т.36, №6. - С.1384-1391.

57. Соловьев В. Д. Замкнутые классы в &-значной логике с операцией разветвления по предикату // Дискретная математика. 1990. - Т.2, №4. - С. 19-25.

58. Тайманов В.А. О функциональных системах £-значной логики с операциями программного типа // Доклада АН СССР. 1983. - Т.268, №6. -С.1307-1310.

59. Угольников А.Б. О замкнутых классах Поста // Известия вузов. Математика. 1988. - №7. С.79-88.

60. Фрейвальд Р. Критерии полноты для частичных функций алгебры логики и многозначных логик // Доклады АН СССР. 1966. - Т.167, №6. - С. 12491250.

61. Яблонский C.B. О замкнутых классах в Р2 II Проблемы кибернетики. Вып. 39. М.-.Наука, 1982. - С.262.

62. Яблонский C.B. О некоторых результатах в теории функциональных систем // Труды Международного конгресса математков. Хельсинки, 1978. -С.963-971.

63. Яблонский C.B. О функциональной полноте в трехзначном исчислении // ДАН СССР. 1954. - Т.95, №6. - С.1153-1156.

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

65. Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.:Наука, 1966.

66. Янов Ю.И., Мучник A.A. О существовании /с-значных замкнутых классов, не имеющих конечного базиса // ДАН СССР. 1959. - Т.127, №1. - С.44-46.

67. Benzaken С. Definitions et propriétés de certains familles de fonctions booléennes croissantes // C.R. Acad. Sei. Paris. 1964. - T. 259, group I. - P. 1369-1571.

68. Benzaken C. Les familles de fonctions booléennes dedutes de certains familles de fonctions booléennes croissantes/ Criteres de determination de l'indice d'une fonction croissante // C.R. Acad. Sei. Paris. 1965. - T. 260, group I. - P. 1528-1531.

69. Geiger D. Closed systems о f functions and predicates / / P acific. J. Math. -1968. V. 27. - P.95-100.

70. Kuntzman J. Algebre de Boole. Paris: Dunod, 1965.

71. Lau D. Submaximalle Klassen von Ръ II Electron. Informationsverarb. Und Kybern. 1982. - В. 18, №4-5. - Р.227-243.77.0ге О. Galois connections II Trans. Amer. Math. Soc. 1944. -V.55.-P.493-513.

72. Post E.L. Introduction to a general theiry of elementary propositions // Amer. J. Math. 1921. - V. 43, № 4. - P. 163-185.

73. Post E.L. Two-valued iterative systems of mathematical logic //Annals of Math. Studies. Princeton Univ. Press. 1941. - V.5.

74. Reschke M., Denecke K. Ein neuer Beweis fur die Ergebnisse von E.L. Post über abgeschlossene Klassen Boolescher Funcktione J. Process. Cybern. EIK. -1989.-Bd.7.-S. 361-380.

75. Rosenberg J. La structure des fonctions de plusiers variables sur un ensemblefini II Comptes Rendus Acad. Sei Paris, 1965. V.260, p.3817-3819.

76. Riguet J. Relations binaire, fermetures, correspondences de Galois // Bull. Soc. Math. France. 1948. - V. 76. - P.114-155.

77. Результаты диссертации опубликованы в следующих работах:

78. Парватов Н.Г. К синтезу схем логического управления с заданным динамическим поведением // VI Международная конференция студентов, аспирантов, молодых ученых «Современная техника и технологии». Томск: Изд-во ТГПУ, 1999.-С. 42-43.

79. Парватов Н.Г. К синтезу формул, реализующих и представляющих квазимонотонные и монотонные функции на полурешетках подмножеств конечного множества // Вестник Томского государственного университета. Т.271, июнь 2000. -С.111-115.

80. Парватов Н.Г. О полноте в классах монотонных и квазимонотонных функций на конечной полурешетке // Труды городской конференции по приборостроению, посвященной 40-летию полета Гагарина в космос. Томск: Изд-во ТГПУ, 2001. - С.55-56.

81. Парватов Н.Г. О полных системах операций для синтеза комбинационных схем с заданным динамическим поведением // Труды городской конференции по приборостроению, посвященной 40-летию полета Гагарина в космос. -Томск: Изд-во ТГПУ, 2001. С.57-58.