Raqamli kutubxona Kibernetikadan matematik masalalar

§ 5. Ochiq muammolar
Ushbu sharhning maqsadlaridan biri yoritish edi
chegaraviy mantiq rivojlanishining tarixiy yo'li va uning qo'llanilishining tavsifi, boshqa
ostona mantiqining har xil bilan bog'lanishini ko'rsatishdan iborat edi
matematika bo'limlari. Diskret matematikaning umumiy rivojlanishi tufayli
chegara mantig'i bir qator muammolarni hal qilishda muvaffaqiyatga erishdi
xususan, sonni baholashning eski muammosida yangi natijalarga erishish
chegara funktsiyalari. Shu bilan birga, chegara mantig'i hali ham qodir

52-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 55
turli sohalardagi mutaxassislarga keng ko'lamli muammolarni taqdim etish
kombinatsion tahlil bo'limlari. Biz ulardan ba'zilarini shunday shakllantiramiz
yoki ushbu ko'rib chiqish kontekstida boshqa tarzda aytib o'tilgan,
etarli darajada xilma-xil vazifalarni tanlashda
tadqiqotchilarning eng keng doirasini qiziqtirish.
1. Eshik soni logarifmining asimptotikasidan keyin
funktsiyalari haqida savol tug'iladi, bu raqamning asimptotikasi haqida. Buni iloji bormi
Bu erda diskret rivojlanishining hozirgi bosqichida muvaffaqiyatga ishonish
matematika? Monoton funksiyalar tarixi keyin takrorlanadimi?
Kleitmsn [73] tomonidan logarifmning asimptotikasi nuqtai nazaridan o'rnatilishi.
nisbatan qisqa vaqt Korshunov [24] topdi
monoton funksiyalar sonining asimptotikasi. Taxmin qilishga urinmasdan
Kelajakda, shunga qaramay, sonning asimptotikasini topish muammosi ekanligini ta'kidlaymiz
chegara funktsiyalari juda qiyin ko'rinadi. Bu istisno qilmaydi
ammo, 17-teoremaning turli takomillashtirilgan va takomillashtirishlari.
2. Yana bir muammo har xil chegara to'plamlari soni bilan bog'liq
kuch. Nn (M), M - 0, 1, .... 2P qiymatlar to'plamini hisobga olgan holda,
diskret taqsimot sifatida, 2n ~ 1 ga nisbatan simmetrik, bitta mumkin
E'tibor bering, 18-teoremadagi barcha taxminlar uning "dumlari" ga tegishli
tarqatish. Shunda tadqiqot masalasini ko'tarish tabiiy
uning markaziy qismi, bu erda ostonaning asosiy qismi
to'plamlar. Shunga o'xshash sozlamani hammaga ma'lum chegara taklif qiladi
ehtimollar nazariyasi teoremalari. Asimptotik haqida nima deyish mumkin
uning markaziy qismida bu taqsimotning xatti-harakati? Bo'ladimi?
to'g'ri tanga tashlanganda gerbning necha marta tushishiga o'xshash
oddiy qonun bilan tavsiflanadi? Bu qiziqarli sifatli savol,
o'rganishga arziydi.
3. § 3, 3-bandda pastki va yuqori o'rtasida katta bo'shliq mavjud
M (n) va M ^ (n) og'irliklarining mutlaq qiymatlari uchun hisob-kitoblar. Tabiiyki
M (n) va Mn (n) qiymatlarini baholash orqali ushbu bo'shliqni yopishga harakat qiling
logarifmning asimptotikasi tartibiga qadar. Buni taxmin qilish mumkin
kardinallikni baholash aniqroq va log M (n) X
X log Mc (n) X n, lekin buni isbotlash uchun hali hech qanday yondashuv yo'q
korinmayapti.
4. 3-§ 4-bandning 22-teoremasida keng sinfning mavjudligi.
ko'rsatkichli murakkablikdagi chegara funktsiyalari d. n. f.
Deyarli barcha chegara funktsiyalariga ega bo'lishi mantiqiy ko'rinadi
eksponensial murakkablik d. n. f., ammo buni isbotlash kerak.
5. 4-§ 3-bandning 26-teoremasida asimptotikaning yuqori va pastki chegaralari.
tipik chegara qiymatlari Xlog n marta farqlanadi. muallif
pastroq quvvat bahosini to'g'ri aks ettiradi deb hisoblaydi
asimptotiklar tartibi va t (f) X 2n / n, lekin uning bu haqiqatni isbotlashga urinishlari,
tasodifiy mantiqiy X2n / n funksiyasining birlik uchlarini sharlar bilan qoplash
Radius 1 ni markazlari birlik cho'qqilari bilan birlashtirish muvaffaqiyatli emas
toj kiygan. A.D.Korshunov 1986 yilda shunday deb xabar bergan edi
qopqoq deyarli har doim e'lon qilingan Xlog ^ 2nM to'plarini talab qiladi
muallif tomonidan [13]. Biroq keyinchalik A.D.Korshunov rad javobini berdi
bayonot berdi. Shunday qilib, birlik sonining tartibi masalasi
tipik Boolean funksiyasi uchun optimal qamrovda to'plar qoladi
ochiq. Bu vazifa, albatta, mustaqildir
qiziqish va ehtimollik bo'yicha mutaxassislarni qiziqtirishi kerak
kombinatsion tahlil usullari. Qidiruv uchun katta kuch sarflagan
bunday quvvat qamrovi X2p / n va muvaffaqiyatsizlikka uchragan, muallif moyil
buni qilishning iloji yo'q deb hisoblang. Agar bu isbotlangan bo'lsa, unda
26-teoremadagi yuqori chegarani tushirishning mumkin bo'lgan usuli bo'lishi mumkin
Markazlari birlik cho'qqilarida joylashgan radiusi 2 bo'lgan sharlarni ko'rib chiqaylik
va 6-bandning 2-bandi, 6-bandidan foydalanish.

53-bet

56
Yu. A. Zuev
6. § 4, 4-bandda, aslida, baholash muammosi
monoton Boolean sinfidagi chegara sonining maksimal qiymati
Hozirgi vaqtda taxminlar mavjud bo'lgan funktsiyalar
([i "2]) ln ^ tfax 1 fa) ^ 2" / "
Chegaraviy vakilliklarda bu muammo, shubhasiz, muammolardan biridir
kalit.
7. 2-§, 7-bandda chegara funktsiyalari grafigi birinchi marta aniqlangan
muallif tomonidan [16] kiritilgan. U qandaydir tabiatning namunasidir
paydo bo'lgan grafik va uning xususiyatlarini o'rganish ifodalashi mumkin
grafik nazariyasi va ko'p o'lchovli geometriyaga qiziqqan har bir kishi uchun qiziqish.
Chegaraviy funksiyalar grafigi ancha murakkab va buning uchun qiyin
muvaffaqiyatli ko'tarilish imkoniyatini oldindan bashorat qiling
ma'lum xususiyatlarni o'rganish. Shuning uchun, har qanday natijaga erishish
qiziqish. Bugungi kunga qadar, faqat
cho'qqilar darajalarining o'zgarish diapazoni va grafik diametri topiladi.
Keyingi tadqiqot uchun mumkin bo'lgan yo'nalishlar tadqiqotdir
ulanish, Gamiltonlik va boshqalar.
8. 2-§, 2-bandda mantiqiy funktsiyalarning Chow parametrlari ko'rib chiqildi,
chegaraviy funksiyalarni kodlashning qulay vositasi hisoblanadi.
Ular bilan bog'liq vazifalar doirasi etarlicha keng. Keling, faqat bittasiga to'xtalib o'tamiz
Ulardan, algoritmik. Chow parametrlari bo'yicha 9-teoremadan kelib chiqqan holda
Mantiqiy funktsiya, printsipial jihatdan, uning mavjudligini aniqlash mumkin
chegara va agar shunday bo'lsa, uni noyob tarzda aniqlang.
Biroq, ularning hisoblash murakkabligi haqida savol tug'iladi
protseduralar. Parametrlar bo'yicha chegaralarni tanib olish vazifasi
Chow polinom vaqtida hal qilinadimi yoki yo'qmi? Chow parametrlari
oltmishinchi va samarali tartib-qoidalarida intensiv o'rganilgan
bu muammoni hal qilish uchun topilmadi. Uni o'rnatish
NP-murakkabligi shunga o'xshashni topishga bo'lgan keyingi urinishlarga chek qo'yadi
tartib.
ADABIYOTLAR RO'YXATI
1. Andreev AE Ts Westpick gradient algoritmining bir modifikatsiyasi haqida
Moskva davlat universiteti. Ser. 1. Matematika. Mexanika.- 1985. - No 3. - B. 29-35.
2. Butakov E. A. Chiziqli qurilmalarni chegaradan sintez qilish usullari
elementlar - M .: Energiya. 1970 yil.
3. Vasil'ev Yu. L., Glagolev VV Dizyunktivlarning metrik xususiyatlari
Pormal shakllar Ts Diskret matematika va matematik masalalar
kibernetika. T. l./ Ed. S. V. Yablonskiy va O. B. Lupapova. - Moskva: Nauka, 1974.-
S. 99-148.
4. Pardalar t A. M., Zuev Yu. A., K r ​​va s va taxminan va rosh va V. V. Ikki darajali bo'ling.
mantiqiy korrektorli tanib olish sxemasi C Tanish, tasniflash,
bashorat: Matematik usullar va ularni qo'llash. Nashr 2.— M .: Fan, - 1989.—
S. 73-98.
5.Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tysh to s.
vich R.I., Grafiklar nazariyasi bo'yicha ma'ruzalar, Moskva: Nauka, 1990.
6. Juravlev Yu.I. Minimal disjunktivni qurish algoritmlari
mantiq algebrasining funktsiyalari uchun normal shakllar C Diskret matematika va
kibernetikaning matematik savollari. T. 1./ Ed. S. V. Yablonskiy va O. B. Lupa
nova.- Moskva: Nauka, 1974. - B. 67-98.
7. Juravlev Yu.I., Kogan A.Yu. Kichik bilan mantiqiy funksiyalarni amalga oshirish.
dis'yunktiv normal shakllar bo'yicha nollar soni va unga bog'liq masalalar Ts
Dokl. SSSR Fanlar akademiyasi.- 1985. - T. 285, No 4. - S. 795-799.
8. Zuev Yu. A., Trishin VN Tengsizliklar sonining pastki chegarasi,
n o'zgaruvchining monoton mantiqiy funksiyasini ifodalovchi Ts Zh. hisoblangan
matematika va matematika. Fizika.- 1983. - T. 23. No 3 - S. 754-756.
9. Zuev Yu.A., Tri kema VN Chiziqli tengsizliklarni monoton bilan bog'lash haqida.
Mantiqiy funksiyalar Ts Jurn. hisoblangan matematika va matematika. Fizika. - 1984. -
T. 24-son, 5-son. - S. 780-781.

54-bet

BOSH FUNKSIYALARI VA BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 57
10. Zuev 10. A. Linear Pen ™ tizimlarida mantiqiy funktsiyalarni tasvirlash to'g'risida.
Identity C Cybernetics, - 1985. - No 5. —S. 7-9, 40.
11. Zuev Yu.A., Lipkin L.I. Chiziqli boʻlinadigan mantiqiy toʻplamlar soni haqida.
berilgan kardinallikning Grafik nazariyasida diskret tahlil usullari va
mantiqiy funktsiyalar. Nashr 43.- Novosibirsk: IM SO AN SSSR, 1986.- S. 29-39.
12. Zuev Yu. A., Lipkin L. I. Berilgan quvvatning chiziqli uzilishlari.
birlik giperkub Ts Izv. SSSR Fanlar akademiyasi. Tech. kibernetika.- 1988. - № 3, - b. 79—
85.
13. Zuev Yu. A., Lipki N. I. Chegara samaradorligini baholash.
Mantiqiy funksiyalarning ko'rinishlari C Kibernetika.- 1988. - No 6. - B. 29-37.
14. Zuev Yu. A., Lipkin LI Berilgan bilan muntazam mantiqiy funktsiyalar
normal shakllar diszyunksiyasining murakkabligi Diskret tahlil usullari
mantiqiy funktsiyalar va grafiklarni o'rganish. Nashr 48.- Novosibirsk: IM SO AN SSSR,
1989.- S. 17-22 / '
15. Zuev Yu.A. Algebraning chegara funksiyalari soni logarifmining asimptotikasi.
mantiq // Dokl. SSSR Fanlar akademiyasi.- 1989. - T. 306, 3-son - S. 528-530.
16. Zuev Yu. A. Kombinator-ehtimollik va geometrik usullarda
chegara mantiqi Ts Diskret matematika 1991 yil 3-jild, №. 2.- 47-57-betlar.
17. Zuev Yu. A. Ko'pchilik tomonidan qaror qabul qilishning statistik xususiyatlari haqida
tasniflash masalalarida ovozlar Ts Dokl. SSSR Fanlar akademiyasi.- 1986.- T. 288, 2-son, -
S. 320-322.
18. Zuev Yu.A.
son. matematika va matematika. Fizika.- 1986. - T. 26, No 2. - B. 276-292.
19. Zuev Yu. A. Ko'pchilik tomonidan qaror qabul qilish uchun eng yomon holat
ovozlar Ts Zhuri, hisoblangan. matematika va mat. Fizika.- 1989. - T. 29, 8-son. -
S. 1256-1257 yillar.
20. Zuev Yu. A., I in ap about S. K. Kompleks qayta ishlash samaradorligini oshirish.
tamoyillari yordamida dipamik tizimlarda axborotni qayta ishlash
tanib olish C Kibernetika savollari. Murakkab muammolar
kibernetik dipamik tizimlar / Ed. E. A. Fedosova. - M .: Ilmiy kengash
murakkab masala «Kibernetika», 1992. - S. 86-106.
20a. Zuev Yu. A., Ivanov S. K. "Tezlashtirilgan" nerseptrott va mustaqil o'rganish.
vaznli ovoz berish tartiblari Ts Dokl. RAS - 1993. - T. 328, 2-son. -
C, 160-163.
21. Kabatianskiy G.A., Panchenko V.I.
birlik sharlari tomonidan bo'sh joy Ts Dokl. AN SSSR. - 1988. - T. 303, LG ° 3.-
S. 550-552.
22. Kabatianskiy G. A., Panchenko V. I. Paketlar va qoplamalar
Birlik radiusi sharlari bo'yicha fazoni hamminglash Axborotni uzatish muammolari.
1988. - T. 24, №. 3.— S. 3-16.
23. Korobkov V.K. Chiziqlining ba'zi butun sonli masalalari haqida
dasturlash C Kibernetika muammolari. Nashr 14.- Moskva: Nauka, 1965.- S. 297-299.
21. Korshunov LD. Monoton mantiqiy funksiyalar soniga oid masalalar
kibernetika. Nashr 38. - Moskva: Nauka, 1981, - S. 5-108.
25. Korshunov A. D. Oddiy shakllarning eng qisqa gaplarining murakkabligi haqida
tasodifiy mantiqiy funktsiyalarning C Optimallashtirishda diskret tahlil usullari
nazorat qilish tizimlari. Nashr 40. - Novosibirsk: IM SO AN SSSR, 1983.- S. 25—
53.
26. Kospapov E. Sh. Markazlari birlik radiusli idishlarni qoplash to'g'risida.
beqiyos C Boshqarish tizimlarini sintez qilishda diskret tahlil usullari.
Nashr 44. - Novosibirsk: IM SO AN SSSR, 1986.- S. 54-57.
27. Kostochka A. V. ē-o'lchovdagi filtr chegarasining maksimal quvvati haqida.
kub C Mantiqiy amalga oshirishni o'rganishda diskret tahlil usullari
funktsiyalari. Nashr 41.- Novosibirsk: IM SO AN SSSR. 1984.- S. 49-61.
28. AV Kostochka, Stgerperian oilasining maksimal grapisiyasi haqida C Dokl.
SSSR Fanlar akademiyasi.— 1990, —T. 310. No I - B. 536-538.
29. Kostochka A. V. "-o'lchovli" antizanjir chegarasining kardinalligi uchun yuqori chegara.
kub // Diskret matematika.- 1989. - T. 1, yo'q. 3.—S. 53-61.
30. Kuznetsov SE. Eng qisqa d uzunligining pastki uyumida Va. f. deyarli hamma
Mantiqiy funksiyalar C Ehtimoliy usullar va kibernetika. Nashr 19.-
Qozon: Qozon davlati Universitet, 1983. - S. 44-47.
31. Laplas N. Ehtimollar nazariyasi falsafasi tajribasi: Ner. frantsuz tilidan - M .. 1908 yil.
32. Lipkin L. I. Hisoblash murakkabligini baholashga
kombinatsion-mantiqiy tanib olish algoritmlari Ts Konspektlar. hisobot 5-Moskva shahri
yosh olimlar va mutaxassislarning kibernetika bo'yicha konferensiyalari va
kompyuter texnologiyalari - M .: 1986 .- - S. 31.
33. Lip cii L. I. Mantiqiy funksiyalarni berilgan sonli o‘qlar bilan tasvirlash haqida.
chiziqli ustunlik tizimlari![Juri, Vychisl. mat. va mat. fizika.
1087. - T. 27, No 6. - B. 949-951.
34. Lupanov O.V. Ts chegara elementlaridan sxemalar sinteziga oid masalalar.
kibernetika. Nashr 26.- Moskva: Nauka, 1973.- S. 109—140.

55-bet

35. II ech va poruk E. I. Eshik elementlaridan sxemalar sintezi haqida Ts Masalalar.
kibernetika. Nashr I. - M .: Nauka, 1964.- S. 49-62.
36. RG Nigmatullin, Boolean funktsiyalarining murakkabligi, Moskva: Nauka, 1991 yil.
37.Sapozhenko A.A.Ko'p qatlamli antichainlar soni bo'yicha
Sets Ts Discrete Mathematics - 1989. - 1-jild, №. 2.—S. 110-128.
38. Tyshkevich R.I., Chernyak A.A. Booleanning chegara kengayishi.
funksiyalar va grafiklar C Kombinator-algebraik va ehtimollik usullari
diskret tahlil.- Gorkiy: Gorkiy davlati. Universitet, 1989. - S. 111 - 129.
39. Feller V. Ehtimollar nazariyasiga kirish va uning qo'llanilishi. T. 1.— M .: Mir,
1984 yil.
40. Xachiyan L. G. Ts ni chiziqli dasturlashda ko‘p nomli algoritm.
Dokl. SSSR Fanlar akademiyasi.- 4979.-T. 244, No 5.- S. 1093-1096.
41. Chux ariq I. II. Antichain C Discrete soyasining maksimal kuchi bo'yicha
matematika.- 1989. - T. 1, №. 4, - 78-85-betlar.
42. V a 1 kabi E., J ego s 1 o w RG Birlik giperkubidagi kanonik kesmalar.- SIAM J.
Ilova. Matematika.— 1972.—V. 23, № 1.—B. 61-69.
43. Irkh o ffda G. Panjara nazariyasi. 3-nashr. - Providence: Amer. Matematika. Jamiyat,
1967. [Rus. per .: Birkhoff G. To'rlar nazariyasi. - Moskva: Nauka, 1984.]
44. Bl och h M., Moravek Ja. Chegaraviy funksiyalar sonining chegaralari D
Axborotni qayta ishlash mashinalari - 1967. - No 13. -P. 67-73. GRus. boshiga:
Blokh M., Moravek J. Chegara funktsiyalari sonini baholash C Kiberentice
osmon to'plami. Yangi seriya. Nashr 6.- M .: Mir, 1969.- B. 82-88.]
45. Bak R. C. Koinotning bo'linishi C Amer. Matematika. Oylik. - 1943. - V. 50, № O.
B. 541-544.
46. ​​Kameron SH. Umumjahon qarorida talab qilinadigan murakkablikni baholash
tarmoq Ts Tech. Rept. 60-600. Bionika simpoziumi materiallari. Rayt
Havoni rivojlantirish bo'limi, Dayton, Ogayo, dekabr 1960. - P. 197-212.
47. C h o w S. K. Chegaraviy funksiyalarni tavsiflash haqida Ts Minimallashtirish.
Mantiqiy funksiyalar va mantiqiy dizayn. Kommutatsiya davri nazariyasi va mantiqiy dizayn /
AIEE maxsus nashri S - 134, sentyabr. 1961. - B. 34-38.
48. Chow S. K. Statistik mustaqillik va chegara funksiyalari O IEEE Trans, on.
Elektron hisoblash.- 1965. - V. EC-14, No 1.-P. 66-68.
49. C hvata 1 V., Hammer PL Tengsizliklarni butun sonda yig'ish
dasturlash C Discrete Mathematics Annals - 1977.- No 1.- P. 145-162.
50.S haqida k SA Teoremani isbotlash protsedurasining murakkabligi C Proc. 3-yillik
Hisoblash nazariyasi bo'yicha ACM simpoziumi. - NY: Hisoblash assotsiatsiyasi
Mashina, 4971.-P. 151-158. GRus. boshiga: Kuk S.A. Jarayonlarning murakkabligi
teoremalarning kelib chiqishi C Kibernetik to'plam. Yangi seriya. Nashr 12.- M .: Mir,
1975.- S. 5-15.]
51. Muqova T. M. Chiziqli sistemalarning geometrik va statistik xossalari
naqshlarni aniqlashdagi ilovalar bilan tengsizliklar // IEEE Trans elektron komp.—
1965. V. EC-14, No 3.-P. 326-334.
52. Qopqoq TM, Efron B. Geometrik ehtimollik va hy ustidagi tasodifiy nuqtalar
perspherc C Matematik statistika yilnomalari.- 1967.- V. 38, No 1.- 213-bet.
220.
53.Cr ama Y. Muntazam mantiqiy funksiyalarning dualizatsiyasi C Diskret Qo'llaniladi
Matematika.1987. No 16. B. 79-85.
54. Danzer L, Griinbaum B., Klee V. Helli teoremasi va uning qarindoshlari.—
Providence: Amer. Matematika. Jamiyat, 1963. [Rus. boshiga: Danzer L., Grünbaum B.,
K Li V. Xelli teoremasi va uning qo'llanilishi. - M .: Mir, 1968.]
55. Dert ouzos M. L. Eshik mantiqi: sintez yondashuvi. - Kembrij,
Massachusets: MIT Press, 1965. [Rus. bo'lak .: Dertouzos M. Ostona mantiq. - M .:
Tinchlik. 1967.]
56. Du da R. O., H art PE Pattern tasnifi va sahna tahlili. - NY:
Wiley, 1973. [Rus. trans .: Duda P., Xart P. Namuna tanib olish va tahlil qilish
sahnalari.- M .: Mir. 1976.]
57. E1 g haqida t C. S. Yagona pol organlar tomonidan amalga oshiriladigan haqiqat funktsiyalari C
Mantiqiy funktsiyalarni minimallashtirish va chegara mantiqiy dizayni. Kommutatsiya davri nazariyasi
va mantiqiy dizayn / AIEE Maxsus nashri S-134, sentyabr. 1961. - B. 225-245.
58. Erdos P. Grafik nazariyasi va ehtimollik, II C Kanada. J. Matematika. — 1961. — V. 13.—
B. 346-352.
59. Fiiredi Z., Kan J., Kleitman DJ Giperkubning sfera qoplamalari
beqiyos markazlari bilan C Diskret matematika.- 1990.-V. 83-son, 1-son.— 129-bet—
134.
60. G ab s 1 man IJ Ko'pchilik (bo'sa) elementlarning funksional harakati.—
Ph. D. Dissertatsiya. Dep. Elec. Eng., Syracuse universiteti, Nyu-York - 1961 yil iyun.
61. Garey MR, Jonson DS Kompyuterlar va qiyinchilik. uchun qo'llanma
NP-to'liqlik nazariyasi - San-Fransisko: Friman, 1979. [Rus. boshiga: Gori M.,
D va bitta D. Hisoblash mashinalari va hal etilmaydigan muammolar, -M .: Mir,
1982.]

56-bet

EOS FUNKSIYALARI II BUL FUNKSIYALARNING BOSHQA FUNKSIYALARI 59
62. Golumbic M. S. Algoritmik grafiklar nazariyasi va mukammal grafiklar. — NY:
Akademik matbuot, 1980 yil.
63. Griinbaum B. Giper tekisliklarning joylashuvi C Proc. Ikkinchi Luiziana Konf. yoqilgan
Kombinatorika, grafik nazariyasi va hisoblash (RC Mullin va boshqalar, tahrirlar) .— 1971.—
41-74-betlar.
64. Hammer PL, I ba g a k i T., P e 1 ed UN Ostona raqamlari va chegarasi
yakunlari C Diskret matematika yilnomalari.1981. № 11. B. 125-145.
65. Hammer PL, I ba gak i T., Simeon e B. Chegara ketma-ketliklari C SIAM
J. Algebraik diskret usullar.- 1981.- V. 2, No 1. - B. 39-49.
66. H arding EF K o'lchamdagi N nuqtalar to'plamining bo'limlari soni
giperplanlar tomonidan qo'zg'atilgan Proc. Edinburg matematika. Jamiyat. - 1967. - V. 15 (seriya
II), № 4.—B. 285-289.
67. Henderson PB, Zalcstein Y. Grafik-nazariy xarakteristikasi.
Sinxronlashtiruvchi primitivlarning PV chunk klassi C SIAM J. Coinput.- 1977.- V. 6.-
B. 88-108.
68. H u S.-T. Eshik mantiqi. Berkli: Kaliforniya universiteti nashriyoti, 1965 yil.
69. Jeroslow RG Giperkubning cho'qqilari to'plamlarini chiziqli tarzda aniqlash to'g'risida
tengsizliklar C Diskret matematika .- 1975.- V. 11, .N2 2.- B. 119 - 124.
70. To anter L, Sompol insky H. Xatolarsiz xotirani assotsiativ esga olish //
Fizika tekshiruvi A. - 1987. - V. 35, No 1. - B. 380-392.
71. Karp RM Kombinator muammolari orasida kamayishi C Miller RE,
Tetcher JW (tahrirlar) Kompyuter hisob-kitoblarining murakkabligi - NY: Plenum Press.
1972. -P. 85-103. [Rus. trans .: Karp PM Kombinatorning qaytarilishi
muammolar C Kibernetik to'plam. Yangi seriya. Nashr 12.- M .: Mir, 1975.- S. 16-
38.1
72. Kirchberger P. Uber Tschebyschefschc Annaherugsmethoden C Matematika. Ann. -
1903. — V. 57. — S. 509-540.
73. Kleytman D. Dedekind muammosi haqida: monoton mantiqiy soni
funktsiyalari / Proc. Amer. Matematika. Soc. - 1969. - V. 21, No 3. - B. 677-682. fPyc. nep.:
Kleitman D. Dedekipd muammosi bo'yicha: monoton mantiqiy funktsiyalar soni //
Kibernetik to'plam. Yangi seriya. Nashr 7.- M .: Mir, 1970.- S. 43-52.]
74. Komlos J. (0, 1) matritsalarni aniqlash haqida Studia Sci. Matematika. Hun
gar.- 1967. - V. 2.—P. 7-21.
75. Komlos J. qoʻlyozma (1977). Bollobas B, Tasodifiy Grafiklar.- Nyu-York
va London: Akademik matbuot, 1985. S. 347-350.
76. Lawler EL, Lenstra JK, Rinnooy Kan AHG Generating all
maksimal mustaqil to'plamlar: NP-qattiqlik va polinom-vaqt algoritmlari C SIAM J.
Hisoblash.- 1980.- V. 9, No 3.-P. 558-565.
77. L o wenschuss O. Ortiqcha avtomatlarda organlarni tiklash O Axborot va.
nazorat.- 1959. - V. 2, No 2. - B. 113—136. [Rus. Lane: Lowenschuss O.
Ortiqcha avtomatlarda tiklovchi organlar Ts Cybernetic kolleksiyasi,
Nashr 2. - M .: IL, 1961.- S. 206-228.]
78. M a s W i 11 iams FJ, S 1 0 ane NJA Xatolarni tuzatuvchi kodlar nazariyasi.—
Amsterdam: Shimoliy Gollandiya nashriyot kompaniyasi, 1977. [Rus. boshiga:
MakWilliams F.J., Sloan H.J.A. Xatolarni tuzatish kodlari nazariyasi. - M .:
Aloqa, 1979.]
79. M ass va JL Threshold dekodlash. - Kembrij, Massachusets: MIT Press, 1963 yil.
fPyc. boshiga: Messi J. Ostona dekodlash. - M .: Mir, 1966.1.
80. M aus S. N. Chegaraviy funksiyalarning chegara matritsasi C IEEE Trans, on
Elektron hisoblash.- 1965 - V. EC-14, No 1. - B. 65-66.
81. McCulloch WS, Pitts W. Immanent g'oyalarning mantiqiy hisobi.
asabiy faoliyat C Matematika byulleteni. Biofizika. - 1943. - V. 5.—P. 115-133.
[Rus. trans.: McCulloch U.S., Pitts W. G'oyalarning mantiqiy hisobi,
C avtomatining asabiy faoliyati bilan bog'liq. - M .: IL, 1956. - S. 362-384.]
82. Minsku, M., Papert S. Perceptrons. - Massachusets: MIT Press, 1969 yil.
GRus. boshiga: Minsky M., Peyperth S. Perceptrons.- M .: Mir, 1971.1.
83. M o re EF, Shannon C. E. Ishonchli sxemalar kamroq ishonchli o'rni C yordamida.
J. Franklin Inst. - 1956.-V. 262. No 3.- B. 191-208; No 4. - B. 281-297. GRus.
boshiga: Mur E. F. Sheppoi K. E. Ishonchsiz o'rni C dan ishonchli sxemalar
Kibernetik to'plam. Nashr 1.- M .: IL. I960.— S. 109-148.1
84. Muroga M., To da I., T akas 11 S. Koʻpchilik qaror qabul qiluvchi elementlar nazariyasi C.
J. Franklin Inst. - 1961.-V. 271, .N2 5.-B. 376-418.
85. Muroga S., Tsuboi T., Baugh C. H. Chegaraviy funksiyalarni sanab o‘tish.
sakkiz o'zgaruvchidan C IEEE Trans, Comp.- 1970.-V. C-19, N ° 9.-P. 818-825.
86. Muroga S. Ostona mantiq va uning ilovalari.— NY: Wiley, 1971.
87. Nilsson NJ O'quv mashinalari. - NY: McGraw-Hill, 1965. [Rus. bo'lak .: H va l
eon H. O'quv mashinalari. - M .: Mir, 1967.1
88. Odlyzko A. M., Richmond L. In Ba'zi bo'linish po birmodalligi haqida.
linomials C Europ. , T. Kombinatorika. - 1982 - V. 3, —P. 69-84.
89. Odlyzko A .. M. +1 vektorlarning tasodifiy tanlanishi bilan ajratilgan pastki fazolarda Ts.
J. Kombin. Nazariya, A.- 1988, V. 47, No 1P. 124-133,

57-bet

90. Yoki d man ET Minimal pol ajratgichlar va xotira talablari uchun
sinxronizatsiya C SIAM J. Hisoblash - 1989. - V. 18, No 1. - B. 152-165.
91. Parallel taqsimlangan ishlov berish: idrok mikrostrukturasini o'rganish / Eds.
DE Rumelhart va JL McClelland. - Kembrij, Massachusets: MIT Press.
1986 yil.
92. P e 1 ed UN, Si me one B. Muntazam uchun polinom-vaqt algoritmlari
to'plamni qoplash va chegara sintezi C Diskret amaliy matematika.- 1985.- № 12.-
B. 57-69.
93. P e g to ins DT, W i 11 is DG, Whitmore EA Fazoning bo'linishi bo'yicha
bir vaqtda giperplanlar C Internal Rept./Lockheed Aircraft Corp. Raketalar va kosmik
Bo'lim. Sunniveyl, Kaliforniya, 1959 yil.
94. P ierce WH Failure-tolerant kompyuter dizayni - Nyu-York va London:
Akademik matbuot, 1965. [Rus. Lane: Pirs W. Ishonchli hisoblashni qurish
mashinalar. - M .: Mir, 1968.]
95. Poljak S. Grafiklarning turg'un to'plamlari bo'yashlari haqida eslatma C Comm. Matematika. Univ. Caro
linae.- 1974. - V. 15. - B. 307-309.
96. Polya G. Matematika va asosli fikrlash. V. 1. Induksiya va analogiya
matematika.- Princeton: Princeton University Press, 1954. [Rus. boshiga: D kuylang.
Matematika va mantiqiy fikrlash. T. 1. Induksiya va analogiya
matematika. - M .: IL, 1957.]
97. IEE materiallari E. - 1990. - V. 78, 9-son, 10-son.
98. Proktor RA. Chiziqli algebra C bilan ikkita kombinatoryal masalaning yechimi
Amer. Matematika. Oylik.- 1982. - V. 89. - B. 721-734.
99. Rademaxer H., Schoenberg IJ Xollining qavariq sohalar haqidagi teoremasi
va Tchebycheffning yaqinlashuv muammosi C Kanada. J. Matematika.— 1950.— V. 2.—
B. 245-256.
100. Hisoblash tizimlari uchun ortiqcha texnikalar (RH Wilcox va WC Mann,
muharrirlar) - Vashington, DC: Spartan Books, 1962. [Rus. boshiga: Kirish usullari
hisoblash tizimlari uchun ortiqcha / Per. ingliz tilidan, ed. V. S. Pugacheva .-
M.: Sov. radio, 1966.]
101. Reed IS Ko‘p xatoliklarni tuzatuvchi kodlar sinfi va dekodlash sxemasi Ts.
Trans. IRE.- 1954. - PGIT - 4. - P. 38-49. [Rus. boshiga: Reed I.S.Code sinf bilan
bir nechta xatolarni tuzatish va dekodlash sxemasi Ts Cybernetic
yig'ish. Nashr 1.- M .: IL, I960.-S. 189-205.]
102. Reiterman J., R o d 1 V., S inaj o v a E., Tum a M. Eshik.
gipergraflar C Diskret matematika - 1985.- V. 54.- B. 193-200.
103. Rosenblatt F. Neyrodinamika tamoyillari: perseptron va nazariyasi.
miya mexanizmlari - Vashington: Spartan kitoblari, 1962. [Rus. boshiga: Rosenblatt
Neyrodipamikaning printsiplari (miya mexanizmlari idroki va nazariyasi) .- M .: Mir,
1965.]
104. R haqida fa G.-C. Kombinatoriya nazariyasi asoslari haqida I. Mobius funktsiyalari Ts
Z. Vahrscheinlichkeitstheor. und verw. Geb. - 1964. - Bd. 2, No 4. - S. 340 -
368.
105. Schlafli L. Gesammeltc matematik Abhandlugen. Guruh 1. - Bazel: Verlag
Birxauzer, 1950 yil.
106. Shrijver A. Chiziqli va butun sonli dasturlash nazariyasi.— Chichester: Wiley,
1986. [Rus. boshiga: Schreiver A. Chiziqli va butun sonlar nazariyasi
dasturlash. - M .: Mir, 1991.]
107. Stenli R. R. Veyl guruhlari, qattiq Lefshets teoremasi va Sperner.
mulk Ts STAM J. Algebraik diskret usullar.- 1980, - V. 1.—B. 168-184.
108. Steiner J. Einige Gczetze uber die Theilung der Ebcne und des Raumes C J.
reine angew. Matematika.— 1826 — No 1.—S. 349-364.
109. Von N'eumann J. Ehtimoliy mantiq va ishonchli organizmlar sintezi.
C Automata Studies ishonchli komponentlaridan (C. E. Shannon va J.
Makkarti, muharrirlar) - Prinston, Nyu-Jersi: Prinston universiteti. Matbuot, 1956. [Rus. boshiga:
Neumann J. Hodisa organizmlarining ehtimollik mantiqi va sintezi
C Avtomataning ishonchsiz komponentlari.- M .: IL, 1956. - S. 68-139.]
110. Wen del JG Geometrik ehtimollik muammosi C Mathemalica Scandinavi.
taxminan - 1962. - V. 11.—B. 109-111.
111. Vasserman PD Neyron hisoblash. Nazariya va amaliyot. - NY: Van
Nostrand Reinxold, 1989. [Rus. boshiga: Wassermon F. Isyrokompyothernaya texnika.
Nazariya va amaliyot. - M .: Mir, 1992.]
112. Widrow B., Stearns SD Adaptiv signalni qayta ishlash - Englewood-Cliffs.
NJ: Prentice-Xall, 1985. [Rus. trans .: Widrow B., Stearns S. Adaptiv
signalni qayta ishlash - M .: Radio va aloqa, 1989.]
FROM. Widrow B., Lehr M. A. 30 yillik moslashuvchan neyron tarmoqlar: perseptron,
madaline, va backpropagation C IEEE materiallari.- 1990.- V. 78, № 9.-
B. 1415-1442.
114. Willis DG Eshik kalitlari uchun minimal og'irliklar Kommutatsiya nazariyasi
Kosmik texnologiyalar. Stenford universiteti nashriyoti, 1963, 91-108-betlar.

58-bet

Mantiqiy funksiyalarning chegaraviy funksiyalari va chegaraviy ko‘rinishlari 61
115. Winder R. O. Bir bosqichli pol mantiqi Ts Mantiqiy minimallashtirish
Funktsiyalar va mantiqiy dizayn. Kommutatsiya davri nazariyasi va mantiqiy dizayn / AIEE Special
Nashr S-134, sentyabr. 1961. - B. 321-332.
116. Winder R. 0. Eshik mantiqi. Ph. D. Dissertatsiya, bo'lim. Matematika, Prinston
Universitet, 1962. Universitet Microfilms tomonidan nashr etilgan, Xerox Co. (Ann Arbor, MI, 1973).
117. Winder R. 0. Etti argumentli chegara funksiyalarini sanab o'tish IEEE
Trans, elektron hisoblashda. - 1965. - V. EC-14, No 3. - P. 315-325.
118. Winder R. 0. N-fazoning giperplanlar orqali bo'linishi C SIAM J. Appl. Matematika.—
1966.—V. 14, № 4.-P. 811-818.
119. Winder R. 0. Eshik mantiqining holati D RCA ko'rib chiqish. - 1969. - V. 30,
№ 1.—P. 62-84.
120. Winder R. 0. Chow parametrlari C asosidagi eshik eshiklarining yaqinlashuvi.
IEEE Trans, kompyuterda - 1969. - V. C-18, No 4. - P. 372-375.
121. Winder R. 0. Eshik mantiqi asimptotalari // IEEE Trans, Comput.- 1970.-
V. C-19, No 4.- B. 349-353.
122. Winder R. 0. Chow parametrlari pol mantiqiy J. uchun assotsiatsiya
Hisoblash mashinalari.- 1971.- V. 18, L- 2.-P. 265-289.
123. Win o grad S., Cowan JD Shovqin mavjudligida ishonchli hisoblash.—
Kembrij, Massachusets: MIT Press, 1963. [Rus. yo'lak .: Uzum C., Koy
:) n JD Shovqin mavjudligida ishonchli hisob-kitoblar.- Moskva: Nauka, 1968.]
124. Yajima S., Ibaraki T. Eshik sonining pastki chegarasi
funktsiyalari C IEEE Trans, elektron hisoblashda - 1965. - V. EC-14, No 6. - P. 926-929.
[Rus. ner .: I dim a S., I b araki T. Eshik soni uchun pastki chegara
funktsiyalari C Kibernetik to'plam. Yangi seriya. Olib ketish 6.- M .: Mir, 1969.-
S. 72-81.]
125. Zaslavskiy T. Aranjirovkaga qarab: bo'limlar uchun yuzni hisoblash formulalari
kosmosning giperplanlar tomonidan Ts Amer xotiralari. Matematika. Jamiyat. - 1975. - V. 1,
№ 154.—B. 1-102.
Tahririyat tomonidan 1990 yil 15 XII olingan
TUZATISHDA QO'SHIMCHA
Yaqinda A.A.Ermatov (A.A.Ermatov, Chegaraviy funksiyalar soni haqida.
Diskret matematika.- 1993.- T. 5, tashqarida. 3.—S. 40-43) taklif qilingan
asimptotiklarni olishning yana bir yondashuvi (7), shuningdek, Odlyzh natijasiga asoslangan
co [89], lekin fazoda emas, balki fazoda (y \, ..., yn) tahlildan foydalanish
og'irliklar, bu esa uni Pechiporuk usuliga yaqinlashtiradi [35]. Agar p o'lchovli pastki fazo bo'lsa,
A <= $ n matritsasi tomonidan yaratilgan, 2p (± 1) -vektorlar - generatorlar va
qarama-qarshi - va boshqa (± 1) -vektorlarni o'z ichiga olmaydi, keyin uni uzaytirish mumkin
(n - 1) -o'lchovli pastki fazo, u ham yangi (= b1) -vektorlarni o'z ichiga olmaydi.
axy \ + ... + anun = 0 fazoda shunday kichik fazo bo'lsin (y \, yn)
Keyin, etarlicha kichik e uchun, faqat
giperkubning 2p uchlari ma'lumotlari {- 1, 1} p. Bu eslatma darhol olish imkonini beradi
asimptotik tarzda 2Pn / p \ 2n n + 1 ning turli o'z-o'zidan ikkilangan funktsiyalari
shaklning o'zgaruvchilari
/ (2/1, • • Yn, Yy-s) ■ = Sgn (a \ Y \ +... + Pnu + 8 Yn \ - \).

Asl matn
84. Muroga М., То da I., Т a k a s 11 S. Theory of majority decision elements Ц
Yaxshiroq tarjima taklif qilish