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

ВВЕДЕНИЕ

ГЛАВА I. ОБЩАЯ ЧАСТЬ. СЛОЖНОСТЬ И ОТНОСИТЕЛЬНАЯ СЛОЖНОСТЬ

Д.Н.Ф. ЧАСТИЧНЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ . II

§ I. Определения и обозначения .II

§ 2. Соотношение между параметрами всюду оцределенных и частичных булевых функции

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

§ 4. Относительная сложность однозначно определяемых д.н.ф.

§ 4.1. Относительная сложность сокращенной д.н.ф.

§ 4.2. Относительная сложность д.н.ф. Квайна • •

§ 4.3. Относительная сложность д.н.ф. суммы тупиковых

§ 4.4. Относительная сложность д.н.ф., получаемой ^ -алгоритмом

§ 4.5. Относительная сложность д.н.ф. суммы

- минимальных

Проблеме минимизации функции алгебры логики в классе дизъюнктивных нормальных форм (д.н.ф.) посвящено большое число работ, среди которых широкую известность приобрели работы С.В.Яблонского, Ю.И.Еуравлева, Ю.Л.Васильева, В.В.Глаголева, А.А.Сапо-женко и др.

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

Исследованию эффективности классов алгоритмов, получающих

- однозначно определяемую д.н.ф. jjE3, 44] ,

- произвольную тупиковую д.н.ф.,

- минимальную в некотором смысле д.н.ф. всюду определенной булевой функции посвящен целый ряд работ (обзор по ним см., например, в [i, 39]), в которых для получения оценок разработаны довольно тонкие конструкции. Тем не менее, для многих параметров, характеризующих эффективность применения алгоритмов, не удалось получить окончательных результатов.

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

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

- алгоритмы, использующие на некотором этапе упрощения, акт удаления несущественных переменных;

- алгоритмы, выделяющие в результирующую д.н.ф. простых имп-ликантов минимального ранга;

- алгоритмы типа градиентного.

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

В главе I приводятся основные понятия и определения (§1), используемые в последующих главах. Показано, что значение некоторых параметров, определенных на множестве частичных и всюду определенных булевых функций, совпадают (§2). Исходя из этого факта и результатов, полученных А.П.Викулиным [4] , В.В.Глаголевым [б] и О.Б.Лупановым [зо] , выводятся оценки максимальных значений сложности д.н.ф., однозначно определяемых при минимизации булевых функций, а также оценки минимальной и максимальной сложности тупиковых д.н.ф. (§ 3).

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

Рис. I

Aju - алгоритм представляет собой модификацию А - алгоритма ( А^ - алгоритма, по новым обозначениям) Ю.И.Куравлева. ций, были рассмотрены в [25-28]. А.С.Федоровым (дипломная работа, выполненная в МГУ в 1982 г.) установлено, что длина сокращенной д.н.ф. функции может в (1,5)^** ^ раз превышать длину д.н.ф. Квайна. А.А.Левиным [25] показано, что сокращенная д.н.ф. может иметь в 3 раз больше слагаемых, чем д.н.ф. суммы тупиковых (суммы кратчайших, кратчайшая д.н.ф.) той же функции. Во столько же раз может отличаться по длине сокращенная д.н.ф. функции от сокращенной д.н.ф. отрицания этой же функции [2б]. Далее, в [27] установлено, что д.н.ф. суммы тупиковых, в свою очередь, сИ>(1-£) , д может быть в 3 раз сложнее, чем д.н.ф., получаемая А ^-алгоритмом Ю.И.Журавлева [12, 13] (д.н.ф. суммы минимальных, минимальная д.н.ф.) данной функции. Наконец, в работе [28] получено, что максимально возможное значение отношения длины д.н.ф. суммы кратчайших к длине кратчайшей д.н.ф. функции находятся в пределах от 2 до $

§ 4 главы I посвящен исследованию аналогичных вопросов для множества частичных булевых функций. Получены порядок роста относительной сложности сокращенной д.н.ф., д.н.ф. Квайна и д.н.ф. суммы тупиковых. Рассмотрены также вопросы относительной сложности д.н.ф., получаемой А^ -алгоритмом и д.н.ф. суммы минимальных. Оценки установлены для произвольных линейных мер сложности (м.с.).

В [2] Ю.Л.Васильевым рассматривались соотношения между длинами и сложностями тупиковых д.н.ф., реализующих одну и ту же всюду определенную булеву функцию. Было показано, что максимальное значение отношения длин (сложности) двух различных тупиковых д.н.ф. булевой функции равно 2^^ ^ . Аналогичная оценка имеет место при рассмотрении произвольных линейных м.с. [з] . В § 5 главы I эти вопросы получили асимптотически окончательные реше

- 8 ния для множества частичных булевых функций.

Гипотеза о том, что среди кратчайших д.н.ф. функции алгебры логики содержится хотя бы одна минимальная д.н.ф. той же функции, была опровергнута Ю.И.Журавлевым [14] . Вопрос о взаимоотношении между сложностями минимальных и кратчайших д.н.ф. для всюду определенных булевых функций был рассмотрен Лин Син-ляном [29] . К.Вебером [з] была обобщена м.с. для д.н.ф. всюду определенных булевых функций и установлено возможное различие при замене минимальной в некотором смысле д.н.ф. на д.н.ф., минимальную в другом смысле. В главе 2 эти вопросы исследуются для множества частичных булевых функций. Дня всех рассмотренных параметров получены окончательные результаты.

Во многих работах, посвященных минимизации частичных булевых функций, предлагается в качестве одного из этапов проводить исключение несущественных переменных. Такой этап представляется на первый взгляд вполне естественным и целесообразным, особенно, если речь идет о минимизации частичных функций, зависящих от большого числа переменных. В практике часто ставится вопрос о минимизации числа входов схемы. Однако Ю.И.Журавлевым [1б] было отмечено, что уменьшение числа элементов исходной совокупности переменных частичной функции может привести к усложнению д.н.ф. .получаемой в результате. В § I главы 3 этот эффект исследуется с количественной стороны. Именно: решается вопрос о максимальном значении отношения сложностей (длин) двух тупиковых д.н.ф. частичной функции, одна из которых зависит лишь от части переменных второй тупиковой д.н.ф. Показано, что максимальное (на множестве частичных булевых функций от ии переменных) значение отношения сложив И/ — 2* ностей (длин) асимптотически равно 2 (соответственно 2 ).

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

В этом же параграфе исследуются алгоритмы упрощения частичных булевых функций [б, 8-II, 36, 45] , использующие в качестве элементарных актов операцию исключения несущественных переменных. На примере алгоритма Акерса [45] показано, что использование этой операции приводит к д.н.ф., существенно (экспоненциально) отличающейся от кратчайшей (минимальной).

§ 2 главы 3 посвящен анализу эффективности применения другого класса приближенных алгоритмов упрощения частичных булевых функций, предложенных в работах [l7, 24, 32, Зб]. Общность этих алгоритмов заключается в том, что на некотором этапе в результирующую д.н.ф. включаются такие простые импликанты функции, которые имеют минимальный ранг. Показано, что д.н.ф., получаемые в результате применения этих алгоритмов, могут быть нетупиковыми и иметь экспоненциальную длину (сложность), несмотря на то, что некоторая конъюнкция, входящая в нее, реализует исходную функцию.

Для приближенного решения задачи построения тестов С.В.Яблонским [43] был предложен метод, который обычно называют градиентным или методом наискорейшего спуска. А.А.Сапоженко [37, 38] установил верхнюю оценку сложности д.н.ф., получаемых с помощью градиентного алгоритма для почти всех всюду определенных булевых функций. Из этого результата, в частности, вытекает, что для почти всех всюду определенных булевых функций, градиентным алгоритмом можно получить д.н.ф., отличающуюся по длине (по сложности) от кратчайшей (минимальной) не более, чем в •раз*

Аналогичная оценка для отношения длин д.н.ф., получаемой градиентным алгоритмом к длине вдатчайшей д.н.ф., независимо,выведена Р.Г.Нигматулиным [31].

В главе 4 рассматриваются вопросы эффективности градиентного алгоритма, а также алгоритмов типа градиентного [7, 16, 33, 34, 46] (т.е. алгоритмов, в которые градиентный алгоритм входит как основной этап). Показано, что в результате применения этих алгоритмов к построенным в работе частичным функциям, получается д.н.ф., которая отличается от минимальной в некотором смысле д.н.ф. в полиномиальное (от числа переменных И/ ) число раз. Используя результат, полученный в [3l] , доказано, что возможное значение отношения сложности д.н.ф., получаемой градиентным алгоритмом, к сложности оптимальной д.н.ф. не превышает полинома (от W ).

Основные результаты диссертации опубликованы в [18-23], [40-427.

Автор считает своим приятным долгом выразить благодарность своему научному руководителю, доценту А.А.Сапоженко за постоянное внимание и большую подщержку при выполнении работы.

ЗАКЛЮЧЕНИЕ Основные результаты, полученные в диссертационной работе, состоят в следующем:

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

- установлены порядок роста максимального значения относительной сложности сокращенной д.н.ф., д.н.ф. Квайна, д.н.ф.суммы тупиковых, а также оценки относительной сложности д.н.ф.получаемой Aju-алгоритмом и д.н.ф., суммы минимальных в некотором смысле д.н.ф.;

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

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

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

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

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

- 114 отличие является максимально возможным.

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

И/

Сравнительно высокая нижняя оценка (3 £ ) относительной сложности сокращенной д.н.ф., д.н.ф. Квайна и д.н.ф. суммы тупиковых по отношению к нижней оценке ( X /Ль £ ) относительной сложности д.н.ф., получаемой А -алгоритмом, а также долгое отсутствие успеха в попытках увеличить последнюю нижнюю оценку, говорят в пользу А -алгоритма.

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

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

Результаты, полученные в диссертации, докладывались на конференциях молодых ученых факультета ВМиК МГУ (Москва, 1980,1981,

1982 гг.), на Пятой (Новосибирск, 1980 г.) и Шестой (Саратов,

1983 г.) Всесоюзных конференциях по проблемам теоретической кибернетики, на семинарах кафедры математической кибернетики факультета ВМиК МГУ, ИМ СО АН СССР и НИВЦ МГУ.

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

2. Васильев Ю.Л. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм. В сб.: Проблемы кибернетики, вып. 10. М.: Физматгиз, 1963, с. 5-61.

3. Вебер К. О различных понятиях минимальности дизъюнктивных нормальных форм. В сб.: Проблемы кибернетики, вып.36. М.: Наука, 1979, с.129-158.

4. Викулин А.П. Оценка числа конъюнкций в сокращенной д.н.ф. -В сб.: Проблемы кибернетики, вып. 29. М.: Наука, 1974,с.151-166.

5. Гаврилов И.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. М.:Наука, 1977. - 351 с.

6. Глаголев В.В. О длине тупиковой д.н.ф. Математические заметки, 1967, т.2, № 6, с.665-672.

7. Горбатов В.А., Демьянов В.Ф. Частично минимальный алгоритм покрытия булевых матриц. В кн.: Оптимизация дискретных систем управления. М.: ГВЦ Госплана СССР, 1972, с.48-57.

8. Гриншпон М.С. Критерий выбора потенциально несущественного аргумента, исключаемого из неполностью определенной логической функции,-Автоматика и вычислительная техника, 1975, № 5, с. 17-21.

9. Диденко В.П. К построению частичных минимальных нормальных форм булевых функций. В кн. Логический язык для представления алгоритмов синтеза релейных устройств. М.: Наука, 1966, с. 194-203.- 117

10. Диденко В.П., Окуджава В.Ш. Алгоритм получения скобочных форм булевых функций. В кн.: Логический язык для представления алгоритмов синтеза релейных устройств. М.: Наука, 1966, с. 204-211.

11. Диденко В.П., Покудин К.Н. О выделении не обязательных переменных в узловых таблицах состояний. В кн.: Программное управление на внутрихозяйственной оросительной сети. Фрун-зе:ИЛИМ, 1971, с. 82-93.

12. Журавлев Ю.И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функции алгебры логики. В кн.: Дискретная математика и математические вопросы кибернетики, т.1. М.: Наука, 1974, с. 67-98.

13. Журавлев Ю.И. Теоретико-множественные методы алгебры логики. В сб.: Проблемы кибернетики, вып.8. М.: Физматгиз, 1962, с. 5-44.

14. Журавлев Ю.И. 0 различных понятиях минимальности дизъюнктивных нормальных форм. Сибирский математический журнал, I960, т.1, № 4, с. 608-609.

15. Журавлев Ю.И. Об отделимости подмножеств вершин ^-мерного единичного куба. Труды ГЛИАН СССР, 1958, т.51,с.143-157.

16. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. -М.: Наука, 1971. 512 с.

17. Казаков В.Д. Минимизация логических функций большого числа переменных. Автоматика и телемеханика, 1962, т.23, № 9, с. 1237-1242.

18. Караханян Л.М., Сапоженко А.А. Оценки параметров не всюду определенных (частичных) функций алгебры логики. В сб.:- 118

19. Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во 1ТУ, 1979, с. 48-56.

20. Караханян JI.M. Относительная сложность однозначно определяемых д.н.ф. частичных функций алгебры логики. В сб.: Оптимизация и управления. М.: Изд-во МГУ, 1983, с. 85-97.

21. Караханян Л.М. Об относительной эффективности градиентного алгоритма минимизации частичных булевых функций. В сб.: Математическое обеспечение автоматизированных информационных систем. М.: Изд-во МГУ, 1984, с. 97-116.

22. Караханян Л.М. Метрическое сравнение минимальных в различном смысле д.н.ф. частичных функций алгебры логики. В сб.: Методы дискретного анализа в оценках сложности управляющих систем, вып. 38. Новосибирск: ИМ СО АН СССР, 1982, с.19-36.

23. Караханян Л.М. Сравнение минимальных в различном смысле д.н.ф. В сб.: Некоторые вопросы прикладной математики и программного обеспечения ЭВМ. М.: Изд-во МГУ,1982, с.59-60.

24. Караханян Л.М. Об эффективности выделения простых импликан-тов минимального ранга. В сб.: Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во 1ТУ, 1982, с. 66-75.

25. Кирюхин В.В. Способ минимизации булевых функций и его программирование для универсальной цифровой вычислительной машины "Урал". Проблемы передачи информации, 1962, вып.II, с. 57-65.

26. Левин А.А. Об относительной сложности сокращенной д.н.ф. -В сб.: Дискретный анализ, вып. 15. Новосибирск: ИГЛ СО АН СССР, 1969, с. 25-34.

27. Левин А.А. Об отношении сложности д.н.ф. функции к сложности д.н.ф. ее.отрицания. В сб.: Дискретный анализ, вып.16.- 119

28. Новосибирск: ИМ СО АН СССР, 1970, с.77-81.

29. Левин А.А. Сложность д.н.ф. суммы тупиковых относительно д.н.ф. суммы минимальных. В сб.: Дискретный анализ, вып. 24. Новосибирск: ИМ СО АН СССР, 1974, с. 50-68.

30. Левин А.А. Сравнительная сложность д.н.ф. В сб.: Методы дискретного анализа в исследовании функциональных систем, вып. 36. Новосибирск: ИМ СО АН СССР, 1981, с. 23-38.

31. Лин Син-лян. О сравнении сложностей минимальных и кратчайших дизъюнктивных нормальных форм. В сб.: Проблемы кибернетики, вып. 18. М.: Наука, 1967, с.П-44.

32. Лупанов О.Б. 0 реализации функции алгебры логики формулами из конечных классов (формулами ограниченной глубины) в базисе "И", "ИЛИ", "НЕ". В сб.: Проблемы кибернетики, вып. 6. М.: Физматгиз, 1961, с. 5-14.

33. Нигматулин Г.Г. Методы наискорейшего спуска в задачах на покрытие. В сб.: Вопросы точности и эффективности алгоритмов (труды симпозиума), вып.5. Киев, 1969, с. II6-I26.

34. Новоселев В.Г. Приближенный метод минимизации слабоопределенных булевых функций. Труды Сиб. физико-техн. ин-та, вып. 44. Томск, 1966, с. 24-30.

35. Новоселов В.Г. Приближенный метод минимизации слабоопределенных булевых функций. Труды Сиб. физико-техн. ин-та, вып. 48, Томск, 1966, с. 104-107.

36. Новоселов В.Г. Приближенный метод минимизации булевых функций, заданных в матричной форме. Труды Сиб. физико-техн. ин-та, вып. 48. Томск, 1966, с. 120-125.

37. Новоселов В.Г., Кирюхин В.В. Метод минимизации булевых функций и их программирование на УЦВМ. В кн.: Международный симпозиум по теории релейных устройств и конечных автоматов.

38. Москва, 1962. Синтез релейных структур» т.2. М.: Наука, 1965, с. 371-377.

39. Першеев В.Г. Минимизация булевых функций большого числа переменных. Труды Московского ин-та инженеров железнодорожного транспорта, вып. 367, 1970, с. 293-299.

40. Сапоженко А. А. Об одном доказательстве верхней оценки сложности минимальных д.н.ф. для почти всех функций. Первая Всесоюзная конференция по проблемам теоретической кибернетики (тезисы докладов). Новосибирск: ИМ СО АН СССР, 1969,с.103.

41. Сапоженко А.А. 0 сложности дизъюнктивных нормальных форм,получаемых с помощью градиентного алгоритма. В сб.: Дискретный анализ, вып. 21. Новосибирск: ИМ СО АН СССР, 1972, с. 6271.

42. Сапоженко А.А. Дизъюнктивные нормальные формы (метрическая теория). М.: Изд-во МГУ, 1975. - 90 с.

43. Сапоженко А.А., Караханян JI.M. Об отношении сложностей и длин д.н.ф. частичных булевых функций. В сб.: Прикладная математика и математическое обеспечение ЭВМ. М.: Изд-во МГУ, 1980, с. 52-53.

44. Сапоженко А.А. Караханян Л.М. О некоторых характеристиках д.н.ф. частичных булевых функций. Пятая Всесоюзная конференция по проблемам теоретической кибернетики (тезисы докладов). Новосибирск: ИМ СО АН СССР, 1980, с. 173-175.

45. Сапоженко А.А., Караханян Л.М. Об отрицательных эффектах, связанных с исключением несущественных переменных.-Автомати-ка и вычислительная техника, 1981, 3, с. 28-35.

46. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем. Труды МИАЕ СССР, 1958, т.51, с.270-360.

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

48. Akers S.B., A truth table method for the synthesis of combinational logic, IRE Trans., 1961, vol, EC-10, U 4, p.604-615.

49. Bowman R.M., McVey E.S., A method for the fast approximate solation of lorge prime implicants charts. IEEE Trans, on Computers, February 1970, vol. C-19, N 2, p. 169-173.

50. Quine ?/.V. , On cores and prime implicants of truth functions. Amer. Math. Monthly, 1959, vol. 66, N 9, p. 755-760.