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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М. В. ЛОМОНОСОВА

РГБ ОД

У г* " - Механико-математический факультет

На правах рукописи УДК 519.71, 519.722

Таранников Юрий Валерьевич

МНОЖЕСТВА ¿-УРАВНОВЕШЕННЫХ БУЛЕВЫХ НАБОРОВ И ФУНКЦИЙ

Специальность 01.01.09 — математическая кибернетика

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

Москва — 2994

Работа выполнена кн. кафедре дискретной математики механико-математического факультета МГУ им. М.В.Ломоносова.

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

профессор О. Б. Лупанов.

Официальные оппоненты — доктор физико-математических наук

А. А. Сапоженко, — кандидат фкзико-математкчееккх наук Г. А. Ткачев.

Ведущая организация — Институт математики

Сибирского отделения РАН.

Зашита диссертации состоится "< ' (УМ^ Д>т 1994 г. в 16 час. 05 мин. на заседании специализированного совета Д.053.05.05 при МГУ им. М. В. Ломоносова по адресу: 119839, ГСП, Москва, Ленинские горы, МГУ, механико-математический факультет, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (14 этаза).

Автореферат разослан " КтШсЩ 1994 г.

Ученый секретарь специализированного совета Д.053.05.05 при МГУ

д. ф.-м. н., профессор В. Н. Чубариков

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

Актуальность темы Последовательности. построенные из букв конечного алфапи-■гц являются важным объектом в математике и ее приложениях. 7ак, us.npnvep, задача. исследования закономерностей блуждания гастищл к& прямой сзодятся и • изучению последовательностей, 5разо:!алкых двумя буквами: —1 и 1. В задачах социальной пси-•ояигпя, социологам, биологии, медицины иногда, удобно предсте-•лять ''разницу" в поведении двух объектов в виде госяедователь-cc'jjK тт3 кулей и единиц.

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

В силу этой и рада других причин особое вигогапне уделяет-s изучению конечных двоичных последователыюстей. Так в те-оии кодирований основной объект изучений •— двоичные коды. оеольно часто математические модели тех или иных реальных роцессов, использующие двоичные последовательности, огр&ни-г:г-алэтся елучр-ем "пегявисимого" появления нуля или единицы, & шовной характеристикой поведения объекта является доля едини (кли нулей) в наборе некоторой фиксированной длины. Од-ixo в целок ряде задач возникают множества двоичных после-ж&телыюстей более сложной структуры, несущих в себе опре-мшнную зависимость ме^ду разрядами. Так, например, при со-[ании моделей физики микромира следует учитывать, что нме-

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

Цель работы

Целью дашюй работы является решение ряда задач, связи ных со свойствами /-уравновешенной метркзш*), а именно, нал зкдение числа пар наборов, отстоящих друг от друга в этой ь трике не более чем на I, нахождение "шара" ыаксиыального об ема, вычислите среднего н максимального "объема шара". Др гой целью работы является классификация булевых функций в < ответствии с их "степенью уравновешенности", решение вощ сов, касающихся описания, нахождения мощности множества уравновешенных функций и оценки сложности реализации cpyi цкй из этого множества схемами из функциональных элемент! а также получение оценок для числа наборов, на которых t vpi новешгкные функции принимают единичные значения.

Научиая ковкзка В работе на основе разработанных методов получены еле. ющне результаты, являющиеся новыми:

*) '-уравновешенная метрика на множестве двоичных набо} длины п была введена в работе:

Липатов Е. П. Об одной мере близости между объектами Сборник докладов III международного рабочего семинара "Мв матические вопросы кибернетики", Братислава, 1987. — Бра слава: Университет ни. Я. А. Коменского, 198Т, с. 30-34.

.) получены формулы для мощностей множества всех упорядо-енных пар /-уравновешенных наборов длины п и множества всех аборов, /-уравновешенных с набором 7* = (1, 0,1, 0,...); для поучения этих формул построены специальные разложения ухазан-

t

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

) решена экстремальная комбинаторная задача нахождения двойного яебора, являющегося /-уравновешенным с наибольшим чи-ijozs двоичных наборов длины п, а именно, доказано, что набор S '.'злается таким набором; для решения этой задачи построены ресбразования и отображения некоторых комбинаторных сбъек-ов (пслос специального вида и содержащихся в mix ломаных); ) найдено явное описание множества всех 1-уравтгове1аеяных бу-евых функций н разработан индуктивный метод, позволивший оказать полноту этсго описания.

Пргнстггчесзаз: дслпость

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

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

кретиом кодировании объектов, обладающих некоторыми сво ствами непрерывности (например, функций).

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

Апробатя результатов Результаты настоящей работы докладывались и обсужд лись на школах-семинарах по синтезу и сложности управляют систем (Нижний Новгород, 1992 и Минск, 1993), ШЕОле-семинв по дискретным моделям в теории управляющих систем (Моек: 1993), конференции молодых ученых механико-математнческс факультета МГУ (1993), научных семинарах кафедр дискрети математики н математической кибернетики Московского унив! ентета.

Публикации

Основные результаты диссертации содержатся в работах тора, список которых помещен в конце автореферата [1—4].

Об-зЬем н структура работы

Диссертация состоит из введения, двух глав, разбитых н параграфов, и списка литературы, включающего 20 н&имено ний. Общий объем работы составляет 133 страницы. Излозге! материала проиллюстрировано 26 рисунками и 5 таблицами.

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава работы состоит из четырёх параграфов. В этой :&ве рассматриваются мнозкества /-уравновешенных наборов, зра наборов (а,/?), с? = (а1 ,...,«„), /3 = ,..., /?-,), {0,1}, г = 1, ...,тг, называется /-уравновешенной (в точности -равновешенной), если.величина

£ (<*р - М

превосходит / (равна /). Впервые /-уравновешенные наборы ли рассмотрены в работе Е. 'П. Липатова*), в-которой на мно-стве двоичных наборов было введено расстоние р{5, /3) = !, где / такое неотрицательное целое число, что наборы а и ¡3 являют-в точности /-уравновешенными. В указанной работе показано, г таким образом введенное расстояние является метрнкой.

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

Липатов Е. П.чтит. соч.

М*(а, Р) = шах

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

; В первом параграфе для мощности множества |jV"(n, /)| в упорядоченных пар I- уравновешенных наборов длины п получ< точная формула:

^=S * W)>

из которой яри I = const, л —► со следует асимптотическая ф мула:

При выводе этих формул в диссертации существенным об зом использовался аппарат теории матриц. Методика полу нкя формул состояла в разбиении исследуемого множества ] наборов на подмножества определенного вида, составлении j мощностей этих подмножеств систем разностных уравнений решении последних. Как следствие приведенных выше форм легко получаются (делением на 2П) точная и асимптотичес (при I = const, n —► со) формулы для среднего числа набос /-уравновешенных со случайно выбранным набором.

Параграфы 2 й 3 посвящены доказательству того, что набор 7^ является /-уравновешенным с наибольшим числом наборов на множестве всех двоичных наборов длины п. Е. П. Липатовым этот результат был установлен при / = 1. Доказательство этого на первый взгляд достаточно прозрачного факта на поверку оказывается, довольно трудоемким. Для придания доказательству более наглядного характера вводится ряд вспомогательных объектоз геометрического типа — ломаных и полос. Как показано в работе, мезкду наборами, /-уравновешенными с некоторым данным набором, и ломаными, содержащимися в полосах определенного вида, мозхно установить-соответствие, позволяющее перейти от рассуждений, связанных с наборами, к рассуждениям, оперирующим более наглядными понятиями ломаных и полос.

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

Параграф 3 завершает доказательство того, что набор 7„ = = (1,0,1,0,...) /-уравновешен с наибольшим числом наборов на множестве всех двоичных наборов длины п. Для этого к произвольному двоичному набору длины п применяется специальным образом определенная операция "сглаживания". Далее с применением лемм, доказанных во втором параграфе и в начале третьего параграфа, строится инъективное отображение для определенных классов ломаных в нехоторой полосе, показывающее в конечном итоге, что число наборов, /-уравновешенных с данным, но не явля-. ющихся /-уравновешенными с его сглаживанием, не превосходит

числа наборов, /-уравновешенных со сглаживанием набора, но не являющихся /-уравновешенными с самим набором. Это, вместе с тем фактом, что последовательное применение операции сглаживания к произвольному набору за конечное число шагов приводит к набору 7„, доказывает результат параграфа 3. .

После того как доказано, что набор 7* = (1, 0,1, 0,.. .) является /-уравновешенным с наибольшим числом наборов на множестве всех двоичных наборов длины п, задача нахождения максимального числа наборов, /-уравновешенных с данным набором на множестве всех двоичных наборов длины п, естественным образом сводится к задаче нахождения мощности множества ¡Л/"(-у*, /)),' состоящего из всех наборов, /-уравновешенных с набором Для случая I = 1 Е. П. Липатовым*) была получена формула

п+З

1.

Нахождению значения величины |Л^(7п1 01 ПРИ произвольном / посвящен четвертый параграф. Техника, применимая в нем, сходна с техникой, применяемой в первом параграфе, поэтому рассуждения во многом аналогичны. Разница состоит в том, что получающиеся системы разностных уравнений имеют несколько нной вид и строятся отдельно для четного и нечетного п. Решения этих систем имеют похожий зид и успешно объединяются в одну формулу:

1+1

1^(7,

1~р1 , т . п

(

Лк(1- !)■ ([-1)к+12 сов

*) Липатов Е. П. цкт. соч.

где

4 ,„ ' 2ГТЗ ^ 2(2ГТЗ)' еСЛИ к НеЧетНО'

1 1-х

-¡К2 —.—>-г, если к четно.

. 2Л-3 ь 2(21 + 3)'

И а полученной точной формулы при I =сопз1, п —► со легко следует асимптотическая:

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

Любой конечный двоичный набор, вообще говоря, задает значения некоторой булевой функции. Существуют различные способы задания отображения, которое устанавливает соответствие между набором из нулей н единиц длины п и буквами из алфавита {0,1}. Это отображение можно задавать в виде таблиц, формул, в виде подмножества вершин булева куба, в которых функция принимает единичное значение. Заданные тем или иным способом функции предполагают некоторую их классификацию: известны симметрические функции, функции с заданным числом единиц*), функции из инвариантных классов**) и так далее. Во многих случаях функцию удобно задавать в виде подмножества вершин булева куба, в которых функция принимает единичное (или нулевое)

*) Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования. // Проблемы кибернетики. Вып. 14., — М.: Наука, 1965, с. 31-110.

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

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

В настоящее время существует несколько понятий "однородности" булевых функций, и в классификации этих понятий нет пока четко выработанной терминологии. Так, часто однородной называют функцию, "центр тяжести" которой расположен точно в середине булева куба. Заметим, однако, что таким образом введенное свойство может ке сохраняться при переходе от функции, заданной на кубе, к ее подфункции, задаваемой на иодкубе. Понятие '-уравновешенности, рассматриваемое во второй главе и предложенное Е. П. Липатовым, свободно от этого недостатка. Булева функция /(ях, гг,. . ., гп) называется /-уравновешенной, если разность числа наборов, на которых функция / принимает едикнчное значение, на любых двух подкубах одинаковой размерности не превосходит /. Из определения видно, что если функция / является /-уравновешенной .на булевом кубе В", то она является /-уравновешенной к на любом его лодкубе.

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

уравновешенная функция , ~2, ..., х„) от п переменных порождена функциями /1 и /2 от (п — 1) переменной, если при разбиении п-мерного куба на два п — 1-мерных лодхуба по :-му разряду*) АТу на этих подкубах есть соответственно Л^ н Соответственно, будем говорить, что функции /1 и /2 порождают функцию /.

В шестом параграфе получены оценки для величины |А/}|, равной числу наборов, на которых функция / обращается в единицу, для функций /, являющихся /-уравновешенными. Показано, что для любого значения I существует такал положительная хон-стзлта а, что если булева функция /ют п переменных является I- уравновешенной;'то лябо ^ 21, либо ¡-/У/] ^ с; • 2П.

Таким образом, если I =соп.ч1, п —► со, то число наборов, на которых I- уравновешенная функция / обращается в единицу, либо не превосходит константы, либо равно по порядку числу всех двоичных наборов.

Основные результаты диссертации опубликованы в следующих работах:

1. Таранников Ю. В. Кл"сс 1-уравнозешенных функций и сложность его реализации. // Вестник Московского Университета. Серия 1. Математика. Механика., 1991, N 2, с. 83-85.

2. Тарашшков ГО. В. О двоичном наборе длины л, /-уравновешенно»! с наибольшим числом двоичных наборов. // Вестник Московского Университета. Серия 1. Математика. Механиха.

*) Через И/ обозначается множество всех двоичных наборов, на которых функция / принимает единичное значение.

3. Тараннкков Ю. В. О мощности множества упорядоченных пар /-уравновешенных наборов длины п. // Теоретические-и прикладные аспекты математических исследований. Сборник трудов конференции молодых ученых механико-математкческого факультета МГУ: — М.: Изд-во МГУ.

4. Таранников Ю. В. О числе упорядоченных пар /-уравновешенных наборов длины п. // Дискретная математика.

Автор выражает искреннюю признательность своим научным руководителям члену-корреспонденту РАН Олегу Борисовичу Лупанову и кандидату физико-математических наук Евгению Петровичу Липатову, а такзке кандидату физико-математических наук Ог.таю Мурад оглы Касим-Заде за всестороннюю поддержку при работе над диссертацией и глубоко скорбит по поводу скоропостижной кончины Евгения Петровича б тот момент, когда работа над .диссертацией, которой он отдал так много своей души, близилась к завершению.