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

Введение

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

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

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

Глава II. Стягиваемые функции и построение сокращенной дизъюнктивной нормальной формы

§3. Оператор минимума и его свойства.

§4. Построение сокращенной дизъюнктивной нормальной формы по полурешетке минимумов функции.

§5. Стягиваемые функции.

Глава III. Минимизация в полиномиальных нормальных формах

§6. Алгоритмы построения минимальных полиномиальных нормальных форм, использующие библиотеки представителей.

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

§8. Алгоритмы нахождения приближенных минимумов в полиномиальных нормальных формах.

В конце XIX - начале XX веков исследования по булевым функциям были связаны с применением к логике и основаниям математики. При этом булевы функции рассматривались как логические формулы над связками конъюнкции, дизъюнкции, импликации, отрицания и эквивалентности. Для становления исследований по булевым функциям как самостоятельной теории существенным явилось открытие новых приложений к описанию релейно-контактных схем и помехоустойчивому кодированию. Задача минимизации булевых функций в классе дизъюнктивных нормальных форм (д.н.ф.) и полиномиальных нормальных форм (п.н.ф.) состоит в построении по произвольно заданной булевой функции реализующего ее терма вида "дизъюнкция конъюнкций" для д.н.ф. и "суммы конъюнкций" для п.н.ф. содержащие минимальное число слагаемых или дизъюнктов. Отдельные задачи, связанные с минимизацией д.н.ф., привлекали внимание специалистов по математической логике еще в XIX веке. Однако актуальной задача минимизации стала лишь в 40-50 годах XX века в связи с применением языка алгебры логики для синтеза управляющих устройств и электронных вычислительных машин. В 50-80 годах XX века было создано большое число эвристических алгоритмов минимизации, возникли различные методы и приемы, механические и электронные устройства, минимизирующие карты и диаграммы для поиска минимальных дизъюнктивных нормальных форм булевых функций.

В основу многих алгоритмов минимизации в классе д.н.ф. положено решение известной комбинаторной задачи о нахождении минимального покрытия множества [6, 7, 18]. Задача минимального покрытия для минимизации в д.н.ф. состоит в том, чтобы из множества простых импликант функции выбрать минимальное подмножество простых импликант, которые реализуют исходную функцию. Задача построения всех простых импликант функции является частью задачи минимизации в классе д.н.ф. и заключается в построении сокращенной д.н.ф. Одним из наиболее известных алгоритмов построения сокращенной д.н.ф. является алгоритм Блейка-Порецкого [17, 24]. Квайн [36] предложил алгоритм построения сокращенной д.н.ф. по совершенной. В работах [13, 15] предложен модифицированный алгоритм Квайна, и этот алгоритм имеет сложность порядка ш4, где т — длина совершенной д.н.ф. Из [5] известно, что длина совершенной д.н.ф. ассимптотически равна 2"-1, где п — количество переменных. Значит сложность алгоритма ассимптотически равна 16n1.

Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И.Й.Жегалкина [8, 9]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения в кругах, далеких от логики.

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

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

Попытки напрямую перенести методы работы с д.н.ф. на п.н.ф. не принесли ощутимых результатов [19, 41]. Это стимулировало исследования по полиномиальным каноническим формам, так как имеется большое количество классов таких канонических представлений. По этому направлению имеется целый ряд публикаций и монографий [22, 35, 43, 45, 46, 58].

Методам минимизации полиномиальных представлений булевых функций и оценкам их сложности посвящены работы [4, 19, 23, 26, 27, 40, 42, 44, 50].

Булевы уравнения широко используются при проектировании и тестировании электронных устройств. В [4] предложен способ представления конечных автоматов в момент времени t одним булевым уравнением L(x,y, z)(t) = 0, называемым уравнением Лангранжа. В уравнении Лангранжа х — множество входных переменных, у — множество переменных-состояний автомата, z = {z\ (х, у),., zn(x, у)) — функция переходов автомата. Действие конечного автомата определено в момент времени t тогда и только тогда, когда уравнение L(x,y, z)(t) = 0 разрешимо по переменным z. Конечный автомат детерминирован тогда и только тогда, когда уравнение L(x,y, z)(t) — 0 однозначно разрешимо по переменным z для любого t. Оператор минимума используется для определения разрешимости уравнения по переменным, способ нахождения решений уравнения, способ определения однозначной разрешимости уравнения.

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

Диссертация состоит из трех глав, которые разбиты на 8 параграфов.

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

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

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

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

По результатам, изложенным в диссертации, имеется 11 публикаций [51 - 61]. Результаты докладывались на международных конференциях по алгебре, дискретной математике, математической и прикладной логике, теоретической и технической кибернетике (XII Международная конференция по математической логике, Новосибирск, 1994; международная конференция по прикладной логике, Иркутск, 1995; международная Сибирская конференция по исследованию операций, Новосибирск, 1998; конференция "Проблемы теоретической кибернетики", Нижний Новгород, 1999; конференция "Математика и ее приложения", посвященная памяти профессора А.И.Кокорина и 275-летию РАН, Иркутск, 1999; международная конференция "Математика, информатика и управление", Иркутск, 2000; международная конференция по проблемам в булевых функциях, Фрайберг (Германия), 2000; 12-ая Байкальская международная конференция, Иркутск, 2001).

Были сделаны доклады в ведущих научных центрах: Институт математики СО РАН (г. Новосибирск), Институт динамики систем и теории управления СО РАН (г. Иркутск), 9 —

Институт прикладной математики и кибернетики (г. Нижний Новгород) Институт информатики (г. Фрайберг, Германия), Иркутский государственный университет.

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

Заключение

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

1. Разработан новый подход к построению сокращенной дизъюнктивной нормальной формы, использующий оператор минимума.

2. Описан алгоритм построения сокращенной д.н.ф. по верхней полурешетке минимумов, дано его обоснование и найдена оценка его сложности.

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

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

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

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

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

2. Ачасова С.М. Алгоритмы синтеза автоматов на программируемых матрицах.- М.: Радио и связь, 1987 135 с.

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

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

5. Глаголев В.В. Некоторые оценки д.н.ф. булевых функций алгебры логики В сб. "Пробл. кибернет.".М: Наука.-1967.- Вып. 19.- С.75-94.

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

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

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

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

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

11. Кириченко К. Д. Верхняя оценка функции Шеннона сложности полиномиальных форм булевых функций // Труды 12-ой Байкальской международной конференции 2001.— Т.5.- С.66-70.

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

13. Любченко Г.Г., Подлипенский B.C. Алгоритмы минимизации многоместных переключательных функций// В сб. Средства автоматиз. передачи и обраб. информ. Киев, Техника, 1974, - С.35-43.

14. Мачикенас Э.К., Супрун В.П. О полиномиальном разложении булевых функций // Изд-во Белорусской АН, физмат. лит-ра, Минск.- 1988.- 31 с.

15. Перчеклий И.И. Полиномиальная разрешимость некоторых алгоритмических проблем касающихся д.н.ф.// Тезисы докладов 3-ей Всесоюзной конференции по проблемам теоретической кибернетики. Новосибирск, 1974, -С.115-116.

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

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

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

19. Тошич Ж. Полиномиальные представления булевых функций и их минимизация// Известия АН СССР. Техн. кибернетика.- 1967.- № 3.- С. 141-143.

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

21. Применение логики в науке и технике. Из-во АН СССР, 1960. - 558 с.

22. Akers S.B. A rectangular logic array. // Trans. IEEE 1972, vol. C-21- P.848-857.

23. Besslich Ph.W. and Riege M.W. An Efficient Program for Logic Synthesis of Mod-2 Sum Expressions / / Proc. EU-ROASIC, Paris, France, 1991.- P. 136-141.

24. Blake A. Canonical expression in Boolean algebra. Dissertation// Chicago. 1937.

25. Bochmann D. Boolean Differential Calculus — an Overview // in: Abel D., Lemmer K. Theory of discrete Systems.-Oldenbourg Verlag, 1998.- P. 161-201.

26. Brand D. and Sasao T. Minimization of AND-EXOR expressions using rewrite rules // IEEE Transactions on Computers, 1993.- No 42(5).- P.568-576.

27. Even S., Kohavi J., Paz A. On minimal modulo-2 sums of products for switching functions // IEEE Trans. Electron. Comput.- 1967.- V.16, No 10.- P.671-674.

28. Dorotska C, Steinbach B. Orthogonal block building using ordered lists of ternary vectors // 4th International Workshop on Boolean Problems. Freiberg, Germany, 2000.-P.125-133.

29. Karnaugh M. The map method for synthesis of combinational logic circuits // Trans. Amer. Inst. E;ectr. Engrs, 1953, 72. P. 593-599.

30. 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 Expantion Application in Circuit Design, Japan, 1995, P.94-101.

31. Koda N., Sasao T. LP characteristic vector of logic functions// IFIP wg 10.5. Workshop on Application of the Reed-Muller Expantion Application in Circuit Design, 1993.

32. McCluskey E.J. Minimization of Boolean functions. Bell Syst. Techn. J. 1956, 35. P. 1417-1444.

33. Muller D.E. Application of Boollean algebra to switching circuit desing and error detection// IEEE Trans. Electron. Comput.- 1954.- V.3, No 3.- P. 6-12.

34. Nelson R.J. Simplest normal truth functions. //J, Symbol. Logic., 1955, 20 P. 105-108.

35. Perkowski M.A. A Fundamental Theorem for Exor Circuits // Proc. RM'93 P.52-60.

36. Quine W.V. A way to simplify truth functions. // Amer. Math. Mon, 1955, 62, P.627-631.

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

38. Sasao T. Input variable assignment and output phase optimization of PLA's // IEEE Trans. Comput., 1984.- Vol. C-33, No. 10.- P.879-894.

39. Sasao Т., Besslich P. On the complexity of mod-2 sum PLA's// IEEE Trans, on Comput.- 1990.- V. 39, No 2.-P. 262-266.

40. Sasao T. (editor) Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993 320 p.

41. Sasao T. AND-EXOR expressions and their Optimization //in: Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993.- P. 289-300.

42. Sasao T. Represeintation of Logic Functions using EXOR Operators // Proc. IFIP WG 10.5 Workshop on Applic. of the Reed Muller Expansion in Circuit Design.- Tokyo, 1995.- P. 11-20.

43. Sasao T. (editor) Logic Synthesis and Optimization. Kluwer Academic Publishers.- 1993.- 320 p.

44. Sasao T. Switching Theory for Logic Synthesis.- Kluwer Academic Publishers.- 1999.- 355 p.

45. Saul J.M., Eschermann B. and Juergen Froessl. Two-level logic circuits using EXOR sums of products // Combinational networks, 1993. In IEE Proceedings Part E, Computers and Digital Techniques U0(6).- P.348-356.

46. Saul J.M. An efficient data structure for the minimization of EXOR sums. IFIP WG10.5 Workshop on Applicationsof the Reed-Muller Expansion in Circuit Design, 1995 P. 116-121.

47. Svoboda A., Ordering of implicants. IEEE Trans., 1967, EC-16, No.l.- P. 100-105.

48. Veitch E.W. A chat method for simplifying truth functions // Proc. Assoc. Сотр. Machinery, 1952, P. 127-133.

49. Wu X., Chen X. and Hurst S.L. Mapping of Reed-Muller Coefficients and the Minimization of Exclusive-OR Switching Functions // IEE Proc.- 1982.- vol.129, No.l.- P.5-20.

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

51. Винокуров С.Ф., Гайдуков А.И. Класс стягиваемых булевых функций // XII Международная конференция по математической логике. Тезисы докладов.- Новосибирск, 1994.- С. 38-39.

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

53. Винокуров С.Ф., Гайдуков А.И., Корсуков А.В. Автоматизированная система для исследования булевых функций // Тезисы докл. Международной конференции "Автоматизация проектирования дискретных систем".-Минск, 1995.- С. 55.

54. Винокуров С.Ф., Гайдуков А.И. BOOLEARN — система для работы с булевыми функциями // Международная конференция по прикладной логике: Тезисы док ладов.-Иркутск, 1995.- С. 17-18.

55. Гайдуков А.И. О некоторых свойствах стягиваемых булевых функций //В кн.: Природные ресурсы, экология и социальная среда Прибайкалья. Том 3. Иркутск, 1995. - С.229-232.

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

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

58. Гайдуков А.И. Алгоритм нахождения всех самых сложных булевых функций в классе п.н.ф. // Труды122 —12.ой Байкальской международной конференции, Том 5, Иркутск, 2001.- С.37-42.

59. Балюк А.С., Винокуров С.Ф., Гайдуков А.И., Зубков О.В., Кириченко К.Д., Пантелеев В.И., Перязев Н.А., Перязева Ю.В. Избранные вопросы теории булевых функций // Под ред. Винокурова С.Ф. и Перязева Н.А.-М.: ФИЗМАТЛИТ, 2001.- 192 е.- ISBN 5-9221-0085-8.

60. Гайдуков А.И. Построение сокращенной дизъюнктивной нормальной формы по полурешетке минимумов / / Иркутский ун-тет. Серия: Дискретная математика и информатика. Вып. 16. Иркутск, 2002. - 28 с.