Методы нахождения бесповторных представлений не всюду определенных булевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

0а-

Семичева Наталия Леонидовна

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

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□0345В826

Иркутск - 2008

003456826

Работа выполнена в Иркутском государственном педагогическом университете

Научный руководитель:

доктор физико-математических наук, профессор Перязев Николай Алексеевич

Официальные оппоненты:

доктор физико-математических наук, доцент Вороненко Андрей Анатольевич

кандидат технических наук Семенов Александр Анатольевич

Ведущая организация:

Сибирский федеральный университет

Защита состоится 25 декабря 2008 г. в 14-00 на заседании диссертационного совета Д 212.074.01 в Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).

Автореферат разослан 24 ноября 2008 г.

Ученый секретарь диссертационного совета, канд. физ.-мат. наук, доцент ^—" В.Г. Антоник.

Общая характеристика работы

Актуальность темы. Теория конечных функций образует одно из главных направлений исследований в дискретной математике. И особое место здесь занимает теория булевых функций, как основной инструмент при разработке математических моделей цифровой техники. Распространенным способом задания булевых функций является их формульное или термальное представление. Большое распространение оно получило за счет того, что является основным этапом при проектировании дискретных устройств.

Прежде чем приступить к представлению функции термом, надо выбрать набор функций, которые можно использовать при этом представлении. Причем, если некоторый набор подходит для задания любой булевой функции, он называется базисом. Основополагающим в данной области был результат Э. Поста1, описывающий все порожденные с помощью суперпозиции классы (замкнутых классов) булевых функций.

Со сложностью представления булевых функций термами связано понятие бесповторности. Бесповторными называются функции, которые можно представить термом, каждая переменная в который входит не более одного раза. Такие функции обладают наименьшей сложностью, если под сложностью понимать количество вхождений переменных в терм. В работе А. В. Кузнецова2 было доказано, что бесповторное представление для булевой функции является «почти» единственным над множеством неразделимых функций, то есть функций, не допускающих бесповторной декомпозиции на функции меньшей размерности. Известно, что бесповторные функции преобладают при описании работы цифровых вычислительных машин. В связи с этим при исследовании бесповторных функций широкое распространение получил вопрос определения по заданной функции, является она бесповторной или нет. Обзор результатов по этому направлению сделан в монографии3.

1 Post Е. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer. J. Math. — 1921. — Vol. 43, № 4. - P. 163-185.

2Кузнецов А. В. О бесповторных контактных схемах и бесповторных суперпозициях функций алгебры логики / А. В. Кузнецов // Труды Математического ин-та им. В. А. Стеклова. - М.: Изд-во АН СССР, 1958. - Т. 51. - С. 186-225.

3Избранные вопросы теории булевых функций / Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

A.A. Вороненко4 разработал алгоритм линейной сложности для распознавания бесповторности всюду определенных булевых функции в любом наследственном базисе.

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

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

Существуют алгоритмы минимизации недоопределенных булевых функций, сужающие исходную задачу ввиду высокой алгоритмической сложности ее решения в общем виде. В частности, такие алгоритмы решают и задачу бесповторного представления исследуемой функции. Например, Я. Хлавичка и П. Фишер5 дают алгоритм минимизации сильно неопределенных булевых функций.

Актуальной задачей является исследование не всюду определенных булевых функций с двумя видами неопределенности, первый из которых совпадает по смыслу с описанным ранее, второй вид неопределенности обозначает запрет на принятие конкретного значения и называется такой вид неопределенности частичностью. Функции с заданными таким образом значениями неопределенности называются недоопределенными частичными булевыми функциями. Впервые рассматривать функции с двумя видами неопределенности начали В. И. Пантелеев и Н. А. Перязев6 в 1990 году при решении некоторых

4Вороненко А. А. Распознавание бесповторности в произвольном базисе / А. А. Вороненко. // Прикладная математика и информатика. — М.: Макс-Пресс, 2006. - Вып. 23. - С. 67-84.

5 Hlavicka J. Algorithm for minimization of partial functions / J. Hlavicka, P. Fiser // Design and Diagnostics of Electronic Circuits and Systems Workshop — Bratislava. — 2000. — P. 130-133.

6Пантеяеев В. И. Обобщенная интерпретация переменных: семантическое исследование и логический вывод / В. И. Пантелеев, Н. А. Перязев // Материалы школы «Пятая школа молодых математиков Сибири и Дальнего Востока». — Новосибирск, 1990. — С. 87-89.

логических вопросов. С. А. Ложкин7 отмечает, что такие функции находят применение в технических приложениях. Важные результаты, необходимые для работы с недоопределенными частичными булевыми функциями, получены в работе8. Так как недоопределен-ные частичные булевы функции применяются при моделировании вычислительных устройств, а при их проектировании преобладают именно бесповторные функции, поэтому естественным является вопрос исследования недоопределенных частичных функций на беспо-вторность.

Цели работы:

• разработка алгоритма нахождения бесповторного представления недоопределенных булевых функций в бинарном базисе, исключающего полный перебор по всевозможным доопределениям;

• исследование свойств бесповторных недоопределенных частичных булевых функций в специальном базисе;

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

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

Основные результаты, выносимые на защиту:

• алгоритм представления недоопределенных булевых функций бесповторными термами в бинарным базисе, доказательство корректности этого алгоритма;

• необходимые условия бесповторности недоопределенных частичных булевых функций в специальном базисе и свойства выде-лимых подмножеств переменных в этих функциях;

7Ложкин С. А. О синтезе формул и схем из не всюду определенных функциональных элементов / С. А. Ложкин // Труды VI международной конференции «Дискретные модели в теории управляющих систем». — М.: ВМиК МГУ. — 2004. - С. 44-47.

8Пантелеев В. И. Недоопределенные частичные булевы функции и булевы уравнения / В. И. Пантелеев, Н. А. Перязев // Материалы VII Международной конференции «Дискретные модели в теории управляющих систем». - М.: ВМиК МГУ, 2006. С. 262-265.

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

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

Личный вклад автора. Все основные результаты, включенные в диссертацию, получены лично автором.

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

Апробация работы. Результаты диссертации были представлены на Международной конференции «Алгебра, логика и кибернетика» (Иркутск, 2004 г.), на VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004 г.), конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2006 г.), школе-семинаре «Синтаксис и семантика логических систем» (Владивосток, 2008 г.), а также неоднократно докладывались на семинаре «Дискретная математика и математическая информатика» кафедры математической информатики Иркутского государственного педагогического университета.

Исследования по теме диссертации были выполнены при частичной финансовой поддержке Российского фонда фундаментальных исследований, проект 07-01-00240.

Публикации. По теме диссертации опубликовано 6 работ. Основное содержание представлено в работах [1-6]. В число указанных работ входит одна статья [1] из «Перечня ведущих рецензируемых журналов и изданий ВАК РФ 2001-2006 гг.», одна статья [2] в научном сборнике, три полных текстов докладов [3-5] в материалах международных и всероссийских конференций.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, содержащего 70 наименований. Общий объем диссертации — 88 страниц, включая 1 рисунок.

Основное содержание работы

Во введении дается обоснование актуальности темы исследований.

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

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

Обозначим Р — множество всех булевых функций.

Пусть В С ^ Д - некоторое множество символов, называемых переменными.

Индукцией определим понятие терма над В от множества переменных X:

1) х из X есть терм;

2) если / £ В, <Ит{}) — т и Фх,..., Фот — термы, то /(Фь..., Фт) есть терм.

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

Бесповторным называется терм от X, каждая переменная в который входит не более одного раза. Если существует бесповторный терм над базисом В, представляющий функцию /, то функция / называется бесповторной в В.

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

Будем использовать следующие обозначения:

• а — двоичный набор;

• х — набор переменных (жх,..., хп).

Остаточными функциями от функции / по переменной Х{ называются функции, размерности которых на единицу меньше размерности /, и определяются они следующим образом:

где а £ {0,1}. Если а = 0, то остаточная функция называется нулевой остаточной; если сг — 1, то — единичной остаточной. Индуктивно понятие остаточной функции распространяется на множество переменных ,..., х^ по набору <7*1, • • •, с», (я < п):

где 5 называется порядком остаточной функции.

Сопряженной функцией от функции / по переменной Х{ называется функция, размерность которой совпадает с размерностью /. Определяется сопряженная функция следующим образом:

Функция /(х) называется разделимой по множествам у и 2, где у1)г — х иуПг = 0, если существуют такие функции Н(у) и д(г, г), что функцию / можно представить в виде

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

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

Недоопределенной булевой функцией называется отображение из {0,1}п в {0,1,—}, где значение «—» вводится для обозначения значения «иедоопределсно».

= /0е 1) • • • > хг-и <*, 2ч+1, ■ • • , хп),

1{х) = 9{Ку),г).

(1)

Терм Ф представляет недоопределенную булеву функцию /, если значения Ф совпадают со значениями / на тех наборах, на которых она определена.

Вторая глава посвящена алгоритму бесповторного представления недоопредленных булевых функций над бинарным базисом. При работе с не всюду определенными булевыми функциями очень сложно подобрать такое доопределение, которое бы удовлетворяло нужным требованиям. Поэтому в третьем параграфе описывается алгоритм получения бесповторного представления недоопределенных булевых функций [1, 3], основанный на рекурсивном доопределении функции, используя критерий бесповторности булевых функций в бинарном базисе и критерий разделимости функции9.

Переменная х называется подозрительной на фиктивность переменной функции /, если существует такое доопределение /, при котором = Обозначение <5*(/) вводится для множества подозрительных на фиктивность переменных функции /.

Так как при описании алгоритма учитываются различные нюансы, не позволяющие привести алгоритм в полном объеме, приведем схематичное его описание. На вход алгоритма подается вектор недо-определенной булевой функции /. Фиксируем множество переменных х функции /. Выбираем переменную х^ € х.

1. Находим множества **(/£).

2. Выбираем двухэлементное множество у € 5*) и и<5*(/^), используя определенную стратегию.

3. Проверяем существует ли такое доопределение /, при котором обе переменные из у являются фиктивными.

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

5. На тех наборах значений переменных /, на которых она недо-определена и существует единственное значение из множества {0,1}, приводящее к выделимости множества у, доопределяем / необходимыми значениями.

9Шоломов Л. А. Основы теории дискретных логических и вычислительных устройств / Л. А. Шоломов // М.: Наука, 1980. — 400 с.

6. Получаем функции д и /1 и применяем к ним рекурсивный вызов алгоритма. При этом найденное выделимое множество у для / накладывает ограничение на множества, получаемые в пункте 1. Если алгоритм не нашел бесповторное представление функции д, переходим к пункту 2 и выбираем другое подмножество для проверки. Функция И выбирается таким образом, что она всегда будет иметь бесповторное преставление над бинарным

Также в третьем параграфе объясняются выбранные стратегии для уменьшения перебора множеств, проверяемых на выделимость.

В четвертом параграфе дается обоснование корректности алгоритма [1].

Теорема 2.1. Алгоритм нахождения бесповторного представления недоопределенных булевых функций в бинарном базисе является корректным.

В конце четвертого параграфа приводятся результаты тестирования алгоритма для функций, зависящих не более, чем от 18 переменных [4].

В третьей главе рассматриваются недоопределенные частичные булевы функции (н.ч.б.ф.), которые определяются как отображения из {0,1}" в {0,1,—,*}, где значение «*» вводится для обозначения значения «частично». Разработан алгоритм нахождения бесповторного представления недоопределенных булевых функций. Данный алгоритм также базируется на поиске выделимого множества. Но в связи с тем, что н.ч.б.ф. могут принимать не два, а четыре различных значения, критерий существования разделительной декомпозиции, определенный для тотальных функций, здесь неприменим. Поэтому в пятом параграфе сначала проводится исследование свойств бесповторных недоопределенных частичных булевых функций [2].

Для представления функций, принимающих значение *, термами над некоторым базисом В необходимо, чтобы в этот базис входила функция, также на некотором наборе значений переменных принимающая значение *. Рассмотрим базис Д> = {—,&;, V, ©,>}, где функция > определеяется следующим образом: >(0,0) = *, >(0,1) = 1, >(1,0)-0, >(1,1) = -.

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

и 1 и собственные н.ч.б.ф., принимающие все четыре значения из множества {0,1, —, *}.

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

Суперпозиция д(х) = /(/1(5),..., /т(я)) для н.ч.б.ф. определяется следующим образом: 1) набор т £ {0,1,*}" называется уточнением набора 7 € {0,1, —, *}", если для тех г, для которых 7* ф —, следует, что т* = 7,-, а для остальных г имеем г, ф *; 2) пусть /¿(я), / — н.ч.б.ф, (г = 1,...,т). Для набора а 6 {0,1} обозначим через 7 набор < Д(о-),..., /т(а) > и тогда

д{5) = *, если существует г 6 {1,..., т} такое, что /¿(¿т) = * и для любых уточнений т набора 7 выполняется № = *;

д{сг) = —, если для всех г £ {1,..., ш} выполняется /г(а') ф *, и существует уточнение т набора 7 такое, что /(т) = — или существуют уточнения а и /? набора 7 такие, что /(Й)=0и/О3) = 1;

д(а) = 1, если для всех г 6 {1,... ,тп} выполняется /¿(сх) ф * и для любого уточнения т набора 7 имеем /(г) € {1, *}, и при этом существует уточнение а набора 7 такое, что /(а) = 1;

д(а) — 0, если для всех г £ {1,... ,т} выполняется /,(<т) ф * и для любого уточнения г набора 7 имеем /(т) 6 {0, *}, и при этом существует уточнение а набора 7 такое, что /(а) = 0.

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

Лемма 1. Если / — бесповторная в Б>, тогда:

1) функция / является либо тотальной, либо собственной;

2) если / — собственная, тогда любая остаточная функция по любой переменной принимает как значения из множества {0,1}, так и значения из множества {—,*}, то есть:

Уст За /£(а) = а, а, а 6 {0,1}, Ма /£ ф)=0, (3 € {-,*},а 6 {0,1}.

Замечание 1. Для двухместных недоопределенных частичных булевых функций условия леммы 1 являются необходимыми и достаточными условиями бесповторности в базисе Д>.

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

В базисе Д> любую н.ч.б.ф. можно представить в виде терма, в котором используются только тесные отрицания. Для перехода к тесным отрицаниям используются законы де Моргана и тождество х>у — у>х. Такие термы будем рассматривать в виде корневого бинарного дерева Т, листья которого помечены переменными или их отрицаниями, а остальные вершины — символами бинарных операций из множества {&, V, ©, >}. Если важно подчеркнуть, переменными из какого множества помечены листья дерева Т, тогда будем обозначать дерево Т(х).

Теорема 3.1. Пусть f — существенная бесповторная н.ч.б.ф. и ее можно представить с помощью разделительной декомпозиции f(y,z) = g{h(y), z), Ф(у,г) = $g($h{y),z), где Ф, Ф5, Ф/, -бесповторные термы, представляющие соответственно функции /, g, h. Причем в терме Ф встречаются только тесные отрицания. Дерево Т представляет терм Ф. Тогда верно следующее:

1) среди остаточных функций от f по множеству переменных у ровно 2 различных h тотальная;

2) среди остаточных функций от f по множеству переменных ■у ровно 3 различных О- h собственная, и для дерева Т существует вершина v, помеченная о, которая является предком поддерева Th, и на пути от корневой вершины поддерева Тн к вершине v не существует вершины v , помеченной ф или >;

3) в остальных случаях, среди остаточных будет ровно 4 различных.

На основании леммы 1 и теоремы 3.1 получаем следствия, определяющие основные шаги алгоритма бесповторного представления н.ч.б.ф.

Следствие 1. Пусть f — бесповторная н.ч.б.ф., представимая в виде (1), и среди остаточных функций от f noy ровно две различных, тогда не существует набора а такого, что = *.

Следствие 2. 1) Пусть / — бесповторная н.ч.б.ф., представимая в виде (1), и среди остаточных функций от f по у три или

четыре различных, тогда существует набор ä такой, что /? = *.

2) Пусть н.ч.б.ф. f можно представить в виде (1) и среди остаточных функций от f по у четыре различных, тогда существует набор öl такой, что = *.

Пусть / — бесповторная, представленная в виде (1), тогда существуют наборы äi, <52, аз такие, что 7?1 (z) = g(0,z), f~2(z) = 5(1,5), /?3(¿) = g(—, z). Функция g(—, z) не имеет самостоятельного значения, а зависит от значений функций 5(0,z) и g(l,z). То есть, исходя из правил суперпозиции, для g(—,z) должны выполняться следующие условия:

1) если д(0, (ст)) = 5(1, (er)) = а,

где а € {0,1, -, *}, тогда д(-,сг) = а;

2) если 5(0, (сг)) = а, д( 1, (<т)) = <5,

где a G {0,1, -, *}, тогда д{~, а) =;

^ ; 3) если g(ß, (er)) = -, g(ß, (er)) = а,

где а е {-, *}, ß 6 {0,1}, тогда g(-,ä) = 4) если g{ß, (í)) = *, g(ß, (¿r)) = а, где а € {0,1,-,*}, ß £ {0,1}, тогда g(-, er) = а.

Определим множества:

A = {ä: д{-,&) = -};

В = {д : ff(0,cr) = -};

C = {ä: 0(1,*) = -};

£> = {ff : 5(0, er) = а, 5(1, сг) = ö}. (2)

Исходя из условий (**), получаем еще два следствия.

Следствие 3. Для введенных в (2) множеств выполняется:

A = BUCUD.

Следствие 4. Для бесповторной булевой функции g справедливо: если А = В или А = С, тогда д(0, z) = g(—, z) или д( 1, z) = g(—,z), соответственно.

В шестом параграфе данной главы представлен алгоритм бесповторного представления н.ч.б.ф. над В> [2, 5, 6]. Схема алгоритма

нахождения бесповторного представления н.ч.б.ф. над В> заключается в следующем. На вход алгоритма подается вектор недоопреде-ленной частичной булевой функции /. Фиксируем множество переменных х функции /.

1. Если местность функции меньше 3, и функция / удовлетро-ряет условиям леммы 1, находим бесповторный терм Ф, представляющий функцию /, иначе переходим к пункту 2. Если одноместная или двухместная функция не удовлетворяет условиям леммы 1, значит, для нее не существует бесповторного представления в базисе В>.

2. Выбираем двухэлементное множество у е х. За время работы алгоритма каждое множество проверяется не более одного раза. Переходим к пункту 3.

3. Находим остаточные функции от / по у и проверяем выполнение следствий 1-4. Если все условия выполняются, то получаем функции д и Ии применяем к ним рекурсивный вызов алгоритма. Иначе возвращаемся к пункту 2 и выбираем другое множество для проверки на выделимость. Функция не имеет бесповторного представления в базисе В>, если при рекурсивном вызове алгоритма бесповторные представления функций д и кие были найдены, или если все двухэлементные подмножества были проверены на выделимость и не дали положительного результата.

Теорема 3.2. Алгоритм нахождения бесповторных представлений недоопределенных частичных булевых функций в базисе В> является корректным.

Если под сложностью понимать количество операций сравнения функций, то сложность алгоритма равна 0(п2), где п — длина входного вектора.

В конце параграфа приводятся результаты тестирования алгоритма для функций, зависящих не более, чем от 19 переменных [2].

В заключении дан обзор основных результатов, полученных в работе.

Публикации по теме диссертации

[1] Коршунова H.JI. (Семичева Н. JL) Представление частичных булевых функций бесповторными термами над бинарным базисом / Н. JI. Коршунова // Вестник БГУ. Серия 13: Математика и информатика. — 2005. — Вып.2. — С. 26-35.

[2] Семичева Н. Л. Нахождение бесповторных представлений недо-определенных частичных булевых функций / Н. JI. Семичева. — Иркутский государственный педагогический университет. Серия: Дискретная математика и информатика. Вып. 19. — Иркутск, 2008. - 35 с.

[3] Коршунова H.JI. (Семичева Н. JI.) Нахождение представления частичных булевых функций бесповторными термами над бинарным базисом / Н. JI. Коршунова // Материалы международной конференции «Алгебра, логика и кибернетика». — Иркутск, ГОУ ВПО „ИГПУ", 2004. - С. 153-155.

[4] Коршунова H.JI. (Семичева Н. JI.) Алгоритм представления частичных булевых функций бесповторными термами и его программная реализация / Н. Л. Коршунова // Материалы Конференции-конкурса работ студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования». — Новосибирск, 2006. — С. 192-193.

[5] Семичева Н. Л. Представление недоопределенных частичных булевых функций бесповторными термами / Н. Л. Семичева // Материалы российской школы-ссминара «Синтаксис и семантика логических схем». — Владивосток, 2008. — С. 45-47.

[6] Семичева Н. Л. Бесповторное предсталение недоопределенных частичных булевых функций / Н. Л. Семичева // Материалы XV международной конференции «Проблемы теоретической кибернетики». — Казань, 2008. — С. 105.

Редакционно-издательский отдел государственного образовательного учреждения высшего профессионального образования «Иркутский государственный педагогический университет» 664003, Иркутск, ул. Нижняя Набережная, 6

Формат бумаги 60x84 1/16. Объем 1,0 п.л. Тираж 100 экз.

Отпечатано в ОКИС ИГПУ 664003, Иркутск, ул. Нижняя Набережная, 6

Введение

Глава 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] показали, что бесповторные функции преобладают при описании работы цифровых вычислительных машин.

С другой стороны, при исследовании слабоповторпых функций (повторных булевых функций в некотором базисе J5, у которых все собственные остаточные подфункции являются бесповторными в В) было показано, что добавление слабоповторной в базисе В функции к этому базису, существенно увеличивает число бесповторных функций [?].

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

Существуют разные подходы к описанию бесповторных предстале-ний булевых функций. Начало одному из подходов положил В. А. Гур-вич [12, 13] Его теорема явилась началом, так скажем, «графического» подхода к нахождению бесповторного представления булевых функций и развивалась в основном на западе. Первый шаг в этом направлении сделал сам В. А. Гурвич [12]. Затем J. P. Hayes [56] разработал алгоритм распознавания бесповторности булевых функций и получения самого такого представления на основе связности переменных. Но предложенный им алгоритм имел слишком большую сложность. Затем J. Peer и R.Pinter [59] улучшили его результат. Но алгоритм все равно имел более чем полиномиальную сложность в следствие необходимости перевода ДНФ в КНФ и обратно. М. С. Golumbic, A. Mintz и U. Rotics [54, 55] нашли способ преодалеть этот барьер. Преложенный ими алгоритм базируется на свойствах кографа, двойственных фукциях и теореме Гурвича. Данный алгоритм находит бесповторное представление функции за полиномиальное время. Параллельно с ними почти аналогичный алгоритм предложили D. Angluin, L. Hellerstein и М. Karpinsky [51]. Сложностью при использовании последних двух алгоритмов связана с тем, что на вход должна подаваться функция в форме сокращеной ДНФ или КНФ.

Другой подход, основанный на результатах А.В.Кузнецова [16] и Г.Н.Поворова [40], о представлении функции в виде суперпозиции двух неунарных функций с непересекающимися множествами переменных. Так как для построения излагаемых в данной работе алгоритмов выбран именно этот подход, основные определения и теоремы, связанные с ним, будут изложены ниже. Важно отметить, что первый подход позволяет находить бесповторное представление функций только в элементарном базисе. А учитывая, что функциональный элемент «исключаючее или» приобретает все большее распространение в связи с тем, что его использование в большинстве случаев приводит к получению термов с меньшей сожностью, первый подход становится менее актуальным.

Второй же подход не накладывает никаких ограничений на базис, и в [31, 15] описаны алгоритмы распознавания бесповторности булевых функций и получения их бесповторного представления в базисах двух и трехместных функций.

А. А. Вороненко [6, 8, 5, 7, 9] разработал алгоритм линейной сложности для распознавания бесповторности всюду определенных булевых функции в любом наследственном базисе.

Большое практическое значение имеют функции, определенные не на всех наборах значений переменных. Как правило, на тех наборах, на которых значение функции не определено, неопределенность понимается как возможность принятия и значения 0, и значения 1, и называются такие функции частичными булевыми функциями. Естественно, минимизировать такие функции является гораздо более сложной задачей. Например, если применять первый подход получения бесповторного представления функций к нахождению бесповторного терма, представляющего частичную функцию, нам необходимо будет выполнить следующие действия: 1) подставить конкретные значения на те позиции, где функция неопределена; 2) найти сокращенную ДНФ этой функции; 3) применить алгоритм; 4) если бесповторное представление не будет найдено, повторить действия с 1-ого по 4-ое. Учитывая, что таких подстановок может быть 2к, где к — число позиций, в которых функция неопределена, тогда время, необходимое на исследование функции на бесповторность, может значительно возрасти.

Поэтому разрабатываются алгоритмы минимизации, применимые конкретно к частичным функциям [2]. В некоторых случаях сужают исходную задачу ввиду высокой алгоритмической сложности ее решения в общем виде. Я. Хлавичка и П. Фишер [57] дают алгоритм минимизации сильно неопределенных булевых функций. То есть определена функция должна быть только на 10-20 позициях. Этот алгоритм интересен тем, что одинакого быстро справляется с поставлнной задачей как для функций, зависящих от 10 переменных, так и для функций, зависящих от 100 переменных. Но, к сожалению, он абсолютно неприменим для решения задачи в общем случае. Еще один частный случай решения задачи представления частичных булевых функций термами рассмотрен в работах Е. Boros, V. Gurvich, P.L. Hammer [52], решающий вопрос о представлении частичной функции термами с заданной структурой. То есть они отвечают за полиномиальное время, например, на такой вопрос: можно ли представить функцию / термом вида / = g(hi(Si), /12(^2), -S3), где Si, S2, S3 также являются термами? К сожалению, при этом не находятся термы Si, S2, S3.

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

Далее рассмотривается другой вид не всюду определенных функций, так называемых частичных недоопределенных булевых функций. Эти функции рассматривались в [17, 22, 23, 25, 34, 35, 36, 37, 38, 39]. Первый вид неопределенности совпадает по смыслу с описанным ранее и называетя «недоопределено». Второй вид неопределенности возникает, когда набор а отображается в пустое множество. То есть функция не принимает на данном наборе никакого значения, или принимает запрещенное значение. Такой вид неопределенности будет называться «частично». Так как при работе дискретных устройств возникает и тот и другой вид неопределенности [17], поэтому актуальной задачей является исследование таких функций.

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

Заключение

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

1. Алгоритм представления недоопределенных булевых функций бесповторными термами в бинарным базисе, доказательство корректности этого алгоритма.

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

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

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

Работа над диссертацией была поддержана Российским фондом фундаментального исследования, проект 07-01-00240.

1. Дискретная математика и математические вопросы кибернетики. Под редакцией Яблонского С. В. и Лупанова О. Б. — М.: Наука, 1974, Т. 1. - 312 с.

2. Избранные вопросы теории булевых функций / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков, О. В. Зубков, К. Д. Кириченко, В. И. Пантелеев, Н. А. Перязев, Ю. В. Перязева; Под ред. С. Ф. Винокурова и Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

3. Алексеев В. Б. О некоторых замкнутых классах в частичной двузначной логике/В. Б. Алексеев, А. А. Вороненко // Дикретная математика. — 1994. — Том 6. Вым. 4, — С. 58-79.

4. Артюхов В. Л. Настраиваемые модули для управляющих логических устройств / В. Л. Артюхов, В. Л. Копейкин, А. А. Шалыто. — Ленинград: Энергоиздат, 1981. — 166 с.

5. Вороненко А. А. Бесповторность распознается схемами линейной сложности / А. А. Вороненко. // Дискретная математика. — 2005. — Том 17. Вып. 4. С. 111-115.

6. Вороненко А. А. О методе разложения для распознавания принадлежности инвариантным классам / А. А. Вороненко. // Дискретная математика. 2002. - Том 14. №4. - С. 110-116.

7. Вороненко А. А. Распознавание бесповторности в произвольном базисе / А. А. Вороненко. // Прикладная математика и информатика. М.: Макс-Пресс, 2006. — Вып. 23. - С. 67-84.

8. Вороненко А. А. Бесповторность распознается схемами линейной сложности / А. А. Вороненко. // Труды VI международной конференции <Дискретные модели в теории управляющих систем». — М.: ВМиК МГУ. 2004. - С. 25-26.

9. Вороненко А. А. Бесповторные булевы функции/ А. А. Вороненко. — М.: Макс-Пресс, 2006. — 61 с.

10. Глушков В. И. Синтез цифровых автоматов / В. И. Глушков. — М: Физматлит, 1962. — 476 с.

11. И. Глушков Р. М. Логическое проектирование дискретных устройств / Р. М. Глушков, Ю. В. Капитонова, А. Т. Мищенко. Киев: Наукова думка, 1987. — 264 с.

12. Гурвич В. А. О бесповторных булевых функциях / В. А. Гурвич // Успехи мат. наук. 1977. - Том 32, № 1. - С. 183-184.

13. Гурвич В. А. Критерий бесповторности функций алгебры логики / В. А. Гурвич // Докл. АН СССР. 1991. - Т. 318, № 3. - С. 532-537.

14. Кириченко К. Д. О критериях бесповторности булевых функций в различных базисах / К. Д. Кириченко // Оптимизация, управление, интеллект. — Иркутск, 2000. — Вып 4. — С. 93-101.

15. Кузнецов А. В. О бесповторных контактных схемах и бесповторныхусуперпозициях функций алгебры логики / А. В. Кузнецов // Труды Математического института им. В. А. Стеклова. — М.: Изд-во АН СССР, 1958. Т. 51. - С. 186-225.

16. Ложкин С. А. О синтезе формул и схем из не всюду определенных функциональных элементов / С. А. Ложкин // Труды VI международной конференции «Дискретные модели в теории управляющих систем». М.: ВМиК МГУ. - 2004. - С. 44-47.

17. Лупанов О. Б. О сложности реализаций функций алгебры логики формулами / О. Б. Лупанов // Проблемы кибернетики. Вып. 3. — М.: Физматлиз, 1960. С. 61-80.

18. Марченков С. С. Замкнутые классы булевых функций / С. С. Мар-ченков. — М.: Физматлит, 2000. — 128 с.

19. Нигматуллин Р. Г. Сложность булевых функций / Р. Г. Нигматул-лин. — М.: Наука, 1991. — 240 с.

20. Пантелеев В. И. Обобщенная интерпретация переменных: семантическое исследование и логический вывод / Н. А. Перязев , В. И. Пантелеев // Материалы школы «Пятая школа моложых математиков Сибири и Дальнего Востока». — Новосибирск, 1990. — С. 87-89.

21. Пантелеев В. И. Недоопределенные частичные булевы функции и булевы уравнения / Н. А. Перязев , В. И. Пантелеев // Материалы VII Международной конференци «Дискретные модели в теории управляющих систем». — М.: ВМиК МГУ, 2006. С. 262-265.

22. Пантелеев В.И. О недоопределенных булевых функциях / В. И. Пантелеев // Материалы школы-семинара «Синтаксис и семантика логических систем». — Иркутск, 2006. С. 78-79.

23. Пантелеев В. И. Логика предикатов при обобщенной интерпретации переменных / Н. А. Перязев, В. И. Пантелеев // Вестнике БГУ. Серии 13: Математика и информатика. — 2005. — Вып. 2. — Улан-Уде. С. 39-45.

24. Пантелеев В.И. Клоны недоопределенных частичных булевых функций / В. И. Пантелеев // Материалы российской школы-семинара «Синтаксис и семантика логических схем». — Владивосток, 2008. — С. 42-43.

25. Перязев Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Фундаментальные проблемы математики и механики. Математика. — М.: Изд-во МГУ, 1994. — С. 320.

26. Перязев Н. А. Представление функций алгебры логики бесповторными формулами / Н. А. Перязев // Материалы XI Международной конференции по математической логике. — Казань, 1992. — С. 35.

27. Перязев Н. А. Алгебраическая характеризация бесповторных булевых функций в некоторых базисах / Н. А. Перязев // Материалы III Международной по алгебре. — Красноярск, 1993. С. 260.

28. Перязев Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Методы и системы технической диагностики. —1993. Вып. 18. - Красноярск. - С. 138-139.

29. Перязев Н. А. Реализация булевых функций бесповторными формулами в некоторых базисах / Н. А. Перязев // Сб. Алгебра, логика и приложения. — Иркутск, 1994. — С. 143-154.

30. Перязев Н. А. Реализация булевых функций бесповторными формулами / Н. А. Перязев // Дискретная математика. — 1995. — Т. 7. № 3. С. 61-68.

31. Перязев Н. А. Сложность представлений булевых функций формулами в немонолинейных базисах / Н. А. Перязев // Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 2. — Иркутск, 1995. — 15 с.

32. Перязев Н. А. Основы теории булевых функций / Н. А. Перязев. — М.: Физматлит, 1999. — 112 с.

33. Перязев Н. А. О недоопределенных булевых функциях Н. А. Перязев. // Материалы школы-семинара «Синтаксис и семантика логических систем». — Иркутск, 2006. С. 80-81.

34. Перязев Н.А. Алгебра не всюду определенных функций / Н. А. Перязев. // Труды международной конференци «Алгебра и ее приложения>". — Красноярск, 2007. — С. 104.

35. Перязев Н.А. Функциональные системы недоопределенных частичных функций / Н. А. Перязев. // Материалы Международного семинара «Дискретная математика и ее приложения>". — М.: Изд-во ММФ МГУ, 2007. - С. 173-174.

36. Перязев Н. А. Недоопределенные частичные булевы функции / Н. А. Перязев. // Материалы XV международной конференции «Проблемы теоретической кибернетики». — Казань, 2008. — С. 92.

37. Перязев Н. А. Суперклоны недоопределенных частичных функций / Н. А. Перязев. // Материалы российской школы-семинара «Синтаксис и семантика логических схем». — Владивосток, 2008. — С. 40-42.

38. Поваров Г. Н. О функциональной разрешимости булевых функций / Г. Н. Поваров// Докл. АН СССР. 1954. - Т. 94, № 5. - С. 801-803.

39. Стеценко В. А. Об одном необходимом признаке для предмакси-мальных базисов в Р2 / В. А. Стеценко // Докл. АН СССР. — 1990. — Т. 315. С. 1304-1307.

40. Стеценко В. А. О предплохих базисах в Рч / В. А. Стеценко // Математические вопросы кибернетики. — 1992. —Вып. 4. — С. 139— 177.

41. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами / Б. А. Субботовская // Докл. АН СССР. 1963. - Т. 149, № 4. - С. 784-787.

42. Сэвидж Д. Э. Сложность вычислений / Д. Э. Сэвидж — М.: <Факториал», 1998. — 368 с.

43. Угольников А. Б. Класс Поста. Учебное пособие / А. Б. Угольников М.: Издательство ЦПИ при ММФ МГУ, 2008. — 64 с.

44. Черухин Д. Ю. Алгоритмический критерий сравнения булевых базисов /Д. Ю. Черухин // Математические вопросы кибернетики. — 1999. —Вып. 8. С. 77-122.

45. Шоломов JI. А. Основы теории дискретных логических и вычислительных устройств / J1. А. Шоломов // М.: Наука, 1980. — 400 с.

46. Яблонский С. В. О суперпозициях функций алгебры логики / С. В. Яблонский // Математический сборник. — 1952. —Т. 30. —№ 2. — С. 329-345.

47. Яблонский С. В. Функции алгебры логики и классы Поста / С. В. Яблонский, Г. П. Гаврилов, В. Б. Кудрявцев. — М.: Наука, 1966. — 120 с.

48. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов. / под ред. В. А. Садовничего / С. В. Яблонский. — 3-е изд., стер. — М.: Высш. шк., 2001. — 384 с.

49. Angluin D. Learning read-once formulas with queries / D. Angluin, L. Hellerstein, M. Karpinski // University of California at Berkeley. — 1989.

50. Boros E. Decomposition of partially defined boolean functions/ E. Boros, V. Gurvich, P.L. Hammer // Special volume on partitioning and decomposition in combinatorial optimization — 1995. — P.51-75.

51. Brayton R. The decomposition and factorization of boolean expressions / R. Brayton, C. McMullen // Proc. Internat. Symp. on Circuits and System. — Rome, 1982. — P. 49-54.

52. Golumbic M. Factoring and recognition of read-once functions using cographs and normality / M. Golumbic, A. Mintz, U. Rotics // 38th conference on Design automation. — Las Vegas. — 2001. — P. 109114.

53. Golumbic M. Factoring logic functions using graph partitioning / M.LGolumbic, A. Mintz // International Conference of Computer^ Aided Design. — 1999. — P. 1995.

54. Hayes J. P. The fanout structure of switching functions / J. P. Hayes // Journal of the ACM. — 1975. — P. 551-571.

55. Hlavicka J. Algorithm for minimization of partial functions / J. Hlav-icka, P. Fiser // Design and Diagnostics of Electronic Circuits and Systems Workshop — Bratislava. — 2000. — P. 130-133

56. Newman I. On read-once booleanfunctions /I. Newman // London mathematical society simposiam on Boolean function complexity. — London, 1968. — P. 175-188.

57. Peer J. Minimal decomposition of boolean functins using nonrepeating literal trees / J. Peer, R, Pinter // Workshop on Logic and Architecture Synthesis. — Grenoble, 1995. — P. 129-139.

58. 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.

59. Post E. L. Two valued iterative systema of mathematical logic / E. L. Post // Annals of Math. Studies. — 1941. —No 5.

60. Shannon С. E. A symbolic analysis of relay and switching circuits / С. E. Shannon // Trans. AIEE. — 1938. — V. 57. — P. 713-723.

61. Shannon С. E. The synthesis of two terminal switching circuits / С. E. Shannon // Bell. System. Techn. J. — 1949. — V. 28. — P. 5998.

62. Stetsenko V. On almost bad Boolean bases / V. Stetsenko // Theoretical Computer Science. — 1994. — V. 136. — P. 419-469.

63. Работы автора по теме диссертации

64. Коршунова H.J1. (Семичева Н. J1.) Представление частичных булевых функций бесповторными термами над бинарным базисом / Н. JI. Коршунова // Вестник ВГУ. Серия 13: Математика и информатика. 2005. - Вып.2. — С. 26-35.

65. Семичева Н. JI. Бесповторное предсталение недоопределенных частичных булевых функций /Н. JI. Семичева // Материалы XV международной конференции «Проблемы теоретической кибернетики». — Казань, 2008. С. 105.

66. Семичева Н. J1. Представление недоопределенных частичных булевых функций бесповторными термами/Н. JI. Семичева // Материалы российской школы-семинара «Синтаксис и семантика логических схем». — Владивосток, 2008. С. 45-47.

67. Семичева Н. J1. Нахождение бесповторных представлений недоопределенных частичных булевых функций/Н. Л. Семичева. — — Иркутский государственный педагогический университет. Серия: Дискретная математика и информатика. Вып. 19. — Иркутск, 2008. — 35 с.