Помощь в учёбе, очень быстро...
Работаем вместе до победы

Нахождение, оценка и сравнение числа бесповторных булевых функций в различных базисах

ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава I. Основные понятия и результаты
    • 1. Основные понятия и терминология
    • 2. Обзор результатов по бесповторным булевым функциям
  • Глава II. Количество бесповторных булевых функций в бинарных базисах
    • 3. Нерекуррентная формула для числа бесповторных булевых функций в элементарном базисе
    • 4. Связь между числом бесповторных функций в элементарном базисе и числами Эйлера второго порядка
    • 5. Оценки числа бесповторных булевых функций в элементарном базисе
    • 6. Нерекуррентная формула для числа бесповторных булевых функций в линейном бинарном базисе
    • 7. Оценки числа бесповторных булевых функций в линейном бинарном базисе".'.-.-.,
    • 8. Сравнение числа бесповторных булевых функций в бинарных базисах
  • Глава III. Количество бесповторных булевых функций в произвольных базисах
    • 9. Рекуррентная формула для числа бесповторных булевых функций в Нелинейном базисе
    • 10. Рекуррентная формула для числа бесповторных булевых функций в линейном базисе
    • 11. Количество бесповторных булевых функций в предэлементарных базисах
    • 12. Сравнение числа бесповторных булевых функций в различных базисах

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

Понятие функции в силу своей фундаментальности занимает одно из самых важных положений в математике. Теория дискретных функций в настоящее время является интенсивно развивающейся областью дискретной математики. Ее простейшей и вто же время значимой частью является теория булевых функций. Математические модели, описываемые на языке булевых функций, находят широкое применение в самых различных областях человеческой деятельности. В связи с этим важное значение приобретает вопрос о представлении булевых функций в виде, удобном для исследования. Традиционно, одним из таких способов является суперпозиция выделенных базисных функций. В теории булевых функций такое задание называется термальным или формульным. В соответствии с этим, большое внимание уделяется термальным представлениям булевых функций [1, 16, 28, 36, 37, 39]. Важным шагом в этом направлении является сделанное Э. Постом описание всех замкнутых классов булевых функций [46, 47].

В связи с тем, что булевы функции являются признанной моделью для проектирования схем, применяемых в электронике [7, 8, 48, 49], сформировалось направление исследований, связанное с нахождением для булевых функций представлений, имеющих наименьшую сложность. Даже для простых базисных множеств точное решение этой задачи связано с почти полным перебором [38]. В связи с быстрым ростом числа булевых функций при увеличении числа аргументов, практическое использование алгоритмов точной минимизации возможно только для функций малой размерности [12, 40]. Даже если требовать не абсолютно точной минимизации, а лишь достаточно хорошего в определенном смысле представления булевых функций в виде термов, то можно найти такое представление для функций незначительно большей размерности [4, 5, 18, 19, 20, 57].

Для произвольных полных базисов известна асимптотическая оценка сложности, полученная О. Б. Лупановым [16, 17]. Им показано, что подавляющее большинство булевых функций имеет сложность 2n/logn. Однако все известные до сих пор эффективно задающиеся последовательности булевых функций имеют лишь полиномиальные оценки сложности [2, 21, 33, 34, 41, 42, 45].

С таких позиций становятся ясными причины интереса, проявляемые к функциям, которые имеют самое простое представление в каком-либо базисе. Наименьшую сложность при термальном представлении имеют бесповторные булевы функции, то есть функции, для которых существует задание в виде терма, где каждая переменная встречается не более одного раза. И хотя, как следует из работы автора [56], бесповторных булевых функций существенно меньше, чем остальных функций, они имеют большое практическое значение. Большая часть функций, применяемых при проектировании микропроцессоров, является бесповторными в базисе, состоящем из конъюнкции, дизъюнкции и отрицания [3]. Кроме того следует отметить результат Б. А. Суббо-товской [31, 32] о том, что базис эквивалентен элементарному в смысле сложности термального задания булевых функций тогда и только тогда, когда он содержит лишь бесповторные функции в элементарном базисе. Для произвольного базиса этот результат был обобщен Д. Ю. Черухиным [35].

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

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

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

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

Слабоповторные булевы функции являются, в некотором смысле, наименьшими из повторных функций. Как следует из результата Н. А. Перязева [26] о том, что всякая слабоповторная функция является неразделимой, добавление к базису слабоповторной функции позволяет, с одной стороны, расширить его, в смысле увеличения возможностей по реализации булевых функций термами, а с другой стороны, сделать это расширение минимальным [35]. Можно так же отметить, что даже такое расширение базиса существенно увеличивает количество бесповторных в нем булевых функций [56].

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

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

Во второй части диссертации производится обобщение некоторых результатов, полученных для бинарных базисов [22, 27, 57] на произвольные базисы, в которых унарные функции реализуются бесповторно. Получены рекуррентные формулы для нахождения числа бесповторных булевых функций для базисов такого вида и как их приложение найдены формулы для нахождения количества бесповторных булевых функций во всех предэлементарных базисах, описанных В. А. Стеценко [30, 50]. Здесь же показано, что добавление к базису слабоповторной в нем функции существенно увеличивает количество бесповторных в нем булевых функций. Этот результат является обобщением доказанного в конце первой части.

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

Заключение

.

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

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

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

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

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

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

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

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

Показать весь текст

Список литературы

  1. Дискретная математика и математические вопросы кибернетики. Под редакцией Яблонского С. В. и Лупанова О. Б. М.: Наука, 1974. — Т 1. — 312 с.
  2. А. Е. Об одном методе получения более чем квадратичных эффективных нижних оценок сложности 7г-схем // Вестн. МГУ. Сер. 1. Матем.Мех. 1987. — N 1. — С. 70 — 73.
  3. В. Л., Копейкин Г. А., Шалыто А. А. Настраиваемые модули для управляющих логических устройств. -Ленинград: Энер-гоиздат, 1981. 166 с.
  4. С. Ф., Манцивода Ю. В., Перязев Н. А. Минимизация булевых функций в классах нормальных форм методом разложения // Фундаментальные проблемы математики и механики. Матматика. М.: Изд-во Московского ун-та, 1994. — С. 316 — 317.
  5. С. Ф., Гайдуков А. И., Корсуков А. В. Библиотека классов булевых функций // Сб. тр. Иркутского университета. Иркутск, 1995. -Т. 3. — С. 228 — 229.
  6. Ю. Б., Полтерович В. М. О бесповторных суперпозициях функций алгебры логики от двух переменных / / Автоматика и телемех. 1966. — С. 71 — 79.
  7. В. И. Введение в кибернетику. Киев: Изд-во АН УССР, 1964. — 324 с.
  8. Р. М., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дискретных устройств. Киев: Наукова думка, 1987. -264 с.
  9. Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики: Пер. с англ. М.: Мир, 1998. -703 с.
  10. В. А. О бесповторных булевых функциях // Успехи матем. наук. 1977. — 32, N 1. — С. 183 — 184.
  11. В. А. Критерий бесповторности функций алгебры логики // ДАН СССР. 1991. — 318, N 3. — С. 532 — 537.
  12. В. Д. О скобочных минимальных выражениях булевых функций // Duexieme Congres Mathematique Hongrois, Budapest.- 1961. V. 2.
  13. К. Д. О критериях бесповторности булевых функций в различных базисах // Оптимизация, управление, интеллект.- 2000, N 4. С. 93 — 101.
  14. К. Д. Критерий бесповторности функции алгебры логики в бинарном базисе // Международная конференция «Логика и приложения». Новосибирск. — 2000. — 57 — 58.
  15. А.В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики // Труды МИ АН СССР. Т.51.— М.: Из-во АН СССР. 1958. С.186−225.
  16. О. Б. О сложности реализаций функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. гиз, 1963. С. 61 80.
  17. О. Б. Асимптотическая оценка сложности управляющих систем. М.: Изд-во МГУ, 1984. — 137 с.
  18. Манцивода (Перязева) Ю. В. Минимизация булевых функций в классе бинарных формул // Международная Сибирская конференция по исследованию операций. Новосибирск. -1998. — С. 131.
  19. Манцивода (Перязева) Ю. В. Минимизация представлений булевых функций термами // Труды Восточно Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в ВУЗе. — Иркутск, 1999. — С. 167 — 170.
  20. Манцивода (Перязева) Ю. В. Алгоритм линейной минимизации булевых функций и его программная реализация. Иркутский университет. Серия: Дискретная математика и информатика. Вып. 9. — Иркутск, 1999. — 25 с.
  21. Р. Г. Сложность булевых функций. М.: Наука, 1991. — 240 с.
  22. Н. А. Представление функций алгебры логики бесповторными формулами // Тезисы сообщений на XI Межреспубликанской конференции по математической логике. Казань. — 1992.- С. 110.
  23. Н. А. Реализация булевых функций бесповторными формулами // Фундаментальные проблемы математики и механики. Математика. М.: Изд-во Моск. ун-та, 1994. — С. 320.
  24. П. А. Реализация булевых функций бесповторными формулами в некоторых базисах // Сб. Алгебра, логика и приложения. Иркутск, 1994. — С. 143 — 154.
  25. Н. А. Реализация булевых функций бесповторными формулами // Дискретная математика. 1995. — Т. 7, N 3. — С. 61 — 68.
  26. Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1999. — 15 с.
  27. Н. А., Разгильдеев В. Т. Число бесповторных булевых функций в бинарных базисах // Тезисы докладов на XI Международной конференции по проблемам теоретической кибернетики.- Ульяновск. 1996. — С. 161 — 162.
  28. Н. А. Основы теории булевых функций. М.: Физматлит, 1999. — 112 с.
  29. Дж. Введение в комбинаторный анализ. М.: ИЛ, 1963.- 287 с.
  30. В.А. О предплохих базисах в // Математические вопросы кибернетики. 4(1992), С. 139 — 177.
  31. . А. О реализации линейных функций формулами в базисе V, // ДАН СССР. — 1961. — Т. 136, N 3. — С. 553 — 555.
  32. . А. О сравнении базисов при реализации функций алгебры логики формулами // ДАН СССР. 1963. — Т.149, N 4.- С. 784 787.
  33. В. М. О сложности реализации линейной функции в классе П-схем // Математические заметки. -1971. Т. 9, N 1. — С. 35 — 40.
  34. В. М. О сложности реализации симметрических функций формулами // Математические заметки. -1972. Т. 11., N 1.- С. 109 120.
  35. Д. Ю. Алгоритмический критерий сравнения булевых базисов // Математические вопросы кибернетики, вып. 8 М.: Наука. Физматлит, 1999. — С. 77 — 122.
  36. К. Э. Работы по теории информации и кибернетике. М.: ИЛ., 1963. — 829 с.
  37. С. В. О суперпозициях функций алгебры логики // Математичесий сборник. 1952. — Т. 30, N 2. — С. 329 — 345.
  38. С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. Вып. 2.- М.: Физматгиз, 1959. С. 75 — 122.
  39. С. В. Введение в дискретную математику. М.: Наука, 1986. — 384 с.
  40. Abhyankar S. Absolute minimal expressions of Boolean function.- «IRE Tr. on EC.». 1959. — V. EC-8, No 1.
  41. Fischer M., Meyer A. R., Paterson M. S. Lower bounds on the size of Boolean formulas, preliminary report // Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque. 1975. — P.37 44.
  42. Fischer M., Meyer A. R., Paterson M. S. Q (nlogn) lower bounds on length of Boolean formulas // SIAM J. Comput. 1962. -V. 11, No 3. — P. 416 — 427.
  43. Gessel I., Stanley R. P. Stirling polinomials // Journal of Combinatorial Theory. series A. — 1978. — P. 24 — 33.
  44. Ginsburg J. Note on Stirling’s numbers // American Mathematical Monthly. 1928. — P. 77 — 80.
  45. Hodes L., Specker E. Lengths of formulas and elimination of quantifiers // Contributions to mathematical logic. Amsterdam.- 1968. P. 175 — 188.
  46. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. — V. 43, No 4. — P. 163 — 185.
  47. Post E. L. Two-valued iterative systema of mathematical logic // Annals of Math. Studies. 1941. — No 5.
  48. Shannon С. E. A symbolic analysis of relay and switching circuits // Trans.AIEE. 1938. -V. 57. — P. 713 — 723.
  49. Shannon С. E. The synthesis of two-terminal switching circuits // Bell.System. Techn. J. 1949. — V. 28. — P. 59 — 98.
  50. Stetsenco V. On almost bad Boolean bases // Theoretical Computer Science. 136. 1994. — P. 419 — 469.
  51. Работы автора по теме диссертации
  52. О. В. Количество бесповторных булевых функций в приведенных базисах // Конф. «Студент и научно-технический прогресс. Молодые ученые к 80-летию ИГУ», тезисы докладов. Иркутск, ИГУ. — 1998. — С 45.
  53. О. В. Число бесповторных булевых функций // Третий Сибирский Конгресс по прикладной и индустриальной математике. Сибирская конференция по исследованию операций. Новосибирск. — 1998. — С 126.
  54. О.В. Формулы для нахождения числа бесповторных булевых функций в различных базисах // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции. Нижний Новгород. — 1999. Часть I, — С 83.
  55. О.В. Число бесповторных функций алгебры логики в некоторых базисах // Материалы международной конференции по математической логике. Новосибирск. — 1999. — С. 24−25.
  56. О. В. Рекуррентные формулы для нахождения количества бесповторных булевых функций в различных базисах // Синтез и сложность управляющих систем. Материалы XII международной школы-семинара. М.: Изд-во МГУ, 2001. Т 1. — С. 93 — 99.
  57. B. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева- Под ред.
  58. C.Ф. Винокурова и Н. А. Перязева. М.: Физматлит, 2001. — 192 с.
  59. О. В. Оценки числа бесповторных булевых функций в бинарных базисах // Иркутский университет. Серия: Дискретная математика и информатика. Вып. 15. Иркутск, 2002. — 36 с.
Заполнить форму текущей работой