Сложность и алгоритмы построения проверяющих тестов и некоторых классов полиномиальных форм булевых функций тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Рябец, Леонид Владимирович

• Рябец, Леонид Владимирович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Рябец, Леонид Владимирович

Введение

Глава 1. Сложность некоторых классов полиномиальных форм булевых функций

§ 1. Сложность вложения специальной операторной формы в класс Кь

§ 2. Сложность булевых функций и кронекеровы спектры

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

§ 3. Алгоритм построения проверяющих тестов.

§ 4. Функция Шеннона для проверяющих тестов относительно бесповторной альтернативы.

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

§ 5. Алгоритм получения сложности специальной операторной формы.

§ 6. Алгоритм нахождения минимального представления функции в классе кронекеровых форм.

§ 7. Алгоритм приближенной минимизации функции в классе полиномиальных нормальных форм.

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

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

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

Задачу правильности функционирования логических устройств можно рассматривать как на структурном, так и на макроуровне. Решение задачи на макроуровне осуществляется с помощью тестового подхода, предложенного С.В. Яблонским [27]. Его суть заключается в следующем. Пусть имеется некоторое логическое устройство с п входами и 1 выходом, реализующее некоторую булеву функцию /. Если логическое устройство ломается, то начинает функционировать другим образом, реализуя при этом функцию д, называемую функцией неисправности.

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

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

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

Исследованию различных характеристик тестов посвящен целый ряд работ, например [18, 23, 24].

Одним из подходов, позволяющих избежать проверки всех наборов функции, является ограничение множества булевых функций, которые могут возникнуть в результате неисправностей логического устройства [49]. В работах [10, 16] получены сложности проверяющих тестов для функций классов Поста. Один из последних обзоров по тестированию содержится в [17].

Интересным классом для исследования сложности тестов является класс бесповторных булевых функций. Схемы, реализующие бесповторную функцию, в случае константных неисправностей и нарушений работы элементов, сохраняют свойство бесповторности. Для бесповторных функций, существенно зависящих от всех своих переменных, в различных базисах получены оценки для функции Шеннона [8, 9]. В данной работе найдено точное значение функции Шеннона для проверяющих тестов относительно бесповторной альтернативы — тестов для бесповторных булевых функций, существенно зависящих от всех своих п переменных, на множестве всех бесповторных булевых функций размерности п.

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

Одним из основных способов задания булевых функций является формульное или, иначе, термальное представление. Вопрос о принципиальной возможности реализации тех или иных булевых функций формулами с использованием специально выбранных базисных функций был решен Э. Постом [38, 39].

Хорошо исследован вопрос о реализации булевых функций дизъюнктивными и конъюнктивными нормальными формами [22, 36]. Но полученные высокие нижние оценки сложности, совпадающие с верхними, наложили определенное ограничение на возможность практической реализации таких нормальных форм.

В конце прошлого века в связи с бурным развитием цифровой техники стали активно использоваться элементы типа "сложение по модулю 2" (EXOR). Это дало новый толчок в развитии исследований по полиномиальным представлениям булевых функций [13, 41]. Было замечено, что при использовании полиномиальных нормальных форм часто получаются представления булевых функций меньшей сложности, кроме того, схемы, построенные с использованием элементов EXOR обладают лучшей тестируемостью.

Впервые полиномиальные нормальные формы были рассмотрены И. И. Жегалкиным при исследовании некоторых вопросов математической логики [11, 12]. Затем, в 50-х годах прошлого века, полиномиальные нормальные формы исследовались в связи с их применением в теории кодирования [37, 40]. Однако вопрос сложности представлений булевых функций полиномиальными нормальными формами остается открытым, известные нижняя [32] и верхняя [15] оценки не совпадают.

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

Ti = [l,®], Т2 = М, Т3 = [х,х].

В этом классе, например, третий базис определяет базис для совершенных полиномиальных нормальных форм, первый — для полиномов Жегалкина. Исследованиям кронекеровых форм посвящены работы [1, 2, 30, 31, 34, 35]. В диссертации найден алгоритм нахождения минимальной сложности булевой функции в классе кронекеровых форм.

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

На языке операторов была сформулирована новая каноническая форма булевых функций — специальная операторная форма [50]. Вид специальной операторной формы оказался очень тесным образом связан со свойствами полиномиальных представлений булевых функций. В диссертации решен вопрос о ее связи со сложностью функций в классе ПНФ. Приблизительным аналогом этого представления может служить специальная нормальная форма, описанная в работах [43, 44].

Значительным и мощным аппаратом для работы с булевыми функциями являются спектральные методы. В основе таких методов лежат дискретные преобразования Уолша и Рида-Маллера. Сами методы нашли широкое применение в логическом синтезе и логическом проектировании (определение эквивалентностей различного типа) [25]. В ряде работ были предложены различные методы нахождения спектров булевых функций: на основе матричных преобразований [25, 42], представлений функций в виде бинарных диаграмм решений [29, 45, 48], с использованием вероятностных методов [46, 47]. В первой главе диссертации с помощью операторного подхода обобщено понятие спектра Рида-Маллера и введено понятие кронекерова спектра булевых функций. Для такого типа спектров предложен метод их нахождения с использованием операторов и получена связь со сложностью булевых функций в классе кронекеро-вых форм.

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

Пусть <Ji £ {0,1}, г Е {1,., п}, тогда выражение (<j\, 02,., стп) (или для простоты (7i,<T2, ., <Jn) называется двоичным набором или просто набором и обозначается а, а число п называется длиной этого набора. Если длина набора а явно не указана, она определяется по контексту. Множество всех наборов длины п будем обозначать через Еп. Очевидно, что количество наборов длины п равно 2". Набор (0,., 0) будет обозначаться через 0, а набор (1,., 1) — через 1. Размерность этих наборов всегда определяется по контексту.

Будем считать, что двоичные наборы д\,.,ат, где т = 2п, упорядочены по натуральному порядку, если для всех s Е {1,. ,ш} выполняется условие п

8= 1 + i=1 где д3 = erf,., asn. Заметим, что двоичные наборы Ъ\,., am, т = 2П, упорядоченные по натуральному порядку, представляют натуральные числа 0,., 2п—1, записанные в двоичном исчислении. При натуральном порядке первым будет набор 0, а последним — 1. Двоичные наборы часто будут использоваться в качестве индексов. В этих случаях будем считать, что они упорядочены по натуральному порядку.

Пусть f = 7"i,., тп — двоичный набор. Тогда набор т = т\,., тп назовем отрицанием набора т.

Булевой функцией далее просто функцией называется отображение из (0,1}п в {0,1}. При этом п называется размерностью функции. Множество всех функций размерности п обозначается через Fn, множество всех функций — F. Бывает удобно представлять функцию в векторном виде. В дальнейшем это представление часто используется. Двоичный вектор (org,., ckj) представляет функцию / £ Fn, если = /(<т), где наборы & £ Еп упорядочены по натуральному порядку.

Пусть В С F и X — некоторое множество символов, называемых переменными. Индукцией определим понятие терма над В от множества переменных X:

1) переменная х из X есть терм;

2) если символом / обозначается функция размерности т, принадлежащая В, и Ф1,., Фт — термы, то /(Ф1,., Фт) есть терм.

Запись

Ефш является сокращением для е фг-2 е • ■ • е Фгга, где / = {zi, «2,., im} — некоторое конечное индексное множество. Для удобства будем использовать обозначение: фв [ Ф если а = 0; 1 Ф, если а = 1.

Выражение xi,.,xn, где жг- £ X при г 6 {1,. ,п}, будем называть набором переменных и обозначать х, при этом п называется длиной набора переменных и чаще всего определяется по контексту.

Сопоставим набору переменных xi,.,xn один из наборов а множества Еп. Считаем, что задано значение переменных х, и для каждой Х{ задано значение Е {1,. ,п}. Определим значение терма Ф при заданных значениях переменных х\,., хп:

1) если Ф — переменная, то значение с совпадает со значением этой переменной;

2) если Ф = /(Фь ., Фт) и значения термов Фх,., Фт есть Т\,., тт соответственно, то значение терма Ф есть /(тi,., rm).

Пусть Ф — терм. Будем говорить, что функция / Е Fn пред ставима термом Ф, если существует упорядочение переменных xi,.,xn из множества переменных, входящих в терм, такое что Ф = f(xi,., хп).

Остаточными функциями от функции / по г-му аргументу называются функции, размерности которых на единицу меньше размерности /, и определяются они следующим образом: для любого f G Еп~1. Если сг; = 0, то остаточная функция называется нулевой остаточной; если <тг- = 1, то — единичной остаточной.

Производной функцией от функции / по г-му аргументу называется функция, размерность которой на единицу меньше размерности /. Определяется производная функция следующим образом: для любого т Е Еп 1.

Полиномиальной нормальной формой (ПНФ) называется терм вида где каждое слагаемое Ф; — элементарное произведение, то есть выражения вида fp(r1, . . . , Tni) = /(ti, . . . , Tjb £7i, Ti, rni) fi(r1, . . . , r„i) = //(rb ., r„i) e /P(ri,., Tn-i)

Ф1 0 9 • • • Ф Ф;

771) в которых все Xjs различны, crs £ {0,1}, s € {1,., к}, к < п. Элементарным произведением при к = 0 будем считать константу 1. Под сложностью Ь(Ф) полиномиальной нормальной формы понимают количество входящих в нее элементарных произведений переменных.

Сложность Ьпнф(/) функции / в классе полиномиальных нормальных форм — это наименьшее число элементарных произведений переменных, необходимое для реализации ее в виде ПНФ: пнф(Я = здесь Ф — всевозможное представление функции в виде ПНФ.

Для оценок сложности представлений в теории булевых функций принято использовать функцию Шеннона, которая определяется как сложность самой сложной функции среди всех функций данной размерности в том или ином классе представлений. Для класса полиномиальных нормальных форм функция Шеннона Ьпиф(п) определяется следующим образом:

Ашф (п) = тах£пнф(/). f€Fn

Операторные формы булевых функций были введены С. Ф. Винокуровым и Н. А. Перязевым [3, 4, 5, 6, 28]. Основной идеей построения операторных полиномиальных форм служит представление базисных функций канонической формы в виде операторных образов некоторой функции от определенного набора — базисного пучка — операторов. Существование, по крайней мере, одной такой функции и таких пучков гарантируют приведенные канонические формы — полином Жегалкина и его обобщения. Общая форма таких полиномов выглядит следующим образом: f(xh.,xn) = ipf(g(xh.,xn)), feEn где ipf : Fn Fn — операторы на множестве всех булевых функций от п переменных.

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

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

Последовательность символов aia2.an, такая что а* 6 {е,р,d} при i £ {1 ,.,п}, называется оператором и обозначается а, ее члены называются компонентами оператора, а число п — длиной оператора. Пустая последовательность задает единственный оператор длины 0. Обозначим его 0. Оператор а длины п задает отображение из Fn в Fn по правилу а/(£) = /п(х), где fn{x) определяется по индукции следующим образом: f0(x) = f(x),

Ifi-i{x), если aj = е; fi-i(x), если а; = р; fi-i(x) ф /»-1(£), если а * = d, л где fi-i(x) = fi-i(xh Xi-i, Xi, xi+i, .,xn),i E {1,., n}. В некоторых случаях, для явного указания области действия оператора будем использовать обозначение a(f(x)).

Множество, состоящее из 2" операторов длины п называется пучком операторов, а число п называется размерностью этого пучка операторов. Пучки операторов будем также называть операторными пучками или просто пучками. Если аа — это оператор из какого-либо пучка, то запись а^ означает г'-й компонент оператора аа. В пучке все операторы имеют одну размерность, длина или количество операторов пучка всегда связана с этой размерностью. А именно, длина пучка операторов размерности п всегда равна 2П.

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

Свойства таких операторов и операторных пучков подробно рассмотрены в [14].

При исследовании классов операторных форм необходимо точно знать, является ли пучок операторов базисным. Ответ на этот вопрос дает следующая теорема.

Теорема I ([14]). Любой двупорожденпый пучок является базисным. Причем базисной функцией моо/сет быть любая функция, в векторном представлении которой присутствует нечетное число единиц.

Пучок операторов А = (а0,., ат,., а1) будем называть двупорожденным, если существуют такие операторы b = bo. Ъп и с = со. сп, bi ф сi для любого г, что оператор а7" = ti. tn пучка А определяется следующим образом:

Класс всех дву порожденных пучков обозначим Н. Следующая теорема связывает двупорожденные пучки и кронеке-ровы базисы.

Теорема II ([14]). Любой кронекеров базис моо/сет быть представлен в виде операторных образов подходящего двупорожденного пучка и функции Х\ •. • хп.

Таким образом, при базисной функции д(х\,., хп) = х\ •. -хп класс Н всех двупорожденных пучков операторов порождает класс кронекеровых форм К. ные образы {Ь °д(х),.Ъ1д(х)} образуют базис линейного пространства

Ьг-, если ц = 0; С;, если Tj = 1. Eb*

Непосредственно на операторах можно ввести операцию "сложение". Для этой операции также будет использоваться символ "©" или Будем говорить, что t а i=1 тогда и только тогда, когда для любой функции f(x) имеет место равенство: t i=1

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

Теорема III ([14]). Для любого оператора b существует единственный (с точностью до перенумерации операторов) двупорожденный пучок операторов А = (а0,., ат,., а1), такой что имеет место равенство: т размерности оператора b и операторов из пучка А совпадают.

Теорема III позволяет ввести новое операторное представление. Пусть (Ь1,., Ы) — набор операторов размерности п. Выражение t f{xi,., хп) = Ъг (g(x 1,., ж„)) (1) i=1 будет называться операторной формой {OF) функции f(x\,. ,хп) по функции g(xi,., хп). Операторная форма называется редуцированной, если в ней нет одинаковых слагаемых. Очевидно, что любую операторную форму можно редуцировать, проведя сокращение пар одинаковых слагаемых.

Если операторы Ь1,., Ь4 — из базисного пучка В, то это представление будем называть операторной формой функции / по пучку В.

Пусть R(OF) обозначает операцию приведения операторной формы OF к редуцированной форме.

По теореме III для любого оператора Ъ1 из (1) найдется двупорож-денный пучок операторов А; = (а0,г,., а1'1), что имеет место равенство:

В равенстве (1) каждый оператор можно заменить на соответствующую сумму и полученное выражение редуцировать. После редуцирования для функции f(x 1,., хп) получается выражение:

Это представление функции f(xi,.,xn) будет называться специальной операторной формой (СОФ) этой функции по функции д{х 1,., хп) и обозначаться SOFgf(xi,., хп).

Свойства специальной операторной формы более подробно рассмотрены в [7] и [50].

Под сложностью представления \OF^(f)\ функции f(x 1,.,жп) операторной формой OF по функции д(х\,., хп) по пучку операторов В понимается число ненулевых слагаемых в OF.

Пусть К — класс операторных пучков. Тогда Lf(f) = min \OFf{f)\ век назовем сложностью функции f(xi,. ,хп) в классе операторных форм К по функции g(xi,., хп).

Через OF обозначим класс всех операторных форм. Тогда Lg(f) = L°F(f) называется сложностью булевой функции f(xi,., хп) в классе операторных форм по функции д(х\,., хп).

Пусть Fn — множество всех булевых функций п переменных. Тогда L^(n) = maxL^-(f) назовем сложностью всех булевых функций, зависящих от п переменных, в классе операторных форм К по функции д(х i,.,zn). т f(xh ., хп) = R £ g af,i(g(x\,., хп)) i=i f

Связь между сложностью операторных полиномиальных форм и сложностью полиномиальных нормальных форм была установлена в [б].

Теорема IV ([6]). Для любой функции f G Fn

Ашф(/) = LXv.Xn(f).

Следующая теорема дает точное значение функции Шеннона для класса кронекеровых форм.

Теорема V ([2]). Значение функции Шеннона для класса кронекеровых форм определяется по формуле: 2

Lfv.,Xn(n) = • 2П 3

Для булевых функций можно определить понятие спектра. Известный спектр Рида-Маллера для булевой функции f(xi,., хп) определяется следующим образом. Пусть функция / имеет совершенную дизъюнктивную форму: f(xh.,xn) = \J ад деЕп xai •. • я17" где € {0,1} . Тогда спектром Рида-Маллера функции / называют функцию fT такую, что f(x ь .,хп)= £ •. • • • , аеЕп где г+ j 1, если т = 0; 1 х, если т — 1. Пусть кронекерово произведение двух матриц А = и В определяется следующим образом: апВ . ainB A(g)B= ; ; OLmXB . . .

Спектр fT может быть также представлен в виде матричного произведения: f = A-f, где

Подробнее свойства спектра Рида-Маллера, а также спектра Уолша, рассмотрены в обзоре [25].

Пусть Ф — терм от множества переменных х. Такой терм Ф называется бесповторным, если каждая переменная входит в него не более одного раза.

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

Далее будем рассматривать булевы функции, представимые бесповторным термом в бинарном базисе В = {—V, ф}. Каждый терм Ф над базисом В может быть представлен в виде терма Ф', в котором отрицания встречаются только над переменными. Такой вид терма можно получить применением следующих преобразований: хку) = х V у, (х V у) = хку, (х © у) = х ® у.

Аналогично, любой терм Ф может быть преобразован в не содержащий констант терм Ф' путем применения следующих тождеств:

Ф V 1 = 1, ФУ0 = Ф, Ф&1 = Ф, ф&о = 0, ф е 1 = ф, ф © о = ф.

Пусть S — множество булевых функций, зависящих от переменных •^Ь • • • 1 хп. Пусть f(x\,.,xn) принадлежит множеству S. Множество наборов М называется проверяющим тестом для функции / на множестве S, если для для любой функции ., хп) из S, не равной тождественно /, в М найдется хотя бы один набор а такой, что д(д) ф f(a) [21].

Множество всех проверяющих тестов для функции / на множестве S обозначим Test(f,S). Под сложностью или длиной проверяющего теста М для функции / понимается количество наборов в тесте. Сложность теста М обозначается \М\.

Пусть RFn — множество всех бесповторных булевых функций размерности п. Пусть f(x 1,., хп) — бесповторная функция, существенно зависящая от всех своих переменных. Проверяющий тест для функции / на множестве RFn называется тестом относительно бесповторной альтернативы [9].

Функция Шеннона Т(п) для класса бесповторных функций вводится обычным образом:

Tin) = max min \М\, 4 feRFn Мет1 где RFn — множество всех бесповторных булевых функций размерности п, существенно зависящих от всех своих переменных, Т' обозначает Test(f, RFn) — множество всех тестов относительно бесповторной альтернативы для функции /.

Пусть бесповторная функция f(x i,.,xn) существенно зависит от всех своих переменных, и для некоторого набора (cki, ., Щ-1, аг-+1,., ctj-1, aj+i,., ап) остаточная функция о; 1, . . . , (Х{-1, Х{, Q^j+l, . . , CXj—lj CXj+ь • • • j является существенной. Тогда множество наборов ai,., i, 0, ai+h ., 0, aj+h .,ап) (q;i, ., ai-1,0, ai+i,., 1, aj+h .,an) («1,., аг,- i, 1, ai+h aj-i, 0, aj+h .,an) (ah., a>i-i, 1, ai+h ., a>j-h 1, aj+ь .,an) называется квадратом существенности переменных xi и Xj для функции / и обозначается S(xi,xj) [9].

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

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

Теорема VI ([9]). Мноэюество квадратов существенности произвольной бесповторной булевой функции является проверяющим тестом относительно бесповторной альтернативы.

Для функций, представимых бесповторными термами над базисом В — {-I, V, &, ©} справедлива следующая теорема.

Теорема VII ([9]). Для функции Шеннона Т(п) для тестов относительно бесповторной альтернативы при п > 2 выполняются соотношения

Zi

Однако, в [8] показано, что для булевых функций, бесповторных над элементарным базисом Bq = {0,1, &;, V, ->} тест относительно бесповторной альтернативы имеет линейную сложность.

Теорема VIII ([8])т Для функции Шеннона Т(п) для тестов относительно бесповторной альтернативы при п > 2 выполняются соотношения п + 1 < Т(п) < 3.5п.

В [16] для булевых функций из классов Поста найдены следующие значения функции Шеннона для проверяющих тестов

Теорема IX ([16]). Имеют место следующие соотношения:

1. Ti{n) = 2 для класса линейных функций;

2. Ts(n) = п + 1 для класса самодвойственных функций;

3. Тм{п) ~ 2п при п -» оо для класса монотонных функций.

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

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

Теорема 1.1. Для сложности представления SOFg(f) в классе Кь имеет место равенство

SOFg(f)\Kь = |M(SOFg(f)) п {а1'1,., где M(SOFg(f)) — миоэ/сество слагаемых в SOFg(f).

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

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

Lf(f) = |SOF„(/)|*b.

Согласно теореме II при д(х) = х\ • . • хп класс двупорожденных операторных пучков совпадает с классом кронекеровых форм. Этот факт позволил на основе предыдущей теоремы сформулировать алгоритм нахождения минимального представления булевых функций в классе кронекеровых форм.

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

Теорема 1.4. Пусть Н — класс двупорожденных операторных пучков ид — базисная функция. Тогда для любой булевой функции f справедливо равенство ш = \SOFg(f)\H

Во втором параграфе вводится понятие кронекерова спектра. Кро-некеров спектр булевых функций fK вводится как произведение матрицы кронекерова базиса М на вектор функции /, где матрица М — кронекерово произведение трех типов матриц a-KW11'

V10 / V01/

Основное свойство кронекеровых спектров дает следующее предложение

Предложение 1. Пусть f(x\,. ,хп) — булева функция. Тогда (.!к)к = /•

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

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

Теорема 1.5. Пусть f(x) имеет операторное представление t j=1 где оj составляют некоторый набор операторов. Тогда кронекеров спектр fK(x) функции f(x) по оператору а и базисной функции х\ • • хп modicuo представить следующим образом: t fK = ^tp(Oj)(xi-.-Xn),

3=1 где (р-(р\. • - Ц>п и каждый компонент ц>-г отображения определен следующим образом: dep ,если а{ — р; dep\

Pi = { | ,если ai = e; edp J dep\ если щ = a. dpe J

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

Теорема 1.6. Сложность функции f(x) связана с кронекеровыми спектрами по функции д(х) = х\ •. • хп соотношением:

Lf(f) = mmwt(f«),

J а где минимум берется по всем операторам а.

Вторая глава диссертации посвящена сложности проверяющих тестов относительно бесповторной альтернативы в базисе {->, V,&, 0}.

В третьем параграфе сформулирован алгоритм построения проверяющих тестов относительно бесповторной альтернативы с заранее известной сложностью.

В четвертом параграфе доказывается ряд вспомогательных утверждений, которые используются для доказательства теоремы о точном значении функции Шеннона для такого типа тестов. Теорема 2.1. Функция Шеннона Т{п) для тестов относительно бесповторной альтернативы удовлетворяет равенству г(„) = +1.

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

В пятом параграфе представлен алгоритм получения сложности вложения специальной операторной формы в класс пучков Къ

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

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

В диссертации используются следующие утверждения: предложения, теоремы, леммы, следствия. Предложения носят вспомогательный характер, леммы используются для структурирования доказательств теорем. Нумерация лемм, предложений и следствий — сплошная, нумерация теорем — двойная: первым идет номер главы, вторым — порядковый номер теоремы в главе. Теоремы, принадлежащих другим авторам нумеруются римскими числами. Формула нумеруются только в том случае, если на нее в тексте есть ссылка. Для формул используется сплошная нумерация.

Начало и конец доказательства предложения или леммы будут обозначаться соответственно символами О и <\, теоремы — ► и А.

Терминология, используемая в диссертации, наиболее приближена к [14, 20, 26]. Там же можно найти все неопределенные в настоящей работе понятия и обозначения.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Рябец, Леонид Владимирович

Заключение

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Рябец, Леонид Владимирович, 2007 год

1. Балюк А. С. О полиномиальных представлениях булевых функций / А. С. Балюк, С. Ф. Винокуров // Материалы VII Международного семинара «Дискретная математика и ее приложения». — М.: Изд-во Центра прикладных исследований МГУ, 2001. — С. 100-101.

2. Винокуров С. Ф. Некоторые оценки сложности булевых функций в классе полипомов / С. Ф. Винокуров // Синтез и сложность управляющих систем, VII Межгосударственная школа-семинар. — Минск, 1995. С. 4-5.

3. Винокуров С.Ф. Полиномиальная декомпозиция булевых функций по образам однородных операторов от невырожденных функций / С.Ф. Винокуров, Н.А. Перязев // Изв. вузов. Матем. — 1996. — № 1. С. 17-21.

4. Винокуров С.Ф. Полиномиальные операторные разложения и канонические формы булевых функций / С.Ф. Винокуров. — Иркутск: Из-во Иркутского ун-та. — 1992. — 26 с.

5. Винокуров С. Ф. Смешанные операторы в булевых функциях и их свойства / С. Ф. Винокуров. — Иркутский Университет. Серия: Дискретная математика и информатика. Вып. 12. — Иркутск, 2000. — 36 с.

6. Винокуров С.Ф. Специальная операторная форма булевых функций и некоторые ее приложения / С.Ф. Винокуров // Международнаяшкола-семинар "Синтез и сложность управляющих систем". — Новосибирск. Изд-во Института математики. — 2004. — С. 26-29.

7. Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0,1, &;, V/->} / А. А. Вороненко // Дискретная математика. — 2005. — Том 17. Выпуск 2. — С. 139-143.

8. Вороненко А. А. О проверяющих тестах для бесповторных функций / А. А. Вороненко // Математические вопросы кибернетики. — 2002. Вып И. - С. 163-176.

9. Долотова О. А. О минимальных проверяющих тестах функций из классов Поста / О. А. Долотова // Дискретная математика. — 1993. Том 5. Выпуск 2. - С. 75-82.

10. Жегалкин И. И. Арифметизация символической логики / И. И. Жегалкин // Мат. сборник. 1928. - Т.35. - С. 311-373.

11. Жегалкин И. И. Арифметизация символической логики / И. И. Жегалкин // Мат. сборник. 1929. - Т.36. - С. 305-338.

12. Закревский А. Д. Минимизация систем булевых функций в полиномах Жегалкина / А. Д. Закревский // Докл. Белорусской АН. — 1995. Т. 39, № 6. - С. 11-14.

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

14. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К. Д. Кириченко // Дискретная математика. 2005. - Т. 17, № 3. - С. 80-88.

15. Кудрявцев В. Б. Теория тестирования логических устройств / В. Б. Кудрявцев, Э. Э. Погосян, О. А. Долотова и др.; Под ред. В. А. Садовничего. — М.:Физматлит, 2006. — 160 с.

16. Кудрявцев В. Б. Теория тестового распознавания / В. Б. Кудрявцев // Дискретная математика. — 2006. — Том 18. Выпуск 3. — С. 3-34.

17. Носков В. Н. О сложности тестов, контролирующих работу входов логических схем / В. Н. Носков // Дискретный анализ. — Новосибирск: ИМ СО АН СССР, 1975. Том 27. - С. 23-51.

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

19. Редькин Н. П. Надежность и диагностика схем / Н. П. Редькин. — М.: Изд-во Моск. ун-та, 1992. 192 с.

20. Сапоженко А. А. Минимизация булевых функций в классе дизъюнктивных нормальных форм / А. А. Сапоженко, И. П. Чухров // ВИНИТИ. Итоги науки и техники. Теоретическая кибернетика. — 1987. Вып. 25. - С. 68-116.

21. Слепян В. А. Длина минимального теста для некоторого класса таблиц / В. А. Слепян // Дискретный анализ. — Новосибирск: ИМ СО АН СССР, 1973. Том 23. - С. 59-71.

22. Соловьев Н. А. Тесты (теория, построение, применение) / Н. А. Соловьев. — Новосибирск: Наука, 1978.

23. Станкович Р. С. Преобразования Уолша и Рида-Маллера в логическом синтезе / Р. С. Станкович // Автоматика и телемеханика. — 1996. Том 57. Выпуск 4. - С. 130-147.

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

25. Яблонский С. В. О тестах для электрических схем / С. В. Яблонский, И. А. Чегис // УМН. 1955. - Том 10. Выпуск 4(66). - С. 182184.

26. Balyuk A. Classes of Operator Forms / A. Balyuk, S. Vinokurov // 5th International Workshop on Boolean Problems. — Freiberg, Germany, 2002. P. 217-224.

27. Bryant R.E. Graph-based algorithms for boolean function manipulation / R.E. Bryant // IEEE Trans. Сотр. 1986. -vol. C-35 No. 8. - P. 667-691.

28. Drechsler R. Efficient representation and manipulation of switching functions based on Ordered Kronecker Functional Decision Diagrams / R. Drechsler, A. Sarabi, M. Theobald, B. Becker В // Proc. DAC'94. -1994. P. 415-419.

29. Drechsler R. Pseudo Kronecker Expressions for Symmetric Functionss / R. Drechsler // Proc. VLSI Design. 1997. - P. 511-513.

30. Even S. On minimal modulo 2 sums of products for switching functions / S. Even, I. Kohavi, A. Paz / IEEE Trans. Electron. Comput. 1967. -V. EC-16, N 10. - P. 671-674.

31. Gaidukov A. Algorithm to derive minimum ESOP for 6-variable function / A. Gaidukov // bth International Workshop on Boolean Problems. Freiberg, Germany. — 2002. — P. 141-148.

32. Ho P. Free Kronecker Decision Diagrams and their Application to ATMEL 6000 FPGA Mapping / P. Ho, M. A. Perkowski // Proc. Euro-DAC'94/Euro-VHDL'94. 1994. - P. 8-13.

33. McCluskey E. J. Minimisation of Boolean functions / E. J. McCluskey // Bell Syst. Techn. J. 1956. - N 35. - P. 1417-1444.

34. Muller D. E. Application of Boolean algebra to switching circuit design and error detection / D. E. Muller // IRE Trans. Electron. Comput. — 1954. V.3, N. 3. - P. 6-12.

35. Post E. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer J. Math. 1921. - V. 43, N 4. - P. 163-185.

36. Post E. L. Two-valued iterative systems of mathematical logic / E. L. Post // Annals of Math. Studies. Princeton Univ. Press. — 1941. —V. 5.

37. Reed I. S. A class of multiply-error-correcting codes and decoding scheme / I. S. Reed // IRE Trans. Inform. Theory. 1954. - V. 4, N. 9. - P. 38-49.

38. Stankovic R. A discussion on the history of research in the arithmetic and Reed-Muller expressions / R. Stankovic, T. Sasao // IEEE transactionson computer-aided design of integrated circuits and systems. 2001. -Vol 20. - № 9. - P. 1177-1179.

39. Steinbach B. SNF: A Special Normal Form for ESOPs / B. Steinbach, A. Mishchenko // Proceedings of the 5th International Workshop on

40. Application of the Reed-Muller Expansion in Circuit Design (RM 2001), August 10-11. 2001. - P. 66-81.

41. Steinbach B. On SNF Optimization: a functional comparison of methods / B. Steinbach, V. Yanchurkin, M. Lukac // RM2003 Proceedings. —Trier, Germany, 2003. — P. 11-18.

42. Thornton M. BDD Based Spectral Approach for Reed-Muller Circuit Realisation / M. Thornton, V. Nair // IEE Proceedings-Computers and Digital Techniques. 1996. - Vol 193. - P. 145-150.

43. Thornton M. Boolean function spectrum computation using a structural representation / M. Thornton, V. Nair //Technical Report, Southern Methodist University, CSE-9440. 1994.

44. Thornton M. Fast Reed-Muller spectrum computation using output probabilities / M. Thornton, V. Nair // Workshop on Applications of the Reed-Muller Expansion in Circuit Design. — 1995. P. 281-287.

45. Townsend W. Computing Walsh, Arithmetic and Reed-Muller spectral decision diagrams using graph transformations / W. Townsend, M. Thornton, R. Drechsler etc. // 12th ACM/IEEE Great Lakes Symposium on VLSI. 2002. - P. 178-183

46. Ubar R. Hieratical defect-oriented test generation / R. Ubar // REASON Tutorial <Advanced methods of digital and analog test», Irkutsk, September 2004.

47. Рябец JI. В. Алгоритм точной минимизации булевых функций в классе кронекеровых форм / С. Ф. Винокуров, JI. В. Рябец // Алгебра и теория моделей 4. — Новосибирск.: Из-во Новосиб. гос. тех. ун-та, 2003. С. 148-159.

48. Рябец Л. В. Кронекеровы спектры булевых функций / Л. В. Рябец // Вестник БГУ. Серия 13: Математика и информатика. — 2005. Вып.2. — С. 45-52.

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

50. Технологии Microsoft в теории и практике программирования: Тезисы докладов. — Новосибирск, 2006. — С. 215-217.

51. Рябец JI. В. Тестирование бесповторных булевых функций / А. С. Валюк, JI. В. Рябец // Вестник Томского государственного университета. Приложение. — 2006. — Вып 17. — С. 10-14.

52. Рябец JI. В. Сложность проверяющих тестов для бесповторных булевых функций / JI. В. Рябец. — Иркутский государственный педагогический университет. Серия: Дискретная математика и информатика. Вып. 18. Иркутск, 2007. - 32 с.