Raqamli kutubxona Kibernetikadan matematik masalalar

§ 2, 6-band 2 log (si) dan ortiq masofadagi cho'qqilarni kesib bo'lmaydi.
dan A. Shuning uchun, yozilgan tengsizliklar soni oshmaydi
va bu qiymat U (/ i) farqining yuqori chegarasi - agar (/ 2) I
r (f 1, / 2) = 1 uchun.
2 "cnjy (cn \ = 2n {c
c log (1 + 1 / c) + log (l + c) - c + 1 ■ = 0.

45-bet

48
Y. A. ZUEYO
Deyarli barcha mantiqiy funktsiyalar asimptotik 2n ~ ga ega! yolg'iz
cho'qqilar; shuning uchun ular uchun £ (/)> 2n ~ 1 / sv. Qiymatlardagi farq
tartib bilan yozilgan ushbu funktsiyalar qatorining o'rtasida chegara raqamlari
kamaymaydigan chegara raqamlari, oshmaydi
2n2n / 22 log (cn) n21ov (cn) = o (2n ~ 1 / c0n),
bu asimptotikaning mavjudligini isbotlaydi.
Nazariy jihatdan d. N. f. Korshunov [25], birozdan keyin esa Andreev
[1] eng qisqa DN uzunligining asimptotika tartibini o'rnatdi. f. 1 (f)
deyarli barcha mantiqiy funktsiyalar uchun /:
r> n
1 (f) X, fn.
u L log p log log p
Ostona vakilliklarida, hozirgacha, odamga erishish mumkin edi.
26-teorema [13]. t (n) funksiya mavjudki, n uchun -
deyarli barcha mantiqiy funktsiyalar uchun f n o'zgaruvchida t (f) ~ t (n). Uchun
t (n) ning asimptotik harakati taxminlarni qondiradi
2n!(C1 + 1) nt ^ t (n) ^ log n 2n “7 / r,
Bu erda c \ ~ 3.41 - tenglamaning ildizi
c log (1 + l / c) + log (l + c) - c = 0.
Isbot. t (n) asimptotikaning mavjudligi allaqachon mavjud
oldingi mulohaza bilan o'rnatildi, bu ham shuni ko'rsatdi
t (n) ^ 2n ~ 1 / cn> 2n / 9.74d. Shannonning kuch usuli darhol imkon beradi
bu past bahoni ikki baravar oshiring. Chunki deyarli barcha funktsiyalar mavjud emas
Kardinallikning ruxsat etilgan chegara to'plamlariga ega (c0 + e) ​​rc, bu erda e -
o'zboshimchalik bilan kichik musbat son va barcha chegara soni
kardinallik to'plamlari (co + o (1))? r ga teng
2n (c0lo- (l4-l / c0) + log (l- | -c0) -h1 + o (l)) _ 2P (S0 + O (1))
tp (s 0 ~ 1-o (1)) t-g
u holda m tengsizliklar ko'pi bilan 2 ta funktsiyani belgilashi mumkin. Shunung uchun
deyarli barcha 2 ta mantiqiy funktsiyani aniqlash uchun asimptotik tarzda talab qilinadi
kamida 2n / con> 2n / 4.87?r chiziqli tengsizliklar.
Pastki chegarani yanada mustahkamlash uchun biz foydalanamiz
birinchi marta Kuznetsov tomonidan taklif qilingan quvvat usulining modifikatsiyasi [30]
uchun d. n. f. Ba'zilar uchun buni hisobga olish g'oyasi
c 1 deyarli barcha funktsiyalar uchun etarli emas. Shuning uchun, funktsiyalar sonini baholashda,
m tengsizliklar bilan aniqlanishi mumkin, shuni hisobga olish kerak
bunday kardinallikning chegara to'plamlarini faqat kichik olish mumkin,
w ga bog'liq bo'lmagan son. Kardinallikning chegara to'plamlari, emas
C [P1 dan oshsa, siz mtr ni olishingiz mumkin, ammo bu tanlov Nn (c \ n) raqamidan qilingan <
c 1 ~ 3.41 tenglamaning ildizi bo'lsin
tiqilib qolish (l + 1 / s) + log (1 + s) - c = 0.
Tenglamaning chap tomoni c> 1 uchun monoton ravishda kamayadi, shuning uchun uchun
har qanday ixtiyoriy kichik e> 0, sonning kutilishi
(ci + e) ​​rc dan katta bo'lgan kardinallikning ruxsat etilgan chegara to'plamlari, tasodifiy
mantiqiy funksiya hisoblanadi
2 ^ (c1log (ljl / c1) +] og (l + c1) ~ c1 + i-61 (s) + o (i)) __ 2r? (1-b1 (8) + o (1))
bu yerda d 1 (e)> 0, 6i (e) -> 0 e0 sifatida. Demak, tengsizlikdan foydalanish
Chebyshev, biz deyarli barcha mantiqiy funktsiyalar uchun ruxsat etilgan sonini olamiz

46-bet

POSA FUNKSIYALARI II MANTIQLI FUNKSIYALARNING BOSHQA FUNKSIYALARI 4Y.
(ci + e) ​​/ 2 dan yuqori bo'lgan kardinallik to'plamlari oshmaydi
2 ^ * har qanday 62 <6i uchun va shunchalik ko'p chegara to'plamlari olinadi
n2
2 dan oshmasligi ma'lum bo'lgan raqam. Chegara o'rnatiladi
quvvat ortiq emas] u (u + e) ​​/ g mavjud
n (c1 log (i + i / c1) + log (i + c1) + l + 63 (e) + o (i)) __ n (ip-c1-f-63 (e) -f 0 (1) )
bu yerda 6s (e)> 0, S3 (k) - »- 0 uchun 8 -> 0. Demak, m tengsizliklar mumkin
ko'proq so'rang
2p22P (1 "62) ^ (c ^ l + Oa + od))
mantiqiy funktsiyalar. Bundan / r22 ^ 2 ^ m o (2n) ekanligini hisobga olsak, biz hosil qilamiz
e ni nolga aylantiradi, bu deyarli barcha 22 mantiqiy funktsiyani belgilash uchun
asimptotik ravishda kamida 2r? / (ci + l) rc tengsizliklari talab qilinadi.
Biz teoremaning yuqori chegarasini isbotlashga o'tamiz, bu