Четверг, 2024-09-19, 10:45 PM
Приветствую Вас Гость

Учебные материалы

Главная » » Скачать Слабоповторные булевы функции в предэлементарных базисах. Шаранхаев, Иван Константинович бесплатно

5:59 AM

Скачать Слабоповторные булевы функции в предэлементарных базисах. Шаранхаев, Иван Константинович бесплатно

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

Диссертация

Автор: Шаранхаев, Иван Константинович

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

Справка: Шаранхаев, Иван Константинович. Слабоповторные булевы функции в предэлементарных базисах : диссертация кандидата физико-математических наук : 01.01.09 Иркутск, 2003 134 c. : 61 04-1/604

Объем: 134 стр.

Информация: Иркутск, 2003

Содержание:

Введение
Глава 1 Основные понятия и результаты
§ 1 Основные понятия и терминология
§ 2 Обзор результатов по слабоповторным и бесповторным булевым функциям
Глава 2 Слабоповторные булевы функции в предэлементар-ных немонотонных базисах
§ 3 Свойства бесповторных булевых функций в предэлементарных базисах
§ 4 Слабоповторные булевы функции в серии предэлементарных немонотонных базисов
Глава 3 Слабоповторные булевы функции в предэлементар-ных парасимметрических базисах
§ 5 Слабо повторные булевы функции в предэлементарном парасимметрическом базисе порядка 5
§ 6 Слабоповторные булевы функции в предэлементарном парасимметрическом базисе порядка 4
Введение:
Теория дискретных функций образует одно из главных направлений исследований в дискретной математике. Простейшим и в то же время важнейшим классом таких функций является класс булевых функций. Из различных способов задания булевых функций основным является представление их с помощью суперпозиции выделенных базисных функций, которое в теории булевых функций называют термальным или формульным.
Представление булевых функций термами над заданным базисным множеством функций относится к основным этапам логического проектирования дискретных устройств [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 параграфов, заключения и списка литературы.

Скачивание файла!Для скачивания файла вам нужно ввести
E-Mail: 3135
Пароль: 3135

Скачать файл.

Просмотров: 101 | Добавил: Аня41 | Рейтинг: 0.0/0

Форма входа

Поиск

Календарь

Архив записей

Друзья сайта