Содержание к диссертации
Введение
Глава 1. Основные определения и обозначения. Обзор предьщущих работ 7
1.1. Некоторые обозначения 7
1.2. Обзор методов синтеза ДНФ по перечню нулей 10
1.3. Обзор: нормальные формы А-значной логики 15
1.4. Задача распознавания образов 18
1.5. Задача распознавания с целочисленной (бинарной) информацией. Логические алгоритмы распознавания 20
1.6. Эффективная реализация логических алгоритмов распознавания 24
1.7. Основные результаты диссертации 27
Глава 2. Тестовый подход к задаче ДНФ-реализации 30
2.1. ДНФ построенная по матрице нулей 30
2.2. Оценка сложности ДНФ [D ] 33
2.3. Построение тупиковой ДНФ [Q*]F 37
2.4. Построение ДНФ булевой функции по перечню её нулей с помощью тестового подхода 41
2.5. Построение ДНФ характеристических функций классов. Равномерные ДНФ 44
2.6. Построение явных ДНФ-формул с помощью тестового подхода 47
2.7. ДНФ-реализация по матрице нулевых интервалов 49
Глава 3. Построение ДНФ последовательным умножением 54
3.1. Умножение ДНФ 54
3.2. Некоторые свойства тестовых ДНФ 60
3.3. Умножение на скобку совершенной КНФ 66
3.4. Реализация метода Нельсона на ЭВМ 67
3.5. Построение ДНФ по формуле СВ. Яблонского 70
Глава 4. ДНФ-реализация функций -звачвой логики. Кодировки 75
4.1. Тестовый подход для ДНФ-реализации квазибулевских функций 75
4.2. Определение кодировки. Соответствие конъюнкций 83
4.3. Возможность построения произвольной ДНФ с помощью кодировки. Построение сокращённых Н-ДНФ и Т-ДНФ 87
4.4. Построение А-ДНФ и квазисокращённой А-ДНФ с помощью кодировки 92
Глава 5. Тестирование алгоритмов распознавания 98
Список литературы 114
Приложение 119
- Задача распознавания с целочисленной (бинарной) информацией. Логические алгоритмы распознавания
- Построение ДНФ булевой функции по перечню её нулей с помощью тестового подхода
- Реализация метода Нельсона на ЭВМ
- Возможность построения произвольной ДНФ с помощью кодировки. Построение сокращённых Н-ДНФ и Т-ДНФ
Введение к работе
Проблема построения кратчайших, минимальных или достаточно простых ДНФ для булевых функций и функций -значной логики была одной из основных в исследованиях по дискретному анализу и математической кибернетики, проводимых в СССР в 50 - 70 годах прошлого столетия. С.В, Яблонским, Ю.И. Журавлёвым, А.А. Сапоженко, Ю.Л. Васильевым, В.В. Глаголевым, У.А. Абдугалиевым, А.Н. Нурлыбаевым и др. были получены фундаментальные результаты, показывающие, что задачи мюшмизации, как правило, являются весьма трудоёмкими и реально неразрешимыми даже при относительно небольшом числе переменных. Так как прикладное применение ДНФ ограничивалось, в основном, решением систем булевых уравнений, для чего были получены при других подходах более эффективные методы, интерес к задачам минимизации в дальнейшем существенно уменьшился, что отразилось и на числе публикаций.
В последние десятилетия снова появилось значительное число публикаций, имеющих отношение к исследованию задач эффективного представления булевых функций и функций -значной логики в классе ДНФ и их обобщений. Это вызвано, в первую очередь, использованием ДНФ для синтеза логических распознающих процедур при решении задач распознавания образов. Как известно, большинство применений теории распознавания связано с плохо формализованными областями науки и практики. Для этих областей не удается построить адекватную математическую модель, поэтому строится алгоритм, аппроксимирующий нужную зависимость по прецедентам, т.е. примерам корректной работы алгоритма: входные данные (описания объектов распознавания) и результаты работы алгоритма (классы этих объектов). Для построения таких алгоритмов потребовалась разработка специального математического аппарата, поскольку прецедентов, как правило, не очень много и, например, традиционные статистические методы не всегда давали нужный эффект. Комбинаторно-логический подход, основы которого заложили работы Ю.И. Журавлёва, оказался одним из самых эффективных при решении задач распознавания. В этом подходе по исходной информации определяются логические закономерности (подописания объектов, содержащие информацию о различиях классов). Например, в случае, когда описания объектов целочисленные, естественно использовать аппарат теории ДНФ. С помощью ДНФ или их аналогов доопределяют характеристические функции классов, заданные только в некоторых точках (описаниях объектов), а элементарные конъюнкции играют роль логических закономерностей. Сокращённая ДНФ задает всевозможные доопределения характеристической функции и всевозможные логические закономерности, однако, её длина растёт экспоненциально с ростом «размеров» задачи. Кроме того, доопределение существенно влияет на вид синтезируемого алгоритма распознавания. Так, часто сложность логической распознающей процедуры линейно зависит от суммы длин построенных ДНФ, поскольку алгоритм осуществляет голосование по всем найденным логическим закономерностям.
Это и определило направление исследований, результаты которых описаны в настоящей диссертации. Отметим основную специфику рассматриваемой задачи. Число переменных характеристических функций классов может быть достаточно велико, поскольку объекты описываются, как правило, большим числом признаков. Число нулей и единиц этих функций мало (интересен случай небольшого числа прецедентов). Универсальный способ построения искомой ДНФ характеристической функции класса -построить ДНФ всюду определённой функции, которая обращается в ноль только на нулях характеристической функции, а затем удалить лишние конъюнкции. Заметим, что при решении задач распознавания образов не требуется построение именно экстремальных (минимальных и/или кратчайших) ДНФ, поскольку они не гарантирует высокого качества распознавания. Из результатов СВ. Яблонского и Ю.И. Журавлёва следует, что, по-видимому, решение задачи построения экстремальной ДНФ методами, исключающими перебор, невозможно, но построение ДНФ близких к экстремальным для функций с «малым» числом нулей возможно за приемлемое время.
В диссертации построены эффективные алгоритмы синтеза ДНФ булевых функций и функций знатной логики для решения задач распознавания образов. При этом рассматривалась как задача быстрого построения достаточно простой ДНФ (близкой к кратчайшей), так и задача быстрого построения произвольной ДНФ, часто достаточно сложной, для синтеза «большой» группы логических закономерностей. В диссертации описаны алгоритмы синтеза ДНФ для логических распознающих процедур и алгоритмы, которые могут быть использованы в различных областях, где требуется быстрое ДНФ-представление булевых функций и функций -значной логики. В данном направлении получены окончательные результаты или близкие к окончательным.
Автор выражает огромную благодарность своему научному руководителю академику РАН Юрию Ивановичу Журавлёву, который оказал значительное влияние на формирование научного мировоззрения автора, а также всем своим коллегам и Учителям из Московского государственного университета и ВЦ РАН.
Задача распознавания с целочисленной (бинарной) информацией. Логические алгоритмы распознавания
Очевидно, что практическая реализация предложенного метода возможна лишь при небольшом числе переменных и нулей функции. Кроме того, для получения «несложной» ДНФ необходимо ещё упрощение полученной сокращённой ДНФ, что является трудоёмким комбинаторным процессом (см. [12,32]).
Поэтому представляет интерес разработка «не прямых» методов (избегая прямого &-перемножения). На возможность применения таких методов указал СВ. Яблонский. Было показано [13], что длина всех кратчайших (минимальных) ДНФ булевых функций от п переменных с двумя нулями равна п или /1-ій такие ДНФ могут быть построены по формуле где (tv...,tn) — произвольный цикл на множестве {1,2,...,л}. Эта формула позволяет без перемножения скобок строить простейшие ДНФ булевых функций с двумя нулями, а при числе нулей к 2 для получения ДНФ функции по её совершенной КНФ выполнять перемножение ]/2[ скобок (а не к), Ю.И. Журавлёву и А.Ю. Когану удалось обобщить результаты С.В.Яблонского на случай А: = 3,4 и построить эффективные алгоритмы синтеза ДНФ по перечню нулей. Изложим некоторые результаты Ю.И. Журавлёва и А.Ю. Когана [33, 34]. Множество булевых функций, зависящих от п переменных и имеющих ровно к нулевых точек, обозначается через Р. Считается, что функция / є Р задана матрицей нулей М, = а1. ]іхи. Поскольку переменные, сопоставленные нулевым и единичным столбцам матрицы А/у, в соответствующих степенях являются конъюнкциями ранга 1, ядровыми [13] для функции /, а преобразования xf -+. і- j(i) -подстановка, ст. є{0,1},/є{1,2,...,и}, оставляют инвариантными все свойства булевых функций, связанные с задачами минимизации, то без ограничения общности можно считать следующее: 1) в матрице М, отсутствуют нулевые и единичные столбцы; 2) одинаковые столбцы в матрице My расположены последовательно; 3) из любых двух двойственных столбцов (один из которых является отрицанием другого) в матрице My присутствует не более одного столбца. Далее считается, что группы одинаковых столбцов My занумерованы последовательно, а переменные, соответствующие столбцам q-й группы, обозначаются через. Сопоставим функции f P функцию Ф = Ф{/)ЄР[, зависящую от переменных zv...,zr Матрица нулей М составлена из всех различных столбцов My так, что столбец, соответствующий переменной z , совпадает со столбцами соответствующими переменным xaj(q) Є0Д...,/}. Стоит отметить, что впервые функцию Ф ввел Б.И. Фиников для реализации булевых функций с малым числом единиц в классе параллельно-последовательных контактных схем [44]. Определение. Функция g называется приведённой, если матрица М е нулевых точек состоит из различных столбцов, исключая нулевой и единичный, причем из каждых двух двойственных столбцов в М содержится ровно один. Определение. Приведённая функция geP называется полной. Заметим, что функция p{f) является приведённой. Пусть D — некоторая ДНФ, реализующая функцию Ф, D„ — ДНФ, получаемая из D преобразова-нием переменных Тогда легко строится ДНФ D1, содержащая не более и конъюнкций, такая, что ДНФ D = jyvD реализует /, причём если D - тупиковая ДНФ функции р, то D - тупиковая ДНФ функции /. Таким образом, для построения тупиковой ДНФ функции / достаточно построить тупиковую ДНФ приведённой функции Лемма 1.1. При log2 « -log2log2п +1 для почти всех функций f Pjf соответствующая им приведённая функция р - полная и справедливо \Dj \ ,n-2k-l+\+\D msK\t причём тупиковая ДНФ [Z j?1I1IKJF функции f строится непосредственно по тупиковой ДНФ [DP1] функции р (указанным выше преобразованием переменных (1.3)). Исходя из этого факта, Ю.И. Журавлёв и А.Ю. Коган построили кратчайшие ДНФ всех булевых функций с тремя и четырьмя нулями. Была доказана возможность замены в совершенной КНФ каждой четвёрки скобок эквивалентной ДНФ, состоящей не более чем из (л + 3)-х конъюнкций. Таким образом, существенно расширился класс практически разрешимых задач построения ДНФ по матрице нулей.
Построение ДНФ булевой функции по перечню её нулей с помощью тестового подхода
Задача построения множества всех допустимых конъюнкций частично определённой функции /к (всех простых импликант) элементарно сводится к аналогичной задаче со всюду определённой функцией /к (см., например, [30]). При таком подходе для построения множества всех простых импликант функции fK необходимо построить сокращённую ДНФ функции /к по перечню её нулей: av...,ar, {av...,ar} = СК с Uk х... х Ек. Заметим, что число нулей функции, как правило, невелико, поскольку на практике число эталонных объектов невелико. Число переменных может быть достаточно большим, поскольку допустимые объекты могут описываться большим набором признаков. Часто не удаётся априорно отделить «плохие» признаки от «хороших», и при постановке практических задач распознавания используется вся имеющаяся информация: первоначальные описания объектов содержат все доступные наблюдению характеристики.
Получаем задачу построения некоторого множества импликант функции по перечню её нулей.
В 70 годах при реализации логических алгоритмов накладывались ограничения на ранг синтезируемых конъюнкций. Так, например, в алгоритмах «Кора» [7-9, 11] использовались конъюнкции, содержащие не более трёх букв (тогда рассматривался только бинарный случай). Однако ясно, что полная информация о всевозможных разделениях содержится в сокращённой ДНФ, построение которой затруднительно из-за вычислительных затрат. Длина сокращённой ДНФ растет экспоненциально с ростом размерности задачи, поэтому решение проблемы только за счйт повышения производительности вычислительной техники нереально. Например, известно [13], что для любого п существует булева функция f{xv.,,,xn), длина сокращённой ДНФ которой d, й с ЪпIn, с = const, а длина d сокращённой ДНФ случайной функции f(xl,...,xn) с вероятностью 1-00) удовлетворяет неравенству
В работах Е.В. Дюковой [24—26] предложен подход к решению этой задачи, являющийся в определённом смысле асимптотически оптимальным по вычислительной трудности. Исходная задача заменяется логически более простой и строится множество конъюнкций, которое асимптотически совпадает с множеством простых импликант.
Однако при больших массивах обучающей информации применение данного подхода затруднительно. Из работ [13, 33, 34; см. также 1.2] следует, что существуют эффективные методы построения ДНФ функции по перечню нулей. Заметим, что в ДНФ содержится та же информация о функции, что и в сокращённой ДНФ (см., например, [47]). Кроме того, сложность процедуры распознавания пропорциональна числу элементарных классификаторов (см., например, (1.7)). Поэтому представляет интерес задача синтеза «несложных» ДНФ. Бели качество построенного алгоритма распознавания окажется недостаточно высоким, ДНФ всегда можно «пополнить» операцией обобщенного склеивания [13]:
Возможно также достроение ДНФ до сокращённой методом Блейка [13,47]: применение к ДНФ операций (1.10) и (1,1) до тех пор, пока не перестанут образовываться новые конъюнкции. Заметим также, что в сокращённой ДНФ содержится много «лишних» конъюнкций (использование которых не повышает качество распознавания). Отметим, что разные обобщения понятия элементарная конъюнкция позволяют по-разному формализовать понятие «элементарный классификатор». Т-конъюнкция выделяет характерное подописание (а, ,...,«у ) и опорное множество Н-конъюнкция выделяет множество характерных подописаний X М,. Для А-конъюнкции это множество имеет вид X [ЬпсА. Поэтому А-ДНФ следует использовать, когда важна упорядоченность значений признаков: 0 1 ... -1. Н-ДНФ — когда качественно значения признаков означают принадлежность типу и нет упорядоченности. Т-ДНФ — когда важен поиск точечных закономерностей в исходных данных и необходимо выделить информативные фрагменты описаний объектов. В [26] рассмотрены элементарные конъюнкции вида (1.5% где — множество выделенных подмножеств Е . В настоящей работе рассмотрены различные формализации понятия «элементарная конъюнкция» и «элементарный классификатор», в том числе самые общие. Задача построения коротких ДНФ функции по перечню её нулей была рассмотрена только для Т-ДНФ [37]. Но предложенные алгоритмы не подходят для синтеза логических распознающих процедур. Это связано с тем, что построенные ДНФ должны определять такие системы опорных множеств, для которых все признаки в некотором смысле были бы равнозначны. В частности, если СІ — система опорных множеств, то значения р(і)=\{СіеС1 ]їєП} должны быть примерно равны для всех і є {1,2,..., и}. ДНФ, которые соответствуют таким системам опорных множеств, называются равномерными (далее понятие будет уточнено). Таким образом, в теории распознавания возникает задача построения коротких ДНФ (различных типов: А-ДНФ, Н-ДНФ, Т-ДНФ и др.) бинарных функций А-значной логики с «небольшим» числом нулей, обладающих к тому же дополнительными свойствами.
Реализация метода Нельсона на ЭВМ
Пусть D0 - множество конъюнкций из D, не содержащих букв из множества { !,..., „}, Dx — содержащих ровно одну букву из множества {xv...,xn}, а остальные конъюнкции образуют множество D2 = D\Di\D0. Очевидно, что все конъюнкции из множества Z)j u D2 допустимы для функции / в ДНФ Z f v flf - поильная. Поэтому искомую ДНФ можно „острое, выполнив умножение в Заметим, что конъюнкции из D1u D2 не могут поглощаться конъюнкциями, полученными в результате умножения в (3.6) 1 Пусть DF = К v...v К тогда, выполнив формально умножение в (3.6), получаем множество конъюнкций D& = {xlKli...,хпК,... АТ ..,хнК}\{0). Ясно, что конъюнкции из этого множества не могут поглощать друг друга и не могут поглощаться конъюнкциями из D2 \ Следовательно, для построения правильной ДНФ Действительно, пусть Кх є D w 2 D, К2 = хК , Кг є DQ D, тогда если Кх - К2, то К. функции f достаточно проверить только поглощения вида К} ч К2, Кх є D&, K2&Dl. Пусть конъюнкции из Dv содержащие букву xft составляют множество Dln /є {1,2,...,«}, т.е. Dx -Dn \J... JD1TI. Тогда любая конъюнкция К2 из Du имеет вид xt & xf, Xс{1,2,...,л}\{ }, она может поглощать конъюнкции из множества {х ,... К }\{0} и не поглощает остальные конъюнкции из D&. Каждая конъюнкция Kf имеет вид & xjt Xt с {1,2,...,«}, t є{1,2,..., ), поэтому конъюнкция К2 поглощает только конъюнкции из множества При построении сокращённой ДНФ по перечню нулей методом Нельсона, последовательно перемножая скобки, необходимо осуществлять умножения вида (xl v...\/x")&DF. Заметим, что все, сказанное в 3.3, справедливо и для задачи построения сокращённой ДНФ функции / = F[{ax,.„,а +1}] по сокращённой ДНФ DF функции F[{S\...,a }]. При этом искомая ДНФ строится выполнением умножений в (3.6), все конъюнкции множества Dx u D2 принадлежат сокращённой ДНФ функции / , а все конъюнкции множества DQ - нет. Осуществив все поглощения вида Kt К2, Кх є D&, К% є Dx, получаем сокращённую ДНФ функции / . При реализации алгоритмов построения ДНФ на ЭВМ одними из наиболее трудоёмких операций являются операции по выделению памяти под конъюнкции и удалению конъюнкций. Поскольку заранее неизвестно число всех конъюнкций, с которыми придется работать, ДНФ представляют в виде динамических списков (а не массивов). Сами же конъюнкции для быстроты работы с ними (например, для эффективного конъюнктивного умножения) удобно представлять в виде массивов (векторов). Заметим, что условие i%Xt X в (3,7) можно эффективно проверять, не создавая новой конъюнкции x.Kf, а используя память, выделенную под конъюнкцию К. Этот факт позволяет реализовать метод Нельсона, минимизируя число трудоёмких операций создания/удаления конъюнкций. Будем кодировать элементарную конъюнкцию К = х1 &... & хт вектором v(K) = (vp... ,v„) \ где v = 1- ,..., =l-crr, vt = 2 при ig{i,,...,/r}. Учитывая способ представления информации в ЭВМ, будем использовать векторы из множества X {0,1,2,3}. Пусть построено множество векторов v= ІІМЛ), DF — сокращённая ДНФ функции [{сг1 ,.-,# }] Покажем как построить множество векторов V , соответствующее сокращённой ДНФ функции F[{a1,...,се ,а}], a = {al,...,an)) не используя при этом лишнюю память. Предложим следующую реализацию метода Нельсона. 1-й этап: пометка векторов. 1. Сравниваем покоординатно вектор а с векторами из Г. В результате выделим подмножество V2, FjCF, векторов, имеющих более одной совпадающей координаты, подмножество Vx векторов, имеющих ровно одну совпадающую координату, и подмножества Vu={v Vi\vi-ai) для всех і є (1,2,...,«}. Здесь и далее І -ю координату вектора К будем обозначать через 1 . -69 2. Последовательно просматриваем векторы из множества V0 = VIVX !V2. Пусть текущий вектор - v. 3. Последовательно просматриваем все координаты вектора v равные двум. 4. Для каждой координаты v. = 2 просматриваем последовательно все векторы из Vy. Пусть такой текущий вектор и є Vl..
Возможность построения произвольной ДНФ с помощью кодировки. Построение сокращённых Н-ДНФ и Т-ДНФ
Поэтому либо элемент дг принадлежит сразу всем множествам /.,...,/, либо не принадлежит ни одному из этих множеств. В любом случае получаем противоречие с исходным предположением. Следовательно, из принадлежности х правой части равенства (3.9) следует принадлежность множеству, записанному в левой части этого равенства. Утверждение доказано. Замечание. Формулу (3.9) можно также получить следующим образом. Преобразуем формулу СВ. Яблонского (1.2) при (tlt...,tn) = (1,2,..,, ) к виду
Теперь сделаем формальные замены: д -»/ v -» u, & -» п, -і переводится в теоретико-множественную операцию «не». Учитывая, что An В A\Bt получаем тождество (3.9). В 3.4 показано, как исключать лишние конъюнкции из множества D& для получения правильной ДНФ функции / . Однако очевидно, что, вообще говоря, можно исключить гораздо больше конъюнкций. Мы будем строить искомую ДНФ в виде D[ V D% V Z f так, чтобы N(D,) = N(D0)\{(0,...,0)}. Полагаем I.,=JV({A 0}) для всех /є {1,2,..., } в (3.9), тогда Іги...иІ = -N(DQ). Покажем как покрывать множество If \І, = N({Kf})\N({K}) для Проведя последовательно такие удаления (каждый раз после удаления множество Y модифицируем), из множества Y получаем множество Y. При этом ДНФ Df v D v [Y2lf v... v [Y -lf v [? f v f реализует функцию f , и при упрощении мы использовали анализ только условий вида (ЗЛО), что может быть сделано до создания конъюнкций из Y0,Y2y,...,Y x,Yf (как это делалось в 3.4 при реализации метода Нельсона). Естественно, сложность построенной ДНФ зависит от нумерации конъюнкций во множестве D0. Пример3.5. Построим ДНФ булевой функции F[{a1,,,,ia1} \ по ДНФ булевой функции F{{а 1,.,.,&6}] из примера 3.1, а7 =(110000). Очевидно, что Заметим, что х х х ч 2 3 , поэтому конъюнкция jfjjCjjCj jfj удаляется. Других поглощений нет. Конъюнкция xix2x4xsx6 приводится к простой импликанте ХуХ2х6. Остальные построенные конъюнкции являются простыми импликантами. Искомая ДНФ — Замечание. Во множестве YQ = (J{jfrf f0} каждую конъюнкцию xdK можно заменить конъюнкцией xdKf для произвольного /є {1,2,...,q}. He трудно видеть, что при этом получаются допустимые для / конъюнкции. Так, в примере 3.4 -Все предложенные методы построения ДНФ были реализованы на ЭВМ. Для задачи построения ДНФ, заданной перечнем нулей a1,..., a , наиболее эффективным оказался следующий метод. ДНФ строится последовательно:
Каждый переход осуществляется по обобщённой формуле СВ. Яблонского в соответствии с 3.3, 3.5 (см. также приложение).
Отметим важную особенность предложенных в диссертации алгоритмов. Одним из основных требований к алгоритму является простота его реализации на ЭВМ в виде программы (или фрагмента программы). Простота обеспечивает «лёгкую» отладку и доработку программы. Заметим, что редукционный алгоритм Журавлёва-Когана [33, 37], несмотря на простоту формулировки, не обеспечивает простоту реализации. Ясно, что реализация этого алгоритма предполагает рекурсивную процедуру, которой в качестве параметра должна передаваться матрица (это приводит к неэффективному использованию памяти) или параметры этой матрицы (номера строк и столбцов основной матрицы нулей). В последнем случае приходится писать процедуры перенумерации строк и столбцов. Алгоритмы, предложенные в диссертации, допускают простую и эффективную реализацию. Например, не составит труда написать программу по алгоритму из 3.4. Метод построения по обобщённой формуле СВ. Яблонского отличается только процедурой удаления из ДНФ «ненужных» конъюнкций.
