Теорема Анселя о числе монотонных функций

Обозначим Е = {0,1}.

Для а = а_п),? =• (Д,…,/?_n) G Е^п будем писать, а < Д если а* < Д для всех i = 1,…, п. Пишем (ori,…, а_п) ДО, если (си,…, а_п) < (Д,…, р_п) и существует такой номер г G {1,…, п}, что а* < Д.

Как и ранее будем описывать тест с помощью булевого вектора? = € Е^п.

Пусть Т = T (Ti, T2) — множество всех тестов для обучающей выборки 7, Т₂.

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

Сопоставим множеству Т его характеристическую функцию fr (t) • Е^п —> Е такую, что.

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

Напомним, что булева функция /(a?i,…, т_п) называется монотонной., если для любых наборов (сц,…, с*_п) и (Д,…, Д) таких, что а* < Д, i = 1,…, п, имеет место соотношение.

Отсюда следует, что число |Т (п)| различных множеств Т всех тестов для некоторых обучающих выборок над множеством признаков {1,2,…, гг} оценивается сверху с числом, монотонных функций от п переменных.

Набор («i,…, Q_n) называется единицей {нулем) монотонной функции /, если

(соответственно /(«х,…, а_п) = 0).

Единица (нуль) монотонной функции / (ах,…, а") называется нижней единицей {верхним нулем) /, если для любого (А, ••-,&>)> такого, что (А,…,Р_п) < (о^,…, а"), выполняется /(А,… , р_п) = 0 (соответственно, для любого {Pi,. —, Р_п), такого, что (а_ь…, а_п) < {Pi,…, Рп), выполняется f (pi =.

1).

С другой стороны справедливо утверждение.

Лемма 3. Для любой монотонной булевой функции f фО существует обучающая выборка Т, Т₂, для которой

Доказательство. Пусть {foi,…, 6*} С Е^п — множество верхних нулей функции /. Положим 7 = {а}, где, а = (ах,…, а_п) =.

(1…1) — единичный набор, Т₂ = {{ц,…, 6*}.

Покажем, что /r (Ti, r₂) — /•.

Рассмотрим произвольный набор? = (tx,…, ?"), на котором f{ti,…, ?") = 1, и произвольный верхний ноль.

Так как /(6ц,…, М = о, то наборы? и bi либо несравнимы, либо 6 < ?. Следовательно, существует номер j 6 {1…п}.

такой, что tj > bij, т. е. ?у = оу = 1, 6у = 0. Откуда в силу произвольности ^ следует, что? — тест для Гх, Г₂ и /r (Ti, r₂)(0 ⁼ 1- Рассмотрим произвольный набор t = (?х,… ,?"), на котором /(t 1,…, t") = 0. Тогда существует верхний ноль.

такой, что? < bi. Это означает, что для любого такого номера j € {1,2, что tj = 1, выполнено 6у = 1 = оу. Следовательно, на множестве? наборы 6* и а совпадают, и, значит,? — не тест для Т_иТ₂ и /т<�Т, Г_а)(<) = 0.

Лемма доказана. ?

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

Рис. 1.11:

Задача определения числа ф (п) монотонных булевых функций от п переменных была поставлена Дедекиндом в 1897 г. [76] и была решена им для п = 4.

Здесь мы покажем, что.

где [п/2] — наибольшее целое, меньшее или равное п/2, С™ — число сочетаний из п элементов по т, причем считается, что С"¹ = 0. Нижняя оценка в этих неравенствах была получена Э. Н. Гильбертом [13], а верхняя — Ж. Анселем [6]. Отметим, что Коршуновым А. Д. [31] получена асимптотика числа ф (п) при п —* оо.

Последовательность элементов из Е^п называется цепью, если получается из (3^ заменой одного нуля (в наборе координат) на единицу, i = 1,2,…, m — 1. Тем самым, < /?(²> < … <

Если три элемента 04,6*2,<*з из Е^п образуют цепь, то четвертый элемент /?, образующий вместе с ними квадрат (см. рис. 1.11), называют дополнением цепи 04,02,03 А° квадрата. Лемма 4 (Анселя). Единичный п-мерный куб Е^п может быть покрыт множеством из попарно непересекающих;

ся цепей, обладающих следующими свойствами:

• а) число цепей длины п — 2р + 1 равно С? — С%~¹ (0 < р < [п/2]), и минимальный элемент каждой такой цепи есть набор с р единицами и п — р нулями, а максимальный — с р нулями и п — р единицами;
• б) если заданы три элемента 04,02,03, образующие цепь и принадлежащие одной и той же цепи длины п — 2р + 1,

Рис. 1.12:

то дополнение цепи а 1,02,0:3 до квадрата принадлежит цепи длины п — 2р — 1.

Доказательство. Доказывать лемму будем индукцией по п.

Базис индукции. Для п— 1,2 лемма верна.

Индуктивный переход.

• 1) Куб Е^п делится на два подмножества Е? и Е™ (минимальное и максимальное), изоморфные кубу Е^п~¹ и полученные соответственно присоединением 0 и 1 слева к координатам куба Е^п~¹. В предположении, что лемма верна для куба Е^п~^х, мы покроем Е^п множеством цепей определяемых следующим образом:
• 1° Пусть Eq и Е" покрыты каждое множеством сЦ™^¹^²^ цепей, обладающих свойствами указанными в формулировке леммы (вторая часть свойства а) — без учета добавления разряда).
• 2° Пусть С1 — одна из цепей Eq. Пусть С2 — цепь, изоморфная Ci в Ei, и пусть 2/2 — ее наибольший элемент. Мы продолжим Ci, добавив к ней уг (см. рис. 1.12).
• 3° Отнимем у цепи С₂ ее наибольший элемент у₂. После осуществления преобразований 2° и 3° для новых цепей будет выполнена вторая часть свойства а).
• 4° Произведем те же самые операции со всеми цепями из

ES-

Тогда цепи, покрывающие Е^п_} не будут пересекаться и число цепей длины п — 2р + 1 будет равно.

2) Свойство б) леммы является непосредственным следствием вышеприведенной конструкции.

В самом деле, цепи в Е^п — двух сортов: «удлиненные», возникшие из цепей Е?~¹_} и «укороченные», возникшие из цепей Е^~. Рассмотрим возможные случаи для трех элементов ai, с*2, <*з, образующих цепь и лежащих на построенной цепи С в Е^п (длины п — 2р + 1).

I. С — удлиненная цепь, и аз не есть ее максимальный элемент. В этом случае а, (*2, <*з лежат на некоторой «старой» цепи в Eq~¹ (длины п — 2р). Дополнение цепи ах, а2, аз до квадрата находится на некоторой цепи С' (длины п — 2р — 2) в Eq~¹ , которая будет продолжена при переходе к Е^п до цепи длины п — 2р — 1.

И. С — удлиненная цепь, и аз — ее максимальный элемент. Пусть С = С[ (рис 1.12) возникла в результате удлинения цепи Ci из Eq~¹ С2 — цепь в Ei"^l_t изоморфная СС₂ — укороченная цепь, возникшая из С2 (С₂ имеет длину п — 2р — 1). Тогда дополнение цепи а_ь а₂, аз до квадрата есть максимальный элемент цепи С₂.

III. С — укороченная цепь. Пусть С = С'₂ возникла из цепи Сг (длины и — 2р + 2) в Е%~^г. Тогда, во-первых, а₃ — не максимальный элемент цепи С2 и, во-вторых, в силу второй части свойства а) максимальный, а элемент цепи С2 имеет р — 1 нулей. В силу свойства б) дополнение /3 цепи ai, аг, аз до квадрата принадлежит некоторой цепи С длины п — 2р в Е^~; максимальный элемент этой цепи имеет р нулей. Так как < аз < а, то р имеет не менее р + 1 нулей и поэтому не является максимальным элементом цепи С. Следовательно, (3 принадлежит укороченной цепи длины п — 2р — 1, получающейся из С.

Лемма доказана. ?

Теорема 6. Число ф (п) монотонных булевых функций п переменных удовлетворяет неравенствам

Доказательство. Нижняя оценка. Понятно, что монотонная функция однозначно задается своими нижними единицами. Любая пара нижних единиц несравнима. Поэтому любое множество несравнимых наборов может быть объявлено множеством нижних единиц монотонной функции и будет ее задавать. Поэтому число монотонных функций не меньше, чем число подмножеств попарно несравнимых наборов булевого куба. Рассмотрим множество 5, являющееся [п/2]-м слоем булевого куба Е^п_} т. е. S — множество всех наборов, содержащих ровно [п/2] единиц. Понятно, что любая пара наборов из S попарно несравнима. Следовательно, любое подмножество S может быть использовано в качестве множества нижних единиц некоторой монотонной функции. Откуда сразу следует, что.

Верхняя оценка. Рассмотрим произвольную монотонную функцию /(х 1,…, х_п). Свойство б) леммы 4 и монотонный характер функции /(xi,…, x_n) позволяют сделать следующий вывод: если значение /(xi,…, x_n) известно во всех вершинах цепей длины тг — 2р — 1, то в каждой цепи длины п — 2р + 1 существует самое большее две (соседние) вершины, где значения /(xi,…, x_n) остаются неопределенными. Тогда, если мы будем определять значения функции, начиная с самых коротких цепей, то в каждой цепи будет не более двух (соседних) вершин ari, c*2> < ог2, где функция неопределена, причем в этих вершинах функция может принимать лишь следующие наборы значений: (0,0) (0,1), (1,1). В результате получаем.

Теорема доказана. ?