А.А. Сапоженко - Оценки длины сокращённой и кратчайшей д.н.ф. для почти всех функций (1158749), страница 2
Текст из файла (страница 2)
Тогдаnk+1jΦ(I, I 0 ) = 22 −2 +2 . Имеем:k Xn n−jn − k 2n −2k+1 +2jS2 =2=jk−jk−jj=1 k n − k 2jn 2n −2k+1 X k=22 .kjk−jj=1j 2jaj+122 (k−j)2Положим aj = kj n−k2.Отношение=меньше 1,aj(j+1)(n−2k+j+1)k−jесли j < blog2 log2 nc, и больше 1, если k > j > blog2 log2 nc. ПоэтомуkX n−1 22kaj 6 k(a1 + ak ) 6 k k2 +2.k−1j=18Таким образом, 2nnk+1S2 622 −2 +1k2k3nk22kk2k 3 k22+ nnk!k2n −1=2vk (n)2k 3 k22+ nnk!,vk 2 (n).(nk)Следствие. Если k 6 k1 − 1 = dlog2 log2 n + log2 log2 log2 ne − 1, тоDvk (n) < c logn 2 n vk 2 (n), где c — константа.
4Утверждение 0.4. Пусть 1 6 k 6 k1 − 1. Тогда доля δn тех функций f ∈ Pn (α̃), для которых |vk (α̃, f ) − vk (n)| > log1 n vk (n), не превосхоа Dvk (n) 6+23дит c logn2 n .Доказательство. Применяя неравенство Чебышёва и полагаяθ=vk (n),log2 nполучаем утверждение.Утверждение 0.5. Пусть f ∈ Pn , bk (f ) — число тех вершин α̃ ∈ Nf ,k (n)для которых |vk (α̃, f ) − vk (n)| > vlog.
Пусть δn0 — доля тех функций, уnкоторых bk (f ) 6log42 n n2 .n2Тогдаδn0>1−c.log2 nnДоказательство. Оценим среднее bk (n) = 2−2Pbk (f ).f ∈Pnbk (n) = 2−2nXΦ(α̃),α̃∈B nгде Φ(α̃) — число функций таких, что α̃ ∈ Nf и |vk (α̃, f ) − vk (n)| >n −1Но Φ(α̃) = δn 226c log32 n.nvk (n).log2 nc log32 n n2 . В силу леммы 1nlog42 nbk (f ) > n , не превосходит4которых bk (f ) 6 logn2 n 2n , боль-Отсюда bk (n) 6доля тех функций f ∈ Pn , для которыхc/ log2 n.
Значит, доля тех функций f , дляше, чем 1 − logc n , что и требовалось доказать.2Теорема 3. [22] Для почти всех функций f (x̃n ) существует д.н.ф. Dnc·2nдлины l(D) . logи сложности L(D) . cn2.nlog nДоказательство. Рассмотрим подмножество Pn00 ⊂ Pn всех функций f (x̃n ), обладающих√ следующими свойствами:0n−11 . |Nf | 6 2+ n 2n−1 ;420 . bk (f ) < logn2 n 2n для всех k 6 k1 − 2;k −230 . ik1 −2 (f ) = k1n−2 2n−k1 +2−2 1 (1 + δn ), где δn → 0 при n → ∞.9Из следствия 2 и предыдущего утверждения вытекает, что почти всефункции обладают свойствами 10 и 20 .Свяжем теперь с каждой функций f ∈ Pn00 гиперграф Hf = (V, E),в котором V = Nf , а E совпадает с множеством всех интервалов функции f . Пусть F — множество всех интервалов размерностиk = dlog2 log2 n + log2 log2 log2 ne − 2,а Y — множество тех α̃ ∈ Nf , для которых vk (α̃, f ) > vk (n)(1 −41).log2 nПоложим ε = 2 logn 2 n .
Ясно, что условия леммы ?? выполняются, поэтомудлина всякого градиентного покрытия гиперграфа H не превосходит1+c · 2nlog42 n n2 + 2n−k1 +2 (1 + δn ) ln(e2k1 −2 (1 + δn0 )) ∼ k1 2n−k1 +2 ∼.nlog nОтсюда и вытекает утверждение теоремы.Таким образом, у почти всех функций f (x̃n ) длина кратчайшей д.н.ф.удовлетворяет неравенствамc · 2nc1 2n−16 l(f ) 6.log2 n log2 log2 nlog2 nОтметим, что верхняя оценка получена в теореме 3 с помощью градиентного алгоритма. Оказывается, что почти всегда с помощью весьмапростого алгоритма можно получить д.н.ф, «довольно близкую» к кратчайшей.10Литература[1] Яблонский С.
В. Функциональные построения в k-значной логике.Труды МИ АН СССР, 1958, 51, с. 5-142.[2] Яблонский С. В. Введение в теорию функций k-значной логики. Cб.«Дискретная математика и математические вопросы кибернетики»,т.1, М., «Наука», 1974, с. 9-66.[3] Журавлёв Ю. И. Алгоритмы построения минимальных д.н.ф. Сб.«Дискретная математика и математические вопросы кибернетики»,т.1, М., «Наука», 1974, с.
67-98.[4] Васильев Ю. Л., Глаголев В. В. Метрические свойства д.н.ф. Сб.«Дискретная математика и математические вопросы кибернетики»,т.1, М., «Наука», 1974, с. 99-148.[5] Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем. Сб. «Проблемы кибернетики», вып. 2,М., Физматгиз, 1960.[6] Карп Р. М. Сводимость комбинаторных проблем. Сб. «Кибернетический сборник», вып.
12 (нов. серия), М., «Мир», 1975.[7] Lubell D. A short proof of Sperner’s lemma. Journ. Comb. Theory 1,N2, 1966.[8] Ансель Ж. О числе монотонных булевых функций n переменных.Сб. «Кибернетический сборник», вып. 5, М., «Мир», 1968, с. 53-57.[9] Викулин А. П. Оценка числа конъюнкций в сокращённой д.н.ф. Сб.«Проблемы кибернетики», вып. 29, М., «Наука», с. 151-166.[10] Гаджиев М.
М. Максимальная длина сокращённой д.н.ф. для булевых функций пяти и шести переменных. Сб. «Дискретный анализ»,вып. 18, Новосибирск, 1971, с. 3-24.11[11] Нигматуллин Р. Г. Метод наискорейшего спуска в задачах на покрытие. Сб. «Вопросы точности и эффективности вычислительныхалгоритмов» (труды симпозиума), вып. 5, Киев, 1969, с. 116-126.[12] Глаголев В. В. О длине тупиковой д.н.ф. Мат. заметки, 1967, 2, №6,с.
665-672.[13] Журавлёв Ю. И. Теоретико-множественные методы в алгебре логики. Сб. «Проблемы кибернетики», вып. 8, М., Физматгиз, 1962, с.5-44.[14] Лупанов О. Б. О реализации функции алгебры логики формуламииз конечных классов (формулами ограниченной глубины) в базисе&, ∨, ¬. Сб. «Проблемы кибернетики», вып. 6, М., Физматгиз, 1961,с. 5-14.[15] Васильев Ю. Л.
О сравнении сложности тупиковых и минимальныхд.н.ф. Сб. «Проблемы кибернетики», вып. 10, М., Физматгиз, 1963,с. 5-61.[16] Журавлёв Ю. И. Оценка для числа тупиковых д.н.ф. функций алгебры логики. Сиб. матем. журнал, 1962, 3, №5, с. 802-804.[17] Васильев Ю. Л. О «суперпозиции» сокращённых д.н.ф. Сб. «Проблемы кибернетики», вып. 12, М., «Наука», 1964, с.
239-242.[18] Коспанов Э. Ш. О произведении кратчайших д.н.ф. Сб. «Дискретный анализ», вып. 18, Новосибирск, 1971, с. 35-40.[19] Левин А. А. Об относительной сложности сокращённой д.н.ф. Сб.«Дискретный анализ», вып. 15, Новосибирск, 1969, с. 25-34.[20] Левин А. А. Об отношении сложности д.н.ф. функции к сложностид.н.ф. её отрицания.
Сб. «Дискретный анализ», вып. 16, Новосибирск, 1970, с. 77-81.[21] Глаголев В. В. Некоторые оценки д.н.ф. функций алгебры логики.Сб. «Проблемы кибернетики», вып. 19, М., «Наука», 1967, с. 75-94.[22] Сапоженко А. А. О сложности д.н.ф., получаемых с помощью градиентного алгоритма. Сб. «Дискретный анализ», вып. 21, Новосибирск, 1972, с. 62-71.[23] Феллер В. Введение в теорию вероятностей и её применения, т.1. М.,«Мир», 1967.12[24] Сапоженко А. А. О наибольшей длине тупиковой д.н.ф. у почти всехфункций. Матем.
заметки, 1968, 4, №6, с. 649-658.[25] Лин Синь-Лян. О сравнении сложностей минимальных и кратчайших д.н.ф. для функций алгебры логики. Сб. «Проблемы кибернетики», вып. 18, М., «Наука», 1967, с. 11-44.[26] Сапоженко А. А. Геометрические свойства почти всех функций алгебры логики. Сб. «Проблемы кибернетики», вып. 30, М., «Наука»,1975, с. 227-261.[27] Лупанов О. Б. О синтезе некоторых классов управляющих систем.Сб. «Проблемы кибернетики», вып. 10, М., Физматгиз, 1963, с. 63-99.[28] Харари Ф.
Теория графов. М., «Мир», 1973.[29] Чухров И. П. О числе тупиковых дизъюнктивных нормальныхформ. Докл. АН СССР, 1982, 262, №6, с. 1329-1332.1314Список сокращений иобозначенийб.ф. д.н.ф. э.к. 4 x̃n Xn Bn Dc , Dfc Dκ , Dfκ DT , DfT -булева функциядизъюнктивная нормальная формаэлементарная конъюнкцияочевидное утверждениеконец доказательствавектор переменных (x1 , x2 , . . . , xn )множество переменных {x1 , x2 , . . . , xn }единичный n-мерный кубсокращённая д.н.ф. (функции f )кратчайшая д.н.ф.
(функции f )тупиковая д.н.ф. (функции f )1516ОглавлениеОценки параметров почти всех функцийОценки длины сокращённой и кратчайшей д.н.ф. для почтивсех функций . . . . . . . . . . . . . . . . . . . . . . . . . . .11Литература11Список сокращений и обозначений1517.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
