Raqamli kutubxona Kibernetikadan matematik masalalar

§ 3, 2-bandda ishlatilgan.
6. Ba'zi elementar pol to'plamlari. Kichik toʻplam
kubning uchlari (0, 1} n, agar u dan ajratilsa, pol deb ataladi.
uning to'ldiruvchisi giper tekislikdir. Shunday qilib, har bir ostonadan
funktsiyasi, ikkita chegara to'plami ulanadi: pol to'plami
nollar va birlarning chegara to'plami. O'rganishning eng to'g'ridan-to'g'ri yo'li
chegara funktsiyalari konstruktiv kombinatoriy tavsifdan iborat
ularning chegara to'plamlarining tuzilishi. Biroq, ko'pincha, chegara
to'plamlar ko'rsatish uchun juda murakkab
o'xshash tavsiflar. Shuning uchun biz ularni tasvirlash bilan cheklanishimiz kerak.
juda tor kichik sinflar.
Eng oddiy chegara to'plamlari pastki kublardir,
elementar qo`shma gaplarga mos keladi, ulardan Zn, qaysi
barcha chegara to'plamlari sonining ahamiyatsiz qismi. Ko'proq
chegara to'plamlarining vakillik sinfini bundaylarni birlashtirib olish mumkin
kichik sonli subkublar qandaydir maxsus tarzda. Boshqalar qulay
chegara to'plamlarining tavsiflangan sinfi poldir
kichik radiusli to'plamlar. Bu eng oddiy chegara sinflari
to‘plamlar [10, 12, 43] da chegara bilan bog‘liq holda ko‘rib chiqilgan
mantiqiy funktsiyalarning tasvirlari, shuningdek, barcha chegaralarni sanash muammosi
berilgan kardinallik to'plamlari.
A chegara to'plami monoton chegara to'plami deb ataladi
nollar, agar a ^ A va (5 = ^ a ^ ^ ^ 4 ni nazarda tutsa, ya'ni
ba'zi bir monoton chegara funksiyasining nollar to'plami; xuddi shunday
birliklarning monoton chegara to'plamini aniqlang. Monotonik chegara
to'plam har doim ishlab chiqarish bilan (1) tengsizlik bilan berilishi mumkin
erkin chegara to'plamiga aylantirilishi mumkin
almashtirishlar bilan monoton 1 - x {for w <0. Aksincha, monoton chegaradan
bunday yordamida barcha koordinatalarga mohiyatan bog'liq bo'lgan to'plam
koordinatalarni aks ettirish 2P turli chegara olish mumkin
bir xil kardinallik to'plamlari. E'tibor bering, chegara belgilangan
g'alati kardinallik har doim deyarli barcha koordinatalarga bog'liq.

24-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 27
Ixtiyoriy A to'plami uchun cho'qqi a e A
biz uni markaz deb ataymiz, agar har qanday £ e A cho'qqisi uchun barcha 2r (ct'p) uchlari y bo'lsa
shunday qilib, r (a, y) + r (y, p) = r (a, (5), A ga tegishli.
Shunday qilib, pol to'plamining markazini quyidagicha aniqlash mumkin
chegarani monotonga aylantirganda o'rnatilgan cho'qqi
nollarning chegara to'plamini nol cho'qqisiga tarjima qilish mumkin.
Eshik to'plamida bir nechta markazlar bo'lishi mumkin. Yuqori, ichida
(1) ning chap tomonidagi chiziqli shaklning ekstremumiga har doim erishiladi
chegara to'plamining markazidir.
Eshik to'plamining radiusi maksimaldir
Uning cho'qqilaridan markazgacha bo'lgan Hamming masofasi. Radius emasligini ko'rish oson
markazning tanloviga bog'liq va to'g'ri belgilangan. Bu minimal radius
Hamming to'pi, unda ostona
kopgina. Nolinchi cho'qqi monoton chegaraning markazidir
nollar to'plami va uning radiusi raqamlarning maksimali bilan belgilanadi
uning uchlarini o'z ichiga olgan qatlamlar.
Eshik to'plamining diametri maksimal sifatida aniqlanadi
Hamming masofalari to'plamning barcha juft juftlari bo'ylab olingan. Tushunarli,
diametri radiusdan ikki baravar oshmaydi. Shuning uchun bu adolatli
ostonaning diametrini uning bilan bog'laydigan quyidagi smeta
kuch.
Bayonot 4. M kardinallik chegarasi to'plamining diametri emas
2 log M dan oshadi.
Nollarning monoton to'plamlari uchun ikkita keyingi bayonot
radius 1 va 2 osongina o'zboshimchalik uchun qayta shakllantirilishi mumkin
nol cho'qqi o'rniga markazlaridan foydalangan holda to'plamlar. Bir
ulardan darhol yig'ilmaslik mezonidan, ikkinchisi esa dan kelib chiqadi
5-bandning oxiridagi izohlar.
Bayonot 5. Nollarning har qanday monoton to'plami
1-qavat ichida, chegara hisoblanadi.
Bayonot 6. Nollarning monoton to'plami uchun,
2 qatlam ichida yotgan ostona edi, u zarur va
2-qiyoslash mumkin bo'lishi kifoya.
Endi bitta chegara to'plamidagi birlashmani ko'rib chiqing
pastki kublarni yoping.
7-bayonot [10, 13]. Agar barcha pastki birliklar monotonik bo'lsa
funksiyalar birlik radiusi bo'lgan Xemming sharining ichida yotadi,
keyin bu chegara.
Isbot. B = (Pi,..., $ K} kichik birliklar bo'lsin,
a - to'pning markazi. Keyin quyidagi uchtadan biri o'zaro
istisnolar: 1) |5j ^ a, i = 1, 2, ..., k; 2) B = (os); 3) pj = i = 1, 2, ..k. Holat 2) ahamiyatsiz. 1-holatda), pastki kubni ko'rib chiqing
kubning {0, 1} n, uchlari x ^ = oe dan iborat. Bu nodcubda, pastroq
birliklar 1-qavatda yotadi va funktsiyaning yig'ilmasligi aniq bo'ladi.
3) holat ham xuddi shunday ko'rib chiqiladi.
7. Chegaraviy funksiyalar to‘plamining strukturaviy xossalari. Shu qatorda; shu bilan birga
chegara funksiyalarining alohida kichik sinflarini ko'rib chiqish hisoblanadi
umuman chegara funktsiyalari to'plamini o'rganishga qiziqish. Agar
chegara funktsiyalari to'plamini alohida olingan elementlar sifatida ko'rib chiqish;
keyin uning uchun paydo bo'ladigan yagona vazifa - uni baholash
kuch. Biroq, chegara funktsiyalari orasida ba'zilari mavjud
tabiiy munosabatlar, ularni hisobga olish juda boyitadi
muammolar. [16] da ikkita shunday munosabatlar ko'rib chiqildi. Ulardan biri
klassik algebraik yondashuvdan foydalanadi va to'plamni beradi
chegara funktsiyalari qisman tartibda, ikkinchisi to'plamni tavsiflaydi
chegara oddiy yo'naltirilmagan grafik sifatida ishlaydi.

25-bet

28
Yu A, Zuev
Tabiiy usulda barcha mantiqiy funktsiyalar to'plamidagi 1a
qisman tartib munosabati kiritiladi: / = Olingan qisman tartiblangan to'plam izomorfdir
buyurtma qilingan 2 "-elementli to'plamning barcha kichik to'plamlari to'plami
inklyuziya va mantiqiy algebradir (ta'riflar uchun [43] ga qarang).
Yuqori va pastki yuzlarni olish operatsiyalari mos ravishda
diszyunsiya va birikma. Xuddi shu munosabat bilan buyurtma qilingan,
ko'pgina pol funktsiyalari bunday boy tuzilishga ega emas. Bu
chegara funktsiyalari birliklari soni bo'yicha gradusli, universalga ega
pastki va yuqori yuzlar, lekin tekshirish oson bo'lganidek, bunday emas
panjara. 1, ammo uni o'rganish qiziqish uyg'otadi. Jumladan,
e'tiborga loyiq narsa - berilgan elementlarning sonini baholash muammosi
balandlik, ya'ni ma'lum birlik soni bilan chegara funktsiyalari soni.
muammo § 3, 2-bandda ko'rib chiqiladi.
Boshqa strukturaviy tavsifni ustadan o'tish orqali olish mumkin
yo'naltirilgan grafikni yo'naltirilmagan qismga qisman tartiblash, ya'ni.
har bir yo'naltirilgan yoyni yo'naltirilmagan chekka bilan almashtirish. Da
Oule funktsiyalarini o'rganish, xususan, yarim effektni o'rganish
Shannon variatsion printsipdan [36] foydalangani ma'lum bo'ldi
ikki funksiya orasidagi masofa bo'lgan foydali ko'rsatkich
ular qabul qiladigan mantiqiy kortejlar soni har xil
qiymatlar. u holda bir-biridan farq qiladigan “qo‘shni” funksiyalarni ko‘rib chiqish tabiiydir
faqat bitta to'plamda. Agar biz cho'qqilari bo'lgan grafikni ko'rib chiqsak
Mantiqiy funktsiyalarga mos keladi va qirralari "qo'shni" funktsiyalarni bog'laydi
u holda u ^ 2 "-o'lchovli kub uchun izomorf bo'ladi. To'plamdagi shunga o'xshash grafik
chegara funksiyalarining grafigi deb ataladi. U egalik qiladi
yanada murakkab struktura, lekin shaffof geometrik imkonini beradi
talqin.
Og'irliklarning (n + 1) o'lchovli fazosida konuslar (8).
"qo'shni" chegara funktsiyalariga mos keladigan qo'shni. Da
ularni ajratib turuvchi giperplan orqali o'tish, o'zgarish sodir bo'ladi
giperkubning bir tepasidagi funksiya qiymatlari. Giperkubning tepalari
konusning yuzlariga mos keladigan pol funksiyasi deyiladi
chegara nuqtalari [68, 80]. Chegara nuqtalari to'plami qanchalik oson
quyidagi xossalarga qarang: a) eng katta to‘plam
cho'qqilar shunday bo'ladiki, chegara funktsiyasi har qanday holatda o'zgartirilishi mumkin
hamma narsa uchun qiymatlarni o'zgartirmasdan to'plamning bir tepasi
giperkub; o) ^ - eng kichik cho'qqilar to'plami, bilim
chegara funktsiyasining qiymatlari, bunda uni hamma uchun tiklash mumkin
giperkub.
Eshik funktsiyasining "qo'shnilari" soni uning chegarasi soniga teng
nuqtalar va grafik talqinda bu grafik cho'qqisining darajasi.
Bu daraja har doim kamida n + 1, chunki qattiq konus bilan
cho'qqi £ "> + I"da kamida n + 1 yuzga ega. Ostonaning "ko'p" qo'shnilari
funktsiyalari x2 A ^ 2 A ••• A xn x \ V x2 V ... V xn, shuningdek y boshqa har qanday
bir nolga yoki bittaga ega bo'lgan chegara funktsiyasi. Maksimal
2P ga teng "qo'shnilar" soni har qanday chegara funktsiyasiga ega,
bu asosan bitta o'zgaruvchiga bog'liq.
Eshik funktsiyasi og'irliklarining doimiy o'zgarishi bilan (4)
mos keladigan nuqta ba'zi traektoriyani tasvirlaydi. Agar bu traektoriya
ma'lum bir "maxsus" tarzda tanlanmagan, ya'ni emas
(2P \
dnt orqali ^ n - 1 o'lchamli pastki bo'shliqlar, ularning kesishmasida
Agar funktsiya bir vaqtning o'zida giperkubning ikkita tepasida qiymatlarni o'zgartirsa, u holda
bir pol funktsiyasidan ikkinchisiga o'tish qirralarning bo'ylab amalga oshiriladi
chegara funksiyalarining grafigi. Bunday uzluksiz diskret analog
traektoriyalar moslashish jarayonida og'irlikdagi o'zgarishlar bo'lib xizmat qilishi mumkin,

26-bet

EOS FUNKSIYALARI II BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 29
etarlicha kichik qadam bilan o'rnatiladi. orasidagi masofaga e'tibor bering
pol funktsiyalari mos keladiganlar orasidagi masofaga teng
grafikning uchlari, ya'ni ular orasidagi eng qisqa yo'ldagi qirralarning soni. V
aslida, agar fo (y) = sgr \ (a0 + a {yi +.,. + apup) va fx (y) - sgn (a0 -j- a1y1 -f)
+ • .. + appup) - to'plamlarda farq qiluvchi chegara funktsiyalari, keyin
grafik bo'ylab / o dan / 1 ga o'tish ham r bosqichlarida amalga oshiriladi
ft (y) = sgn (a + t (a - a)) formulasining t ni 0 dan 1 ga o‘zgartirishi.
darhol quyidagi bayonot keladi.
Bayonot 8 [16]. Eshik funksiyasi grafigining diametri
2p ga teng.
8. Chegaraviy funksiya sintezining algoritmik murakkabligi.
Eshik funktsiyasini sintez qilish muammosi, ya'ni chegara va chegarani tan olish.
berilgan mantiqiy funksiya uchun chiziqli tengsizlikni (1) topish
uning qiymatlari jadvali yoki uning ba'zi d. n. f., har doim bo'lgan
ostona mantiqining asosiy vazifalaridan biri (qarang [2, 55, 68, 86]). Keyin
Kuk [50] va Karp [71] asarlarini qat'iy bajarish mumkin bo'ldi
Ushbu muammoni o'rganishga matematik yondashuv va uni tasniflash
yechimning murakkabligiga ko'ra, ya'ni biriga tayinlash
standart sinflar, ularning eng muhimi P sinfi - muammolar sinfi,
polinom vaqtida echilishi mumkin va NP sinfi sinfdir
polinom algoritmi uchun universal sanab masalalari
mehnat sarfi, ehtimol, mavjud emas (qarang [61]). Bunday tadqiqot
Pild va Simeone [92] ishida amalga oshirilgan bo'lib, ikkalasi ham
taqdimot asos qilib olingan.
E'tibor bering, birinchi navbatda, agar / funktsiyasi uning yordamida berilgan bo'lsa
mukammal d. n. f., ya'ni butun to'plamdagi uning qiymatlari jadvali
2n ikkilik to'plamlar, keyin sintez muammosi dan tizimni echish uchun qisqartiriladi
2n chiziqli tengsizliklar. Va bu vazifa uchun, keyin aniq bo'lganidek
Xachiyan ishining [40], uni hal qiladigan algoritm mavjud
uning yozuvi uzunligining polinomi, ya'ni qiymati 2P, vaqt. Vazifa qoladimi
koʻpnomli echiladigan boʻlsa, d.n. f. umumiyroqmi?
Bu savolga javob, Ref [92] da ko'rsatilganidek, asosan quyidagilarga bog'liq
tur d. n. ph .. Agar bir jinsli mantiqiy funktsiya uning tomonidan berilgan bo'lsa
qisqartirilgan d. n. f., keyin ostona va yozishni tan olish muammosi
tengsizlik (1) polinomli yechiladi. Bunaqa
umumiylikni yo'qotmagan mantiqiy funktsiya har doim ko'rib chiqilishi mumkin
monoton mantiqiy funktsiya uning pastkilari bilan aniqlanadi.
Agar d. N. f. hech qanday cheklovlar qo'ymang, keyin vazifa
tanib olish chegarasi - ZhR-to'liq. Demak, bundan kelib chiqadiki,
xususan, qisqartirilgan DN olish muammosining ZhR-qiyinligi. f. uchun
uning ixtiyoriyligi uchun bir jinsli funktsiya d. n. f. nimaligini bilmasdan
o'zgaruvchilar inkor bilan, qaysilari esa inkorsiz qabul qilinishi kerak.
15-teorema [92]. tomonidan chegarani tan olish muammosi
ixtiyoriy d. n. f. NP-to'liq.
Isbot. Keling, taniqli LP-to'liq muammo ekanligini ko'rsatamiz
birlikning o'ziga xosligini o'zboshimchalik bilan tan olish d. n. f.
chegarani tan olish muammosiga kamaytirilishi mumkin. Bo'lsin
ixtiyoriy d. n. f. D (x). Ikkita yangi o'zgaruvchini kiritish orqali biz dn quramiz. f.
D '(x, Y !, l / 2) (x) Z / 2 V Y \ Y2 V Y \ Y2- Agar B (x) e1 bo'lsa, u holda funktsiya
X, y va z / 2) = ViVz / 2 - chegara. Agar P> (x °) = 0 uchun
bir oz x °, keyin A '(x °, 0, 0) = D' (x °, 1, 1) = 1, D '(x °, 0, l) = D, (x °, 1, 0) - • 0
u (x °, 0, 0) + (x °, 1, 1) - * (x °, 0, 1) + (x °, 1, 0), ya'ni berilgan funktsiya
d. n. f. D '(x, y va 1/2) 2-summable va shuning uchun emas
chegara. Teorema isbotlangan.
Keling, ixtiyoriy monoton mantiqiy uchun qandayligini ko'rsatamiz
uning quyi birliklari tomonidan berilgan funksiya samarali yechiladi

27-bet

o'ttiz
Yu. A. Zuev
uning ostonasi haqida so'rash ™. Funksiyaning quyi birliklari toʻplami {aj boʻlsin
f. Agar u bilan birga uning yuqori nollari {pD to'plami ma'lum bo'lsa, u holda
uning chegarasi masalasi tizimning mosligini o'rganishga qisqartiriladi
(a, "0> b,
(a, P ^) <6,
a, b 0,
ya'ni samarali hal etiladi.
Monoton funksiyaning har bir yuqori noli komponentli hisoblanadi
asliyatga qo‘sh funksiyaning pastki birligining inkori, shuning uchun
pastki to'plamdan yuqori nollar to'plamini olish muammosi
birliklar monoton mantiqiy funksiya uchun dualizatsiya muammosi deb ataladi.
O'zboshimchalik bilan monoton funksiyasi bo'lsa, muammo
dualizatsiya samarali echilishi mumkin emas, shundan kelib chiqadiki, bilan
o'zgaruvchilar soni ortib borishi bilan, yuqori nollarning soni bo'lishi mumkin
pastki sonining eksponentsial o'sish funktsiyasi. Buni aylanib o'tish uchun
qiyinchilik bo'lsa, avvalo ph ni 2-taqqoslash uchun tekshirib ko'raylik. Bu test
samarali qondirish mumkin, chunki (xi = 1, ^ = 0) ph ^ sharti uchun
^ (xi = 0, xj = 1) ph har bir pastki uchun zarur va etarli
funktsiya birligi (t * = • 1, t = 0) ph dan kichik yoki teng bo'lgan.
u funksiyaning quyi birligi (Xi = 0, xj = l) cp. Agar ijro etilgan bo'lsa
o'zgaruvchilarni almashtirish orqali 2-taqqoslash shartlari ph ni muntazam qilamiz.
Muntazam funktsiya uchun dualizatsiya muammosi birinchi marta bo'lgani kabi
[92] da ko'rsatilgan, samarali hal qilinadi. Bu muammoni hal qilish uchun oddiyroq
aniq ko'rsatkichga asoslangan yuqori nollarning soni uchun eng yaxshi baho
ularning tuzilishi tavsifi, Krama [53] tomonidan berilgan. Xuddi shu yaxshilanishlardan qat'i nazar
Lipkin tomonidan taklif qilingan [32]. Quyidagi lemma ularga asoslanadi
tadqiqot.
Lemma 1. Muntazam funktsiyaning har bir yuqori noli bo'lishi mumkin
birining qiymatini o'zgartirish orqali uning quyi birligining bir qismidan olinadi
uning birlik koordinatalaridan simultane bilan nolga
barcha koordinatalar birligiga tenglashtirib, nolga teng bo'lgandan o'ng tomonda.
Isbot. p = (fii, ..., Jin) yuqori nol bo'lsin
muntazam funktsiya ph. Agar Pn = 0 bo'lsa, to'plam ..., 1) bo'ladi
ph uchun birlik va ph ning muntazamligi tufayli birlikdan hech biri
a koordinatalari bitta qiymatni saqlab turganda nolga tenglashtirilmaydi
funktsiyalari. Shunday qilib, os pastki birlik bo'lib, undan
p ning yuqori noli olinadi.
Endi p to'plamdagi eng o'ng nol r-o'rinda bo'lsin,
bu erda i fc-u) o'rnating
1, ..., 1) ph uchun birlikdir. Biz doimiy ravishda harakatlanamiz
dan boshlab, o'ngdan chapga, uning birlik koordinatalarini nolga aylantiradi
ikkinchisi, har safar ph funksiyasining qiymati saqlanib qolganligini tekshirish
birga teng. Shunday qilib, 7-10 koordinatasini nolga tenglashtirgandan so'ng, biz /> ga kelamiz
ai = to'plamiga (fii, ..., fit-i, 1, ..1, 0, ..., 0), bunda nolga tenglashtiriladi.
(/ - 1) --chi koordinata funksiya qiymatini nolga o'zgartiradi. tufayli
ph ning muntazamligi, to'plamning birlik koordinatalaridan hech biri oci mumkin emas
ph qiymatini o'zgartirmasdan nolga tenglashtiriladi, ya'ni a \ pastki
p olinadigan birlik. Lemma isbotlangan.
1-Lemmadan kelib chiqqan holda, muntazam funktsiyaning barcha yuqori nollari
samarali olingan to'plamda mavjud bo'lib, ularning asosiyligi yo'q
mn dan oshadi, bu erda ng - funksiyaning quyi birliklari soni. Tanlov vazifasi
undan yuqori nollar qiyin emas. Umuman
oldingi fikrlash quyidagi natijani o'rnatdi.
16-teorema [92]. Berilgan monoton mantiqiy funktsiya uchun
ularning quyi birliklari, chegarani tan olish muammosi va
(1) tengsizlikni olish polinom vaqtida yechiladi.

28-bet

MATQIY FUNKSIYALARNING EOS FUNKSIYALARI VA BOSHQA FUNKSIYALARI.