Слабоповторные булевы функции в предэлементарных базисах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Шаранхаев, Иван Константинович

• Шаранхаев, Иван Константинович
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Шаранхаев, Иван Константинович

Введение

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

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

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

Глава 2. Слабоповторные булевы функции в предэлементар-ных немонотонных базисах

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

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

Глава 3. Слабоповторные булевы функции в предэлементар-ных парасимметрических базисах

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

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

Введение диссертации (часть автореферата) на тему «Слабоповторные булевы функции в предэлементарных базисах»

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

Представление булевых функций термами над заданным базисным множеством функций относится к основным этапам логического проектирования дискретных устройств [6, 7, 46, 47]. Поэтому неудивителен интерес, проявляемый к термальным представлениям [1, 16, 27, 36, 37, 39]. Существенным в изучении таких представлений явился результат Э. Поста об описании всех порожденных с помощью суперпозиции классов булевых функций, так называемых замкнутых классов булевых функций [43, 44]. Первоначальное доказательство этого результата было упрощено и изложено в более доступной форме [19, 20, 38].

Теоретический, а также практический интерес вызывают вопросы, касающиеся сложности представлений булевых функций термами. С одной стороны, имеем асимптотическую оценку сложности термальных представлений булевых функций над произвольными полными базисами. О. Б. Лупановым доказано [18], что почти все булевы функции имеют сложность 2n/log п. С другой стороны, при получении эффективных нижних оценок сложности возникают определенные трудности [17, 33, 49]. На сегодняшний день все известные эффективно заданные последовательности булевых функций имеют лишь полиномиальные оценки сложности [3, 21, 31, 32, 40, 41, 42, 45]. Таким образом, можно сказать, что исследования в этом направлении еще далеки от завершающей стадии.

При изучении вопросов сложности представлений булевых функций термами возникают такие понятия как бесповторность и слабоповтор-ность булевых функций. Бесповторные булевы функции, то есть функции, для которых существует представление в виде терма, в котором каждая переменная встречается не более одного раза, изучались еще с 50-х годов прошлого века, когда в работе А. В. Кузнецова [15] было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. Повторные булевы функции в некотором базисе В, у которых все собственные остаточные подфункции являются бесповторными в В, называются слабоповторными в базисе В. Из результата Н. А. Перязева [25] следует, что все неразделимые булевы функции есть слабоповторные функции в некотором базисе.

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

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

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

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

О. Б. Лупановым замечено (результат сформулирован в [30]), что элементарный базис bq ={V, —,0,1} является самым плохим по сложности реализаций функций термами. Слабоповторные булевы функции в этом базисе в терминах обобщенной однотипности были найдены В. А. Стеценко, им же было доказано, что предплохие базисы имеют следующий вид 5oU {/}, где / - слабоповторная функция в Во [28, 29, 48]. В обратную сторону это утверждение доказано Д. Ю. Черухиным [34]. Таким образом, все базисы, описанные В. А. Стеценко, являются предэле-ментарными.

Следующий шаг в этом направлении был сделан Н.А. Перязевым [26], описавшим слабоповторные булевы функции в предэлементарном базисе В\ ={©, V, •, —, 0,1}. Затем К. Д. Кириченко дал описание всех слабоповторных булевых функций для двух серий предэлементарных базисов [13].

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Шаранхаев, Иван Константинович

Заключение

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

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

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

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

Автор выражает искреннюю благодарность своему научному руководителю Н.А. Перязеву, а также всем участникам семинара «Дискретная математика и математическая информатика».

Список литературы диссертационного исследования кандидат физико-математических наук Шаранхаев, Иван Константинович, 2003 год

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

2. Избранные вопросы теории булевых функций / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков, О. В. Зубков, К. Д. Кириченко, В. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева; Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

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

4. Артюхов В. Л., Копейкин В. Л., Шалыто А. А. Настраиваемые модули для управляющих логических устройств / В. Л. Артюхов, В. Л.

5. Копейкин, А. А. Шалыто. —Ленинград: Энергоиздат, 1981. — 166 с.

6. Бохманн Д., Постхоф X. Двоичные динамические системы / Д. Бох-манн, X. Постхоф. — М.: Энергоатомиздат, 1986. — 401 с.

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

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

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

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

11. Зубков О. В. Соотношение количества бесповторных булевых функций в различных базисах / О. В. Зубков // Дискретная математика:

12. Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 61-66.

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

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

15. К. Д. Кириченко Слабоповторные булевы функции в некоторых предэлементарных базисах / К. Д. Кириченко // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 13. — Иркутск, 2000. — 60 с.

16. Кириченко К. Д. Слабоповторные булевы функции в небинарных базисах / К. Д. Кириченко // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 14. — Иркутск, 2000. — 20 с.

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

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

19. Лупанов О. Б. О методах получения оценок сложности и вычисления индивидуальных функций / О. Б. Лупанов // Дискретный анализ. Вып. 25. Новосибирск, 1974. — С. 3-18.

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

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

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

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

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

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

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

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

28. Перязев Н. А. Слабоповторные булевы функции в бинарном базисе / Н. А. Перязев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 4. — Иркутск, 1998. — 12 с.

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

30. Стеценко В. А. Об одном необходимом признаке для предмакси-мальных базисов в Р2 / В. А. Стеценко // Докл. АН СССР. — 1990. — Т. 315. С. 1304-1307.

31. Стеценко В. А. О предплохих базисах в Р2 / В. А. Стеценко // Математические вопросы кибернетики. — 1992. —Вып. 4. — С. 139— 177.

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

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

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

35. Храпченко В. М. Нижние оценки сложности схем из функциональных элементов / В. М. Храпченко // Кибернетич. сб. Новая серия.1' Вып. 21. М.: Мир, 1984. - С. 3-54.

36. Черухин Д. Ю. О предплохих булевых базисах / Д. Ю. Черухин // Дискретная математика. 1999. - Т. 11. - № 4. — С. 118-160.

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

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

39. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов. / под ред. В. А. Садовничего / С. В. Яблонский. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.

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

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

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

43. Post E. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer. J. Math. — 1921. — V. 43. —No 4. — P. 163185.

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

45. Pudlak P. Bounds for Hodes Specker theorem / P. Pudlak // Lecture Notes in Computer Science 171, Springer - Verlag. — 1984. — P. 421— 445.

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

47. Shannon С. E. The synthesis of two terminal switching circuits / С. E. Shannon // Bell. System. Techn. J. — 1949. — V. 28. — P. 5998.

48. Stetsenko V. On almost bad Boolean bases / V. Stetsenko // Theoretical Computer Science. — 1994. — V. 136. — P. 419-469.

49. Wegener I. The Complexity of Boolean function / I. Wegener // Wiley Teubner Series in Computer Science, Wiley - Teubner. — 1987.

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

51. Шаранхаев И. К. Слабоповторные булевы функции в одном предэле-ментарном базисе / И. К. Шаранхаев // Дискретная математика: Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 151-155.

52. Шаранхаев И. К. О слабоповторных булевых функциях / И. К. Шаранхаев // XIII Международная конференция по проблемам теоретической кибернетики. Тезисы докл. — Казань, 2002. — Часть 2. — С. 195.

53. Шаранхаев И. К. О слабоповторных булевых функциях в одном базисе / И. К. Шаранхаев // Материалы конференции «Дискретный анализ и исследование операций». — Новосибирск, 2002. — С. 139.

54. Шаранхаев И. К. Слабоповторные булевы функции в предэле-ментарных немонотонных базисах / И. К. Шаранхаев // Труды Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. — Иркутск, 2003. — С. 87-90.

55. Шаранхаев И. К. О слабоповторных булевых функциях в одном предэлементарном базисе / И. К. Шаранхаев // Дискретный анализ и исследование операций. — Новосибирск, 2003. — Серия 1. — Т. 10. — № 2. С. 79-101.

56. Шаранхаев И. К. Слабоповторные булевы функции в некоторых базисах / И. К. Шаранхаев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 17. — Иркутск, 2003. — 64 с.