Методы нахождения бесповторных представлений не всюду определенных булевых функций

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

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

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

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

§ 2. Обзор результатов по бесповторному представлению булевых функций

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

§ 3. Алгоритм бесповторного представления недоопределенных

булевых функций над бинарным базисом

§ 4. Корректность алгоритма бесповторного представления недоопределенных функций над бинарным базисом

Глава 3. Бесповторное представление недоопределенных частичных булевых функций

§ 5. Необходимые условия бесповторности недоопределенных
частичных булевых функций в специальном базисе
§ 6. Алгоритм бесповторного представления недоопределенных
частичных булевых функций в специальном базисе
Заключение
Список литературы

Введение
Теория конечных функций образует одно из главных направлений исследований в дискретной математике. И особое место здесь занимает теория булевых функций, как основной инструмент при разработке математических моделей цифровой техники. Из различных способов задания булевых функций основным является представление их с помощью суперпозиции выделенных базисных функций. Такое представление называют формульным или термальным. Большое распространение оно получило за счет того, что представление функций термами над заданным базисным множеством являетя основным этапом при проектировании дискретных устройств [10, 11, 62, 63].
Прежде чем приступить к представлению функции термом, надо выбрать набор функций, которые можно использовать при этом представлении. Причем, если некоторый набор подходит для задания любой булевой функции, он называется базисом. Основополагающим в данной области был результат Э. Поста об описании всех порожденных с помощью суперпозиции классов (замкнутых классов) булевых функций [60, 61]. Существуют более короткие доказательства этого результата, например, [45, 19, 49]. О базовых результатах, касающихся формульных представлений функций, можно узнать из [1, 18, 33, 48, 50].
Как правило, представление функций термами над заданным базисом является неединственным. Поэтому, необходимы некоторые критерии, позволяющие выбрать один из них. Зачастую таким критерием является сложность. Под сложностью, в зависимости от решаемой задачи, может пониматься и количество функциональных символов в терме, и количество символов переменных, и количество конструкций определенного вида. Множество работ посвящено нахождению минимальных представлений функций, разработке эффективных алгоритмов получения минимальных представлений, определению сложности в различных

классах функций [20, 46, 44].
Со сложностью представления булевых функций термами связано понятие бесповторности. Бесповторными называются функции, которые можно представить термом, каждая переменная в который входит не более одного раза. Такие функции обладают наименьшей сложностью, если под сложностью понимать количество вхождений переменных в терм. В работе А. В. Кузнецова [16] было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих беспо-вторной декомпозиции на функции меньшей размерности. В. JI. Артюхов, Г. А. Копейкин, А. Шалыто [4] показали, что бесповторные функции преобладают при описании работы цифровых вычислительных машин.
С другой стороны, при исследовании слабоповторных функций (повторных булевых функций в некотором базисе В, у которых все собственные остаточные подфункции являются бесповторными в В) было показано, что добавление слабоповторной в базисе В функции к этому базису, существенно увеличивает число бееповторных функций [?].
В связи с большой степенью применимости бесповтоных функций широкое распространение получил вопрос поиска функций, обладающих свойством бесповторности, определения по заданной функции, является она бесповторной или нет. Больше всего этот вопрос исследовался для элементарного базиса, состоящего из конъюнкции, дизъюнкции и отрицания.
Существуют разные подходы к описанию бееповторных предстале-ний булевых функций. Начало одному из подходов положил В. А. Гур-вич [12, 13] Его теорема явилась началом, так скажем, «графического» подхода к нахождению бесновторного представления булевых функций и развивалась в основном на западе. Первый шаг в этом направлении сделал сам В. А. Гурвич [12]. Затем J. P. Hayes [56] разработал алгоритм распознавания бесповторности булевых функций и получения са-

Х2 х5
Естественно, множество подозрительных на фиктивность переменных у*, найденное для функции д по той же переменной Х, будет являться подмножеством множества Щ, и нам не надо будет проверять на выделимость те множества, которые мы проверяли для функции /.
Дальнейший процесс проверки на выделимость множеств и формирования из них новых функций меньшей размерности выглядит так:
V V V
/У хз хб У хз ж6 z3 х3 х6
Xl у Xi Z2
Z Х4
На этом этапе множество переменных сформированной функции не содержит переменной х, и весь процесс начинается заново для переменной z3.
Пример 1. Теперь посмотрим, как описанные выше действия выглядят, когда мы работаем с вектором функции. Получим векторное задание вышеописанной функции
/(®1, ®2,®з, *4, ®5, ®б) = (00001111 01011111 00111111 01111111 11110000 11110101 11000000 11010101).
Теперь «испортим» полученную функцию, то есть сделаем так, чтобы она стала недоопределенной, например, следующим образом:
f(x 1,Х2,Х3,Х4,Х5,Х6) = (0
1__1 100 -- 111 --101 1 00 -0 - 1 10-).