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

• Автор: Шаранхаев, Иван Константинович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Иркутск
• Количество страниц: 134 с.

Оглавление
Введение

Глава 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/og п. С другой стороны, при получении эффективных нижних оценок сложности возникают определенные трудности [17, 33, 49]. На сегодняшний день все известные эффективно заданные последовательности булевых функций имеют лишь полиномиальные оценки сложности [3, 21, 31, 32, 40, 41, 42, 45]. Таким образом, можно сказать, что исследования в этом направлении еще далеки от завершающей стадии.

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

уд(х°*, Х?‘, Х^1 X?2). Переменные X,-3 И Хг’4 ОТЛИЧНЫ ОТ XI, что следует из леммы 3. В силу симметричности Хц и х,-2 считаем, что х,-, = х. По К лемме 3 переменная х,-2 отлична от х2 и хз, поэтому хг-2 = х4. Имеем
Д = ухд(х2,х^,х^ V уу(х?3, х?*, х^х^2). При од = 1 по лемме 5 получаем функции /11 = ух1у(х2,х3,х4)/уу(х2, х3, ххх4) иЛ2= ухд(х2, х3, х4) V уу(хз,Х2,Х1Х4). Остаточные функции Дх*2 = х3(у V Х1) V ххх4 и Д2*3 = хг(у/х1)/х1х4 повторны в В. При од = 0 рассмотрим Д* = уу(х2, хз, х4) V ух?*. По лемме 5 ст4 = 1. Если х,4 = х2, то остаточная функция Д®2 = ух1Хзх4 V ух!Хд3х^2 повторна в В. Если х,4 = хз, то Д®3 = ух 1X2X4 V ух 1Х23х42 повторна в В.
Докажем, что / не представима в виде 6. Пусть Д = ух1у(х2, хз, х4) V уд{хЦ V х£,х£,х£). Из леммы 3 следует, что пересечение {х,-,,х,-2} и {х2,х3} пусто. Тогда Д = ух1у(х2,х3,х4) V уд(х1 V Х42,х?3, х?4). При любой (т 1 остаточная функция кх повторна в В по лемме 5.
0. Пусть Щ — д(х 1Х2,хз,х4). Докажем, что t не представима в виде 1.
Пусть Д = уд(х 1Х2, хз, х4) /уд(х?', х?2, х?з). Пусть в / фиктивна переменная XI или х2, в силу симметричности этих переменных считаем, что это х. По лемме 5 функция бесповторна в В, если £ = д(х2,хз,х4). Но тогда Д разделима по теореме III. Переменная хз не может быть фиктивна / по лемме 3, значит фиктивна х4. Имеем Д = уу(х 1Х2,хз, х4) V уд(х°1,х?*,х°*). При од — 1 функция Д^ = уу(х2, х3, х4) V у^1 V Хд2), а при од = 0 функция Д*4 = уу(х2,хз, х4) V ух^хд2 повторны в В.
Функция / не представима в виде 2 и 3, иначе она обобщенно однотипна с Х1у(х2,хз,х4), а такой случай рассмотрен выше.
Докажем, что / не представима в виде 4. Пусть Д = уу(х 1Х2, хз, х4) V уд{х?хх?*, х?з, х?*). Переменная х,3 отлична от Х1 и х2, а х,, и хг-2 отличны от хз по лемме 3. Пусть {х,-,,х,-2} совпадает с {х1,х2}. Тогда по лемме 5 + од = од = 0 и имеем Д = уд(х 1х2,хз,х4) V уу(х 1х2,х4,хз). Остаточная
функция Л*з°4 = ух4Х2 V ухХ2 повторна в В.
Пусть {х,д,х,-2} не совпадает с {х1,х2}. В силу симметричности XI и