Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ТЕОРЕМА АНСЕЛЯ ПРО КІЛЬКІСТЬ МОНОТОННИХ ФУНКЦІЙ

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

Для а = а п ) ,? = • (Д, ..., /? N ) G Е п писатимемо

а <Д якщо а * <Д для всіх i = 1, ..., п. Пишемо (ori, ..., а п ) <(Д, • • •> ДО, якщо (сі, ..., а п ) <(Д, ..., р п ) і існує такий номер г G {1, ..., п}, що а * <Д.

Як і раніше будемо описувати тест за допомогою булевого вектора? = € Е п .

Нехай Т = T (Ti, T 2 ) - безліч всіх тестів для навчальної вибірки 7, Т 2 .

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

Порівняти безлічі Т його характеристическую функцію fr (t)Е п -> Е таку, що

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

Нагадаємо, що булева функція / (a? I, ..., т п ) називається монотонної ., Якщо для будь-яких наборів (сц, ..., с * п ) і (Д, ..., Д) таких, що а * <Д, i = 1, ..., п, має місце співвідношення

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

Набір ( «i, ..., Q n ) називається одиницею {нулем) монотонної функції /, якщо

(відповідно / ( «х ..., а п ) = 0).

Одиниця (нуль) монотонної функції / (ах, ..., а ") називається нижньої одиницею {верхнім нулем ) /, якщо для будь-якого (А, •• -, &>)> такого, що (А, ..., р п ) <(про ^, ..., а "), виконується / (а, ... , р п ) = 0 (відповідно, для будь-якого {Pi, .. -, р п ), такого, що ( а ь ..., а п ) <{Pi , ..., Рп), виконується f (pi =

1).

З іншого боку справедливим є твердження.

Лема 3. Для будь-якої монотонної булевої функції f ФО існує навчальна вибірка Т, Т 2 , для якої

Доведення. Нехай {foi, ..., 6 *} З Е п - безліч верхніх нулів функції /. Покладемо 7 = {а}, де а = (ах, ..., а п ) =

(1 ..... 1) - одиничний набір, Т 2 = (ц, ..., 6 *}.

Покажемо, що / r (Ti, r 2 ) - / •

Розглянемо довільний набір? = (Tx, ...,? "), На якому f {ti , ...,?") = 1, і довільний верхній нуль

Так як / (6ц, ..., М = о, то набори? І bi або непорівнянні,

або 6 <?. Отже, існує номер j 6 {1 ..... п}

такий, що tj> bij, тобто ? у = оу = 1, 6У = 0. Звідки в силу довільності ^ слід, що? - тест для Гх, Г 2 і / r (Ti, r 2 ) (0 = 1 Розглянемо довільний набір t = (? Х, ...,? "), На якому / (t 1, ..., t ") = 0. Тоді існує верхній нуль

такий, що? <Bi. Це означає, що для будь-якого такого номера j € {1,2, що tj = 1, виконано 6У = 1 = оу. Отже, на безлічі? набори 6 * і а збігаються, і, отже,? - Чи не тест для Т і Т 2 і / т <Т ,, Г а ) (<) = 0.

Лема доведена. ?

З леми відразу випливає, що | 3 (п) | дорівнює числу монотонних функцій від п змінних.

Мал. 1.11 :

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

Тут ми покажемо, що

де [п / 2] - найбільше ціле, менше або рівне п / 2, С ™ - число поєднань з п елементів по т, причому вважається, що С " 1 = 0. Нижня оцінка в цих нерівностях була отримана Е.Н.Гільбертом [13], а верхня - Ж.Анселем [6]. Відзначимо, що Коршунова А.Д. [31] отримана асимптотика числа ф (п) при п - * оо.

Послідовність елементів з Е п називається ланцюгом , якщо виходить з (3 ^ заміною одного

нуля (в наборі координат) на одиницю, i = 1,2, ..., m - 1. Тим самим, </? ( 2 > <... <

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

ся ланцюгів , що володіють такими властивостями:

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

Мал. 1.12 :

то додаток ланцюга а 1 , 02 , 0: 3 до квадрата належить ланцюга довжини п - 2 р - 1.

Доведення. Доводити лемму будемо індукцією по п.

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

Індуктивний перехід.

  • 1) Куб Е п ділиться на два підмножини Е? і Е ™ (мінімальне і максимальне), ізоморфні кубу Е п ~ 1 і отримані відповідно приєднанням 0 і 1 зліва до координат куба Е п ~ 1 . У припущенні, що лема вірна для куба Е п ~ х , ми покриємо Е п безліччю ланцюгів визначаються наступним чином:
  • 1 ° Хай Eq і Е " покриті кожне безліччю СЦ ™ ^ 1 ^ 2 ^ ланцюгів, що володіють властивостями зазначеними в формулюванні леми (друга частина властивості а) - без урахування додавання розряду).
  • 2 ° Нехай С1 - одна з ланцюгів Eq. Нехай С2 - ланцюг, ізоморфна Ci в Ei, і нехай 2/2 - її найбільший елемент. Ми продовжимо Ci, додавши до неї уг (див. Рис. 1.12).
  • 3 ° Віднімемо у ланцюзі З 2 її найбільший елемент у 2 . Після здійснення перетворень 2 ° і 3 ° для нових ланцюгів буде виконана друга частина властивості а).
  • 4 ° Зробимо ті ж самі операції з усіма ланцюгами з

ES-

Тоді ланцюга, що покривають Е п} Не перетинатимуться і число ланцюгів довжини п - 2 р + 1 дорівнюватиме

2) Властивість б) леми є безпосереднім наслідком вищенаведеної конструкції.

Справді, ланцюги в Е п - двох сортів: "подовжені", що виникли з ланцюгів Е? ~ 1} І "укорочені", що виникли з ланцюгів Е ^ ~ . Розглянемо можливі випадки для трьох елементів ai, з * 2 , <* з, що утворюють ланцюг і лежать на побудованій ланцюга С в Е п (довжини п - 2р + 1).

I. З - подовжена ланцюг, і я не їсти її максимальний елемент. В цьому випадку а , (* 2 , <* з лежать на деякій "старої" ланцюга в Eq ~ 1 (довжини п - 2р). Доповнення ланцюга ах, а2, аз до квадрата знаходиться на деякій ланцюга С ' (довжини п - 2р - 2) в Eq ~ 1 , яка буде продовжена при переході до Е п до ланцюга довжини п - 2 р - 1.

І. З - подовжена ланцюг, і я - її максимальний елемент. Нехай С = С [ (рис 1.12) виникла в результаті подовження ланцюга Ci з Eq ~ 1 С 2 - ланцюг в Ei " lt ізоморфна СС 2 - укорочена ланцюг, що виникла з С2 2 має довжину п - 2р - 1). Тоді доповнення ланцюга а ь а 2 , аз до квадрата є максимальний елемент ланцюга З 2 .

III. З - укорочена ланцюг. Нехай С = С ' 2 виникла з ланцюга Сг (довжини і - 2р + 2) в Е% ~ г . Тоді, по-перше, а 3 - не максимально елемент ланцюга С2 і, по-друге, в силу другої частини властивості а) максимальний а елемент ланцюга С2 має р - 1 нулів. В силу властивості б) доповнення / 3 ланцюга ai, аг, аз до квадрата належить деякій ланцюга С довжини п - 2р в Е ^ ~ ; максимальний елемент цього ланцюга має р нулів. Так як @ <аз <а, то р має не менше р + 1 нулів і тому не є максимальним елементом ланцюга С. Отже, (3 належить укороченою ланцюга довжини п - 2р - 1, що виходить з С.

Лема доведена. ?

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

Доведення. Нижня оцінка. Зрозуміло, що монотонна функція однозначно задається своїми нижніми одиницями. Будь-яка пара нижніх одиниць незрівнянна. Тому будь-яка множина непорівнянних наборів може бути оголошено безліччю нижніх одиниць монотонної функції і буде її здавати. Тому число монотонних функцій не менше, ніж число підмножин попарно непорівнянних наборів булевого куба. Розглянемо безліч 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). В результаті отримуємо

Теорема доведена. ?

 
<<   ЗМІСТ   >>