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

Введение

Глава 1. Классы полиномиальных форм

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

§ 2. Иерархия классов операторных пучков

§ 3. Обзор результатов по полиномиальным формам.

Глава 2. Функция Шеннона и нахождение коэффициентов полиномиальных форм

§ 4. Коэффициенты полиномиальных форм по обратимым операторам

§ 5. Общие свойства функции Шеннона для операторных полиномиальных формах.

§ 6. Точные значения функции Шеннона для а-кронекеровых и свободно-кронекеровых классов полиномиальных форм

Глава 3. Сложные функции в классах полиномиальных форм

§ 7. Функции экспоненциальной сложности в классе полиномиальных нормальных форм.

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

§ 9. Функции наибольшей сложности в классах операторных полиномиальных нормальных форм

§ 10. Функции наибольшей сложности в классах операторных полиномиальных форм.

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

До сих пор аппарат булевых функций является наиболее адекватным для проектирования цифровой, в том числе микропроцессорной техники. Постоянное стремление к повышению быстродействия систем, уменьшению их размера, потребляемой энергии и стоимости ставит задачи не только поиска новых технологий реализации цифровых устройств, но и более простой и эффективной реализации существующих. Это ведет к интенсивному исследованию и проектированию различных регулярных структур. Одними из наиболее распространенных являются программируемые логические матрицы (PGA и FPGA).

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

Одним из основных способов задания булевых функций является формульное или, иначе, термальное представление. Одним из вопросов формульных представлений является вопрос о принципиальной возможности реализации тех или иных булевых функций формулами, использующими специально выбранные, базисные функции. Этот вопрос был решен Э. Постом [20, 44, 45].

И в теории, и в приложениях одним из наиболее интересных вопросов является вопрос о сложности представлений булевых функций с помощью тех или иных структур. Важными результатами в этом направлении, являются асимптотически точные оценки сложности реализаций булевых функций формулами и схемами из функциональных элементов, которые принадлежат О. Б. Лупанову [15, 16, 17, 18, 29]. Однако, несмотря на полученные экспоненциальные оценки, нахождение конкретных функций большой сложности, другими словами, нахождение эффективных нижних оценок, сопряжено с определенными трудностями [30, 31]. К настоящему времени построены лишь булевы функции, сложность которых в классе схем из функциональных элементов линейна [34], а в классе формул полиномиальна. Обзор результатов по этим вопросам можно найти в [21, 27, 28]. В более специализированных классах представлений удается получить более высокие эффективные нижние оценки сложности.

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

Хорошо исследован вопрос о реализации булевых функций дизъюнктивными и конъюнктивными нормальными формами [25, 33, 42, 46, 26]. Однако здесь уже для хорошо известных и часто применяемых функций, например, для линейной, найдены высокие нижние оценки сложности, которые совпадают с верхними оценками [19]. Величина этих оценок накладывает определенные ограничения на возможности практической реализации данных нормальных форм.

В этой связи более интересными представляются полиномиальные нормальные формы. Впервые полиномиальные нормальные формы были рассмотрены И. И. Жегалкиным при исследовании некоторых вопросов математической логики [9, 10]. Затем, в 50-х годах прошлого века, полиномиальные нормальные формы исследовались в связи с их применением в теории кодирования [43, 47]. Следующий всплеск интереса к полиномиальным нормальным формам произошел в конце прошлого века, после того как в цифровой технике стали активно применяться элементы типа «сложение по модулю 2» («EXOR») [11, 32, 40, 41].

Для сложности представлений булевых функций полиномиальными нормальными формами были найдены нижняя [37] и верхняя [13, 12] границы. Эти оценки отличаются на множитель logrc, поэтому вопрос об асимптотически точной оценке еще ждет своего решения. Также были построены эффективно заданные булевы функции, которые в классе полиномиальных нормальных форм имеют экспоненциальную сложность [58]. Однако, сложность построенных булевых функций значительно меньше теоретической верхней оценки. Поэтому стойт также вопрос о поиске эффективно заданных сложных функций.

Для того чтобы провести более глубокие исследования, из всего класса полиномиальных нормальных форм выделяют некоторые подклассы, обладающие теми или иными свойствами. Эти подклассы образуют некоторую иерархию. Различные подходы к описанию подклассов приводят к различным иерархиям [35, 36, 39, 56]. В большинстве случаев между иерархиями нетрудно найти соответствие. Но одни классы удобнее описывать и исследовать на одном языке, другие — на другом.

В ряде работ был предложен и разработан операторный подход к исследованию булевых функций [1, 22]. Использование операторов позволило обобщить полиномиальные нормальные формы на полиномиальные формы по базисным функциям, а введение понятия пучка операторов и применение аппарата линейной алгебры открыло возможность описывать произвольные классы полиномиальных форм по базисным функциям, в том числе классы полиномиальных нормальных форм [3, 4, 5, 6, 7, 38, 56].

В классах полиномиальных нормальных форм, исключая классы, порождаемые единственным операторным пучком, долгое время стоял вопрос о нахождении точных оценок сложности. Лишь в 1995 году появился первый результат такого рода [24]. В дальнейшем были получены точные оценки сложности для различных классов [2, 3, 54, 56, 59].

Методы, использованные для нахождения высоких нижних границ сложности, предполагают построение конкретных функций, на которых эта граница достигается. Встал вопрос об описании всех функций наибольшей сложности в различных классах полиномиальных форм. Этот вопрос был решен для всех классов, точные оценки сложности которых известны [52, 54, 56, 57, 59].

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

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

Заключение

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

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

2. Найдены точные оценки сложности для а-кронекеровых и свободно-кронекеровых классов полиномиальных форм.

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

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

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

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

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

2. Винокуров С. Ф. Некоторые оценки сложности булевых функций в классе полиномов // Синтез и сложность управляющих систем, VII Межгосударственная школа-семинар. — Минск, 1995. — С. 4-5.

3. Винокуров С. Ф. Смешанные операторы в булевых функциях и их свойства. — Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 12. — Иркутск, 2000. — 36 с.

4. Винокуров С. Ф., Перязев Н. А. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций // Изв. вузов. Матем. — 1996. — № 1. — С. 17-21.

5. Винокуров С. Ф., Перязев Н. А. Полиномиальные разложения булевых функций // Кибернетика и системный анализ. — 1993. — № 6. — С. 34-47.

6. Винокуров С. Ф., Перязев Н. А. Полиномиальные разложения булевых функций по образам неоднородных операторов // Кибернетика и системный анализ. — 2000. — № 4. — С. 40-55.

7. Винокуров С. Ф., Перязев Н. А. Представление булевых функций полиномиальными формами // Кибернетика и системный анализ. — 1992. № 3. - С. 175-179.

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

9. Жегалкин И. И. Арифметизация символической логики. — Мат. сборник. 1928. - Т. 35. - С. 311-373.

10. Жегалкин И. И. Арифметизация символической логики. — Мат. сборник. 1929. - Т. 36. - С. 305-338.

11. Закревский А. Д. Минимизация систем булевых функций в полиномах Жегалкина // Докл. Белорусской АН. — 1995. — Т. 39, № 6. — С. 11-14.

12. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Труды XII Международной школы-семинара „Синтез и сложность управляющих систем" — М., 2001. Т. 1. - С. 115-120.

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

14. Корсуков А. В. Ращложения булевых функций с оператором векторной производной // Алгебра, логика и приложения. — Иркутск: Иркут. ун-т, 1994. С. 116-124.

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

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

17. Лупанов О. Б. Об одном методе синтеза схем // Известия высших учебных заведений. Радиофизика. — 1958. Т. 1, № 1. — С. 120-140.

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

19. Лупанов О. Б. О реализаций функций алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе

20. V, // Проблемы кибернетики. Вып. 6. — М.: Физматгиз, 1961. — С. 5-14.

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

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

23. Пантелеев В. И., Перязев Н. А. Об операторах булевых функций // Труды XI Межгос. школы-семинара „Синтез и сложность управляющих систем" — М.: Изд-во Московск. ун-та, 2000. — Часть. 2. — С. 141-146.

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

25. Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика — 1995. — Т. 34. — №. 3. С. 323-326.

26. Порецкий П. С. О способе решения логических равенств и об обратном способе математической логики // Собр. протоколов заседаний секции физ.-мат. наук Об-ва испытателей природы при Казанском ун-те. Т. 2. — 1884.

27. Сапоженко А. А., Чухров И. П. Минимизация булевых функций в классе дизъюнктивных нормальных форм // ВИНИТИ. Итоги науки и техники. Теоретическая кибернетика. — 1987. — Вып. 25. — С. 68116.

28. Сэвидж Д. Э. Сложность вычислений: пер. с англ. — М.: Изд-во «Факториал», 1998. — 368. с.

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

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

31. Яблонский С. В. О невозможности элиминации перебора всех функций из Р2 при решении некоторых задач теории схем // Докл. АН СССР. 1959. - Т. 124, № 1. - С. 44-47.

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

33. Besslich Ph. W., Riege M. W. An efficient program for logic synthesis of mod-2 sum expressions // Proc. EUROASIC. Paris, France, 1991. — P. 136-141.

34. Blake A. Canonical expression in Boolean algebra. Dissertation — Chicago, 1937.

35. Blum N. A. A Boolean function requiring 3n network size // Theoret. Comput. Sci. — 1984. — V. 28, N 3. — P. 337-345.

36. Chrzanowska-Jeske M., Perkowski M., Mishchenko A. How to catch the golden fish of minimum ESOP into the net of canonical forms. — Portland State Univer., USA, 2001 — 11 p.

37. Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions // IEEE Trans. Electron. Comput. — 1967. — V. EC-16, N 10. — P. 671-674.

38. Gaidukov A. I., Vinokurov S. F. Operator polynomial expansions of Boolean functions// 4th International Workshop on Boolean Problems. — Freiberg, Germany, 2000. — P. 63-68.

39. Green D. H. Families of Reed-Mnller Canonical Forms // Intern. J. of Electr. — Febr. 1991 — N. 2 — P. 259-280.

40. Koda N., Sasao T. An upper bound on the number of products in minimum ESOPs // IFIP wg 10.5. Workshop on application of the Reed-Muller expansion application in cicuit design. Japan, 1995 — P. 94-101.

41. Logic synthesis and optimization / ed. T. Sasao. — Kluwer Academic Publishers, 1993. — 320 p.

42. McCluskey E. J. Minimisation of Boolean functions // Bell Syst. Techn. J. — 1956. — N 35. — P. 1417-1444.

43. Muller D. E. Application of Boolean to switching circuit desing and error detection // IRE Trans. Electron. Comput. — 1954. — V 3, n. 3. — P. 6-12.

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

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

46. Quine W. V. A way to simplify truth functions //J. Symbol. Logic. — 1955. — N 20. — P. 105-108.

47. Reed I. S. A class of multiply-error-correcting codes and decoding scheme // IRE Trans. Inform. Theory. — 1954. — V 4, N. 9. — P. 38-49.

48. Schnorr C. P. Zwei lineare untere Schranken fur die Komplexitat Boo-lescher Funktionen // Computing. Archiv fur elektronisches Rech-nen. — 1974. — V. 13, N 2. — P. 155-171.

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

50. Балюк А. С. Сложные симметрические булевы функции в классах поляризованных полиномиальных форм // Труды ВосточноСибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. — Иркутск, 1999. — С. 148-149.

51. Балюк А. С. Сложные в полиномиальных поляризованных формах симметричные булевы функции // XII Международная конференция по проблемам теоретической кибернетики. Тезисы докл. — Нижний Новгород, 1999. — С. 17.

52. Балюк А. С. Булевы функции, имеющие наибольшую сложность в классах поляризованных полиномов Жегалкина и кронекеровских форм // Студент и научно-технический прогресс: тез. докл. студ. и асп. — Иркутск: Иркут. ун-т, 1999. — С. 63.

53. Балюк А. С. Сложные в полиномиальных поляризованных формах функции алгебры логики // Международная конференция по математической логике. Тезисы докл. — Новосибирск, 1999. — С. 9-10.

54. Балюк А. С., Винокуров С. Ф. Функция Шеннона для некоторых классов операторных полиномиальных форм // Оптимизация, управление, интеллект. — Иркутск, 2000. — Вып 5. — С. 111-121.

55. Балюк А. С., Винокуров С. Ф. О полиномиальных представлениях булевых функций // Материалы VII Международного семинара «Дискретная математика и ее приложения». — М.: Изд-во Центра прикладных исследований МГУ, 2001. — С. 100-101.- 94

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

57. Балюк А. С. Сложные булевы функции в классах двупорожденных операторных пучков // Дискретная математика: Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 17-21.

58. Балюк А. С. Нижняя оценка сложности одной последовательности булевых функций в классе полиномиальных нормальных форм // Труды XII Международной школы-семинара „Синтез и сложность управляющих систем'.' М., 2001. — Т. 1. — С. 18-21.

59. Balyuk A., Vinokurov S. Classes of Operator Forms // 5th International Workshop on Boolean Problems. — Freiberg, Germany, 2002. — P. 217-224.