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

Слабоповторные булевы функции в предэлементарных базисах

Диссертация: Слабоповторные булевы функции в предэлементарных базисах
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Теоретический, а также практический интерес вызывают вопросы, касающиеся сложности представлений булевых функций термами. С одной стороны, имеем асимптотическую оценку сложности термальных представлений булевых функций над произвольными полными базисами. О. Б. Лупановым доказано, что почти все булевы функции имеют сложность 2n/log п. С другой стороны, при получении эффективных нижних оценок… Читать ещё >

Содержание

  • Глава 1. Основные понятия и результаты
    • 1. Основные понятия и терминология
    • 2. Обзор результатов по слабоповторным и бесповторным булевым функциям
  • Глава 2. Слабоповторные булевы функции в предэлементар-ных немонотонных базисах
    • 3. Свойства бесповторных булевых функций в предэлементарных базисах
    • 4. Слабоповторные булевы функции в серии предэлементарных немонотонных базисов
  • Глава 3. Слабоповторные булевы функции в предэлементар-ных парасимметрических базисах
    • 5. Слабо повторные булевы функции в предэлементарном парасимметрическом базисе порядка
    • 6. Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка

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

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

Представление булевых функций термами над заданным базисным множеством функций относится к основным этапам логического проектирования дискретных устройств [6, 7, 46, 47]. Поэтому неудивителен интерес, проявляемый к термальным представлениям [1, 16, 27, 36, 37, 39]. Существенным в изучении таких представлений явился результат Э. Поста об описании всех порожденных с помощью суперпозиции классов булевых функций, так называемых замкнутых классов булевых функций [43, 44]. Первоначальное доказательство этого результата было упрощено и изложено в более доступной форме [19, 20, 38].

Теоретический, а также практический интерес вызывают вопросы, касающиеся сложности представлений булевых функций термами. С одной стороны, имеем асимптотическую оценку сложности термальных представлений булевых функций над произвольными полными базисами. О. Б. Лупановым доказано [18], что почти все булевы функции имеют сложность 2n/log п. С другой стороны, при получении эффективных нижних оценок сложности возникают определенные трудности [17, 33, 49]. На сегодняшний день все известные эффективно заданные последовательности булевых функций имеют лишь полиномиальные оценки сложности [3, 21, 31, 32, 40, 41, 42, 45]. Таким образом, можно сказать, что исследования в этом направлении еще далеки от завершающей стадии.

При изучении вопросов сложности представлений булевых функций термами возникают такие понятия как бесповторность и слабоповтор-ность булевых функций. Бесповторные булевы функции, то есть функции, для которых существует представление в виде терма, в котором каждая переменная встречается не более одного раза, изучались еще с 50-х годов прошлого века, когда в работе А. В. Кузнецова [15] было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. Повторные булевы функции в некотором базисе В, у которых все собственные остаточные подфункции являются бесповторными в В, называются слабоповторными в базисе В. Из результата Н. А. Перязева [25] следует, что все неразделимые булевы функции есть слабоповторные функции в некотором базисе.

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

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

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

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

О. Б. Лупановым замечено (результат сформулирован в [30]), что элементарный базис bq ={V, —, 0,1} является самым плохим по сложности реализаций функций термами. Слабоповторные булевы функции в этом базисе в терминах обобщенной однотипности были найдены В. А. Стеценко, им же было доказано, что предплохие базисы имеют следующий вид 5oU {/}, где / - слабоповторная функция в Во [28, 29, 48]. В обратную сторону это утверждение доказано Д. Ю. Черухиным [34]. Таким образом, все базисы, описанные В. А. Стеценко, являются предэле-ментарными.

Следующий шаг в этом направлении был сделан Н. А. Перязевым [26], описавшим слабоповторные булевы функции в предэлементарном базисе В ={©, V, •, —, 0,1}. Затем К. Д. Кириченко дал описание всех слабоповторных булевых функций для двух серий предэлементарных базисов [13].

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

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

Заключение

.

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

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

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

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

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

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

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

  1. Дискретная математика и математические вопросы кибернетики, ¦f" Под редакцией Яблонского С. В. и Лупанова О. Б. — М.: Наука, 1974, Т. 1. — 312 с.
  2. Избранные вопросы теории булевых функций / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков, О. В. Зубков, К. Д. Кириченко, В. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева- Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.
  3. А. Е. Об одном методе получения более чем квадратичных оценок сложности тг схем / А. Е. Андреев // Вестник МГУ, — 1987. — Серия 1. — Матем. Мех. — № 1. — С. 70−73.
  4. В. Л., Копейкин В. Л., Шалыто А. А. Настраиваемые модули для управляющих логических устройств / В. Л. Артюхов, В. Л.
  5. , А. А. Шалыто. —Ленинград: Энергоиздат, 1981. — 166 с.
  6. Д., Постхоф X. Двоичные динамические системы / Д. Бох-манн, X. Постхоф. — М.: Энергоатомиздат, 1986. — 401 с.
  7. В. И. Введение в кибернетику / В. И. Глушков. — Киев: Изд-во АН УССР, 1964. 324 с.
  8. Р. М., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дискретных устройств / Р. М. Глушков, Ю. В. Капитонова, А. Т. Мищенко. — Киев: Наукова думка, 1987. — 264 с.
  9. В. А. О бесповторных булевых функциях / В. А. Гурвич // Успехи мат. наук. 1977. — Т. 32, № 1. — С. 183−184.
  10. В. А. Критерий бесповторности функций алгебры логики / В. А. Гурвич // Докл. АН СССР. 1991. — Т. 318, № 3. — С. 532−537.ч
  11. О. В. Соотношение количества бесповторных булевых функций в различных базисах / О. В. Зубков // Дискретная математика:
  12. Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 61−66.
  13. К. Д. О критериях бесповторности булевых функций в различных базисах / К. Д. Кириченко // Оптимизация, управление, интеллект. — Иркутск, 2000. — Вып 4. — С. 93−101.
  14. К. Д. Критерий бесповторности функции алгебры логики в бинарном базисе / К. Д. Кириченко // Международная конференция «Логика и приложения». — Новосибирск, 2000. — С. 57−58.
  15. К. Д. Кириченко Слабоповторные булевы функции в некоторых предэлементарных базисах / К. Д. Кириченко // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 13. — Иркутск, 2000. — 60 с.
  16. К. Д. Слабоповторные булевы функции в небинарных базисах / К. Д. Кириченко // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 14. — Иркутск, 2000. — 20 с.
  17. А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики / А. В. Кузнецов // Труды Математического института им. В. А. Стеклова. — М.: Изд-во АН СССР, 1958. Т. 51. — С. 186−225.
  18. О. Б. О сложности реализаций функций алгебры логики формулами / О. Б. Лупанов // Проблемы кибернетики. Вып. 3. — М.: Физматгиз, 1960. С. 61−80.
  19. О. Б. О методах получения оценок сложности и вычисления индивидуальных функций / О. Б. Лупанов // Дискретный анализ. Вып. 25. Новосибирск, 1974. — С. 3−18.
  20. О. Б. Асимптотические оценки сложности управляющих систем / О. Б. Лупанов. — М.: Изд-во Моск. ун-та, 1984.
  21. С. С., Угольников А. Б. Замкнутые классы булевых функций / С. С. Марченков, А. Б. Угольников. — М.: Изд-во ИПМ АН СССР, 19 900. 147 с.
  22. С. С. Замкнутые классы булевых функций / С. С. Марченков. — М.: Физматлит, 2000. — 128 с.
  23. Р. Г. Сложность булевых функций / Р. Г. Нигматул-лин. М.: Наука, 1991. — 240 с.
  24. Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Фундаментальные проблемы математики и механики. Математика. — М.: Изд-во МГУ, 1994. — С. 320.
  25. Н. А. Реализация булевых функций бесповторными формулами в некоторых базисах / Н. А. Перязев // Сб. Алгебра, логика и приложения. — Иркутск, 1994. — С. 143−154.
  26. Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Дискретная математика. — 1995. — Т. 7. — № 3. С. 61−68.
  27. Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах / Н. А. Перязев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1995. — 15 с.
  28. Н. А. Слабоповторные булевы функции в бинарном базисе / Н. А. Перязев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 4. — Иркутск, 1998. — 12 с.
  29. Н. А. Основы теории булевых функций / Н. А. Перязев. — М.: Физматлит, 1999. — 112 с.
  30. В. А. Об одном необходимом признаке для предмакси-мальных базисов в Р2 / В. А. Стеценко // Докл. АН СССР. — 1990. — Т. 315. С. 1304−1307.
  31. В. А. О предплохих базисах в Р2 / В. А. Стеценко // Математические вопросы кибернетики. — 1992. —Вып. 4. — С. 139— 177.
  32. Р 30. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами / Б. А. Субботовская // Докл. АН СССР. 1963. — Т. 149, № 4. — С. 784−787.
  33. В. М. О сложности реализации линейной функции в классе 7 г схем / В. М. Храпченко // Математические заметки. —1971. Т. 9, № 1. — С. 35−40.
  34. В. М. О сложности реализации симметрических функций формулами / В. М. Храпченко // Математические заметки. —1972. Т. 11, № 1. — С. 109−120.
  35. В. М. Нижние оценки сложности схем из функциональных элементов / В. М. Храпченко // Кибернетич. сб. Новая серия.1' Вып. 21. М.: Мир, 1984. — С. 3−54.
  36. Д. Ю. О предплохих булевых базисах / Д. Ю. Черухин // Дискретная математика. 1999. — Т. 11. — № 4. — С. 118−160.
  37. Д. Ю. Алгоритмический критерий сравнения булевых базисов / Д. Ю. Черухин // Математические вопросы кибернетики. — 1999. -Вып. 8. С. 77−122.
  38. К. Э. Работы по теории информации и кибернетике / К. Э. Шеннон. М.: ИЛ., 1963. — 829 с.
  39. С. В. Введение в дискретную математику: Учеб. пособие для вузов. / под ред. В. А. Садовничего / С. В. Яблонский. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.
  40. М., Meyer A. R., Paterson М. S. О(nlogn) lower bounds on length of Boolean formulas / M. Fischer, A. R. Meyer, M. S. Paterson // SIAM J. Comput. — 1962. — V. 11. —No 3. — P. 416−427.
  41. Fischer M., Meyer A. R., Paterson M. S. Lower bounds on the size of Boolean formulas, preliminary report / M. Fischer, A. R. Meyer, M. S. Paterson // Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque. — 1975. — P. 37−44.
  42. Hodes L., Specker E. Lengths of formulas and elimination of quantifiers / L. Hodes, E. Specker // Contributions to mathematical logic. — Amsterdam, 1968. — P. 175−188.
  43. 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.
  44. Post E. L. Two valued iterative systema of mathematical logic / E. L. Post // Annals of Math. Studies. — 1941. —No 5.
  45. Pudlak P. Bounds for Hodes Specker theorem / P. Pudlak // Lecture Notes in Computer Science 171, Springer — Verlag. — 1984. — P. 421— 445.
  46. Shannon С. E. A symbolic analysis of relay and switching circuits / С. E. Shannon // Trans. AIEE. — 1938. — V. 57. P. 713−723.
  47. Shannon С. E. The synthesis of two terminal switching circuits / С. E. Shannon // Bell. System. Techn. J. — 1949. — V. 28. — P. 5998.
  48. Stetsenko V. On almost bad Boolean bases / V. Stetsenko // Theoretical Computer Science. — 1994. — V. 136. — P. 419−469.
  49. Wegener I. The Complexity of Boolean function / I. Wegener // Wiley Teubner Series in Computer Science, Wiley — Teubner. — 1987.
  50. Работы автора по теме диссертации
  51. И. К. Слабоповторные булевы функции в одном предэле-ментарном базисе / И. К. Шаранхаев // Дискретная математика: Труды XII Байкальской международной конференции «Методы оптимизации и их приложения». — Иркутск, 2001. — Т. 5. — С. 151−155.
  52. И. К. О слабоповторных булевых функциях / И. К. Шаранхаев // XIII Международная конференция по проблемам теоретической кибернетики. Тезисы докл. — Казань, 2002. — Часть 2. — С. 195.
  53. И. К. О слабоповторных булевых функциях в одном базисе / И. К. Шаранхаев // Материалы конференции «Дискретный анализ и исследование операций». — Новосибирск, 2002. — С. 139.
  54. И. К. Слабоповторные булевы функции в предэле-ментарных немонотонных базисах / И. К. Шаранхаев // Труды Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе. — Иркутск, 2003. — С. 87−90.
  55. И. К. О слабоповторных булевых функциях в одном предэлементарном базисе / И. К. Шаранхаев // Дискретный анализ и исследование операций. — Новосибирск, 2003. — Серия 1. — Т. 10. — № 2. С. 79−101.
  56. И. К. Слабоповторные булевы функции в некоторых базисах / И. К. Шаранхаев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 17. — Иркутск, 2003. — 64 с.
Заполнить форму текущей работой

Пора сдавать?