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

• Автор: Зубков, Олег Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Иркутск
• Количество страниц: 96 с.

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

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

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

§2. Обзор результатов по бесповторным булевым функциям 13 Глава 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]. Им показано,

что подавляющее большинство булевых функций имеет сложность 2"/ log п. Однако все известные до сих пор эффективно задающиеся последовательности булевых функций имеют лишь полиномиальные оценки сложности [2, 21, 33, 34, 41, 42, 45].
С таких позиций становятся ясными причины интереса, проявляемые к функциям, которые имеют самое простое представление в каком-либо базисе. Наименьшую сложность при термальном представлении имеют бесповторные булевы функции, то есть функции, для которых существует задание в виде терма, где каждая переменная встречается не более одного раза. И хотя, как следует из работы автора [56], бесповторных булевых функций существенно меньше, чем остальных функций, они имеют большое практическое значение. Большая часть функций, применяемых при проектировании микропроцессоров, является бесповторными в базисе, состоящем из конъюнкции, дизъюнкции и отрицания [3]. Кроме того следует отметить результат Б. А. Суббо-товской [31, 32] о том, что базис эквивалентен элементарному в смысле сложности термального задания булевых функций тогда и только тогда, когда он содержит лишь бесповторные функции в элементарном базисе. Для произвольного базиса этот результат был обобщен Д. Ю. Черухиным [35].
Ключевым для раздела, изучающего бесповторные булевы функции, является результат В. А. Кузнецова [15] о том, что бесповторные термы, представляющие одну и ту же булеву функцию, то есть эквивалентные между собой, весьма похожи друг на друга и могут отличаться только по четко выделенным позициям. Это утверждение позволяет каждой бесповторной булевой функции поставить в соответствие единственный в определенном смысле терм, представляющий ее.
Возможны качественный и количественный подходы к изучению бесповторных булевых функций.
Основной задачей первого является нахождение эффективных алгоритмов, позволяющих определить, является ли заданная функция

где сумма берётся по всевозможным неубывающим наборам длины к + 1, у которых последний член равен п — к — 1.
Следствие 2. Число Кп бесповторных булевых функций ранга п в элементарном базисе Во находится по формуле
Имеется возможность, рассуждая несколько иначе, чем в теореме 1, получить другую нерекуррентную формулу для числа бесповторных в Во булевых функций. При ее построении и доказательстве будем использовать установленную в теореме 2 связь между коэффициентами В(іф) и числами Эйлера второго порядка. Эта новая формула необходима для получения более хороших оценок для числа бесповторных функций в Во.
Теорема 3. Число Кп бесповторных булевых функций ранга п в элементарном базисе Во может быть вычислено по формуле
Доказательство. При доказательстве этой теоремы будем получать упорядоченные термы от та переменных {ад,. .. ,хп} из упорядоченных термов от та — 1 переменной {од,... ,тп_і} путем добавления переменной хп. В отличие от теоремы 1, где эта операция производилась в структуре упорядоченного терма, то есть все бинарные функции были заменены на нейтральный символ о, в этом доказательстве переменную хп будем добавлять непосредственно в упорядоченный терм.
Напомним, что двойственным к терму Ф называется терм Ф*, получаемый из Ф заменой в нем всех & на V и всех V на &.
Очевидно, что если терм Ф упорядоченный над До, то Ф* так же