Нахождение, оценка и сравнение числа бесповторных булевых функций в различных базисах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение.

Глава I. Основные понятия и результаты.

§1. Основные понятия и терминология.

§2. Обзор результатов по бесповторным булевым функциям

Глава II. Количество бесповторных булевых функций в бинарных базисах.

§3. Нерекуррентная формула для числа бесповторных булевых функций в элементарном базисе

§4. Связь между числом бесповторных функций в элементарном базисе и числами Эйлера второго порядка.

§5. Оценки числа бесповторных булевых функций в элементарном базисе

§6. Нерекуррентная формула для числа бесповторных булевых функций в линейном бинарном базисе

§7. Оценки числа бесповторных булевых функций в линейном бинарном базисе".'.;.;.,--------.

§8. Сравнение числа бесповторных булевых функций в бинарных базисах.

Глава III. Количество бесповторных булевых функций в произвольных базисах.

§9. Рекуррентная формула для числа бесповторных булевых функций в Нелинейном базисе

§10. Рекуррентная формула для числа бесповторных булевых функций в линейном базисе

§11. Количество бесповторных булевых функций в предэлементарных базисах.

§12. Сравнение числа бесповторных булевых функций в различных базисах.

Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Теория дискретных функций в настоящее время является интенсивно развивающейся областью дискретной математики. Ее простейшей и вто же время значимой частью является теория булевых функций. Математические модели, описываемые на языке булевых функций, находят широкое применение в самых различных областях человеческой деятельности. В связи с этим важное значение приобретает вопрос о представлении булевых функций в виде, удобном для исследования. Традиционно, одним из таких способов является суперпозиция выделенных базисных функций. В теории булевых функций такое задание называется термальным или формульным. В соответствии с этим, большое внимание уделяется термальным представлениям булевых функций [1, 16, 28, 36, 37, 39]. Важным шагом в этом направлении является сделанное Э. Постом описание всех замкнутых классов булевых функций [46, 47].

В связи с тем, что булевы функции являются признанной моделью для проектирования схем, применяемых в электронике [7, 8, 48, 49], сформировалось направление исследований, связанное с нахождением для булевых функций представлений, имеющих наименьшую сложность. Даже для простых базисных множеств точное решение этой задачи связано с почти полным перебором [38]. В связи с быстрым ростом числа булевых функций при увеличении числа аргументов, практическое использование алгоритмов точной минимизации возможно только для функций малой размерности [12, 40]. Даже если требовать не абсолютно точной минимизации, а лишь достаточно хорошего в определенном смысле представления булевых функций в виде термов, то можно найти такое представление для функций незначительно большей размерности [4, 5, 18, 19, 20, 57].

Для произвольных полных базисов известна асимптотическая оценка сложности, полученная О. Б. Лупановым [16, 17]. Им показано, что подавляющее большинство булевых функций имеет сложность 2n/logn. Однако все известные до сих пор эффективно задающиеся последовательности булевых функций имеют лишь полиномиальные оценки сложности [2, 21, 33, 34, 41, 42, 45].

С таких позиций становятся ясными причины интереса, проявляемые к функциям, которые имеют самое простое представление в каком-либо базисе. Наименьшую сложность при термальном представлении имеют бесповторные булевы функции, то есть функции, для которых существует задание в виде терма, где каждая переменная встречается не более одного раза. И хотя, как следует из работы автора [56], бесповторных булевых функций существенно меньше, чем остальных функций, они имеют большое практическое значение. Большая часть функций, применяемых при проектировании микропроцессоров, является бесповторными в базисе, состоящем из конъюнкции, дизъюнкции и отрицания [3]. Кроме того следует отметить результат Б. А. Суббо-товской [31, 32] о том, что базис эквивалентен элементарному в смысле сложности термального задания булевых функций тогда и только тогда, когда он содержит лишь бесповторные функции в элементарном базисе. Для произвольного базиса этот результат был обобщен Д. Ю. Черухиным [35].

Ключевым для раздела, изучающего бесповторные булевы функции, является результат В. А. Кузнецова [15] о том, что бесповторные термы, представляющие одну и ту же булеву функцию, то есть эквивалентные между собой, весьма похожи друг на друга и могут отличаться только по четко выделенным позициям. Это утверждение позволяет каждой бесповторной булевой функции поставить в соответствие единственный в определенном смысле терм, представляющий ее.

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

Основной задачей первого является нахождение эффективных алгоритмов, позволяющих определить, является ли заданная функция бесповторной в рассматриваемом базисе, и в случае положительного ответа, найти ее бесповторное представление. Для бинарных базисов существует множество критериев бесповторности функции [10, 11, 24, 25, 32, 14]. Для произвольных базисов следует отметить описание метода получения критериев бесповторности, опубликованное в [13].

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

Слабоповторные булевы функции являются, в некотором смысле, наименьшими из повторных функций. Как следует из результата Н. А. Перязева [26] о том, что всякая слабоповторная функция является неразделимой, добавление к базису слабоповторной функции позволяет, с одной стороны, расширить его, в смысле увеличения возможностей по реализации булевых функций термами, а с другой стороны, сделать это расширение минимальным [35]. Можно так же отметить, что даже такое расширение базиса существенно увеличивает количество бесповторных в нем булевых функций [56].

Диссертация относится к числу работ, изучающих бесповторные булевы функции с точки зрения их количества.

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

Во второй части диссертации производится обобщение некоторых результатов, полученных для бинарных базисов [22, 27, 57] на произвольные базисы, в которых унарные функции реализуются бесповторно. Получены рекуррентные формулы для нахождения числа бесповторных булевых функций для базисов такого вида и как их приложение найдены формулы для нахождения количества бесповторных булевых функций во всех предэлементарных базисах, описанных В. А. Стеценко [30, 50]. Здесь же показано, что добавление к базису слабоповторной в нем функции существенно увеличивает количество бесповторных в нем булевых функций. Этот результат является обобщением доказанного в конце первой части.

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

Заключение

На защиту выносятся следующие результаты:

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

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

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

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

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

6. Доказано, что при добавлении к базису слабоповторной в нем функции, существенно увеличивается число бесповторных булевых функций.

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

1. Дискретная математика и математические вопросы кибернетики. Под редакцией Яблонского С. В. и Лупанова О. Б. М.: Наука, 1974. - Т 1. - 312 с.

2. Андреев А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности 7г-схем // Вестн. МГУ. Сер. 1. Матем.Мех. 1987. - N 1. - С. 70 - 73.

3. Артюхов В. Л., Копейкин Г. А., Шалыто А. А. Настраиваемые модули для управляющих логических устройств. -Ленинград: Энер-гоиздат, 1981. 166 с.

4. Винокуров С. Ф., Манцивода Ю. В., Перязев Н. А. Минимизация булевых функций в классах нормальных форм методом разложения // Фундаментальные проблемы математики и механики. Матматика. М.: Изд-во Московского ун-та, 1994. - С. 316 - 317.

5. Винокуров С. Ф., Гайдуков А. И., Корсуков А. В. Библиотека классов булевых функций // Сб. тр. Иркутского университета. Иркутск, 1995. -Т. 3. - С. 228 - 229.

6. Гершкович Ю. Б., Полтерович В. М. О бесповторных суперпозициях функций алгебры логики от двух переменных / / Автоматика и телемех. 1966. - С. 71 - 79.

7. Глушков В. И. Введение в кибернетику. Киев: Изд-во АН УССР, 1964. - 324 с.

8. Глушков Р. М., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дискретных устройств. Киев: Наукова думка, 1987. -264 с.

9. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. М.: Мир, 1998. -703 с.

10. Гурвич В. А. О бесповторных булевых функциях // Успехи матем. наук. 1977. - 32, N 1. - С. 183 - 184.

11. Гурвич В. А. Критерий бесповторности функций алгебры логики // ДАН СССР. 1991. - 318, N 3. - С. 532 - 537.

12. Казаков В. Д. О скобочных минимальных выражениях булевых функций // Duexieme Congres Mathematique Hongrois, Budapest.- 1961. V. 2.

13. Кириченко К. Д. О критериях бесповторности булевых функций в различных базисах // Оптимизация, управление, интеллект.- 2000, N 4. С. 93 - 101.

14. Кириченко К. Д. Критерий бесповторности функции алгебры логики в бинарном базисе // Международная конференция "Логика и приложения". Новосибирск. - 2000. - 57 - 58.

15. Кузнецов А.В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Труды МИ АН СССР. Т.51.— М.: Из-во АН СССР. 1958. С.186-225.

16. Лупанов О. Б. О сложности реализаций функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. гиз, 1963. С.61 80.

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

18. Манцивода(Перязева) Ю. В. Минимизация булевых функций в классе бинарных формул // Международная Сибирская конференция по исследованию операций. Новосибирск. -1998. - С. 131.

19. Манцивода(Перязева) Ю. В. Минимизация представлений булевых функций термами // Труды Восточно Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе. - Иркутск, 1999. - С. 167 - 170.

20. Манцивода(Перязева) Ю. В. Алгоритм линейной минимизации булевых функций и его программная реализация. Иркутский университет. Серия: Дискретная математика и информатика. Вып. 9. - Иркутск, 1999. - 25 с.

21. Нигматуллин Р. Г. Сложность булевых функций. М.: Наука, 1991. - 240 с.

22. Перязев Н. А. Представление функций алгебры логики бесповторными формулами // Тезисы сообщений на XI Межреспубликанской конференции по математической логике. Казань. - 1992.- С. 110.

23. Перязев Н. А. Реализация булевых функций бесповторными формулами // Фундаментальные проблемы математики и механики. Математика. М.: Изд-во Моск. ун-та, 1994. - С. 320.

24. Перязев П. А. Реализация булевых функций бесповторными формулами в некоторых базисах // Сб. Алгебра, логика и приложения. Иркутск, 1994. - С. 143 - 154.

25. Перязев Н. А. Реализация булевых функций бесповторными формулами // Дискретная математика. 1995. - Т. 7, N 3. - С. 61 - 68.

26. Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 2. - Иркутск, 1999. - 15 с.

27. Перязев Н. А., Разгильдеев В. Т. Число бесповторных булевых функций в бинарных базисах // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики.- Ульяновск. 1996. - С. 161 - 162.

28. Перязев Н. А. Основы теории булевых функций. М.: Физматлит, 1999. - 112 с.

29. Риордан Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.- 287 с.

30. Стеценко В.А. О предплохих базисах в // Математические вопросы кибернетики. 4(1992), С. 139 - 177.

31. Субботовская Б. А. О реализации линейных функций формулами в базисе V, // ДАН СССР. - 1961. - Т. 136, N 3. - С. 553 - 555.

32. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // ДАН СССР. 1963. - Т.149, N 4.- С. 784 787.

33. Храпченко В. М. О сложности реализации линейной функции в классе П-схем // Математические заметки. -1971. Т. 9, N 1. - С. 35 - 40.

34. Храпченко В. М. О сложности реализации симметрических функций формулами // Математические заметки. -1972. Т. 11., N 1.- С. 109 120.

35. Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики, вып. 8 М.: Наука. Физматлит, 1999. - С. 77 - 122.

36. Шеннон К. Э. Работы по теории информации и кибернетике. М.: ИЛ., 1963. - 829 с.

37. Яблонский С. В. О суперпозициях функций алгебры логики // Математичесий сборник. 1952. - Т. 30, N 2. - С. 329 - 345.

38. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. Вып. 2.- М.: Физматгиз, 1959. С. 75 - 122.

39. Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. - 384 с.

40. Abhyankar S. Absolute minimal expressions of Boolean function.- "IRE Tr. on EC.". 1959. - V. EC-8, No 1.

41. Fischer M., Meyer A. R., Paterson M. S. Lower bounds on the size of Boolean formulas, preliminary report // Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque. 1975. - P.37 44.

42. Fischer M., Meyer A. R., Paterson M. S. Q(nlogn) lower bounds on length of Boolean formulas // SIAM J. Comput. 1962. -V. 11, No 3. - P. 416 - 427.

43. Gessel I., Stanley R. P. Stirling polinomials // Journal of Combinatorial Theory. series A. - 1978. - P. 24 - 33.

44. Ginsburg J. Note on Stirling's numbers // American Mathematical Monthly. 1928. - P. 77 - 80.

45. Hodes L., Specker E. Lengths of formulas and elimination of quantifiers // Contributions to mathematical logic. Amsterdam.- 1968. P. 175 - 188.

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

47. Post E. L. Two-valued iterative systema of mathematical logic // Annals of Math. Studies. 1941. - No 5.

48. Shannon С. E. A symbolic analysis of relay and switching circuits // Trans.AIEE. 1938. -V. 57. - P. 713 - 723.

49. Shannon С. E. The synthesis of two-terminal switching circuits // Bell.System. Techn. J. 1949. - V. 28. - P. 59 - 98.

50. Stetsenco V. On almost bad Boolean bases // Theoretical Computer Science. 136. 1994. - P. 419 - 469.

51. Работы автора по теме диссертации

52. Зубков О. В. Количество бесповторных булевых функций в приведенных базисах // Конф. "Студент и научно-технический прогресс. Молодые ученые к 80-летию ИГУ", тезисы докладов. Иркутск, ИГУ. - 1998. - С 45.

53. Зубков О. В. Число бесповторных булевых функций // Третий Сибирский Конгресс по прикладной и индустриальной математике. Сибирская конференция по исследованию операций. Новосибирск. - 1998. - С 126.

54. Зубков О.В. Формулы для нахождения числа бесповторных булевых функций в различных базисах // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции. Нижний Новгород. - 1999. Часть I, - С 83.

55. Зубков О.В. Число бесповторных функций алгебры логики в некоторых базисах // Материалы международной конференции по математической логике. Новосибирск. - 1999. - С. 24-25.

56. Зубков О. В. Рекуррентные формулы для нахождения количества бесповторных булевых функций в различных базисах // Синтез и сложность управляющих систем. Материалы XII международной школы-семинара. М.: Изд-во МГУ, 2001. Т 1. - С. 93 - 99.

57. B. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева; Под ред.

58. C.Ф. Винокурова и Н.А. Перязева. М.: Физматлит, 2001. - 192 с.

59. Зубков О. В. Оценки числа бесповторных булевых функций в бинарных базисах // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 15. Иркутск, 2002. - 36 с.