Raqamli kutubxona Kibernetikadan matematik masalalar

4-sahifa

BO‘LIK FUNKSIYALARI va BO‘LIK FUNKSIYALARNING BOSHQA FUNKSIYALARI J.
Afsuski, bular birinchi navbatda mantiqiy chegarada ishlaydi
SSSR kutubxonalari qabul qilinmadi. Shunga qaramay, 1964 yilda Pechinoruk edi
dan zanjirlarni sintez qilish bo'yicha fundamental ish [35]
chegara elementlari, bunda murakkablik asimptotikasi tartibi olinadi
bunday sxemalar. Ushbu tadqiqotlar 1973 yilda Lupanov [34] tomonidan yakunlangan.
chegara elementlarining minimal soni etarli ekanligini ko'rsatdi
har qanday mantiqiy funktsiyani sintez qilish uchun asimptotik ravishda 2V2n / n ga teng,
deyarli barcha mantiqiy funktsiyalar bu murakkablikka ega.
1965 yilda ikkita monografiya ostonada
mantiq. Amerikalik matematik Xu [68] kitobida, taniqli muallif
topologiyaga oid monografiyalar, chegara funksiyalarining xossalari keltirilgan
shu kungacha o'z yorqinligini yo'qotmagan inoyat. Asl ko'rinish
chegara mantig'i Dertouning rus tiliga tarjima qilingan kitobida ishlab chiqilgan
zos [55], texnik masalalarga ko'proq bag'ishlangan
chegara funksiyalari va sxemalarini sintezi. Va nihoyat, 1971 yilda
Murogi kitobi [86] 400 ga yaqin asardan iborat bibliografiya bilan
natijalarning haqiqiy ensiklopediyasiga aylangan chegara mantig'i,
barcha oldingi yillar uchun olingan. Etarlicha to'liq taqdimot
rus tilidagi chegara mantiqini Butakov [2] kitobida topish mumkin.
Elektron sxemalarni yanada miniatyuralashtirish va paydo bo'lishi bilan
keng ko'lamli integral mikrosxemalar chegara mantig'iga qiziqish ortib bormoqda. Kon
junctors, disjunctors va inverters, qattiq kichik qadoqlangan
kerakli ixchamlik, ishonchlilik va tezlikni ta'minlagan hajm
kompyuterning mantiqiy sxemalarini ishlatgan, shuningdek, kerakli texnoga ega edi
mustahkamlik. Kuchliroq, ammo murakkabroq chegaralarga ehtiyoj
vovullagan mantiq g'oyib bo'ldi va yetmishinchi yillarning boshida, lekin ostona
mantiq kamdan-kam uchraydigan narsaga aylanib bormoqda. Biroq, yetmishinchi yillarning o'rtalariga kelib, qiziqish
muammoga yana jonlanadi. Bu safar chegara funktsiyalariga
butunlay boshqa sohadan kelgan - - h haqida to'liq vazifalardan unga kimga kuyladi
dasturlash (masalan, [106] ga qarang).
Aslida, eng mashhur AR-qavat puf vazifalaridan biri
Lineer mantiqiy dasturlash yukxalta muammosidir:
maksimal 2 cgxr (2)
Shartiga ko'ra
bu erda o'zgaruvchilar mantiqiy, va haqiqiy raqamlar. Shunday qilib, haqiqiy qiymatlar oralig'i
bu yerda monoton chegara funksiyasining nollar to‘plami va
uning tuzilishini o'rganish algoritmik muammoni yoritishi mumkin
kabi muammolarni hal qilishda qiyinchiliklar.
Chiziqli mantiqiy dasturlash muammolarida ruxsat etilgan domen
bir emas, balki tengsizliklar tizimi orqali aniqlanishi mumkin. Qayerda
tengsizliklarni jamlash, ya'ni ularni kichikroq raqam bilan almashtirish muammosi paydo bo'ladi.
tegishli maydonni o'zgartirmasdan. Shu kabi masalalarni o'rganish
mantiqiy chegaraviy tasvirlar nazariyasining paydo bo'lishiga olib keldi
funktsiyalar - chiziqli tengsizliklar tizimlaridan foydalangan holda bunday tasvirlar,
mantiqiy to'plamlar tizim uchun ruxsat etilganda va faqat ular
mantiqiy funktsiyaning o'qlari. Eshikning geometrik tasviri
Mantiqiy funktsiyaning barcha funktsiyalari giper tekisliklari bilan kesilgangacha qisqartiriladi
birlik uchlari. Kerakli chiziqli minimal soni
tengsizliklar mantiqiy funksiyaning chegara soni va bilan birga deyiladi
uzunligi bilan uning eng qisqa dis'yunktiv normal shaklini ko'rib chiqish mumkin
uning murakkabligining o'lchovi bo'lishi kerak.
Eshik ko'rinishini ajratish sifatida ham ko'rish mumkin
chegara funktsiyalari, ya'ni dis'yunktiv normal shaklga o'xshash
(dn. f.) uni 2-chuqurlik sxemasi sifatida ko'rib chiqing (3-rasm). Bundan tashqari, analogiya