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

ЛКАДЕЛШЯ НАУК СССР ^ О

— . 9 1

Вычислительный центр

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

ГУРОВ Сергей Исаевич

УДК 519.714.7

АППРОКСИМАЦИЯ ПОДМНОЖЕСТВ п-МЕРНОГО ЕДИНИЧНОГО КУБА МНОЖЕСТВАМИ ЕДИНИЦ МОНОТОННЫХ БУЛЕВЫХ ФУНКЦИЙ

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

Автореферат

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

Москва 1991

Работы выполнены в Вычислительном центре Академии Наук СССР.

Научный руководитель: чл.-корр. АН СССР, профессор

Ю. И. Журавлев.

Официальные оппоненты: д. ф.-м. н. В. П. Мазурик,

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

Защита состоится ДО****}** 1991 года в на заседании специализированного совета К.002.32.01 в Вычислительном центре Академии Наук СССР по адресу: 117333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного центра АН СССР.

к. ф.-м. н. Г. Ф. Лосев.

Автореферат разослан

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

К. В. Рудаков

Заказ 850. Объем 1 п. л. Тираж 100 экз.

.Типография МГТУ им. Н. Э. Баумана

10Г"АЯ ХАРАКТЕРИСТИКА РАЕОШ

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

Автоматизированный синтез цифровых упраэляюших схзм - лша из таких задач. При проектировании управлявших автоматов их комбинационные части реализуются, как иравило, на основа регулярных структур - постоянных запоминавших устройств (ПЗУ), программируемых логических матриц (ПЛМ), дешифраторов и т.д. Математически комбинационно-логическая схема задается системой частичных булевых функций (СЧБФ). В процессе синтеза схег-СЧБФ заменяется системой дизъюнктивных норлальных форм (СДНФ), каясая из которых является .зозможным доопределением соответст-вушей функции исходной системы» При этом возникает задача нахождения простых отделителей подмножеств Я - мерного единичного куба (гиперкуба).

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

методов„ Отметим, что при этой реализации на треоуется прэдетаглени" входов в парофазном виде.

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

Пусть единичное и нулевое множества частичной булевой функции $ соответствуют обучающим выборкам диух классов объектов. Как правило, основная содержательная чгсть эврис тичеоких алгоритмов распознавания образов о бинарной информацией со'тоил в выборе того или иного дооцрздеячния ■{■ не весь П. -мерный единичный куб ( П. чиоло признаков) или его часть» В зависимости от значения доопределенной функции принимается решение об отнесен! I нового объекта к одному из двух классов.

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

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

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

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

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

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

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

Апробация раб ли. Результата диссертационной работа докла-внгыоь и обсундалиоь на семинарах отдала ыэтодор комбинаторного анализа и проблем распознавания ВЦ АН СССР и КИИ молекулярной электроники МЗП,

Публикации. По материалам диссертации опубликованы 4 работы.

Структура и объем работы. Диссертация состоит из введения, пяти глав, прил^енил, заключения я содержит 77 страниц машинописного текста. Список литературы включает 16 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В начале главы привечены основные понятия, определения и обозначения, используемые в диссертации. В частности счииет-ся, что над булевыми векторами - элементами единичного rv -мерного куба Е - все логические о^рации выполняются поразрядно ( + обозначает су ту по wool Zt г товде- т-во). Координаты обобщенных булэвых векторов принимают значения из В а I О, и соответствуют граням (подкубам) Е

Множества индексов единичных и нулевых координат булев- вектора (набора) С- обозначаются и О С*-). соответственно. Из оме трите скши называются преобразования Г ^ , сохраняющие расстояние Хэдаинга. Еоли f - булева фужция (б.ф.), то f * - функция, с ней соприяженная.

На множестве В рведено не транзитивное отношение < •• & 4 4 справедливо для всех В, иро^е аИ^-О.

Такое обозначение позволяет просто записывать отношения между исходной частичной булевой функцией (ч.б.ф,) -f и аппроксимирующими ее соответственно снизу и сверху полностью определенными булевыми функциями (п.б.ф.) Q и k-. g ^ -fi W. Указанное двойное неравенство эквивалентно включениям

^ ^li. С ^-f, , ^$ обозначают, как обычно, единичное, нуелевое и неопределенное множества б.ф.; ^ -f- назовем а^кже задавшими множееттми).

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

На П. -мерном единичном кубе Е ^ даны непуотые непересекающиеся подмножестве вершин А и В> .задающие ч.о.ф„ о "А, Е> . в обшей пострчовке за-

дача состоит в построении непересекающихся п .пмножеств А' и 2> куба Ел , содержащих заданные множества А и ЕЬ соответственно и обладавших следующими свойствами; (I ) А и В ' являют 1 единичным и нулевым множеством монотонных п.б.ф, 1° г соответственно;

(2) мощности множеотв А ' 4 А Е В'^В минимальны;

(3) А' и 8/ эадана на образе биективного преобрчзо-вания Хл/^ к"ба Е , причем преобразование отвечает "критерию простоты".

Если отказаться от условий непересечения А , Ь ' и (3), получаем задачу аппроксимации исходной ч.б.^ сверху и снизу монотонными п.б.ф. + ° и- . Аппроксимация за-

ключается в том, что значения ° и { 4 несут, вообще говоря, информацию о значении { : „ { « = -{ => £

Г = Г - О ~> * "Г =0, -> * «-.

Выбор монотонных функций в качестве аппроксимируших о.5ъяс-няется простотой структуры их экстремальных дизъюнктивных и конъюнктивных нормальных форм, поучаемых о помощью известных алгоритмов. Задача естественно дополняется оценкой мощности множества отказов /V) /V^» Л •« .определяющей эф$ек-

тивнооть аппроксимации.

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

Отделяющие множества на , вообшэ говоря, можно испо-

льзовать для распознавания образов. Однако т-^кое их примоне-ниэ будет обоснованным, если преобразование ^ $ сохраняэт значения некоторой функции Злизооти (метрики) на В а , которые позволяют доопределить исходную булеву функцию { , пополняя множества А и 6> такими наборами, для которых отнесение соответотвушего объекта к указанным классам совершенно оправдано. Дополняя общую постановку задачи требованием указания такой метрики и понимая "критерий простоты" как минимальность множества таборов гиперкуба с нэоохраненной метелкой, п лучаем уточненную задачу, ориентированную на проблему распознавания образов в двоичном признаковом пространстве.

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

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

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

обеспечивают'« выполнение условия (2) постановки задачи. Это условие требует минимального отклонения аппроксимирующих функций. от походной.

Понятие нижней единицы и верхнего нул.. обобщается на случай произвольной б.ф, Множества всех нижних единиц и верхних нулей б.ф. f обозначаются LU(i) и Hi?(-f) соответственно.

Определение. Пусть на £а задана б.ф. П.б.ф. -f ^ называется мажорантой , если она монотонна и Ш({ц> J" 1М(<Д

II.б.ф, f^ называется минорантой tf , если она монотонна и H2Cftf)-hZr«>).

Из определения следует, что мажоранта -f ° и миноранта ■f^ J.$. -f единственны и имеют вид:

í2 сх> - V & _ X;,

* LUC-f) ^je-íc*) V

-fz & Ч

* H?cf) П6 °Cf * '

Ясно, что в указанных формулах множество можно заменить на N^ ( N^ ) , т.к. это приведет лишь к добавлению поглощаемых конъюнкций в д.н.ф. мажоранты (дизъюнк-

Г ° £ <

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

; Доказываемые далее теоремы I и 2 утверждают, что мажоранта и миноранта суть единстг-шная пара функций, обес»ечив£. хая выполнение условий (I) и (2) постан^чки задачи и обеспечивающая, кроме того, минимальность mol ;ооти множества отказов AYf )

В теореме 3 устанавливается равенство C'f 4 )* f для п.б.ф. f.

Указывается связь монотонных аппроксимирующих функций с задачей о кратчайшем покрытии (БКП). Эта связь заключается в

_ о

том, что мажоранта + + редуцирует йШ, заданную в функциональной постановке б.ф. 4 { № + состоит из векторов

Еа таких, что с.1^ равно I либо 0, ислк (. -е множество соответственно содержит либо не содержит £ -Й элемент). Редукция состоит э исключении млнорируемых покрывае-^х элементов и несущественных покрываших их множеств.

Пусть характеристическая функция покрытия Р 15 Е если и только если $ <-,,¿2>..., } >

- есть покрытие в ЗКП, функционально заданной б.ф, . й.»е-тся простая связь между Р и мажорантой б.ф. г 5-я

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

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

Преобразование Р 1 £ -»Б будем рассматривать как многомерную функцию и задавать кортежем булевых функций

< ^¿.сГ» , ¿-йТа таких, что .....=

= *г+ЧьС*).....

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

Монотонизируюшую б.ф. ^ биекцию (Л £ будем представлять совокупностью транспозиций. Число таких транспозиций есть сло-яость ЬЦ (заметил, что при таком ^пределе-

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

Рангом антимонотонности ft.aiw(f) б.ф. -f назовем величину | А^С-Оv А/+ I-

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

Если -f - монотонна, то - тождественное цреобра-

зование гиперкуба. В противном случае существует подходящая транспозиция гиперкуба} проведем ее. При этом умень-

шится не менее, чем на 2. В случае неравенства нулю ранга анти-монотонносхи б.ф. f , заданной на праобразова.-лом гиперкубе, опять найдется подходящая транспозиция и т.д. Процесс закончится после выполнения ..в болев [Rem» СО/23 шагов. Совокупност1 указанных транспозиций образует искомую монотонизируюшую биекцию.

И- приведенного алгоритма следует, что для данной б.ф. существует непустое множество [ бие^-ций, монотонизи-руюши -f и порожд нных приведенным алгоритмом. Биекции из { К.( } назовем допустимыми. Допустимые биекции различаются последовательностью транспозиций, причем выбоо одной из них может исключить выбор другой.

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

- п -

не более, чем в одной транопозиции. Отсюда следует, ч'о алгоритм М строит минимальную но сложности из всех эквивалентных гчнотониг труюших биекций.

На стно"9нии теоремы 6 об аналитической заш-пи композиции лвух транспозиоШ, заданных четырьмя попарно различными вершинами гиперкуба, устанавливается аналитическая запись

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

доказано, что задача минимизации сложности ионотонизируюшей биекции сводится к задаче .нахождения минимального по мощности максимального паросочеталия на двудольнок гра$чэ. Эта задача, как известно, А'Р -полна. В связи с этим предложено приближенное "жадное" правило выбогч шдходягчх транспозиций. Теорема 7 чонстатирует,. что задача минимизации сложности и { сводится к ЗКП, а алгоритм М, дополненный указанным правилом выбора транспозиционной пары, соответствует градиентному методу еа решения.

Заключительная часть третьей главы овязана с проблемой распознавания образов.

На £ ,5" вводится числовая функция потенциала

определяемая исходной б.ф. +-. Зпеоь ■■ обозначают вводимые т.н. верхнее

и ниженее числа ..¡ля со & Е Для нас важно , что доопределение исходной б.ф. на к .бгре со "о "1 в олучае Р^Оо)»'* и до О , в случае по способу введения потенциа-

ла совершенно оправданс при классификации объекта, соответствующего со € /V ^

Вычисление верхнего и нижнего чг ел дл.. набора из областл неопределенности -р задается, вообше говоря, переборной процедурой. Однако и именно это существенно для нас, при монотонной у значеяпя потенциала вычисляются очень просто: если -Г» Р^Н, если «О и Рр =0, если 0% $Л (поиледня,. область Е Л обозначается

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

раняит знак потенциала и ( ) сохраняет нулевое значение потенциала для векторов №>\ Если же = О, <25 ^ N \ то значение потенциала набора со на преобразованном гиперкубе завист от выбора той или иной бнекции и .р. из числа попустшых.

Доказанные свойства функции Р^ позволяют использовать ее знак при доопределении + на преобразованном гиперкубе аля классификации образов. При этом значение потенциала легко в: шсляется. Также естественней отк 1 от классификации при Р4 (ьи) = 0 и со £ А/0,1 по недостатку информации.

Четвертая глава посаяшена рассмотрению изомегричесой части VI биектиного преобразования . Ясно, что в качестве V^ можно рассматривать лишь преобразования, состоящие в инвертировании о..редоленяых разряпов на всех наборах £ Такие преобразования названы движениями. Движение ааляьтся вектором поляризация у £ £•"" и обозначается (Е ; при этом ели о<. £ , а ^ £ (Бл} , то

Nи <**я ^ а - , ,

Определение. Величина ■» называется степенью

антимонотонности б.ф. £.

Ясно, что минимальность является критерием оптималь-

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

Вектор ть , обеспечивающий минимум I С (£а)))| по ^ называется полюсом б.ф. Показывается, что задача нахождения г">люса б.ф. /V Р -полна.

Далее рассматривается случай точного решения указанной задачи: любой вектор р , обращающий в I функцию ¡¡"(хТ): (аСх}« & V

еоть полюс б.ф.4,

■ >

При ^Гх')=0 для нахождения полюса предложен приближенный е горитм Г градиентного '.¡;па.

Нахождение полюса ^ б.ф. / Сначшиется о обобщенного бг 'зва вектора 6" » (—. ......- ) и заключается в

уточнении значений координат: замене - на 4 либо на О. При этом используется матрица размером |I строк

у Л. столбцов, троянтоя по задающим £ . множествам.

Для обоснования алгоритма доказываются две теоремы. Теорема Л позволяет в опрепеле них случе^х точно определять значе-иия некоторых разрядов 1С . Теорема 12 :юз"1лявт бе? потери информации о полюсе зокрашеть задающие б.ф. f множества,

л*

упрошая при этом опред .ленив Ц. . При невозможности ->дно-значного определения какого-либо разряда X в алгоритме Г выбирается значение, обеспечивающее минимальную верхнюю оцрч-ку для степени ан '¿монотонности.

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

При исследован, л свойств почтя всех б.ф. из некоторого клас са использу: ? понятие случайной б.ф., принадлежащей д иному классу. Известны две основные модели получения случайной б.ф. • ко.-'бшщторная и вероятностная. В диссертация вводится смешанная комбинаторно-вероятностная модель: функции иь классов Р (и,и} (ч.б.ф. с П. единицами СГ нулями) и №п(иг) (монотонные п.б.ф. с иг нижними единицами) определяются в резуль-тлте некоторого случайного процесса При этом выражение "пог ти все функции из некоторого класса обладают свойством $ " пон'тыается как ^ комбинаторной г дали (стремление к 0 доли Функций, не облапавших свойством $ ).

Назовем процедурой Р выбор наборов дл, ш п.

у которых разряды с равной вероятностью принимают значения С и I. Ль.ко видеть, что при ^*о(2к) почти всегда среди подучек"ых наборов не будет совпадающих.

С помощью процедуры Р определяется модель получения случайной б,ф. $ лз Р*Си,1Г) и показывается, что данны модель корректна почти всегда при и,«/"в о (2Л), Далее доказывается теорема 13, утверждающая, что если «г.о<12/ГаТ), то почти всегда среди г лучедах процедурой Р иг набсров длины П. не будет сравнимых. Заладим модель получения случайной б.ф. ■( из /Лл С^) генерацией по процедуре Р иг наборов длины П. о объявлением их !ижними единицами $. Из теоремы 13 следует, что эта модель при указанном ограничении корректна почти всегда.

Из этой же теорем ог дует, что иакоррчта и миноранта олу-Ч8йной ч.б.ф. т из Р (и, 1Г) подавно суть случайные п.б.ф. из и соответственно, если и и

1Г растут ка. некоторый полином от а. Такие функции назовем ола ^определенными; соответствующее множество функций обозначш Р* Г И, У). Теорема 13 позволяет использовать предложенную модель случайной функции из (иг) для исследования мажоранты, миноранты и степени антимонотонностя случайной слабоопрвделенной б.ф.

Пусть с помоиыо процедуры Р генерируются наборы для-

ш П. , а - математическое ожидание числа таких

наборов веса К , К £ Я.. Теорема 14 устанавливает, что среди сгенерированных наборов почтк всегда отсутствуют (присутствуют) набор веса К , если г "тремится к ^ (к бесконечности).

На основании этого факта доказывается теорема 15 о структуре случайной монотонной б.*>. с малым числом нижних единиц. Эта теорема утвержд зт, чтг у б.ф. £ в ЛЛ когда иг рас-

тет полиномпналыю от П. , почти °свгда тсутствуют нижн!.

Рп.

_____ . ж _, с номерами

± Ц>Слу<(гГ 1 ) если ^ СП.) - произвольная функция .растущая быстрее (1 , причем в любом слое из указ^лной группы почти всег.-п имеется хотя сл одна нижняя едишла, ес-

ли С^) растет медленнее ' ¿п П. .

В конце главы даются оценки степени антимонот нности слабоопределенных ч.б.ф.

Теорема 16 утверждает, что средняя величина степени анти-монот нности для о.ф. из Рс СЫ,1Г) не меньше Л и не больше {А-0~. Т. „<ие оценки, однако, малоинформативны, т.к. ненулевую ст' лень антимонотонности имеет бесконечно мь ля доля всех слабоопрэделешшх ч.б.ф. В связи с этим доказывается теорема 17, устанавливающая асимптотически верхнюю п нижнюю ' оценки степени аптимонотоняости для почти всех б.ф. из Р с ( Обе оценки, естественно, стремятся к 0 при

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИЗСЕРТАЦИИ, ВЫНЕСЕННЫЕ НА ЗАЩИТУ

1« Предложен метод аппроксимации произвольЕюй булевой фуик-дии днучя "окотонными, дана оценка его эффективности для сла-боопределешых функций, указана аналитическая форма апирок-оширухших функций,

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

3. Введена комбинаторно-вероятностная модель случайной бу-леьой функции. Исоле„овг"а структура случайной монотонной бу-левоЗ функция с малым числом нижних единиц.

Опубликованные работы, содержащие получении*) в ; тсоертации результаты

1. Авдеев Ю.В., Гуров С.И. .Наденшн Д.И. Программный комплекс проектирования программируемых логических матриц "Сигма'.1// Электронная техника. Серия 3. Микроэлектроника, 1989, вип.5, (134). - С.53-55.

2. Гуров С.И. МетоД интервальной аппроксимации булевых функций онотояными. - 1.1.:ВЦ АН СССР, ТЧ88. - 20 с.

3. Гуров С.И. Определение полюса булечых функций. -М.: ВЦ АН СССР. 1989. - 22 с.

4. Гуров С.И. Приведение про~зволы_1х булевых функций к монотонным.// Курная вяч.юлит. матем-ки и матем. физики, 1991, т. 31. *1. - С.143-150.