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

• Шабанин, Олег Васильевич
• кандидат физико-математических наук
• 2000

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

Введение. ~>

Глава1. Оценка сложности дизъюнктивной нормальной формы пороговых функций.

§1.0 связи числа нижних единиц пороговой функции с коэффициентами вектора Чоу.

§ 2. Оценка сложности дизъюнктивной нормальной формы пороговой функции в "типичном" случае.

Глава 2. Оценки сложности многочлена Жегалкина пороговой функции.

§1.0 связи длины многочлена Жегалкина булевой функции с числом нижних единиц. Оценк&дай&Ш!>$шогочлена Жегалкина пороговой функции в "типичуом'^Ш^^чае

§ 2. Оценка степени многочлена Жегалкина пороговой функции.

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

§ 1. Оценки расстояний между классами обобщенно-монотонных и линейных функций.

§ 2. Некоторые неравенства для коэффициентов Чоу пороговых функций.

§ 3. Декомпозируемость самодвойственных пороговых функций.

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

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

Интерес к теории сложности стимулируется вычислениями на ЭВМ. Основные результаты по теории сложности связаны с именами К. Шеннона, С.В. Яблонского, О.Б. Лупанова, Ю.И. Журавлева, Р.Г. Нигматуллина, А.Д. Коршунова А.Д. и ряда других авторов. Достаточно полный обзор результатов по теории сложности представления булевых функций в различных базисах из функциональных элементов можно найти в работе Р.Г. Нигматуллина "Сложность булевых функций". Оценка сложности д.н.ф. пороговых функций представляет теоретический и практический интерес. Хорошо известен факт, что пороговых функций от п переменных имеет мажоритарная функция. Большая сложность реализации пороговых функций в "традиционных" базисах служит аргументом для использования в ряде случаев пороговых представлений булевых функций вместо наибольшую сложность д.н.ф., равную в классе представлений в виде д.н.ф. С другой стороны, исследование сложности д.н.ф. пороговых функций тесно связано с проблемой алгоритмической сложности NP - полных задач. Например, с известной задачей о ранце, имеющей естественную экономическую интерпретацию и тесно связанную с задачами линейного программирования. Изучение строения множество нулей монотонной пороговой функции может дать ответ на проблему алгоритмической сложности решения этой задачи. Отдельной задачей является получение оценок сложности д.н.ф. для "почти всех" пороговых функций.

Задача оценки сложности д.н.ф. типичной пороговой функции предложена Ю.А. Зуевым. Наилучшая известная нижняя оценка получена в работе Ю.А. Зуева и Л.И. Липкина, где доказано, что почти у всех пороговых функций сложность д.н.ф. не меньше n2Aog2n.

Оценки расстояний между монотонными и линейными функциями имеют как теоретический, так и практический интерес, связанный с потребностями теории кодирования и прикладными вопросами идентификации функций. При решении различных задач применяется метод линеаризации -приближения произвольной булевой функции линейной. С этой точки зрения расстояние по Хеммингу до ближайшей линейной функции также служит мерой сложности функции / Постановку задачи и подходы к решению можно найти в работе Балакина Г.В. и Никонова В.Г. "Методы сведения булевых уравнений к системам пороговых соотношений" (Обозрение прикладной и промышленной математики, 1994 г. -т.1, вып. 3. - с. 389 -401).

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

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

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

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

Решена задача нахождения ближайшей линейной к данной обобщенно-монотонной функции.

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

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

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

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

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

Материалы работы докладывались и обсуждались на следующих конференциях и семинарах: Конференция "Нейрокомпьютеры и их применение" (14-16 февраля 1996 г.), конференция "Нейрокомпьютеры и их применение" (4-6 февраля 1997 г.), шестая Всероссийская конференция "Нейрокомпьютеры и их применение" (16-18 февраля, 2000 г.), семинар отдела дискретной математики МИАН им. Стеклова под руководством профессора Зубкова A.M. (20 марта 1999 г.), семинар механико-математического факультета МГУ им. Ломоносова под руководством профессора Сидельникова В.М. (20 мая 1999 г.), шестая Всероссийская конференции по стохастическим методам. (Самара, 15 - 21 августа, 1999 г.); вторая межведомственная конференция "Научно-техническое и информационное обеспечение деятельности спецслужб" (г. Москва, 4-6 февраля 1998 г.); научные семинары, проводимые в Институте криптографии, связи и информатики. Основные положения диссертации, выносимые на защиту.

1) Принципиально новые экспоненциальные асимптотические оценки сложности д.н.ф. и длины многочлена Жегалкина случайной пороговой функции.

2) Оценки степени многочлена Жегалкина пороговой функции.

3) Оценки расстояния от данной обобщенно-монотонной функции до линейной функции от одной и от нескольких переменных.

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

1. Шабанин О.В. О сложности дизъюнктивной нормальной формы пороговых функций // Обозрение прикладной и промышленной математики. Шестая Всероссийская конференции по стохастическим методам. Тезисы докладов. -М.: ТВП. - 1999. - Т. 6, вып. 1,- с. 213-214.

2. Шабанин О.В. О сложности представления пороговых функций в традиционных базисах // Шестая Всероссийская конференция "Нейрокомпьютеры и их применение". Тезисы докладов. Изд. "Радиотехника". - 2000 г. - с. 454 - 455.

3. Шабанин О.В. О сложности представления пороговых функций в традиционных базисах // Информационные технологии. - 2000 г. - N 10. - с. 45 - 48.

4. Шабанин О.В. О сложности дизъюнктивной нормальной формы пороговых функций // Дискретная математика. - 2000 г. - Т. 12, вып. 2. - с. 85 - 92.

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

Пороговой функцией [3], [5], [60] называется двоичная или булева функция / : {0, 1}" —» {0, 1} такая, что существуют действительные числа W\, ., wn, Т, удовлетворяющие условию хЬ Хъ ., X») = 1 О wpci I . + wnxn > Т. При этом будем говорить, что функция / имеет реализацию [wh ., wn;7].

Коэффициенты w,- называются весами, Т- порогом.

Будем считать, что два вектора (xh ., х„) и (yh ., у„), Xj,yj е {0,1}, /=1,2,., л, связаны соотношениями (х1; ., хп) < (уь ., у„), если Xi < yt для всех / = 1,2, ., п; (xh ., хп) < (yh ., у„Х х„у{ Е {0, 7}, i = 1, 2, ., п, если ., хп) < (Уь . Уп\ НО (хь ., хп) ф (уь ., у„).

Функция f(x\,x2,.,xn) называется монотонной, если из условия (хь . Хп) < (уь Уп) следует/(xj , . xw) < f {ух , ., Уп).

Нижней единицей монотонной функции / (Х] , ., х„) называется вектор (аь ., ап) такой, что/(аь ., ап) = 1 и f {Ь\, Ь„) = 0 для любого (bi, b2, . b„) < (ah .,a„).

Элементарной конъюнкцией называется логическое произведение и = х? ■х** •.•х

1 2 'к где все х, различны и f * При сг = 1,

X = < х©1 при сг — 0.

Представление булевой функции / х2) ., х„) в виде дизъюнкции элементарных конъюнкций, называется ДИЗЪЮНКТИВНОЙ НОрмаЛЬНОЙ формой фуНКЦИИ f(X\ , Л'2, ., хп).

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

Функция / (х\, х2, ., хп) называется обобщенно -монотонной, если существует монотонная функция g (х\, х2, ., х„), однотипная с функцией j{X], х2, ., хп).

Для монотонной функции / обозначим через Lv (f) - количество нижних единиц функции / Для обобщенно -монотонной функции g положим Lv (g) - количество нижних единиц монотонной функции, однотипной с функцией g.

Известно, что любая пороговая функция является обобщенно-монотонной. Учитывая тот факт, что для монотонной функции нижние единицы и только они соответствуют простым импликантам в записи д.н.ф. [44], легко показать, что минимальное число импликант, входящих в запись д.н.ф. пороговой функции равна Lv (f).

Для удобства выкладок перейдем к базису {-1,1}. При дальнейшем изложении часто будем рассматривать двоичные функции, отображающие {-1Д}П в {-1Д}. Однозначное соответствие таких функций булевым осуществляется заменой переменных и значений, равных "-1" на "О". Известно [3], что функция / является пороговой в базисе {0,1} тогда и только тогда, когда/ - пороговая в базисе {-1,1}. Все введенные выше определения несложно перенести на базис {-1,1}. При этом останутся в силе и сформулированные выше результаты.

Для двоичной функции f(X], х2, ., хп) обозначим .Г1(1)= { (ah аъ . ап)е{-1, 1}" :f(ah а2, ., а„)= 1}.

Заметим, что порог Т , по существу, входит в определение пороговой функции f(x 1, х2, . , хп) равноправно с весами wu w2, ., w п. Это позволяет ввести дополнительную переменную хп+\ и рассмотреть функцию от п +1 переменных g(xb--4Xnixn+\) = xn+\ ' f(x\>--->xn) vxn+l ' f(xb---?xn) » совпадающую с исходной функцией f{x\, х2, ., хп) в подкубе хп+\=\. Нетрудно также заметить, что функция g является самодвойственной, то есть g(xj,х2,.,хп+]) = g(xl,х2,.,хп+1). При этом известно [3], что функция g является пороговой тогда и только тогда, когда / - пороговая.

Большинство введенных выше определений и обозначений можно найти в работах [3], [5], [44].

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

Подмножество вершин куба {О, 1}п будем называть пороговым, если оно отделимо от своего дополнения гиперплоскостью. Таким образом, с каждой пороговой функцией / связаны два пороговых множества: пороговое множество ее нулевых вершин /~1(0) и пороговое множество ее единичных вершин / '(О- Каждое из них (как легко видеть) является связным, т.е. из произвольной вершины можно попасть в любую другую, переходя по ребрам куба и не выходя за пределы множества.

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

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

Первой работой, положившей начало развитию пороговой логики, послужила статья американских ученых Маккалока и Питтса [59], вышедшая в 1943 г. В ней была предпринята попытка описания функционирования нервной клетки - нейрона с помощью логической функции, получившей название пороговой. Эти идеи, развитые в дальнейшем Розенблаттом [32], впервые показавшим адаптивные возможности такой модели, стали в настоящее время органической частью теории искусственных нейронных сетей [36] - одного из ведущих направлений современных исследований по искусственному интеллекту.

В конце пятидесятых годов пороговые функции привлекли внимание исследователей простотой своей технической реализации, открывавшей возможности эффективного использования в логических схемах. Шестидесятые годы относятся к периоду бурного развития пороговой логики, о которой уже говорят как о сложившейся дисциплине. На это время приходится основное число исследований по пороговым функциям и функциональным возможностям синтеза в пороговом базисе, т.е. по проблематике, объединенной в настоящее время под общим термином "пороговая логика". Среди огромного числа появившихся в это время публикаций можно отметить работы Чоу К.К. [48], [49], Элгота К.К. [52], Уиндера P.O. [62], монографии Ху [58] и Дертоузоса М. [5], а среди отечественных авторов работы Нечипорука [28] и Лупанова О.Б. [20],[21], монографию Бутакова Е.А. [3].

В результате этих исследований в пороговой логике возникли параметры Чоу, появилось понятие несуммируемости как критерия пороговости, а также найдены эффективные алгоритмы синтеза управляющих систем в пороговом базисе, весьма полно отражены в вышедшей в 1971 году в США монографии Муроги С. - настоящей энциклопедии по пороговой логике [60].

Вероятностные методы в пороговой логике предложены Ю.А. Зуевым. С использованием свойств случайных +1 матриц, им была получена асимптотика логарифма числа пороговых функций от п переменных [11], [14].

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

Приведем вместе с кратким обоснованием некоторые из этих базовых для пороговой логики фактов. 1. Условия линейной разделимости множеств.

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

Функция f (х\, х2, ., х„) называется ^-суммируемой, если для некоторого j : 2 < j < к существуют j не обязательно различных наборов СС-^ j СС ^ 5., СС - g / 1 (1) и j также не обязательно различных наборов p],/32,.,/3J g/1(°) таких, что а\ + а2 + ■ ■ ■ + oi,j - + /32+. + fij , где под сложением понимается обычное покоординатное сложение векторов в поле действительных чисел. В противном случае функция / называется /с-несуммируемой. Если / к-несуммируема для всех натуральных к, то она называется несуммируемой. Критерий пороговости [52], [5].

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

Следующее понятие является одним из центральных в пороговой логике. Целочисленный вектор Ao(f ),A\(f ), ., An(f )) называется характеристическим вектором (вектором Чоу) функции f (хх2, . х„) (см. [3], [5], [60]), если

А0(/)=2"-1-|/-1а)|.

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

МЛ,.„А „(./))= ^(а, ,а2,.,ап). а1,Й2,.,а„)е,Г10)

Основное свойство, определяющее исключительное внимание к изучению характеристического вектора в пороговой логике состоит в следующем [5], [48]: если /(хь хъ ., - пороговая функция, то для любой функции g(xb х2, хп) : g*f верно

AQ(g),Ax(g), .,An(g))*(A,(f),Ax(f), .,An(f)). Данное свойство часто используется для оценки числа пороговых функций, обладающих некоторыми свойствами. В частности, число пороговых функций Р(п) от п переменных не превосходит количества всевозможных векторов (4з, А\,., Ап) с ограничениями | А , I < Т~1 для всех i = 0,1, ., п. Но тогда Р(п) < (2п + 1)"+1 .

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

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

Обозначим подфункции функции f, полученные фиксацией первой переменной.

1 (-^1 , ■■■, хп-1) =/( -1. хь . Хп.\ ), /i () =/( 1 . X], ., ХпЛ).

Тогда для характеристических векторов (A0(f.\), A\(f.\),., An(f.\)) и

4)(/i), A\{f\), ■■■, 4,(/i)) функций/.i и f\ соответственно, выполняются равенства

Л,{f) = 4-i(/i) + 4-i(/i) для всех / = 2, 3, ., п.

Нетрудно также заметить, что

Ы/(/) I < 2"'1 для всех; = 0,1, .,«.

Пусть f(X], х2, • ••> -О - пороговая функция с реализацией [w\, ., w„; 7]. Хорошо известны следующие свойства характеристического вектора (4)(/), 4(/), ., An{f)) [3]: w, >0 => 4(/) > 0, / = 1,2,.,и; w, <0 => 4(/)< 0, / = 1,2, ., л ; > Wy zz> 4(/) > 4(Л, i, j = 1,2,., и.

Данные свойства позволяют рассматривать вместо произвольной пороговой функции f (х\, х2, хп) с реализацией [w 1, ., wn; 7] однотипную с ней монотонную пороговую функцию g {х\, х2, ., хп) с реализацией [ I W\ \ ,\w2 I , ., I w „ I;

I * I I * I

Т]. При этом веса упорядочены по убыванию | w\ I > I w2 I > . > > I wn* | и (W]\ w2*, ., wn ) - перестановка чисел (w\, w2, ., wn). В ряде случаев для таких пороговых функций упрощаются формулировки и доказательства теорем.

Интересный подход к параметрам Чоу был предложен Дертоузосом [5]. Им разрабатывались также приближенные алгоритмы для получения линейного неравенства по вектору Чоу. Уиндером проведено экспериментальное исследование различных подходов к получению таких приближений. Наиболее полное освещение теоретических вопросов, связанных с параметрами Чоу, можно найти в работе Уиндера [62].

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

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

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

Изучение подобных вопросов привело к изучению пороговых представлений булевых функций - таких представлений с помощью систем линейных неравенств, когда допустимые для системы булевы наборы и только они являются нулями булевой функции. апх, + . + а1пхп >Ь} ат1х,+.латпхп>Ьт

Геометрически пороговое представление булевой функции сводится к отсечению гиперплоскостями всех ее единичных вершин. Минимальное число t(f) необходимых для этого линейных неравенств называется пороговым числом булевой функции / и наряду с длиной ее кратчайшей дизъюнктивной нормальной формой (д.н.ф.) может считаться мерой ее сложности.

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

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

Х2 +.+ *„ >—, но требует для своего представления с помощью д.н.ф. элементарных конъюнкций - огромного числа при больших п.

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

В классе всех булевых функций задача определения максимального значения порогового числа решается достаточно просто - оно, как и максимальная длина кратчайшей д.н.ф., достигается на счетчике четности и равно 2пЛ. Значительно сложнее в классе всех булевых функций оказалась задача получения порядка типичного значения порогового числа, которая до сих пор не решена до конца. В классе же монотонных булевых функций, наоборот, более простой задачей оказалось определение порядка типичного значения порогового числа, а определение порядка максимального значения столкнулось со значительными трудностями. Сначала Хаммером, Ибараки и Пильдом [55] было доказано существование монотонных булевых функций f(xх2, ., хп), с пороговым числом t(f), равным

Построенный в [56] пример воспринимался как исключительный, пока Зуевым Ю.А. и Липкиным [13] с помощью открытого Коршуновым А.Д. строения множества почти всех монотонных булевых функций [18] не было показано, что почти все они имеют пороговые числа, по порядку равные

Большой практический интерес представляет "Классификация минимальных представлений всех булевых функций от четырех переменных", проведенная Никоновым В.Г. [30]. Для каждой булевой функции от 4-х переменных в данном каталоге приводятся минимальные пороговые представления функций / и /. Относительно небольшой объем и простота обращения к каталогу обеспечиваются благодаря использованию принципа классификации булевых функций с помощью графов связности вершин.

4. Пороговая логика и теория графов.

За последние 20 лет выявились также интересные связи между пороговой логикой и теорией графов. Монотонная булева функция называется графической, если все ее нижние единицы находятся в слое 2, т.е. в ее сокращенную д.н.ф. входят только двухбуквенные конъюнкции. Графические функции от п переменных находятся во взаимно однозначном соответствии с п-вершинными графами, вершины которых соответствуют переменным, а ребра - конъюнкциям. Граф называется пороговым, если соответствующая ему графическая функция является пороговой. На языке теории графов пороговость графа эквивалентна существованию линейного неравенства, отделяющего независимые подмножества его вершин от зависимых. Введенные Хваталом и Хаммером, пороговые графы вызвали интерес у специалистов по теории графов, и им было посвящено значительное число публикаций. Они также нашли применение при управлении параллельными вычислительными процессами. В настоящее время связанные с ними вопросы вошли в монографии и учебники по теории графов [7].

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

5. Целочисленная реализация пороговых функций.

Значительный интерес представляют новейшие результаты, связанные с целочисленной реализацией пороговых функций. Основной вопрос здесь состоит в оценке диапазона весов, достаточного для реализации любой пороговой функции от п переменных. Из элементарных мощностных соображений вытекает существование пороговых функций, для которых log2|w;| >п при достаточно больших п. На заре пороговой логики такие функции были построены и в явном виде [60]. Однако верхняя оценка, основанная на неравенстве Адамара для модуля определителя, давала

I I я+1, п+\ „ togzH^—-log2—+ 1.

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

Впервые пример пороговой функции, при целочисленной реализации которой требуются веса м>г такие, что

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

ЗАКЛЮЧЕНИЕ Общим результатом работы является исследование сложностных параметров пороговых функций.

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

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

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

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

1. Балакин Г.В., Никонов В.Г. Методы сведения булевых уравнений к системам пороговых соотношений. - Обозрение прикладной и промышленной математики. ТВП, - 1994 г., Т.1, вып. 3, с. 389 -401.

2. Блох М., Моравек Я. Оценка числа пороговых функций // Кибернетический сборник. Новая серия. Вып. 6. М.: Мир, 1969. - С. 82-88.

3. Бутаков Е.А. Методы синтеза релейных устройств из пороговых элементов М.: Энергия, 1970.

4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М. : "Наука", 1977 г.

5. Дертоузос М. Пороговая логика. М.: Мир, 1967.

6. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: 1976.

7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.

8. Журавлев Ю.И. Оценки сложности алгоритмов построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. // Дискретный анализ. Вып. 3. Новосибирск, 1964. - с.41 - 77.

9. Журавлев Ю.И. Алгоритмы построения минимальных д.н.ф. для функций алгебры логики. В сб.: Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974, с. 67 - 82.

10. Ю.Зуев Ю.А. О статистических свойствах принятия решения большинством голосов в задачах классификации // Докл. АН СССР. 1986,- Т. 288, N 2. - С. 320-322.

11. П.Зуев Ю.А. Асимптотика логарифма числа пороговых функций алгебры логики // Докл. АН СССР. 1989. - Т. 306, N 3. -С.528-530.

12. Зуев Ю.А. Пороговые функции и пороговые представления булевых функций // Математические вопоросы кибернетики. Вып. 5. 1994. - с. 5 -61.

13. Зуев Ю. А., Липкин Л.И. Регулярные булевы функции с заданной сложностью дизъюнктивных нормальных форм // Методы дискретного анализа в изучении булевых функций и графов, вып. 48 Новосибирск : ИМ СО АН СССР, 1989, с. 17 -22.

14. Зуев Ю.А. Комбинаторно вероятностные и геометрические методы в пороговой логике // Дискретная математика. - 1991. -Т. 3, вып. 2. - с.47 - 57.

15. Зуев Ю.А., Иванов С.К. О статистических свойствахвзвешенного голосования // Докл. РАН. -- 1995. Т. 342, N 5. -С. 586-588.

16. Зуев Ю.А., Иванов С.К. Обучение и самообучение в процедурах взвешенного голосования // Журн. вычислит, математики и матем. физики. ~ 1995. ~ Т. 35, N 1. ~ С. 104121.

17. Коробков В.К. О некоторых целочисленных задачах линейного программирования // Проблемы кибернетики. Вып. 14. М.: Наука, 1965. - С. 297-299.

18. Коршунов А.Д. О числе монотонных булевых функций // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. - С. 5-108.

19. Коршунов А.Д. О сложности кратчайших дизъюнктивных нормальных форм случайных булевых функций. // Методы дискретного анализа в оптимизации управляющих систем. Вып. 40. Новосибирск : ИМ СО АН СССР, 1983. - С. 25 - 53.

20. Лупанов О.Б. О синтезе схем из пороговых элементов // Проблемы кибернетики. Вып. 26. -- М.: Наука, 1973. С. 109140.

21. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М.: Изд. МГУ, 1984.

22. Лупанов О.Б. О методах получения оценок сложности и вычисления индивидуальных функций // Дискретный анализ. Вып. 25. Новосибирск, 1974. - с. 3-18.

23. Мак-Вильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

24. Месси Дж. Пороговое декодирование. М.: Мир,1966.

25. Минский М., Пейперт С. Персептроны. -М.: Мир, 1971.

26. Мур Э.Ф., Шеннон К.Е. Надежные схемы из ненадежных реле // Кибернетический сборник. Вып. 1. М.: ИЛ, 1960. — С. 109148.

27. Нейман Дж. Вероятностная логика и синтез надежных организмов из ненадежных компонент. — В сб.: Автоматы. -М.: ИЛ, 1956, с. 68-139.

28. Нечипорук Э.И. О синтезе схем из пороговых элементов // Проблемы кибернетики. Вып. 11. -- М.: Наука, 1964. ~ С. 4962.

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

30. Никонов В.Г. Пороговые представления булевых функций. -Обозрение прикладной и промышленной математики. ТВП, -1994 г., Т.1, вып. 3, с. 402-457.

31. Пирс У. Построение надежных вычислительных машин. М: Мир, 1968.

32. Розенблатт Ф. Принципы нейродинамики (персептрон и теория механизмов мозга). М.: Мир, 1965.

33. Селезнева С.Н. // Дискретная математика. 1997. - Т. 9, вып. 4. - с.24 - 31.

34. Селезнева С.Н. // Дискретная математика. 1998,- Т. 10, вып 3, с. 64 - 72.

35. Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991.

36. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. М., Мир, 1992

37. Шабанин О.В. О сложности дизъюнктивной нормальной формы пороговых функций // Обозрение прикладной и промышленной математики. Шестая Всероссийская конференции по стохастическим методам. Тезисы докладов. М.: ТВП. 1999,- Т. 6, вып. 1, с. 213 - 214.

38. Шабанин О.В. О сложности представления пороговых функций в традиционных базисах. // Шестая Всероссийская конференция «Нейрокомпьютеры и их применение». Тезисы докладов. Изд. «Радиотехника», 2000 г, с. 454 455.

39. Шабанин О.В. О сложности представления пороговых функций в традиционных базисах. // Информационные технологии. 2000 г. -N 10. - с. 45 -48.

40. Шабанин О.В. О сложности дизъюнктивной нормальной формы пороговых функций // Дискретная математика, 2000 г Т. 12, вып. 2, с. 85 -92.41 .Шеннон К. Работы по теории информации и кибернетике. -М.: ИЛ, 1963.-с. 9-45.

41. Шурупов А.Н. О функциональной разделимости булевых пороговых функций. // Дискретная математика. 1997. - Т. 9 вып. 2. - с.59 - 73.

42. Яблонский С.В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. Вып. 2.-М.: Физматгиз, 1959.-е. 75 121.

43. Яблонский С. В. Введение в дискретную математику. М.: Наука. - 1979.

44. Яджима С., Ибараки Т. Нижняя оценка числа пороговых функций // Кибернетический сборник. Новая серия. Вып. 6. -М.: Мир, 1969.-С. 72-81.

45. Alon N., Vu V.H. Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs // J. Combin. Theory, A. 1997. - V.79. - P. 133-160.

46. Ashenhurst R.L. The decomposition of switching functions. Ann. of Comput. Labor. Of Harv. Univ., 1959, N 29, pp. 74 116.

47. Chow C.K. On the characterisation of threshold function // Minimization of Booleon Function and Logic Design. Switching Circuit Theory and Logical Design / AIEE Special Publication S-134, Sept. 1961. P. 34-38.

48. Chow С.К. Statistical independence and threshold functions // IEEE Trans, on Electronic Comput. 1965. - V. Ec-14, N 1. - P. 66-68.

49. Chvatal V., Hammer P.L. Aggregation of inequalities in integer programming // Annals of Discrete Mathematics. 1977. - N 1. - P. 145-162.

50. Condorcet M.J. Essai sur l'application de l'analyse a la probabilite des decisions rendues a la plurit e des voix. Paris, 1785.

51. Elgot C.C. Truth functions realizable by single threshold organs // Minimization of Booleon Function and Logic Design. Switching Circuit Theory and Logical Design / AIEE Special Publication S-134, Sept. 1961. P. 225-245.

52. Furedi Z., Kahn J., Kleitman D.J. Sphere covering with incomparable centers // Discrete Mathematics. 1990. - V. 83, N 1. -P. 129-134.

53. Gabelman I.,J. «А Note on the Realization of boolean Functions Using a Singl Threshold Element», IRE TEC, Vol. EC-11, No. 2, pp. 639-642.

54. Golomb S.W. On the classification of the Boolean functions. IRE Trans. CT6, 1959, 176 - 186.

55. Hammer P.L., Ibaraki Т., Peled U.N. Threshold numbers and threshold completions // Annals of Discrete Mathematics. ~ 1981. N 11. - P. 125-245.

56. Hastad J. On the size of weights for threshold gates // SIAM J. Discrete Math. 1994. - V. 7. - P. 484 - 492.

57. Hu S.-T. Treshold logic. Berkeley: Univercity of California Press, 1965.

58. Muroga S. Threshold logic and its applications. New York : Wiley, 1971. -478 p.61 .Piers W.H. Failure Tolerant computer dezign. - New York and London: Academic Press, 1965. Рус. пер.: Пирс У. Построение надежных вычислительных машин. - М.: Мир, 1968.

59. Winder R.O. Chow Parameters in Threshold Logic. J. of the Association for Computing Machinery, vol. 18, N 2, 1971, pp. 265 -289.

60. Widrow В., Lehr M.A. 30 Years of adaptive neural networks: perceptron, madaline, and backpropagation // Proceedings of the IEEE. 1990. - V.78, N 9. - P. 1415-1442.