Raqamli kutubxona Kibernetikadan matematik masalalar

§ 4. Eshik ko'rsatkichlari
1. Muammoning bayoni. Eshik funktsiyalari, ya'ni
bitta chiziqli tengsizlik (1) bilan ifodalanishi mumkin, yo'q bo'lib ketadi
barcha mantiqiy funktsiyalarning kichik bir qismi. Biroq, har qanday mantiqiy funktsiya
chiziqli tengsizliklar sistemasi bilan berilishi mumkin
a \\ X \ + ... + a \ nxn ^ bu
& m \ X \ “b ... 4“ & mnXn ^ b gy
(31)
Shunday qilib, funktsiya uchun to'plamlar nolga teng va faqat ular qanoatlantiradi
tizimi. Chiziqli tengsizliklar sistemasi bilan mantiqiy funktsiyaning bunday ta'rifi
uning chegara tasviri, eng kichik soni esa w deb ataladi
buning uchun zarur bo'lgan tengsizliklar - Booleanning chegara soni t (f).
funktsiyalari /. Geometrik jihatdan funktsiyaning chegara ko'rinishi / ga qisqartiriladi
uning barcha birlik cho'qqilarini giperplanlar orqali kesib tashlash. Shuning uchun, in
bundan tashqari, funktsiya uchun identifikatsiyadan tashkil topgan chegara to'plami /
cho'qqilari / uchun joiz deb ataladi. Chegara raqami £ (/) hisoblanadi,
Shunday qilib, / pol uchun ruxsat etilgan minimal soni
qoplamalar to'plami / _1 (1).
Mantiqiy funktsiyaning chegara ko'rinishi (31) / bo'lishi mumkin
ko'rib chiqish va chegara funktsiyalarining diszyunksiyasi sifatida, ya'ni DN ga o'xshash. f.
uni 2-chi chuqurlikning diagrammasi sifatida ko'rib chiqing (3-rasm). Har qanday boshlang'ich
konjunksiya chegara funktsiyasidir, shuning uchun chegara ko'rinishlari
imkoniyatlari bo'yicha d.n.dan kam emas. f. Buning bevosita natijasi
izoh quyidagi natijadir.
Bayonot 9. Mantiqiy funktsiyaning chegara soni t (f) /
har doim uning eng qisqa dn uzunligidan oshmaydi. f ..
pol soni eng qisqa d uzunligi bilan bir xil bo'lishi mumkin Va. f., lekin
mayor misolida ancha kichik bo'lishi mumkin

40-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 43
tara funktsiyasi. Shunday qilib, seriyadagi chegara ko'rinishlari
muhim holatlar tejamkorroq.
D. N.ga ko'ra aniqlash vazifasi. f. uning chegarasining chegara funksiyasi
Bu raqam, 14-teoremaning 2 xulosasiga ko'ra, NP-qattiq allaqachon mavjud
grafik funktsiyalar sinfi. Shuning uchun o'rganish juda muhimdir
ostona ko‘rinishlari bilan bog‘liq savollarga ega bo‘ladi
chegara raqamlari qiymatlarini taqsimlash. Vazifalarni belgilash orqali va
ishlatiladigan usullar, bu tadqiqotlar tegishli muammolarga yaqin
nazariya d. n. f., bu erda eng qisqa d.n uzunliklari uchun hisob-kitoblar. f. ga bag'ishlangan
sezilarli miqdordagi asarlar (qarang [3]). Ikkala holatda ham muammo hal qilinadi
to'plamini qamrab / _ 1 (1), lekin d. n yilda. f. bu qamrov amalga oshiriladi
ruxsat etilgan elementar birikmalarga mos keladigan pastki kublar
[6], va chegara vakolatxonalarida / ~ * (1) ruxsat etilgan bilan qoplangan
chegara to'plamlari. D.N. nazariyasidagi kabi. f., ostonada
vakolatxonalar chegaraning haddan tashqari va tipik qiymatlarini o'rganadi
raqamlar va barcha mantiqiy funktsiyalar sinfi bilan bir qatorda, eng muhimi
ko'rib chiqilayotgan kichik sinf monoton funktsiyalardir.
E'tibor bering, neyron tarmoqlar nazariyasi nuqtai nazaridan, pol
ko'rinishni adaptiv ikki qatlamli neyron deb hisoblash mumkin
sozlanishi mumkin bo'lgan eng oddiy konfiguratsiya tarmog'i
birinchi qatlamning elementlari, ikkinchisi esa sobit foydalanadi
mantiqiy blok - disjunksiya. "Madalina" deb nomlangan shunga o'xshash tarmoqlar
va ularni sozlash algoritmlari adabiyotlarda ko‘rib chiqilgan (qarang [113]).
Ostona-dizyunktiv sxemalar sifatida, pol ko'rinishlari
oltmishinchi yillarda o'qigan (qarang [55]), lekin sabab bo'lmagan
katta qiziqish uyg'otadi, chunki ularni jismoniy amalga oshirish qiyin
ko'p sonli kirishlar tufayli kontaktlarning zanglashiga olib barqaror ishlashiga erishish,
har bir chegara elementiga beriladi. Nazariy nuqtai nazardan
bunday sxemalar ham ibtidoiy va iqtisodiy emas. Ko'p
kaskadli sxemalar har tomonlama jozibali ko'rinardi (qarang.
[2, 34, 55]).
Chiziqli muammolar paydo bo'lganda vaziyat o'zgardi
mantiqiy dasturlash, xususan, ko'p o'lchovli sumka muammosi:
sphp ni maksimal darajada oshirish
shartiga ko'ra
4 "♦ • • + (1shxn ^ bb
Wmixi 4- • • • + atnxn ^ bt.
(32)
(32) dagi barcha koeffitsientlar manfiy emas, shuning uchun domen
Bu erda mumkin bo'lgan echimlar monoton mantiqiy nollar to'plamidir
chegara tasviri yordamida belgilangan funksiya. Shu nuqtadan
ko'rish chegarasi tasvirlari, shekilli, birinchi marta
Korobkov tomonidan ko‘rib chiqilgan [23].
Ostona ko'rinishlar nazariyasini ishlab chiqishda alohida rol o'ynadi
(32) turdagi masalalarda chiziqli tengsizliklarni yig'ish muammosi, ya'ni.
ruxsat etilganlarni o'zgartirmasdan ularni eng kam sonli tengsizliklar bilan almashtirish
hudud. Bunday holda, chegara soni faqat maksimalni ifodalaydi
bunday yig'ilishning mumkin bo'lgan darajasi. Bu aniq birlashtirish vazifasidir
tadqiqotlarning boshlang'ich nuqtasi edi [10, 49, 64, 69]. Yugurish
oldinga, shuni ta'kidlaymizki, bularning birinchi natijalari sifatida
tadqiqotlar, umumiy holatda to'g'ri yig'ish imkoniyati juda katta
cheklangan. Eshik sonli mantiqiy funktsiyalar mavjudligi aniqlandi,
2n_1 ga teng va chegara soniga ega monoton mantiqiy funktsiyalar,
ga teng ^ [rc / 2] ^ | 71 • Biroq, bu samarali yig'ilishni istisno etmaydi
sinf kabi mantiqiy funktsiyalarning tor kichik sinflarida
grafik funksiyalar, bu erda 14-teorema bo'yicha chegara soni doimo bo'ladi

41-bet

44
Yu. A. Zuev
kamroq / g. Darhaqiqat, ushbu sohadagi natijalarning muhim qismi
aniq grafik funksiyalar uchun olingan va ichida tuzilgan
chegara grafigi parchalanish tili.
Bugun, orqaga qarab, biz pol o'rganish, deb aytish mumkin
sxemalar bilan solishtirganda yangi nuqtai nazardan taqdimotlar,
60-yillarning mantiq bo'sag'asidagi ishlari allaqachon bo'lganida
butunlay unutilgan, garchi u birinchi navbatda muqarrarga olib keldi
ma'lum natijalar kashf, ammo, barqaror qiziqish ta'minladi
uzoq vaqt davomida muammoga. Sabab
aftidan, bu erda yuzaga keladigan muammolar asosiy oqimda yotadi
zamonaviy diskret matematikaning rivojlanishi va uning ko'pchiligi bilan bog'liq
bo'limlar.
2. Chegara teoremalari. 9-bayonotga ko'ra, chegara
mantiqiy funksiyaning soni uning eng qisqa DN uzunligidan oshmaydi. f.,
va u, o'z navbatida, ma'lumki (qarang [3]), oshmaydi
2 / '“1 va f (x) = xi + ... paritet hisoblagichida bu qiymatga etadi.
... + xn (mod 2). Paritet hisoblagichining yagona tepalari bir-biriga o'ralgan
nolga teng, shuning uchun 2-bandning 3-taklifidan kelib chiqqan holda, 4-band,
ruxsat etilgan chegara to'plamlari yagona va uning chegara soni
uning birlik uchlari soniga teng, ya'ni, shuningdek, 2n ~ 1. Aniqroq,
oddiy tahlil faqat ikkita ekanligini ko'rsatadi-da
chegara raqami bu maksimalni oladigan funktsiyalar
qiymat: paritet hisoblagichi va uning inkori. Shunday qilib, bu haqiqat
quyidagi natija.
Teorema 23. n ning mantiqiy funksiyalarining chegara sonlari
o'zgaruvchilar 2n ~ 1 dan oshmaydi va har bir natural k uchun 1 <271 "1, chegara soni t (f) = k bo'lgan funktsiyalar to'plami bo'sh emas.
2P "1 ga teng bo'lgan chegara sonining maksimal qiymati ikkitaga erishiladi
funktsiyalari: paritet hisoblagichi va uni inkor qilish.
Haqiqat shundaki, chegara sonining maksimal qiymati 2P ~ 1 va
Paritet hisoblagichida erishilgani yaxshi ma'lum edi
oltmishinchi yillardagi pol mantiq bo'yicha mutaxassislar (qarang [2, 165-bet]),
ammo buning isboti birinchi marta Jeroslow tomonidan nashr etilgan bo'lishi mumkin,
u maksimal ikkiga erishiladi, deb ishora qilmagan bo'lsa-da
funktsiyalari.
Mantiqiy funktsiyaning chegara soni raqamdan oshmasligi aniq
uning birlik uchlari. Lipkin [33] ancha kam ochiq edi
uning nol cho'qqilari sonidan oshmaganligi aniq haqiqat.
24-teorema [33]. Ixtiyoriy mantiqiy qiymatning chegara soni uchun
f funksiya tengsizlikni qanoatlantiradi
t (f) Isbot. t (f) ^ 1 / ~ 1 (1) nisbati | aniq.
0) 1 munosabatini nol uchlari soni bo’yicha induksiya yo’li bilan isbotlaymiz.
/ - 1 (0) 1 = 1 uchun bu to'g'ri. Bu barcha mantiqiy funktsiyalar uchun to'g'ri bo'lsin
nollarning soni k - 1 dan oshmaydigan va f (xl ..., xn) funktsiyasi bo'lsin.
k nolga ega. Keyin har birida Xj o'zgaruvchisi mavjud
Xj = 0 va Xj = 1 pastki kublar funksiyaning nol uchlariga ega. Yo'qotmasdan
umumiylik, biz / = n deb faraz qilamiz.Xn = 1 pastki kubda mn = 1 yotsin.
funksiyaning nollari, va pastki kubda xn = 0 k - m nollar, bu erda nr k - m ^ k - l. Keyin, induksiya gipotezasiga ko'ra, tizim mavjud
m tengsizliklar
ax \ + ... + ain ^.\ Xn-i & m \ X \ "f * ... Hh am - \ xn - \ ^ bm,

42-bet

MATQIY FUNKSIYALARNING ESA FUNKSIYALARI VA BOSHQA FUNKSIYALARI 45.
{xn = 1) / funksiyasini va k - m tengsizliklar tizimini aniqlash
HT + \\ X \ "b. ... ... In— l ^ n— 1 ^
& k \ .X \ "P • • •" P n— 1 * ^ n — 1 & k 1
aniqlovchi funksiya (# i = 0) /. Keyin tizim
d \\ X \ +. ... ... + CL \ n- \ Xn- \ + Mxn ^ b \ + M,
0'm \ X \ "P... * P & mn— 1 Xn— 1” P ^ * T? R "P ^)
f 1 \ X \ T ". ... ... 4 (lm + 1n ~~ \ Xn - i ~ MXn ^ ^ mf 1 *
ak \ X \ + ... + ak n- \ Xn- \ - ^ bk,
bu erda M etarlicha katta bo'lsa, / funktsiyani belgilaydi. Teorema isbotlangan.
24-teorema darhol chegara soni mumkin emasligini anglatadi
2n ~ 1 dan oshadi. E'tibor bering, 24-teoremaning DN nazariyasida o'xshashi yo'q. f.
(qarang [7]). Shuni ham unutmangki, isbotlash jarayonida bor edi
ixtiyoriy chegara funksiyasi uchun ba'zilarida aniqlanganligi aniqlandi
birlik kubining tugun kubi, ustida belgilangan chegara funktsiyasi mavjud
tanlangan tugundagi asl nusxaga to'g'ri keladigan va teng bo'lgan barcha kub
uning tashqarisida nol.
Keling, berilgan qiymatga ega mantiqiy funktsiyalar sonini hisoblaylik
chegara raqami. Chegara funksiyalar to‘plamini Fya bilan belgilaymiz

Fp - ularning ko'pgina inkorlari. Har bir monotonik chegara funktsiyasi,
nol yoki bir xil bo'lmagan Fp ga tegishli, shuning uchun
| F «| = | Fya | = L $ -2.
25-teorema [13]. i Eshik soni t bo'lgan n ta o'zgaruvchining funktsiyalari uchun quyidagi taxminlar amal qiladi:
(A ^] 1-chi, r - 2) 4 R "(*) Isbot. Teoremaning yuqori chegarasi darhol olinadi
kuch nuqtai nazaridan. Pastki chegarani isbotlash uchun
birinchisining turli qiymatlarini o'rnatib, n o'lchovli kubda t pastki kublarni tanlang
] log £ [koordinatalar. Ajratilgan (n -] log t [) to'plami -o'lchovli
pastki kublar ikkita kichik to'plamga bo'linadi: juft va toq pastki kublar, in
] jurnal * [
yig'indisining paritetiga qarab 2 x \. Fn mantiqiy to'plamini ko'rib chiqing
r = 1
f (x 1, ..., xn) chiqish funksiyalari quyidagicha olinadi. V
tanlangan tugunlarga tegishli bo'lmagan uchlari (uchun] log t [> log £),
/ nolga tenglashtirildi. Hatto subcubes / o'yinlarning har birida
Fp-nog Ts dan o'zboshimchalik bilan tanlangan funksiya bilan, har birida
g'alati — funksiyasi bilan Pn-] 1ov * [- Keyin \ Fn \> (Nn-] logt {- 2y.
f ^ Fn funksiyaning chegara raqami t ga teng ekanligini ko'rsatamiz. Emas
t dan oshib ketishi mumkin, chunki har bir t kichik kubda / funksiyasi mavjud
chegara. t dan kam bo'lmasligini ko'rsatamiz. Buning uchun
t pastki kublarning har birida / va uchun birlik bo'lgan bitta tepani tanlang
bu t cho'qqilardan ikkitasini bittasi bilan kesib bo'lmasligini isbotlang
tengsizlik. Hatto pastki kublarda biz bunday cho'qqilarni olamiz
cho'qqilari av ~ = l, i =] log £ [+ 1, ..., n, toq bo'lganlarda - xx = 0, i =] log £ [+
+1, •••, men.

43-bet

46
10. A. ZUEV
Birinchidan, ikkita tanlangan cho'qqi a va £ ga tegishli bo'lsin
bir xil paritetning pastki kubi, masalan, juft, a = (ai, ..., ajiogf [, 1, ..., 1),
P = (Pi, fWa> 1 »1) * Keyin y = (Tb ••• cho'qqilari mavjud.
Tnog u, 1, 1) va 6 = (6i, ..., 6] i0g a [, 1, 1), bo'lmaganlarga tegishli.
hatto subkublar va, demak, / uchun nolga teng, a + p ==
= Y + 6 va havoni kesadigan har qanday giperplaneni kesish kerak
cho'qqilarning kamida bittasi yoki 6. Agar ikkita tanlangan cho'qqi a
va p turli a = paritetli subkublarga tegishli (ai, ..
1, ..., 1), p = (Pi, P] i0gi ["•••" 0 "• ••, 0)" keyin noldan kamida bittasi
funktsiya / uchlari uchun Y = (ai, ..., a ^ n, 0, ..., 0), 6 = (Pi, ..., P] uv
1, ..1) bir xil tengsizlik bilan kesilishi kerak. Teorema isbotlangan.
Natijada, biz ē -> °° sifatida logt ^ = o (n) ekanligini topamiz.
logBn (t) ~ tn2.
3. Bo‘sag‘a ko‘rinishlarida statistik usullar. Shu qatorda; shu bilan birga
raqamli xususiyatlarning ekstremal qiymatlarini o'rganish
kombinatsion ob'ektlar, ularning tipikligini o'rganish qiziqish uyg'otadi
qadriyatlar, ya'ni ob'ektlarning asosiy qismida qabul qilinadigan qiymatlar.
Bu erda ehtimollik tadqiqot usullari muhim rol o'ynaydi.
qo'llanilishi kombinatorlar to'plamida ekanligiga asoslanadi
ob'ektlarga yagona ehtimollik taqsimoti beriladi va
o'rganilayotgan raqamli xususiyatlarning ehtimollik taqsimoti o'rganiladi;
bu yondashuv bilan tasodifiy o'zgaruvchilarga aylanadi va ularga
ehtimollar nazariyasi teoremalari qo'llaniladi.
Ko'p hollarda oddiy ehtimollik mavjudligi juda muhimdir
kombinatsion ob'ektlar to'plamini yaratish modeli, unda
har bir ob'ekt bir xil ehtimollik bilan sodir bo'ladi. Shunday qilib, bilan grafiklar uchun
barcha grafiklar to'plamida uchlari bir xilda belgilangan
bilan har bir chekka mustaqil paydo bo'lganda taqsimlash paydo bo'ladi
ehtimollik 1/2. Mantiqiy funksiyalar bo'lsa, to'plamda bir xillik to'plami
Barcha funktsiyalarning taqsimlanishini mustaqil ravishda o'rnatish orqali olish mumkin
1/2 ehtimollik bilan kubning har bir cho'qqisiga qiymat nolga yoki bittaga teng.
Ob'ektni yaratishning bunday modellari juda qulay bo'lib chiqadi.
ehtimollik usullarida.
Ba'zi hollarda, ba'zi sonli ekstremal qiymati
Mantiqiy funksiyalarning xarakteristikalari uning qiymatiga asimptotik tarzda mos keladi
odatiy holatda. Bu, masalan, murakkablik uchun
mantiqiy funktsiyalarni sxemalar bo'yicha amalga oshirish. Bunday holda, ular borligini aytishadi
Shennon effektini joylashtiring. Boshqa hollarda, masalan, uzunlik uchun
eng qisqasi d. n. f., ekstremal qiymat muhim bo'lib chiqadi
katta, lekin deyarli barcha mantiqiy funktsiyalar asimptotik tarzda mos keladi
raqamli xarakteristikaning qiymatlari, ya'ni tipikning asimptotikasi
qiymat mavjud, lekin ekstremal qiymatga mos kelmaydi. Keyin
Shannonning yarim ta'siri haqida gapiring. Muayyan darajada bo'lishi mumkin
ko'rsatilgan ehtimollar nazariyasidagi katta sonlar qonuni bilan solishtiring
deyarli barcha realizatsiyalar uchun chastotaning ehtimollikka yaqinlashishi
tasodifiy ketma-ketlik.
1967 yilda Nig'matullin o'zi chaqirgan usulni taklif qildi
o'zgaruvchanlik printsipi (qarang [36]), bu ko'p hollarda imkon beradi
Shennon yarim effektining mavjudligini isbotlang. Usul asoslanadi
raqamlar bilan rc-o'lchovli kub qatlamlarida ma'lum bir haqiqat bor
[n / 2 - l / nlogn] dan [n / 2 + ynlogn] gacha uning deyarli barcha uchlari topilgan,
va shuningdek, Nigmatullin tomonidan tasdiqlangan tasdiq, agar P ^ {0, 1} n
va (? ^ {0, 1} n - rc oʻlchamli kubning ikki choʻqqi toʻplami va \ P \>
^ 2 (r L | £ H ^ 2 [i b keyin P va Q orasidagi Xemming masofasi oshmaydi.
tashlaydi I - to.

44-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 47
Usulning mohiyati quyidagicha. Har bir mantiqiy funktsiya
(0, 1} n -> (0, 1} 2n ning tartiblangan to'plami sifatida qabul qilinadi
qiymatlar, ya'ni u 2n o'lchovli kubning tepasi hisoblanadi. Masofalar sifatida
r (/ i, / 2) / 1 va / 2 funktsiyalari orasida ^ o'lchovli kubning uchlari soni olinadi,
bunda ularning qiymatlari farqlanadi, ya'ni Xemming masofasi
2n o'lchamli kubning mos keladigan uchlari.
Mantiqiy funktsiyalarning o'rganilgan sonli xarakteristikasiga to'xtalib o'tamiz
h (f) r (/ i, / 2) = 1 dan \ h (fi) - A (/ 2) I ^ R (n) ekanligini ko'rsatish mumkin.
Agar r (/ b / 2) = r bo'lsa, u holda | A (/ i) -h (f2) I deyarli barcha mantiqiy funktsiyalar uchun h (f) Nigmatullinning asimptotikani isbotlash retsepti
Keyingi. Qatorda h (f)> H (n) bo'lgan mantiqiy funksiyalarni yozamiz
h (f) qiymatlarining kamaymaydigan tartibida. Seriyaning boshlang'ich segmentini tanlang
tanlangan segmentlar orasidagi intervalda qatorning o'rta qismi
deyarli barcha mantiqiy funktsiyalar topilgan va 2n ~ o'lchovli kubdagi masofa
tanlangan boshlang'ichga mos keladigan to'plamlar o'rtasida va
cheklangan segmentlar 2n2u / 2 dan oshmaydi. Shuning uchun h (f) qiymatlarining tarqalishi
qatorning o'rta qismida 2n2n / 2R (n) dan oshmaydi. Agar hozir bo'lsa
2n2ll / 2R (n) = o (H (n)) qo'ying, demak, bu deyarli barcha mantiqiy
funktsiyalari / asimptotik jihatdan bir xil qiymatlarga ega h (/).
Nig'matullinning o'zi isbotlash uchun bu usuldan foydalangan
eng qisqa dn uzunligi asimptotikasining mavjudligi. f., lekin bu qiyinchiliksiz
chegara raqamlariga o'tadi. Tasodifiy mustaqil va
birlik cho'qqilarida mantiqiy funktsiya qiymatlarining teng ehtimolli tayinlanishi
n o'lchovli kubning ba'zilari aniqlangan ehtimoli
kuchning chegara to'plami cn ga teng bo'lganlar bilan to'liq to'ldiriladi
2 “mlrd. Shuning uchun, ruxsat etilgan chegara sonining matematik kutilishi
kardinallik to'plamlari cn hisoblanadi
Log (1 + 1 / c) + log (l + c) + 1 - c bilan funksiya monoton ravishda kamayadi.
c> 1 ((tiqilib qolish (l + 1 / c) + log (l + c) - c) '= log (l + 1 / c) - 1). Demak,
Chebishev tengsizligidan foydalanib, biz deyarli barcha mantiqiy funktsiyalar emasligini aniqlaymiz
c> c0 uchun cn kardinallikning ruxsat etilgan chegara to'plamlariga ega bo'ling, bunda c o ~
~ 4.87 - tenglamaning ildizi
Ushbu izohga asoslanib, biz U (/ i) - £ (/ 2) farqini baholaymiz! da
shart r (/ 1, / 2) = 1. / i (a) = 0, / 2 (a) = 1 bo'lsin. Keyin chegara
/ 2 uchun vakillik / 1 uchun chegara ko'rinishidan olinishi mumkin
kesuvchi bitta tengsizlikni qo'shib, shuning uchun £ (/ 2) ^
^ t (/ i) + 1. Aksincha, f \ ning ifodasini olish mumkin
uchun ifodalash / 2, a kesgan barcha tengsizliklarni olib tashlash va uchun yozish
har bir cho'qqi, a dan tashqari, kamida bittasi tomonidan kesilgan
uzoqdagi tengsizliklar, alohida tengsizliklar. Chiziqli tengsizlik,
4-bayonotga muvofiq, eng ko'p cn cho'qqilarini, shu jumladan a-ni kesib tashlang