О сложности реализации функций многозначной логики формулами специального вида тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Трущин, Дмитрий Владимирович

• Трущин, Дмитрий Владимирович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Трущин, Дмитрий Владимирович

Введение

1 Определения и вспомогательные утверждения

1.1 Основные определения и обозначения.

1.2 Некоторые замкнутые классы.

1.3 Бинарные операции с правым сокращением.

2 Булевы функции

2.1 Эквивалентные преобразования а-формул

2.2 Верхние оценки функций Шеннона.

2.3 Реализация монотонных функций.

2.4 Реализация немонотонных функций.

3 Двоично представимые функции трехзначной логики

3.1 Критерий двоичной представимости функции

3.2 Частичная эквивалентность многочленов.

3.3 Сопоставление многочленов формулам

3.4 Верхние оценки функции Шеннона для класса двоично представимых функций.

3.5 Нижние оценки функции Шеннона для класса двоично представимых функций.

3.6 Верхние оценки глубины для произвольной функции.

4 Функции многозначной логики

4.1 Функции из Р/г)

4.2 Верхние оценки глубины для произвольной функции Список литературы

Введение диссертации (часть автореферата) на тему «О сложности реализации функций многозначной логики формулами специального вида»

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

Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения их сложности. В общем случае эта задача, может быть сформулирована следующим образом. Рассматривается набор базисных элементов, из которых по некоторым правилам строятся более сложные объекты — управляющие системы (например, схемы из функциональных элементов, контактные схемы, формулы). Заданы правила, позволяющие каждой системе сопоставить реализуемую ей функцию. Кроме того, каждой системе сопоставлено положительное число (сложность), которое характеризует ее стоимость. Рассматриваемая задача состоит в построении по заданной функции такой управляющей системы, которая реализует эту функцию и является оптимальной относительно выбранной меры сложности; при этом сложность построенной системы называется сложностью этой функции. Для заданного множества функций исследуется также поведение функции Шеннона, которая характеризует сложность реализации в рассматриваемом классе управляющих систем самой сложной функции, принадлежащей этому множеству и зависящей от фиксированного числа перменных.

Пусть к > 2. Положим = {0,1,.,/: — 1}. Обозначим через Рк множество всех функций &-значной логики. Формулы над конечными базисами, реализующие функции из Р;с, — один из основных модельных классов управляющих систем. Основными мерами сложности формул являются число символов переменных, входящих в формулу, и глубина; число символов переменных характеризует "стоимость", а глубина — время вычисления реализуемой функции. Для каждой конечной системы 21 С Рк через [21] обозначим множество функций, реализуемых нетривиальными формулами над системой 21. Пусть Р € [21]. Функцию Шеннона по сложности (числу символов переменных) для множества Р обозначим через Ь%(Р(п)), а функцию Шеннона по глубине — через Дя^п)). Если Р = [21], то функции Шеннона Ь^(Р(п)) и Да{Р(п}) будем обозначать также через Ь%(п) и соответственно.

Асимптотически оптимальные методы синтеза для основных модельных классов управляющих систем были разработаны О. Б. Лупановым [14, 15, 20, 21, 22, 23, 24, 25]. В частности, он показал [16, 17], что для любого полного в Рч конечного базиса 21 имеет место асимптотическое равенство

2 п

Ь%(п) ~ р--,

1оё2 п где р — константа, зависящая от системы 21 (минимальный приведенный вес элементов базиса).

Наряду с задачей о поведении функции Шеннона для класса Р2, рассматривается также задача о поведении функции Шеннона для различных подмножеств этого множества. Одной из наиболее известных и хорошо изученных с функциональной точки зрения классификаций булевых функций является описание семейства всех замкнутых относительно операции суперпозиции классов функций, полученное Э. Постом [46, 47]. Он показал, что это семейство является счетным, и что для каждого замкнутого класса существует конечная порождающая система. Изложение этих результатов содержится также в [40, 32, 26, 44, 27, 45, 35].

При исследовании задачи синтеза формул в конечных базисах, реализующих функции из замкнутых классов Поста, рассматриваются две отдельные задачи — синтез в полных базисах и синтез в неполных базисах. Для каждого полного конечного базиса и каждого замкнутого класса булевых функций, не содержащегося полностью ни в одном из классов1 3,Ь,К,И, асимптотически точные формулы для соответствующих функций Шеннона были получены А. Е. Андреевым [3, 4]. Для некоторых замкнутых классов и любых конечных систем, порождающих эти классы, асимптотически точные формулы для соответствующих функций Шеннона получены А. Б. Угольниковым [28, 29]. Он показал также [30, 31], что для произвольной конечной системы булевых функций функции Шеннона по глубине и сложности имеют соответственно линейный и экспоненциальный порядок роста относительно числа переменных.

Таким образом, в задаче о сложности реализации булевых функций получен ряд существенных результатов. Получение аналогичных результатов для функций Ахзначной логики (к > 3) сопряжено со значительными трудностями, которые связаны с континуальностью семейства замкнутых классов [42] (см. также [41]) и отсутствием описания семейства всех конечнопорожденых замкнутых классов2. Вместе с тем, для некоторых полных в базисов асимптотически точные формулы для соответствующих функций Шеннона были получены в работах Ю. В. Захаровой [11], С. Б. Гашкова [6], С.А. Ложкина [13]. Задачу о реализации формулами функций из класса3 Рз,2 исследовал Д.А. Дагаев [8, 9, 10]. Он получил оценки и асимптотически точные формулы для функций Шеннона, соответствующих некоторым замкнутым классам. В то же время при исследовании задачи синтеза формул в неполных базисах приведены примеры последовательностей функций многозначной логики, сложность которых имеет сверхэкспоненциальный порядок роста относительно числа переменных [31, 33, 34, 1, 2]. Эти результаты говорят о принципиальных отличиях многозначных логик от двузначной логики с точки зрения теории сложности.

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

1 Здесь Б — класс всех самодвойственых функций, Ь — класс всех линейных функций, К — класс всех конъюнкций, О — класс всех дизъюнкций.

2К настоящему времени получено описание лишь отдельных семейств замкнутых классов функций многозначной логики (см., например, работы [38, 39, 48, 49]).

З3десь РК2 — класс всех функций к-значной логики, принимающих значения 0 и 1, к > 3. специального вида. Подобный подход можно найти в ряде работ [43, 16, 5]. В работах О. Б. Лупанова [18, 19] изучаются формулы ограниченной глубины в базисе {У,&,-п}, включающие дизъюнктивные и конъюнктивные нормальные формы. В этих работах показано, что при построении асимптотически наилучших формул для почти всех функций алгебры логики достаточно ограничиваться формулами глубины не более 3. К этому направлению исследований относится также задача о реализации функций многозначной логики си-формулами, т.е. такимим формулами, в которых каждая подформула содержит не более одной нетривиальной главной подформулы. Впервые эту задачу рассмотрел М. М. Глухов [7]. Он показал существование в Рь при к > 7 конечных а-полных систем4. А. Л. Чернышов [36] нашел условия а-полноты систем функций многозначной логики, при каждом к > 5 построил а-полные системы из двух бинарных операций с правым сокращением, а также показал отсутствие конечных о;-полных систем в Р2. А. Л. Шабунин [37] привел примеры конечных а-полных систем в Рз и Р4.

В данной работе рассматривается задача о сложности реализации а-формулами функций Акзначной логики (к > 2). В качестве меры сложности формул выступает глубина. Для каждой конечной системы функций 21 через [21]а обозначается ее а-пополнение, т.е. множество всех функций, реализуемых нетривиальными си-формулами над системой 21. Для каждой функции / € [21] а глубина этой функции обозначается через !)$(/). Исследуется поведение функции Шеннона

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

Список литературы диссертационного исследования кандидат физико-математических наук Трущин, Дмитрий Владимирович, 2012 год

1. Андреев A.A. Об одной последовательности функций многозначной логики // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2011. Вып. 6. С. 52-57.

2. Андреев A.A. Об одной последовательности функций многозначной логики / / Мат-лы XI Междунар. сем. "Дисретная математика и ее приложения" (Москва, 18-23 июня 2012 г.) М.:Изд-во механико-математического факультета МГУ, 2012. С. 88-90.

3. Андреев А.Е. О сложности монотонных функций // Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 1985. Вып. 4. С. 83-87.

4. Андреев А.Е. О синтезе функциональных сетей // Докт. диссертация. М.: МГУ им. М.В.Ломносова, 1985.

5. Васильев Ю.Л., Глаголев В. В. Метрические свойства дизъюнктивных нормальных форм // Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974. С. 99-147.

6. Гашков С. В. О параллельном вычислении некоторых классов многочленов с растущим числом переменных // Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 1990. Вып. 2. С. 88-92.

7. Глухое М.М. Об а-замкнутых классах и а-пол пых системах функций fc-значной логики // Дискретная математика. 1989. Т. 1, вып. 1. С. 16-21.

8. Дагаев Д.А. О сложности псевдолинейных функций // Вестник Московского университета. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2010. Вып. 2. С. 53-56.

9. Дагаев Д.А. О сложности функций из некоторых классов трехзначной логики // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. М.: Изд-во МГУ, 2011. Вып. 3. С. 60-63.

10. Дагаев Д.А. О сложности функций многозначной логики, принимающих два значения // Канд. диссертация. М.: МГУ им. М.В.Ломносова, 2011.

11. Захарова Ю.В. Реализация функций из Рк формулами // Матем. заметки. 1972. Т. 11, вып. 1. С. 99-108.

12. Курош А.Г. Курс высшей алгебры. М.: Наука, 1975.

13. Ложкин С.А. О сложности реализации функций /¿-значной логики формулами и квазиформулами // Проблемы теоретической кибернетики: Мат-лы XI Междунар. конф. Ульяновск. М.: РГГУ, 1996. С. 125-127.

14. Лупанов O.E. О синтезе контактных схем // ДАН СССР. 1958. Т. 119. 1. С. 23-26.

15. Лупанов О.В. Об одном методе синтеза схем // Известия вузов, Радиофизика I. 1958. С. 120-140.

16. Лупанов О.Б. Об асимптотических оценках сложности формул, реализующих функции алгебры логики // ДАН СССР. 1959. Т. 128, вып. 3. С. 464-467.

17. Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып.З. М.: Физматгиз, 1960. С. 61-80.

18. Лупанов О. Б. О реализации функций алгебры логики формулами ограниченной глубины в базисе {V,&,-.} // Докл. АН СССР. 1961. Т. 136, 5. С. 1041-1042.

19. Лупанов О. Б. О реализации функций алгебры логики формулами ограниченной глубины в базисе -1} // Проблемы кибернетики. Вып. 6. М.: Физматгиз, 1961. С. 5-13.

20. Лупанов О.Б. Об одном классе схем из функциональных элементов // Проблемы кибернетики. Вып. 7. М.: Физматгмз, 1961. С. 60-114.

21. Лупанов О.Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 63-97.

22. Лупанов О.Б. О сложности реализации функций алгебры логики релейно-контактными схемами // Проблемы кибернетики. 1964. Вып. 11. С. 25-48.

23. Лупанов О. Б, Об одном подходе к синтезу управляющих систем — методе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31-110.

24. Лупанов О. Б. О синтезе схем из пороговых элементов // Проблемы кибернетики. 1973. Вып. 26. С. 109-140.

25. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: МГУ, 1984.

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

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

28. Угольников А.Б. Синтез схем и формул в неполных базисах // Докл. АН СССР. 1979. 249, 1. С. 60-62.

29. Угольников А.Б. Синтез схем и формул в неполных базисах // Препринт ИПМ АН СССР. 1980. Вып. 112.

30. Угольников А.Б. О глубине формул в неполных базисах // Математические вопросы кибернетики. 1988, вып. 1. С. 242-245.

31. Угольников А.Б. О глубине и сложности формул, реализующих функции из замкнутых классов // Докл. АН СССР. 1988. 298, вып.6. С. 1341-1344.

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

33. Угольников А.Б. О сложности реализации формулами одной последовательности функций многозначной логики // Математические вопросы кибернетики. 1989, вып. 2. С. 174-176.

34. Угольников А.Б. О сложности реализации формулами одной последовательности функций 4-значной логики // Вестник Московского университета. Сер. 1. Математика. Механика. 2004. Вып. 3. С. 52-55.

35. Угольников A.B. Классы Поста. М.: Изд-во ЦПИ при мех.-мат. ф-те МГУ им. М.В.Ломоносова, 2008.

36. Чернышов А.Л. Условия а-полноты систем функций многозначной логики // Дискретная математика. 1992. Т. 4, вып. 4. С. 117-130.

37. Шабунин А.Л. Примеры а-полных систем /г-значной логики при к = 3,4 // Дискретная математика. 2006. Т. 18, вып. 4. С. 45-55.

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

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

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

41. Яблонский C.B. Введение в дискретную математику. М.-Высшая школа, 2008.

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

43. Abhyankar S. Minimal «sum of products sum» expressions of Boolean functions. IRE Trans., EC-7, 4, 1958. P. 268-276.

44. Lau D. On closed subsets of Boolean functions (A new proof of Post's theorem) // J. Process. Cybern. EIK. 1991. V. 27, 3. P. 167-178.

45. Lau. D. Function Algebras on Finite Sets. Springer-Verlag, Berlin, 2006.

46. Post E.L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. 43, 3. P. 163-185.

47. Post E.L. Two valued iterative systems of mathematical logic // Annals of Math. Studies. Princeton-London: Princeton Univ. Press. 1941. 5. 122.

48. Rosenberg I. G. La structure des functions de plusieurs variables sur un ensemble finil // Comptes Rendus, de l'Academ. Paris, Ser. A.B. 260. 1965. P. 3817-3819.

49. Rosenberg I.G. Uber die funktionale Vollständigkeit in den mehrvertigen Logiken // Rozpravy Öeskoslovenske Academie ved. Rada matematickych a priridnich ved. Praha, 1970. Rocnik 80, Sesit 4. S. 3-93.

50. Трущин Д. В. О глубине а-пополнений систем булевых функций // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2009. Вып. 2. С. 72-75.

51. Трущин Д.В. О нижних оценках глубины формул специального вида // Мат-лы X Междунар. сем. "Дисретная математика и ее приложения" (Москва, 1-6 февраля 2010 г.) — М.: Изд-во механико-математического факультета МГУ, 2010. С. 139-141.

52. Трущин Д.В. Об оценках глубины Cü-пополнений систем функций трехзначной логики // Проблемы теоретической кибернетики: Мат-лы XVI Междунар. конф. Н.Новгород: Изд-во ННГУ, 2011. С. 484-487.

53. Трущин Д.В. О сложности реализации функций трехзначной логики формулами специального вида // Мат-лы VIII молодежной научной школы по дискретной математике и ее приложениям (Москва 24-29 октября 2011 г.). Часть II. С. 44-48.

54. Трущин Д.В. О сложности реализации функций из одного класса трехзначной логики формулами специального вида // Вестн. Моск. ун-та. Сер. 1. Математика. Механика. 2012. Вып. 4. Стр. 20-26.