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

{ГА,¿..¿71,Г.-:. 'АКАДЕМИЯ НАУК СССР !■ Вычислительный центр

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

АЛЕКСАНЯН Ара Ананиковяч

УДК 519.7

ИССЛЕДОВАНИЕ И ПРИМЕНЕНИЕ ДИСКРЕТНЫХ МОДШЙ,.

СВЯЗАННЫХ С ПРЕДСТАВЛЕНИЕМ ВШЕЫХ ФУНКЦИЙ ФОРМУЛАМИ СПЕЦИАЛЬНОГО КЛАССА

Специальность: 05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1990

Работа, выполнена в Ереванском Ордена Трудового Красно: Знамени государственном университете

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

член.корр.АН УССР, доктор ф.м.наук, профессор

Летичевский А.А. доктор ф.м.наук, профессор Солодов В.М.

доктор ф.м.наук, ст.н.с. Шоломов Л.А.

Ведущая организация: Московский физико-технический институт

Защита состоится 1990 г. в, /7

час. на заседании Специализированного Совета Д002.32.04 Вычислительного центра АН СССР по адресу: 117967, Москва, ГСП-1, ул.Вавилова, дом 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке МИ АН I

Автореферат разослан щ/3 " Л ¿/л 1990 г.

Ученый секретарь специализированного совета доктор фаз.-мат.наук

А.А.Белолипэцкий

ОНДАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблема. Одним из наиболее.задних дис1фвг-х модельных объектов теории систем переработки информации, шедшим широкое применение во многих областях науки и техники ких, как конструирование вычислительной техники, исследова-е операций, математическое моделирование в медицине, геоло-и, биологии и др. являются дизъюнктивные нормальные формы .н.ф.) булевых функций.

Исследование д.н.ф. исторически началось в рамках матема-ческой логики. Однако истинной датой рождения теории д.н.ф. здует считать начало второй половины XX века, когда появле-э электронной вычислительной техники и революционных работ Иеннона выдвинуло д.н.ф. на место одного из основных дискрег-к модельных объектов теории управляющих систем. Особенно бур-з развитие теория д.н.ф. получила в 50-60-х гг. и отчасти в зале 70-х годов. Решающий вклад в становление и развитие тега д.н.ф. внесен советскими математиками С.В.Яблонским, Ю.И. равлевым, А.А.Саложенко, В.В.Глаголевым, Ю.Л.Васильевым и др. ■ Однако тонкие математические результаты этих лет в весьма той степени прямо использовались при решении конкретных при-эдных экстремальных задач в основном из-за того, что исследу-1й модельный объект - дизъюнктивные нормальные формы - отли-юь большим числом весьма специфических особенностей, црису-с только этому классу моделей, не получил сколько-нибудь ши-юго расцросхранения в тех прикладных областях, где действи-тьно это было бы необходимо. Специфичность модели д.н.ф. по-збовала преодоления существенных трудностей, присущих не ис-щой содержательной задаче, а возникавших ввиду необходимо-I трансляции ее на алгебраически "бедный" и специфичный язык 1.ф.

Тем не менее в настоящее время все практические метода эектирования, синтеза и диагностики схем кодирования и пере-5отки информации на ШС и СБИС, основываются на ггредваритель-1 реализации логических функций в .виде достаточно простых 1.ф. Большой, практически необозримый, крут дискретных экстре- • шных задач, задач распознавания образов и т.д. сводится к пению систем нелинейных булевых уравнений. На решение именно к задач и ориентированы основные применения представления

булевых функций в виде д.н.ф.

Таким образом, "кризисное" состояние в теории д.н.ф., о< ловленное недостаточной адекватностью выбранной модели исхода содержательной задаче, может быть преодолено лишь путем отка: от привычной математической модели и перехода к существенно ] вой, более адекватной исходной содержательной задаче, модели, избегая при этом существенного усложнения математического аш рата.

Среда требований, предъявляемых к такой модели следует ; делить в качестве основных два следующих:

- новая модель должна естественным образом обобщать мода д.н.ф. и допускать.использование алгбераически более "богаты: чем булева алгебра средств, что позволило бы преодолеть несб; лансированность в теории д.н.ф. в сторону "геометрических" м( тодов;

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

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

Цель работы:

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

- построить основы математической теории новой модели;

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

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

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

(ейными функциями.

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

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

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

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

- разработаны метода реализации булевых функций, ориенти- ' званные на решение нелинейных систем булевых уравнений;

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

- разработанные методы применены для решения конкретных »икладных задач.

Все результаты работы являются новыми и получены автором :ервые.

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

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

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

Апробация работы и публикации. Представленная работа явля-;я частью исследований, выполненных автором в Ереванском гос-.версктете с 1985-1990 гг.

Результаты работы докладывались на научных конференциях ванского госуниверситета (1985-1990 гг.), на 1У Всесоюзной ференции "Математические методы распознавания образов" (Рига,

1989), на УТ Международной конференции "Основы теории вычисле ний" (Казань, 1987), на советско-германском рабочем семинаре дискретной математике "Логико-комбинаторные методы в.задачах работки информации" (Ереван, 1989), на семинаре отдела пробле распознавания и комбинаторных методов Вычислительного центра АН СССР,! неоднократно докладывались на семинарах кафедр те ори систем и математической кибернетики Ер1У, на семинаре в Ж Ж УССР, на семинарах Вычислительного центра АН Арм.ССР.

По теме диссертации автором опубликовано 10 научных рабе По материалам исследований в 1990 г. опубликована монография "Дизъюнктивные нормальные формы над линейными,функциями. (Те< рия и приложения)" (издательство Е1У).

Структура и объем работы. Диссертация состоит из 6 глав, заключения, содержащего основные результаты и выводы, списка литературы, включающего 48 наименований. Полный объем - 235 страниц машинописного текста.

СОДЕЕЕАНИЕ РАБ0Ш

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

Пусть

(I) ' i , i=L,Z,...,m ,

- система нелинейных булевых уравнений. "Универсальная схема" решения системы (I) заключается в следующем. Каждая функция i представляется в виде (желательно кратчайших) д.н.ф. D^ =

VJQ V. ■ ■ V „ Далее раскрываются скобки в произве-

дении -A'iV ... ' -^Vn и получается результирующая д.н.ф.

De V Кх V... V Ks t реализующая множество всех решеш системы (I). Основная причина, ограничивающая применимость "yi версальной схемы", заключается в большой трудоемкости процесса перехода от • Х^•... - ~£>'т к результирукщей д.н.ф. D ,

которая напрямую зависит от длин (количества дизъюнктивных чле

нов) д.н.ф. T>l , i = 1, Z,..m

Использование д.н.ф. в "универсальной схеме" мотивируется простотой перечисления единиц функции, реализуемой д.н.ф. Х>. В самом деле, решение уравнений Ki~i , L=i, ■ ■■> ^ - суть тривиальная задача. Но уравнение К = X,i СС.^-.. /Г6*--!, где

W i Li ' ¿к ~~ g-

ft - элементарная конъюнкция б^ 6 {Oj i] у j . , а X =4

ос. = 6" , может быть легко записано в виде линейной над полем Галуа GFfZ) (т.е. по т-оо/Z. ) системы уравнений:

С CCL = % 1

или же !

\ % + 4 = 1 и K=(xCt+6i + LKccL+6b+l)...(xLK+*'K + L).

Решение систем линейных уравнений над полем &F U-) , ввиду отсутствия ошибок округления, может быть довольно просто получено методом исключения Гаусса. В этом смысле линейные системы уравнений - суть цростейше. Следовательно, "универсальная схема" полностью проходит и в случае, когда результирующая д.н.ф. J} и все , 1 = i,Z,...,tnсостоят из дизъюнктивных членов К , представимых в виде произведения линейных над G-F(I) функций.

Можно сделать следующий вывод: для задачи решения систем нелинейных булевых уравнений (и, вообще говоря, не только для нее) более адекватно использование представления булевых функций посредством формул вида FL V % И... , где Щ -произведение линейных над GFfZ) функций, ¿ = i,...,S .которые являются обобщениями обычных д.н;ф. (всякая д.н.ф. - частный случай такой формулы).

Законно ожидать, что кратчайшее в смысле числа дизъюнктивных членов, представление функции 4 формулами указанного ти-• па, называемыми линеаризированными д.н.ф. (л.д.н.ф.), должно быть существенно проще д.н.ф. - представления. Это позволит

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

Далее во введении приводится кгя^ое изложение- содержания работы.

Глава I посвящена исследованию метрических (количественных), геометрических и теоретико-структурных свойств функций, представших в виде произведения линейных над СР(2,) функций.

Через Р(и.) обозначается множество булевых функций, зависящих от не более, чем К переменных, а через ЕП - множество вершин гь -мерного единичного куба. Функция вида ЗС/1... ,

& Г1 сс-б' г ■> 1 ик

где X ^"¡о' лфб' ' ^е г од} . называется элементарной конъюнкцией.

Напомним, что функция г £ называется линейной, ес-

ли о^ + о^Хд+о^а^+.-.+о^, где <х£е {о,1], ¿=0,1,...,^.

С каждой функцией ^ е связывается линейное подпространство линейного пространства линеиных над функций от переменных {ОС. 1 г ХЛ}...:

$£ и*) >*•}=(>} .

В § I вводится понятие аналога элементарной конъюнкции.

Определение 1.7. Функция 4 £ Р (п) называется линеаризируемой, если ^ представима в виде произведения некоторого конечного числа линейных функций из ¡-.(а) , т.е.О.^ Множество линеаризируемых функций обозначается через ПЬ(п-). В частности, всякая элементарная конъшкий-является линеаризируемой функцией, ибо

В § 2 проводится исследование линеаризируемых фунвдий.

Предложение 1.8. Для всякой

ит

(Щ имеет место

Предложение 1.9. Для £ € ЛШ имеет место

, где Ё> - произвольный базис в Мр

Такое цредставление ^ называется базисным и является кратчайшим в смысле количества линейных сомножителей.

С каждым базисным представлением 4 связываются две матрицы к* и В* . Пусть 4 = Гк14?ь) и %1 -^ЭСп.; ¿=0 а

Тогда

/*00 <*01 •

<*1о 0Сц . ■ • а-1

. - • га

^01 . . . \

. . . )

^К-И . . - П }

го

Предложение 1.10. Если ^ е Пи«;.

а) ¿¿т = о/е^ф $ Л- , если 4ф 0 (здесь

) - степень многочлена по тос( Ц , реализующего $ );

б) ¿¿т., если 1= 0 о

Определение 1.11. Размерность функции ^ £ П Ь (л) - суть

число Л- о!^ ({)- п.- сйт-М^ = окю. (р .

Предложение 1.12. Пусть Тогда условия ( и

гад*^ -то-п-к В^ равносильны.

Предложение 1.13. Соответствие между П \_>(п) и

множеством линейных подпространств цространства Х/л-; является инъективным отображением, образ которого состоит из самого 1_,(п) и из всех подпространств, содержащихся целиком'хотя бы в одном

Пусть УЦ =(* 6 В*1! $(*)=[} и )6

П ^€[0,13.

Основная теорема § 2 состоит в следующем. Теорема 1,14.

а) Если = 0 , то с&т Nр = п +1 ;

б) если О^сШЛп.) , = ^ -смежный класс (сдвиг) по линейному подпространству Мр Г) £П'+1.

, й Л. | = | ;

в) = . 'где

rtl/l

LK.I~7?C

- го -

U«-L)Uk-ii)... (Z-L)

- коэффициент Гаусса -

количество К -мерных линейных подпространств в El,

п-

* к.

Шш = i + Z &[*]

v)

к=о

Порядок роста числа линеаризируемых функций получен в теореме I.I6: з л (n+if | , (jm)

• «2 4 ^ ПЬ^)'^ Çj/^ 4 » гдв ^-i. константы. В § 3 исследуются основные теоретико-структурные свойства класса Î1L (-п) . .

Множество 1 i L (п-) рассматривается в качестве частично упорядоченного отношением ^ - поглощения функций.

Предложение 1,17. Для 6 J1L W условия f é £ и

Mq S Mjf равносильны.

На множестве П !_.(«-) вводится операция (J » взятия верхней грани, т.е. - наименьшая функция из ilL(ft) , поглощающая | Vj. . Другими словами, И = М| П M г. • жение функций определяет нижнюю грань - = Jvj

Для € flLl^) таких, что ^^о имеем;

с^г с 4) + = "¿^(ft) + cii-m

Теорема I.I9. Система (HLWj ' ^ U, 4 ) является полной модулярной решеткой с дополнениями и ранговой функцией Она изоморфна решетке линейных подпространств в EH+i~ • имеющих непустое пересечение с Е, , и антиизоморфна решетке,

состоящей из подпространств в L('n) t содержащихся целиком

хотя <5ы в одном Мр для ^ПЬ^ , i-фо и самого Е . Далее исследуются количественные характеристики решетки

Назовем множество

слоем

решетки (flL с номером К , 0$ к^ П- . Положим длиfè

Леша 1.20 te (к, m, £) -

для m <. к и для к ^-т. .

Лемма 1.22. ^Л™'* [Т] .

Пусть ^ е Ьк , и

ЗС<,т)в: (иКбЬк = ■

Пусть ^^

ЙШа^ (? (К, ^ _

Следствие. Пусть об € £ , тогда | б >

■'к

■пъ\ .

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

Теорема 1.25. Максимальная антицепь в (ЛиЮ; ^) реализуется слоем п и . «, Гт\ А I I ± {п+1)

'¿.еЧд « , где

Г -А,

« } .

В § 4 описано геометрическое строение множества единиц функции ^ £ Л Ь •

Теорема 1.28. Пусть ^ПЬс»1-) и £ зависит явно от К

переменных, к ¿п. . Тогда

а) единственным образом разлагается в объединение (п.-к. ) - мерных параллельных интервалов в Е , натянутых на вершины некоторого смежного класса в ЕК ;

б) размерность наибольшего интервала, содержащегося цели. ком в и участвующего в разложении из пункта а) равна

п-к .

Во второй главе введено и исследовано центральное понятие работы - линеаризированные д.н.ф.

Определение 2.2. Выражение У^У..У , где ^ €Щ.,^ 1 = .. .,пг , называется линеаризированной дизъюнктивной нормальной формой (л.д.н.ф.). Числом, называется длиной л.д. н.ф. Если ^ = 0 для всех пар , то л.д.н.ф. называ-

ется ортогонализированной.

ч»

Определение 2.3. Л.д.н.ф. ^ = ^V.. .Vf^ называется кратчайшей, если функцию нельзя представить с помощью л.д.н.ф. длины меньшей, чем trv .

Определение 2.4. Функция $ £ J1 L(n-) называется максимальной для ^бР(чг) , если ^ ^ и »¿'tüLW следует: 1 = .

Определение 2.5. Сокращенной л.д.н.ф. функции f € Г(-п) называется л.д.н.ф., составленная из всех максимальных для ^ Функций.

Основная задача теории л.д.н.ф. - кратчайшая (или близкая к кратчайшей) реализация булевых функций посредством л.д.н.ф. Задача построения 1фатчайшей л.д.н.ф. геометрически интерпретируется как задача кратчайшего покрытия множества единиц булевой функции смежными классами по линейным подпространствам в .

В § 2 известные метода синтеза сокращенной д.н.ф. Елейка и Нельсона модифицируются применительно к задаче построения со-1фащенной л.д.н.ф.

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

Теорема 2.II. Для почти всех функций j € iW _ ко-

личество К -мерных линеаризируемых функций, поглощаемых удовлетворяет неравенствам:

Теорема 2.12. Дяя почти всех функций максимальная

размерность линеаризируемой функции, поглощаемой £ , не превосходит величины fV + + ^ '

Теорема 2.13. Для почти всех функций

| в PítW длина ¿(4)

сокращенной л.д.н.ф. удовлетворяет неравенствам:

ШЫп*1^*»* ,где ^ =

'ТТЛ! ТТЛПЛП П Г<f7- 1 — , ______

i € Р(Ю

и 5 < <3 + 6 • Обозначим через /("«•; - •

Теорема 2.16. , , , Л

-Уз (п--О р 4- Щг1

. -Л-.

ух для п, = о

Теорема 2.17. Почти все максимальные для 4- функции € Пдля почти всех функций | € п.)имеют размерность, удовлетворяющую неравенствам: п. - ^ < с^^т + 3

В § 4 исследована для почти всех функций важнейшая характеристика - длина кратчайшей л.д.н.ф. Основной результат содержат теоремы 2,18 и 2.20: . . ' для почти всех функций

длина В ({) кратчайшей л.д.. н.ф. удовлетворяет неравенствам ^ .

-и^п, = ¿¿-т. = О о

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

I Г^1-4

Следующий § 6 целиком посвящен сравнению случаев л.д.н. ф. - и д.н.ф. - реализации булевых функций-.

Известно, что решетка элементарных конъюнкций не симметрична и максимальная антицепь реализуется слоем с номером Гд 1. ^ Теорема 1.25 показывает,■что переход к линеаризируемым функциям "симметризует", решетку, т.к. максимальная антицепь реализуется слоем Г!;-! . Кроме того, количество функций из "среднего" слоя всего, лишь в константу раз меньше общего количества всех функций из П Ь (11-) , в то время как в случае элементарных конъюнкций доля функций из максимального слоя стремится к нулю с ростом П .

Для случая д.н.ф. - реализации известно, что максимальная размерность интервалов для почти всех функций равна [-1о^гь~1+[ ,

I) Дискретная математика и математические вопросы кибернетики. т.1, Наука, 1974.

в то'время как типичная размерность имеет меньший порядок -

л-^л.^ ® случае же л.д.н.ф. типичная и максималь-

ная размерности для почти всех функций имеют одинаковый порядок - О(^гг) •

Из полученных1 оценок следует, что длина сокращенной л.д.н, ф. для почти всех функций существенно больше длины сокращенной д.н.ф. *

Для "ьСп) _ максимальной душны сокращенной л.д.н.ф. имеем 0(пЛ) , в то время как для ъ(1ь) / - максимальной длины совращенной д.н.ф. имеет место -¿о^^ -С (п) = 0(к-) Наконец, дога почти всех функций длина 1фатчайшей л.д.н.ф., по крайней мере в п/(• раз меньше, чем дайна

кратчайшей д.н.ф.

К сказанному следует добавить, что самая сложная в смысле д.н.ф.-реализации (длина 1фатчайшей д.н.ф. равна Л, ) функция - "счетчик четности" - ± 4-оеА-ь.. .4- ос^ 1 - имеет л.д.н.ф. -реализацию длины 1 . Далее, любая пара вершин в Е образует смежный класс, т.е. соответствует линеаризируемой функции. Следовательно, все функции получаются связными и в случае л.д.н.ф. принципиально невозможно применение локальных методов, развитых в теории д.н.ф.

В теореме 2.23 послоен аналог "счетчика четности" дая случая л.д.н.ф.-реализации. "Счетчик четности" характеризуется тем, что множество единиц содержит лишь интервалы нулевой размерности в наибольшем возможном количестве В случае л.д.н.ф.-реализации подобная функция должна иметь множество единиц, содержащее лишь одномерные смежные классы в наибольшем возможном количестве. Как это следует из теоремы 2.23 мощность множества единиц функции в этом случае имеет порядок 0(л и аналогом "счетчика четности" является функция, множество единиц которой совпадает с множеством корней(¿"^-ь1)-й степени из единицы, если Е^ рассмотреть в качестве конечного поля GF(s, ) . Таким образом, получено новое существенное .различие понятий д.н.ф. и л.д.н.ф., а именно: если в случае д.н.ф.-реализации множество единиц самой сложной функции состоит из интервалов наименьшей возможной размерности, то в случае л.д.н.ф.-реализации получить сложнейшую функцию, используя одномерные смежные классы, невозможно.

1) Дискретная математика и математические вбросы кибернетики. т.1, Наука, 1974.

2) Там же7

Группой инвариантных преобразований теории л.д.н.ф. является полная группа аффинных преобразований Е^, т.е. преобразований вида ос АН , где А - невырожденная булева матрица, -вектор "новых", а ас - "старых" переменных, которая включает в, себя алгебраически более "бедную" группу Шеннона-По-варова (группу изометрических перестановок куба Еп) - группу инвариантных преобразований теории д.н.ф.

Глава Ш посвящена исследовании задачи кратчайшего л.д.н.ф. - представления булевых функций из некоторых важнейших классов.

В § I рассмотрены симметрические булевы функции. Функция называется симметрической, если 4 ■ = ^С&с

) для отбой перестановки '" переменных.

Пусть к <; |Г Д 1 н ^ - симметрическая функция, обращающаяся в 1 только на вершинах из Е^, имеющих в точности к единичных координат. Тогда каждому дизъюнктивному члену совращенной л.д.н.ф. функции $ соответствует разбиение множества {I, ¿¿■■у = С!... иТ^ и , удовлетворяющее свойствам:

а) для всех имеет место | Т^ | =«2.;

б) из следует (]$ ;

По такому разбиению однозначно выписывается явный вид дизъюнктивного члена соодащенной л.д.н.ф.:

% = и = к.

£. = 1 ре^ '¿ей сГ

Теорема 3.5. Длина &С<) кратчайшей л.д.н.ф. функции удовлетворяет неравенствам: /п.\

/А- )

_ г*-,

¿п к ^ при ^ I

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

Теорема 3.8. Максимальная длина Тстг} кратчайшей л.д.н.ф? фоизвольной симметрической булевой функции из Р(ъ-) удовлетво->яет неравенствам:

Тем самым в■ теореме 3.8 установлена асимптотика логарифма максимальной длины кратчайшей л.д.н.ф. симметрических функций, т.е. €а^Т(п) — «-(-¿с^З -1) .

Кяасс симметрических булевых функций является одним из важнейших классов, на котором достигаются почти все рекорды сложности в теории д.н.ф. Из теорем 3.8, 2.18 и 2.20 следует, что все симметрические функции имеют существенно более простую л.д.н.ф.-реализацию, чем почти все функции из Р(к) , и класс симметрических булевых функций не является одним из сложнейших в случае л.д.н.ф.-реализации.

В § 2 основная задача исследуется для другого важного класса булевых функций, а именно: класса функций с малым числом нулей. Этот класс булевых функций привлекает внимание исследователей в связи с многочисленными и важными приложениями в задачах, связанных с синтезом алгоритмов распознавания с логическими разделителями классов или с так называемыми представительными наборами. Эта задача известна1^ как задача реализации в виде д.н.ф. булевой функции, эквивалентной произведению левых частей нельсоновской системы булевых уравнений:

(2) , где

сС_ Г СС. , оС-1

01 ~ X сс. +1, = 0 и множество нулей данной функции - суть [(1 + ..., Непосредственное перемножение левых частей - весьма трудоемкая задача и практически осуществима лишь при достаточно малом к . Поэтому очень важно уметь сокращать количество уравнений в (2) без существенного увеличения числа слагаемых в каадом из уравнений. В случае д.н.ф.-реализации всякую систему вида (2) можно сократить в лучшем случае в 4-5 раз.

Задача л.д.н.ф.-реализации функций с малым числом нулей заключается в реализации функции, заданной таблицей, состоящей из К" нулей, где к - с(з.п) или к = ( р - полином.

Обозначим через г - ранг матрицы нулей функции ^ из ?к - множества функций из ~Р(п) с К нулями.

I)' Журавлев Ю.И., Коган А.Ю., Реализация булевых функций с малым числом нулей дизъюнктивными нормальными формами и смежные задачи, Докл.АН СССР, т.285, 4, 1985, с.795-799.

В работе описывается метод сведения задачи к л7ДоН,ф<>-реализации функции из (т) , обращающейся в нуль на всех вершинах из Е , содержащих не более одной единичной координаты.

Обозначим через Ь (-п, к,-г) максимальную длину кратчайшей л.д.н.ф., реализующей функцию | б Рк (п.) , ранг матрицы нулей которой'равен -г и $ (о) = о .

Теорема 3,12. (п,К,г)^ П-г + ]^(г}к,г) ,

Теорема ЗЛЗ. Если г ^ (с^^п. - у 1-п.) о(п) ^

гдв гС^ = + 00 и -у(п) = к) то

Определение 3.14. Пусть /г. ^ . Система векторов [ы. * <у£ с Гп

» ;..«с ^ находится в общем положении, если из ус-

ловий Я1<х- +..= о и Л^ч-. . . + Я^ = О следует: о , где Д£ е ¿=1,.

Это означает, что размерность наименьшей в (ЛЬс-к^у функции такой, что ■ ■ 3 равна«г-1

Теорема 3.15. Пусть К^п + 1 и нули функции £ е находятся в общем положении, тогда длина зфатчайшей л.д.н.ф. функции | не больше, чем п - 4 .

Более того, можно легко построить л.д.н.ф.-реализацию дайны п--1 в явном виде. Теорема 3.16.

( > При К € {!,?}

4 "п"1> при

■П + 1, при к = & > при К € 0}

Таким образом, любая нельсоновская система вида (2) всегда может быть сокращена не менее, чем в 10 раз. Предложен алгоритм реализации этого сокращения.

"Частотное" решение поставленной задачи содержит

Теорема 3.19. Почти все функции ^ € при к $ П.- у Щ

где Ч(п)= + и ^(ъ)=о('п) > реализуются л.д.н.ф.

длины п-1 .

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

количество уравнений системы гп. = о , при зтом число чле-

нов в каждом из новых уравнений не больше .По сравнению

со случаем д.н.ф.-реализации функций из ¿к (Ю л.д.н.ф.-реализация имеет существенно меньшую длину. При д.н.ф.-реализации длина д.н.ф. выражается в виде п. +-яи(<) р-' Если обозначить аналогичную величину дам случая л.д.н.ф.-реализации через 1ъ-ь1(к то получаетоя следующая картина: к=2 345 6 789 10 т(к)~ О I 4 14 31 66 133 271 537 1(К)= -I -I -I -1-1 0 12 2

Для методов д.н.ф.-реализации функций из ^к^ не известно эффективных "частотных" решений для типичного случая, аналогичных теореме 3.19,

В § 3 приводится аналитическое решение задачи 1фагчайшей л.д.н.ф.-реализации квадратичных булевых функций, т.е. функций вида ссС]х7-*-с{ , где ф - (пхп) булева матрица, = ■■■> вектор переменных , с/е { о, 1] .

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

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

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

1) ;

2) >

3) и

где число - ранг матрицы + .

Приводится полиномиальный метод приведения функции \ к каноническому виду.

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

I) Журавлев Ю.И., Коган А.Ю„ Реализация булевых функций с малым числом нулей дизъюнктивными нормальными Формами и смежные задачи. Докл. АН СССР, т.285, 4, 1985, с.795-799.

Теорема 3.22.

1) Кратчайшая л.д.н.ф. функции

имеет длину Я*1- { и может быть выбрана ортогонализированной;

2) кратчайшая л.д.н.ф. функции^

имеет длину Л ж может быть выбрана ортогонализированной;

3) существует л.д.н.ф. функции • • + ^-фж1 длины 1 и ортогонализированная л.д.н.ф. длины Л^ , которые могут быть длиннее кратчайшей не более, чем вдвое.

Явный вид дизъюнктивных членов л.д.н.ф. пункта I) задается системой линейных уравнений:

ь+г

■3,

= oi

I

+ m. =■ o^-m-

¿=1

где OLC , КdfOijr...-оСгп-О Л.д.н.ф.'из пункта 3) состоит из членов вида:

Ö^w-i + ^¿-т. = i = i

Все члены л.д.н.ф. из пункта 2) получаются следующим образом:

*П г»

m.

Л.д.н.ф. длины 2-1 имеет следующие члены:

ЗЧ-i + г, = & ¿^ + ¿Ц, , Г = л,^ • • V *

т

.ZT 1+^)^=0 , где = О, «^ = ... = <^=0,^=1

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

т

в явном виде л.д.н.ф.-реализации канонической функции.

Итак, длина кратчайшей л.д.н.ф.-реализации квадратичной

* 4-глпА (Q+QT> г л

булевой функции имеет порядок _ ^ , •

Теорема 3.23. Для почти всех матриц +QT размера (ях-п.) имеет место: Т1

■я-ак-п.)^т&п-к (Q+Q ) « ^

*

где ы. (-ft) сколь угодно медленно стремится к +■»■=> .

Кратчайшая д.н.ф.-реализация квадратичных булевых функций из Р(лп.) может иметь длину порядка^ 1, например для

' Поэтому дал» в худшем случае длина л.

д.'н.ф.-реализации существенно меньше, чем длина д.н.ф.-реализации.

Теорема 3.27. Если Oti € V (ft) , ¿гя (() = ,

к I ЛГ t П-к+i v

3- Я- , тогда |фатчайшая л.д.н.ф.функ-

ции f равна либо , где -ft^ к + р , к > р-^З , либо

равна i , где п.-к-1-z > .2.

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

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

Пусть фиксированы число -п->о и совокупность линейно независимых линейных форм [ ii U, ■ ■ ' J ¿■"¿Я- 3 — L (к) , где

Определение 3.28. Л.д.н.ф. вида

(з) $ = V(ti.+«i.)... + _ ^

Coil,...^^jeЖе ¿7™

называется специальной, если ^(ы., ы ) ~ линеаризируемая функция из 1 ILfjg , не равная тождественно нулю, которая однозначно определяется двоичным вектором бЛ/ , где -некоторый смежный класс по подпространству в А и при

.. v°<V) ^ ^ имеет место:

= w {^.....

для всех . Число называется рангом специаль-

ной л.д.н.ф.

Обозначим через L линейную оболочку системы .

Теорема 3.29. Пусть специальная л.д.н.ф. ранга т. вида (3) реализует функцию £ и удовлетворяет условиям:

а) ^-(ati, = сой-s~t для не более, чем одного ;

б) если _ _ , го (Аы^...^)) = * ;

в) множества линейных, с предварительно удаленными свободными членами, сомножителей функций ф-cc^st допускают

систему различных представителей, линейная оболочка которых пересекается с L лишь по нулю.

Тогда -t(() - длина кратчайшей л.д.н.ф. функции f удовлетворяет неравенствам:

' Л ^/ф« 3L

?

Теорема 3.30. Пусть L .... fD £ Р(п), \ = Г1 i,i ,

w.) ? р .

функции i; реализованы специальными-л.д.н.ф. Тогда функция +

^ "Ж.

реализуется посредством л.д.н.ф. длины не большей, чем Д. , где ■ы, - совокупный ранг системы функций {t± -1^} - ранг некоторой, определяемой по -f^i,.. .,4^3 системы линейных уравнений.

Отсюда следует, что при совокупном ранге порядка ОЦо^ъ) , построение л.д.н.ф.-реализации функции f требует полиномиального времени, и длина л.д.н.ф. полиномиальна по п-

Глава ТУ" посвящена методам и алгоритмам л.д.н.ф.-реализацяи булевых функций.

\ В § I изложен алгоритм построения наименьшей в ( ilLoi^i) линеаризируемой функции, поглощающей заданную f € Р(ft) \ Построение такой функции сводится к решению системы линейных уравнений и может быть осуществлено за 0 (-п.3) операций в G F(1) , а при удачной реализации на ЭЕМ практически и за 0 (-п-л) операций. На основе этого алгоритма в § 2 предложен алгоритм понижения размерности систем нелинейных булевых уравнений.

В § 3 приводится алгоритм градиентного типа построения л. д.н.ф.-реализации булевых функций, тан называемый П - алгоритм. Основная идея алгоритма состоит в выеделении линеаризируемых функций в - множестве единиц функции | путем отсечения смежных классов от УЦ с помощью линейных функций. На каждом шаге алгоритма требуется выбрать линейную функцию, которая отделяет от JVj> подмножество наибольшей мощности. Эта задача

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

В § 4 предлагается другой алгоритм л.д.н.ф.-реализации булевых функций - 2 - алгоритм. В отличие от -П -алгоритма,2-алгоритм применим также и к частичным функциям. В 2 -алгоритме последовательно выделяются смежные классы в множестве . Излагаются две версии 2 -алгоритма - работающая с множествами вершин из ' и работающая с аналитическими выражениями линеаризируемых функций. Если мощность области определения функции, к которой применяется -алгоритм, ограничена полиномом от П, , то 2! -алгоритм требует полиномиальных по п- времени выполнения и объема памяти.

В § 5 изложен метод упрощения д.н.ф. выделением линеаризируемых подчасгей.

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

нений решается за полиномиальное по «- время. Следует отметить, что предложенный метод допускает легкое распараллеливание.

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

Пусть задан класс задач распознавания с бинарной информацией и двумя непересекающимися классами К0 и К1 и таблицами

I) Баскакова Л.В., Журавлев Ю.И. Модель распознающих алгоритмов с представительными наборами и системами опорных множеств, Журн.вычисл.матем. и матем.физ., т.21, 5, 1981, с.1264-1275.

обучения То и , т.е. состоит из векторов-строк описаний эталонов класса Кр, , Р е . Другими словами Т^ и - заданные булевы матрицы, множества строк которых не пересекаются.

Определение 5.3. Пусть зафиксировано число' £ & о . Выражение Ь = П (¿¿0 + + > гда * € £=1 °

ск , iJг называется линеаризированным разделителем (л.р.) для класса Кр , , если

Число к называется длиной разделителя.

Определение 5.4. Л.р. !_, (для классаКр ) называется тупиковым (т.л.р.), если для всякого л.р. Ь (для Кр ) из Ь £ .ь следует I, = . '

Кавдый т.л.р. является обобщением эмпирических гипотез, основанных на тупиковых представительных наборах, и выполнение условия I, = 1 , что равносильно совместности линейной системы

выражает эмпирическую гипотезу о принадлежности вектора Га классу о

Каждый конкретный алгоритм из модели с л.р. определяется заданием рдца параметров:

а) для каждого класса Кр , > зафиксирована л. д.н.ф. Я^ь , составленная из множества т.л.р. для Кр ;

б) каждому 1, € приписан вес - число р(Ъ).^о ;

в) каадому и ^Тр » .У3* {о, , пришсан вес - число о .

По описанию ос объекта, подлежащего распознаванию, алгоритм вычисляет оценку по л.р. I* £ Кр для класса Кр, по формуле:

гга^^м-рам: хс&ии

Оценка принадлежности объекта ос классу Кр равна

Объект ос заносится в класс** , если + % >

где -У) > о - некоторый порог. В противном случав алгоритм отка-

зывается от классификации объекта .

Наиболее трудоемкой частью синтеза конкретного алгоритма является процесс отделения эталонов Тр, и Туь+1 посредством л.д.Нсф. Яр . Эта задача сводится к задаче л.д.н.ф.-реализации функций с малым'числом нулей, которая решена в главе Ш.

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

В § 4 приводится подробная вычислительная схема реализации алгоритма приведения к канонической форме квадратичных булевых функций. Сложность алгоритма имеет порядок О Сн.2) , но удачная реализация на ЭВМ позволяет снизить порядок сложности до

0Ыг) .

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

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

Задача классификации возникла при экспериментальном исследовании состояния хроматина в ядрах разных типов клеток по его отношению к кислотному гидролизу. Исследовались экспериментальные кривые гидролиза ядер 15 типов клеток, отличающихся друг от друга по степени конденсации хроматина. Каждая экспериментальная ' кривая кислотного гидролиза представляется'82-мерным вектором, компоненты которого задают распределение ДНК-фуксина по оптическим плотностям, общее количество ДНК-фуксина и некоторые другие характеристики.

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

Классификации подвергнуты 63 кривые кислотного гидролиза дцер клеток 15 типов. Построение эвристического алгоритма таксономии потребовало 7 итераций, т.е. 7-кратного решения квадратичных систем булевых уравнений и заняло порядка 20 минут процессорного времени на ЭВМ ЕС 1046.

В результате решения задачи таксономии получены 5 классов эквивалентности - 5 таксонов. Все кривые оказались классифици-

рованы.

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

В качестве модели алгоритмов распознавания была использована шдель алгоритмов с линеаризированными разделителями, описанная в главе У . Синтез алгоритма и сам процесс распознавания заняли порядка 5 минут процессорного времени на ЭВМ ЕС 1046.

В результате применения алгоритма распознавания оказались распределены по классам 10 из 13 кривых, предъявленных к распознаванию. Результаты распознавания соответствуют содержательному смыслу задачи и допускают простое биологическое объяснение.

"заключение

Перечислим основные результаты диссертационной работы.

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

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

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

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

5. Исследована задача л.д.н.ф.-реализации булевых функций с малым числом нулей. Показано, что количество уравнений системы нельсоновского типа всегда может быть сокращено в ТО раз,без увеличения количества дизъюнктивных членов в каждом из исходных уравнений. Получено эффективное "частотное" решение задачи.

6. Для класса квадратичных булевых функций выписаны в явном аналитическом виде кратчайшие (или близкие к ним) л.д.н.ф.-реализации.

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

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

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

Ю.С помощью предложенных в работе методов решены задачи класси-

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

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

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

1. Алексанян A.A. Дизъюнктивные нормальные формы над линейными функциями (Теория и приложения). Ереван:Е1У,1990, 200 с.

2. А1ехапущ A.A. Linearized disjunctive aormal fores of Boolean functions.// Jundea.Comp.Theory.Int.Conf.FCT'ey,Lecture Notes in Comput.Sci., Springer-Verlag,1987,v.278, p.14-16.

3. Алексанян A.A. 0 сложности представления симметричных подмножеств -мерного единичного куба совокупностью систем линейных уравнений.// Докл.АН Арм.ССР, 1987, т.84, № 5, с. 195-197«.

4. Алексанян A.A. Нельсонов.ские системы булевых уравнений и функции с.малым числом нулей. // Докл. АН Арм.ССР, 1988, T.8S, а 5, с.213-217.

5. Алексанян A.A. Оценки, связанные с представлением булевых функций посредством линеаризированных дизъюнктивных нормальных форм. // Докл. АН Арм.ССР, 1988, т.87, J6 I, с.5-9.

6. Алексанян A.A. Реализация булевых функций дизъюнкциями произведений линейных форм. Ц Докл. АН СССР, 1989, т.304, М, с.781-784.

7. Алексанян A.A. О реализации квадратичных булевых функций системами линейных уравнений. // Кибернетика, 1989, № I, с. 9-14.

8. Алексанян A.A. Об одном обобщении модели алгоритмов распознавания с представительными наборами. // Кибернетика, 1989, Ш 5, с.36-39.

9. Алексанян A.A. О реализации слабо определенных булевых функций посредством линеаризированных дизъюнктивных нормальных форм. // Журн. вычисл. матем. и матем. физ., 1989, г. 29,

№ II, с.1722-1729.

10. Алексанян A.A. Об одном обобщении модели алгоритмов распознавания с представительными наборами. // Математические методы распознавания образов. 1У Всесоюзная конференция» Тез. докладов. Рига, 1989, с.9-11.

11. Алексанян A.A. Об одной экстремальной задаче, связанной со сложностью реализации булевых функций в классе д.н.ф. над линейными функциями.//Докл о АН Арм.ССР, 1990, т. 90, ¡Ш, с. 51-55*