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

• Семичева, Наталия Леонидовна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Семичева, Наталия Леонидовна

Введение

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

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

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

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

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

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

Глава 3. Бесповторное представление недоопределенных частичных булевых функций

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

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

Введение диссертации (часть автореферата) на тему «Методы нахождения бесповторных представлений не всюду определенных булевых функций»

Теория конечных функций образует одно из главных направлений исследований в дискретной математике. И особое место здесь занимает теория булевых функций, как основной инструмент при разработке математических моделей цифровой техники. Из различных способов задания булевых функций основным является представление их с помощью суперпозиции выделенных базисных функций. Такое представление называют формульным или термальным. Большое распространение оно получило за счет того, что представление функций термами над заданным базисным множеством являетя основным этапом при проектировании дискретных устройств [10, 11, 62, 63].

Прежде чем приступить к представлению функции термом, надо выбрать набор функций, которые можно использовать при этом представлении. Причем, если некоторый набор подходит для задания любой булевой функции, он называется базисом. Основополагающим в данной области был результат Э. Поста об описании всех порожденных с помощью суперпозиции классов (замкнутых классов) булевых функций [60, 61]. Существуют более короткие доказательства этого результата, например, [45, 19, 49]. О базовых результатах, касающихся формульных представлений функций, можно узнать из [1, 18, 33, 48, 50].

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

Со сложностью представления булевых функций термами связано понятие бесповторности. Бесповторными называются функции, которые можно представить термом, каждая переменная в который входит не более одного раза. Такие функции обладают наименьшей сложностью, если под сложностью понимать количество вхождений переменных в терм. В работе А. В. Кузнецова [16] было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. В. JI. Артю-хов, Г. А. Копейкин, А. Шалыто [4] показали, что бесповторные функции преобладают при описании работы цифровых вычислительных машин.

С другой стороны, при исследовании слабоповторпых функций (повторных булевых функций в некотором базисе J5, у которых все собственные остаточные подфункции являются бесповторными в В) было показано, что добавление слабоповторной в базисе В функции к этому базису, существенно увеличивает число бесповторных функций [?].

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

Существуют разные подходы к описанию бесповторных предстале-ний булевых функций. Начало одному из подходов положил В. А. Гур-вич [12, 13] Его теорема явилась началом, так скажем, «графического» подхода к нахождению бесповторного представления булевых функций и развивалась в основном на западе. Первый шаг в этом направлении сделал сам В. А. Гурвич [12]. Затем J. P. Hayes [56] разработал алгоритм распознавания бесповторности булевых функций и получения самого такого представления на основе связности переменных. Но предложенный им алгоритм имел слишком большую сложность. Затем J. Peer и R.Pinter [59] улучшили его результат. Но алгоритм все равно имел более чем полиномиальную сложность в следствие необходимости перевода ДНФ в КНФ и обратно. М. С. Golumbic, A. Mintz и U. Rotics [54, 55] нашли способ преодалеть этот барьер. Преложенный ими алгоритм базируется на свойствах кографа, двойственных фукциях и теореме Гурвича. Данный алгоритм находит бесповторное представление функции за полиномиальное время. Параллельно с ними почти аналогичный алгоритм предложили D. Angluin, L. Hellerstein и М. Karpinsky [51]. Сложностью при использовании последних двух алгоритмов связана с тем, что на вход должна подаваться функция в форме сокращеной ДНФ или КНФ.

Другой подход, основанный на результатах А.В.Кузнецова [16] и Г.Н.Поворова [40], о представлении функции в виде суперпозиции двух неунарных функций с непересекающимися множествами переменных. Так как для построения излагаемых в данной работе алгоритмов выбран именно этот подход, основные определения и теоремы, связанные с ним, будут изложены ниже. Важно отметить, что первый подход позволяет находить бесповторное представление функций только в элементарном базисе. А учитывая, что функциональный элемент «исключаючее или» приобретает все большее распространение в связи с тем, что его использование в большинстве случаев приводит к получению термов с меньшей сожностью, первый подход становится менее актуальным.

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

А. А. Вороненко [6, 8, 5, 7, 9] разработал алгоритм линейной сложности для распознавания бесповторности всюду определенных булевых функции в любом наследственном базисе.

Большое практическое значение имеют функции, определенные не на всех наборах значений переменных. Как правило, на тех наборах, на которых значение функции не определено, неопределенность понимается как возможность принятия и значения 0, и значения 1, и называются такие функции частичными булевыми функциями. Естественно, минимизировать такие функции является гораздо более сложной задачей. Например, если применять первый подход получения бесповторного представления функций к нахождению бесповторного терма, представляющего частичную функцию, нам необходимо будет выполнить следующие действия: 1) подставить конкретные значения на те позиции, где функция неопределена; 2) найти сокращенную ДНФ этой функции; 3) применить алгоритм; 4) если бесповторное представление не будет найдено, повторить действия с 1-ого по 4-ое. Учитывая, что таких подстановок может быть 2к, где к — число позиций, в которых функция неопределена, тогда время, необходимое на исследование функции на бесповторность, может значительно возрасти.

Поэтому разрабатываются алгоритмы минимизации, применимые конкретно к частичным функциям [2]. В некоторых случаях сужают исходную задачу ввиду высокой алгоритмической сложности ее решения в общем виде. Я. Хлавичка и П. Фишер [57] дают алгоритм минимизации сильно неопределенных булевых функций. То есть определена функция должна быть только на 10-20 позициях. Этот алгоритм интересен тем, что одинакого быстро справляется с поставлнной задачей как для функций, зависящих от 10 переменных, так и для функций, зависящих от 100 переменных. Но, к сожалению, он абсолютно неприменим для решения задачи в общем случае. Еще один частный случай решения задачи представления частичных булевых функций термами рассмотрен в работах Е. Boros, V. Gurvich, P.L. Hammer [52], решающий вопрос о представлении частичной функции термами с заданной структурой. То есть они отвечают за полиномиальное время, например, на такой вопрос: можно ли представить функцию / термом вида / = g(hi(Si), /12(^2), -S3), где Si, S2, S3 также являются термами? К сожалению, при этом не находятся термы Si, S2, S3.

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

Далее рассмотривается другой вид не всюду определенных функций, так называемых частичных недоопределенных булевых функций. Эти функции рассматривались в [17, 22, 23, 25, 34, 35, 36, 37, 38, 39]. Первый вид неопределенности совпадает по смыслу с описанным ранее и называетя «недоопределено». Второй вид неопределенности возникает, когда набор а отображается в пустое множество. То есть функция не принимает на данном наборе никакого значения, или принимает запрещенное значение. Такой вид неопределенности будет называться «частично». Так как при работе дискретных устройств возникает и тот и другой вид неопределенности [17], поэтому актуальной задачей является исследование таких функций.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Семичева, Наталия Леонидовна

Заключение

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

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

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

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

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

Работа над диссертацией была поддержана Российским фондом фундаментального исследования, проект 07-01-00240.

Список литературы диссертационного исследования кандидат физико-математических наук Семичева, Наталия Леонидовна, 2008 год

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

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

3. Алексеев В. Б. О некоторых замкнутых классах в частичной двузначной логике/В. Б. Алексеев, А. А. Вороненко // Дикретная математика. — 1994. — Том 6. Вым. 4, — С. 58-79.

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

5. Вороненко А. А. Бесповторность распознается схемами линейной сложности / А. А. Вороненко. // Дискретная математика. — 2005. — Том 17. Вып. 4. С. 111-115.

6. Вороненко А. А. О методе разложения для распознавания принадлежности инвариантным классам / А. А. Вороненко. // Дискретная математика. 2002. - Том 14. №4. - С. 110-116.

7. Вороненко А. А. Распознавание бесповторности в произвольном базисе / А. А. Вороненко. // Прикладная математика и информатика. М.: Макс-Пресс, 2006. — Вып. 23. - С. 67-84.

8. Вороненко А. А. Бесповторность распознается схемами линейной сложности / А. А. Вороненко. // Труды VI международной конференции <Дискретные модели в теории управляющих систем». — М.: ВМиК МГУ. 2004. - С. 25-26.

9. Вороненко А. А. Бесповторные булевы функции/ А. А. Вороненко. — М.: Макс-Пресс, 2006. — 61 с.

10. Глушков В. И. Синтез цифровых автоматов / В. И. Глушков. — М: Физматлит, 1962. — 476 с.

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

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

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

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

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

16. Ложкин С. А. О синтезе формул и схем из не всюду определенных функциональных элементов / С. А. Ложкин // Труды VI международной конференции «Дискретные модели в теории управляющих систем». М.: ВМиК МГУ. - 2004. - С. 44-47.

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

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

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

20. Пантелеев В. И. Обобщенная интерпретация переменных: семантическое исследование и логический вывод / Н. А. Перязев , В. И. Пантелеев // Материалы школы «Пятая школа моложых математиков Сибири и Дальнего Востока». — Новосибирск, 1990. — С. 87-89.

21. Пантелеев В. И. Недоопределенные частичные булевы функции и булевы уравнения / Н. А. Перязев , В. И. Пантелеев // Материалы VII Международной конференци «Дискретные модели в теории управляющих систем». — М.: ВМиК МГУ, 2006. С. 262-265.

22. Пантелеев В.И. О недоопределенных булевых функциях / В. И. Пантелеев // Материалы школы-семинара «Синтаксис и семантика логических систем». — Иркутск, 2006. С. 78-79.

23. Пантелеев В. И. Логика предикатов при обобщенной интерпретации переменных / Н. А. Перязев, В. И. Пантелеев // Вестнике БГУ. Серии 13: Математика и информатика. — 2005. — Вып. 2. — Улан-Уде. С. 39-45.

24. Пантелеев В.И. Клоны недоопределенных частичных булевых функций / В. И. Пантелеев // Материалы российской школы-семинара «Синтаксис и семантика логических схем». — Владивосток, 2008. — С. 42-43.

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

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

27. Перязев Н. А. Алгебраическая характеризация бесповторных булевых функций в некоторых базисах / Н. А. Перязев // Материалы III Международной по алгебре. — Красноярск, 1993. С. 260.

28. Перязев Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Методы и системы технической диагностики. —1993. Вып. 18. - Красноярск. - С. 138-139.

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

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

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

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

33. Перязев Н. А. О недоопределенных булевых функциях Н. А. Перязев. // Материалы школы-семинара «Синтаксис и семантика логических систем». — Иркутск, 2006. С. 80-81.

34. Перязев Н.А. Алгебра не всюду определенных функций / Н. А. Перязев. // Труды международной конференци «Алгебра и ее приложения>". — Красноярск, 2007. — С. 104.

35. Перязев Н.А. Функциональные системы недоопределенных частичных функций / Н. А. Перязев. // Материалы Международного семинара «Дискретная математика и ее приложения>". — М.: Изд-во ММФ МГУ, 2007. - С. 173-174.

36. Перязев Н. А. Недоопределенные частичные булевы функции / Н. А. Перязев. // Материалы XV международной конференции «Проблемы теоретической кибернетики». — Казань, 2008. — С. 92.

37. Перязев Н. А. Суперклоны недоопределенных частичных функций / Н. А. Перязев. // Материалы российской школы-семинара «Синтаксис и семантика логических схем». — Владивосток, 2008. — С. 40-42.

38. Поваров Г. Н. О функциональной разрешимости булевых функций / Г. Н. Поваров// Докл. АН СССР. 1954. - Т. 94, № 5. - С. 801-803.

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

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

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

42. Сэвидж Д. Э. Сложность вычислений / Д. Э. Сэвидж — М.: <Факториал», 1998. — 368 с.

43. Угольников А. Б. Класс Поста. Учебное пособие / А. Б. Угольников М.: Издательство ЦПИ при ММФ МГУ, 2008. — 64 с.

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

45. Шоломов JI. А. Основы теории дискретных логических и вычислительных устройств / J1. А. Шоломов // М.: Наука, 1980. — 400 с.

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

47. Яблонский С. В. Функции алгебры логики и классы Поста / С. В. Яблонский, Г. П. Гаврилов, В. Б. Кудрявцев. — М.: Наука, 1966. — 120 с.

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

49. Angluin D. Learning read-once formulas with queries / D. Angluin, L. Hellerstein, M. Karpinski // University of California at Berkeley. — 1989.

50. Boros E. Decomposition of partially defined boolean functions/ E. Boros, V. Gurvich, P.L. Hammer // Special volume on partitioning and decomposition in combinatorial optimization — 1995. — P.51-75.

51. Brayton R. The decomposition and factorization of boolean expressions / R. Brayton, C. McMullen // Proc. Internat. Symp. on Circuits and System. — Rome, 1982. — P. 49-54.

52. Golumbic M. Factoring and recognition of read-once functions using cographs and normality / M. Golumbic, A. Mintz, U. Rotics // 38th conference on Design automation. — Las Vegas. — 2001. — P. 109114.

53. Golumbic M. Factoring logic functions using graph partitioning / M.LGolumbic, A. Mintz // International Conference of Computer^ Aided Design. — 1999. — P. 1995.

54. Hayes J. P. The fanout structure of switching functions / J. P. Hayes // Journal of the ACM. — 1975. — P. 551-571.

55. Hlavicka J. Algorithm for minimization of partial functions / J. Hlav-icka, P. Fiser // Design and Diagnostics of Electronic Circuits and Systems Workshop — Bratislava. — 2000. — P. 130-133

56. Newman I. On read-once booleanfunctions /I. Newman // London mathematical society simposiam on Boolean function complexity. — London, 1968. — P. 175-188.

57. Peer J. Minimal decomposition of boolean functins using nonrepeating literal trees / J. Peer, R, Pinter // Workshop on Logic and Architecture Synthesis. — Grenoble, 1995. — P. 129-139.

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

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

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

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

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

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

64. Коршунова H.J1. (Семичева Н. J1.) Представление частичных булевых функций бесповторными термами над бинарным базисом / Н. JI. Коршунова // Вестник ВГУ. Серия 13: Математика и информатика. 2005. - Вып.2. — С. 26-35.

65. Семичева Н. JI. Бесповторное предсталение недоопределенных частичных булевых функций /Н. JI. Семичева // Материалы XV международной конференции «Проблемы теоретической кибернетики». — Казань, 2008. С. 105.

66. Семичева Н. J1. Представление недоопределенных частичных булевых функций бесповторными термами/Н. JI. Семичева // Материалы российской школы-семинара «Синтаксис и семантика логических схем». — Владивосток, 2008. С. 45-47.

67. Семичева Н. J1. Нахождение бесповторных представлений недоопределенных частичных булевых функций/Н. Л. Семичева. — — Иркутский государственный педагогический университет. Серия: Дискретная математика и информатика. Вып. 19. — Иркутск, 2008. — 35 с.