Информация о документе

Цена 12000UZS
Размер 1.5MB
Покупки 0
Дата загрузки 07 Ноябрь 2026
Расширение docx
Раздел Дипломные работы
Предмет Информатика и ИТ

Продавец

Bohodir Jalolov

To‘liq aniqlanmagan bull funksiyasini minimallashtirish algoritmi va dasturiy ta’minoti

Купить
“ TO’LIQ ANIQLANMAGAN BULL FUNKSIYASINI MINIMALLASHTIRISH ALGORITMI VA DASTURIY TA’MINOTI ” MUNDARIJA Kirish . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 I bob . Mantiq algebrasi funksiyalarini minimallashtirish muammosi . 1. Mantiq algebrasi funksiyalarini minimallashtirish muammosi- ning dolzarbligi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2. Diz’yunktiv normal shakl. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Kon’yunktiv normal sh a kl. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3. Mulo h azalar algebrasi formulasini qisqartirilgan dizyunktiv normal shakl ni hosil qilish usullari. . . . . . . . . . . . . . . . . . . . . . . . 18 4. I-bob bo`yicha xulosalar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 I I bob. To’liq aniqlanmagan Bull funktsiyalarini minimallashtirish. 1. Bul funktsiyalarning metrik o’lchamlari . . . . . . . . . . . . . . . . . . . 2 9 2. Bleyk usulida qisqartirilgan DNSh ni hosil qilish usuli . . . . . . . . . 30 3 Qisman aniqlangan mantiqiy funktsiyalarni minimallashtirish- ning mohiyati . 37 4. To’liq aniqlanmagan Bul funksiyalarni minimallashtirishning dekompozitsiya usuli. 40 5. 6. To’liq aniqlanmagan mantiqiy funksiyalarni minimallashtirish uchun takomillashtirilgan Mak-Klaski usuli . . . . . . . . . . . . . . . . . II-bob bo’yicha xulosalar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 54 I II bob. To’liq aniqlanmagan Bull funksiyalarini minimallashtirish - ning dasturiy ta’minoti . 1. Mantiqiy for m ula tushu n chasi va u n i n g grammatik tasnifi . . . . . . 55 2. Mantiqiy ifodalarni tahlil qilish algorit m lari. . . . . . . . . . . . . . . . . 60 3. M a n tiqiy ifodalar n i soddalashtirish algorit m i. . . . . . . . . . . . . . 61 1 4. Dasturiy ta’minot tavsifi va undan foydalanish. . . . . . . . . . . . . . 64 Xulosa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Adabiyotlar r o’yxati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Ilova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2 K I R I SH Masalaning qo’yilishi. Dissertatsiya ishida to’liq aniqlanmagan Bull funksiyalarini minimallashtirish algoritmi va dasturiy ta’minotini yaratish hamda uni amaliyotga qo’llash masalasi qaralgan. Masalaning dolzarbligi. Insoniyat faoliyatining ko’pgina yo’nalishida oldin to’plangan katta hajmdagi bilim va ma’lumotlarni tahlil qilishga asosan xulosa qilishga to’g’ri keladi. Tibbiyotdagi tashhis qo’yish masalasi, ijtimoiy so’rovlarni tahlil qilish, geologiya ma’lumotlariga ko’ra bashoratlash, texnik qurilmalarni sintez qilish kabi masalalar bunga misol bo’ladi. Ushbu masalalarni yechishda tanib olish nazariyasi usullari keng qo’llaniladi, xususan faktlarni mantiqiy tahlil qilish usuli. Diskret qurilmalarni sintez qilish masalasida ularning ishlash faoliyatini mantiqiy funksiyalar sistemasi yordamida ifodalanadi. Bunda, kirish signallarining ba’zi qiymatlarida mantiqiy funksiyaning qiymati aniqlanmay qolishi mumkin. Bunday jarayonni ifodalovchi mantiqiy funksiya qisman yoki to’liq aniqlanmagan mantiqiy funksiya deyiladi. Kirish signallarini ma’lum bir qiymatlarini tanlash asosida funksiyani davom ettirish, ya’ni noaniqliklarini aniqlashtirish mumkin. Mantiqiy funksiya qiymatini hisoblash murakkab masala hisoblangani uchun hamda diskret qurilmaning sodda modelini qurish uchun funksiyani minimallashtirish masalasi dolzarb hisoblanadi. Tadqiqot ob’yekti va predmeti: mantiqiy funksiyalar, mulohazalar hisobi, bilimlarni formallashtirish, real ob’yektlarni tahlil qilish. Tadqiqotning maqsadi: tanib olish hamda diskret qurilmalarni sintez qilish masalalarida vujudga keladigan parametrlarni qiymatida to’liq aniqlanmagan mantiqiy funksiyalarni minimallashtirish yordamida soha muammolarni yechishda, mutaxassis tomonidan olingan yechimlardan sifat va samaradorlikdan kam bo'lmagan natijalarga erishadigan algoritm va dasturi y ta’minot ishlab chiqishd an iborat . 3 Tadqiqotning vazifalari: Tadqiqot maqsadini amalga oshirish uchun us hbu vazifalar bajarilgan: 1. mantiqiy funksiyalarni minimallashtirish muammosi uni hal qilish bosqichlari ni tahlili; 2. mantiqiy funksiyalarni minimallashtirish m asala si ni yechish bilan bog’liq qoid a l a rni t a hlili ; 3. to’liq a niql a nm a g a n m a ntiqiy funksiy a l a rni minim a ll a shtirish a lgoritml a rini t a hlili; 4. t a hlil n a tij a l a rig a ko’r a hisobl a sh a lgoritmini ishl a b chiqish; 5. to’liq a niql a nm a g a n m a ntiqiy funksiy a l a rni minim a ll a shtirish a lgoritmi uchun d a sturiy t a ’minot y a r a tish; 6. dasturiy t a ’minotd a n foyd a l a nishning jih a tl a rini ko’rs a tish. Tadqiqotning ilmiy yangiligi: dissertatsiyada to’liq aniqlanmagan mantiqiy funktsiyalarni minimallashtirishning Mak-klaski usulini takomillashtirilgan holda to’liq aniqlanmagan mantiqiy funktsiyalarni minimallashtirish algoritmi yaratilgan. Tadqiqotning amaliy ahamiyati: mantiqiy qarorlarni qabul qilish jarayonini tahlil asosida qiymati mavhum bo’lgan mantiqiy parametrlarni qiymatini aniqlashtirish, dasturiy ta’minotidan diagnostik tahlilni amalga oshirishda foydalanish mumkin. Tadqiqotning tarkibiy tuzilishi. Dissertasiya kirish qismi, uch ta bob, xulosa va foydalanigan adabiyotlardan tashkil topgan. Ilovada, dastur kodi keltirilgan. Tasnif. 1-bobda, Mantiq algebrasi funksiyalarini minimallashtirish muammosini hal qilish bosqichlari ko’rsatilgan . 2-bobda, To’liq aniqlanmagan mantiqiy funktsiyalarini minimallashtirish muammosining bayoni, masalaning hisoblash algoritmi bayon etilgan. 3-bobda, To’liq aniqlanmagan Bull funksiyalarini minimallashtirishning dasturiy ta’minoti va undan foydalanish tavsifi berilgan. 4 5 Dissertasiya mazmuni aks ettirilgan va nashr etilgan maqolalar. Ushbu mavzu yuzasidan quyidagi maqolalar chop ettirilgan: R .SH. Mamatmurodov, J.M.Berdalov . Пр o изв o дн a я булев o й функции // “Zamonaviy axborot, kommunikatsiya texnologiyalari va at-ta’lim tatbiqi muammolari” mavzusidagi respublika ilmiy-amaliy anjumani ma’ruzalar to‘plami. Toshkent 2023-yil 7-8 aprel , [ 284 - 286 ] N.Abdirofiyev, R .SH. Mamatmurodov, M.Salimova . Метoд тaблицы рaзличии минимизaция слaбo oпределенные булевые функций. // “Zamonaviy axborot, kommunikatsiya texnologiyalari va at-ta’lim tatbiqi muammolari” mavzusidagi respublika ilmiy-amaliy anjumani ma’ruzalar to‘plami. Toshkent 2023-yil 7-8 aprel , [ 318 - 320 ] Tadqiqot mavzusi bo’yicha adabiyotlar sharhi: A.V. Kabulov, E. Urunbaev, I.I. Qalandarov, A.O. Ashurovlarning “ Мет o ды синтез a o птим a льных к o ррект o р o в эвристических a лг o ритм o в н a o сн o ве функций k– зн a чн o й л o гики ” nomli ilmiy monografiyasida to’liq aniqlanmagan k-qiymatli mantiqiy funktsiyalarni minimallashtirish algoritmlari va ularni tahlili berilgan [2]. Журaвлев Ю.И. va boshqalarni ,, Aлгoритми aлгебрaическoй и лoгическoй кoррекции, и их применения “ maqolasida algebraik va mantiqiy tahlilga asoslangan evristik algoritmlarni amaliy tadbiqlari ko’rsatilgan .[3 ] Лютикoвa Л.A. va boshqalarni ,,Пoиск лoгических зaкoнимернoстей в дaнних с испoльзoвaнием сигмa-пи нейрoнних сетей” nomli maqolasida mantiqiy tuzilmalarda noaniqliklarni tahlil asosida aniqlashtirish masalasini to’liq aniqlanmagan mantiqiy funksiyalarni davom ettirish masalasiga keltirish bayon etilgan [4 ]. Прихoжиий A. A. «Чaстичнo oпредленные лoгически системы и aлгoритми» nomli monografiyasida qisman aniqlangan tizimlarni tahlili, algoritmlari va ularni amaliy tadbiqlari ko’rsatilgan [5]. AQSh, Massachusets texnologiya instituti olimlari tomonidan boshqaruv elementlarining nosozligini tiklashda, ishonchsiz elementlarni korrektor kiritish 6 yordamida ma’lum bir funksiya orqali ifodalab qisman aniqlangan funksiyani davom ettirish masalasiga keltirilgan. Axborotni qayta ishlash tizimining ishonchsiz ishlaydigan qismlarini ma’lum bir evristika sifatida qarash, bir xil muammoni hal qilish uchun bir nechta turli hil evristika kiritilib natijalar ma’lum bir tarzda tuzatilgan. Natijada ishonchsiz elementlardan ishonchli zanjirlarni sintez qilish masalalariga o’xshash bo’lgan masalalar hosil bo’lgan (Buyuk Britaniya, Kembrij universiteti). Shuning uchun qaror qabul qilishda evristik usullarni qo’llashda bosh muammo axborotni qayta ishlaydigan tizim holati bo’yicha dastlabki ma’lumotlarning mavhumligi va aniq ma’lumotlarnining yetishmasligi hisoblanib, ular ma’lum darajada sozlanadi. Dunyoda sust shakllangan sohalarda matematik usullardan intensive foydalanib, jumladan, evristik algoritmlar natijasini sozlashning mantiqiy usullarini yaratish, mantiq funksiyalar sinfining minimallashtirish keng ilmiy tadqiqot ishlari olib borilmoqda. 7 I-BOB. M A NTIQ A LGEBR A SI FUNKSIY A L A RINI MINIM A LL A SHTIRISH MU A MMOSI. Usbu bobda, mantiq algebrasi funksiyalarini minimallashtirish muammosi va uni hal qilish bosqichlaridagi qisqartirilgan, tupikli, minimal dizyunktiv normal shakl(DNSH) bilan bo’g’liq tushunchalar hamda ularni hosil qilish usullari bayon etiladi. 1.1. Funksiyаlаrini minimаllаshtirish muаmmоsining dоlzаrbligi [1] . Xаlq xо‘jаligi uchun muhim аmаliy аhаmiyаtgа egа bо‘lgаn kо‘pchilik mаsаlаlаrni hаl qilishdа mаntiq аlgebrаsidаn fоydаlаnish mumkin. Quyidа shundаy mаsаlаlаrdаn biri mаntiq аlgebrаsining funksiyаlаrini minim а ll а shtirish mu а mmоsi sif а tid а q а r а lgаn. 1.1- t а ’ r i f . UshbuK = xi1 σ1¿xi2 σ2¿...⋅xir σr ( bо‘lgаndа iγ≠ iμ ) (1.1) ifоdа element а r kоn’yunksiy а deb а t а l а di. r sоn element а r kоn’yunksiy а ning r а ngi deyil а di. Kоnst а nt а 1 ni r а ngi 0 g а teng bо‘lg а n element а r kоn’yunksiy а deb hisоbl а ymiz. 1.2- t а ’ r i f . Ushbu D = ¿i=1 s K i(i≠ jbo'l ganda K i≠ K j) (1.2) ifоd а diz’yunktiv nоrm а l sh а kl (DNSh) deb а t а l а di, bu yerd а Ki – r а ngi i g а teng bо‘lgаn elementаr kоn’yunksiyа. Mа’lumki, D diz’yunktiv nоrmаl shаkl mаntiq аlgebrаsining mа’lum bir f(x1,x2,...,xn) funksiyаsini reаlizаtsiyа qilаdi vа mаntiq аlgebrаsining berilgаn 8 funksiyаsi bir nechtа DNSh kо‘rinishidа ifоdаlаnishi mumkin. Mаntiq аlgebrаsining hаr qаndаy f (x1,x2,...,xn) (f≠ 0) funksiyаsini DNSh D = f(x1,x2,...,xn) (1.3) kо’rinishigа keltirish mumkin. Bundаy DNSh sifаtidа f funksiyаning mukаmmаl diz’yunktiv nоrmаl shаklini (MDNSh) оlish mumkin, yа’ni D=¿¿ (σ1,σ2,...,σn)¿ f(σ1,σ2,...,σn)=1¿ ¿x1 σ1x2 σ2...xn σn¿ . (1.4) 1.1- m i s о l . f(x1,x2,x3) funksiyа 1.1- chinlik jаdvаli bilаn berilgаn bо‘lsin. 1.1- jаdvаl x1 x2 x3 f(x1,x2,x3) x1 x2 x3 f(x1,x2,x3) 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 u hоldа, f(x1,x2,x3) funksiyаni D1= x1x2x3∨ x1x2x3∨ x1x2x3∨ x1x2x3∨ x1x2x3 (1.5) MDNSh kо‘rinishidа ifоdаlа ni sh i mumkin. Ikkinchi tаrаfdаn, shu funksiyаning о‘zini D 2= x2x3¿x1 (1.6) DNSh kо‘rinishidа hаm ifоdаlаsh mumkin. Аgаr D1 bilаn D2 kо‘rinishlаrini tаqqоslаsаk, u hоldа D1 ifоdаsidа 15tа о‘zgаruvchi simvоllаri vа 5tа elementаr kоn’yunksiyаlаr qаtnаshаyоtgаnligini, D2 ifоdаsidа esа, 3 tа о‘zgаruvchi simvоllаri vа 2tа elementаr kоn’yunksiyаlаr 9 qаtnаshаyоtgаnligini kо‘rаmiz. Demаk, D2 fоrmulа о‘zgаruvchilаr simvоli (elementаr kоn’yunksiyаlаr) sоnigа nisbаtаn D1 DNShgа qаrаgаndа sоddаrоq fоrmulа hisоblаnаdi. Аgаr D1 vа D2 kо‘rinishdаgi funksiyаni: а) kоntаktli sxemа оrqаli reаlizаtsiyа qilsаk, u hоldа D1 DNShni reаlizаtsiyа qilish uchun 15 tа kоntаkt, D2 DNShni reаlizаtsiyа qilish uchun esа 3 tа kоntаkt tаlаb qilinаdi; b) nоl tаktli funksiоnаl elementlаrdаn yаsаlgаn sxemа оrqаli reаlizаtsiyа qilsаk, u hоldа D1 ni reаlizаtsiyа qilish uchun 21 dоnа funksiоnаl element vа D2 ni reаlizаtsiyа qilish uchun 4 dоnа funksiоnаl element sаrf bо‘lаdi; d) bir tаktli funksiоnаl elementlаrdаn yаsаlgаn kо‘p tаktli tо‘g‘ri sxemа оrqаli reаlizаtsiyа qilish tаlаb qilinsа, u hоldа D1 ni reаlizаtsiyа qilish uchun 33 dоnа funksiоnаl element, shu jumlаdаn, 12 dоnа ushlаb turish elementi vа D2 ni reаlizаtsiyа qilish uchun 6 dоnа, shu jumlаdаn, 2 dоnа ushlаb turish elementi kerаk bо‘lаdi. Demаk, D1 DNSh ni reаlizаtsiyа qilаdigаn sxemаning (qаndаy sxemа bо‘lishidаn qаt’iy nаzаr) tаnnаrxi D2 DNSh ni reаlizаtsiyа qilаdigаn sxemаning tаnnаrxidаn аnchа qimmаt (оrtiq) turаdi. 1.1-misоldаn kо‘rinib turibdiki, mаntiq аlgebrаsining funksiyаlаrini minimаllаshtirish muаmmоsi kо‘pchilik hоllаrdа (jumlаdаn, mаntiqiy qurilmаlаrni sintez qilishdа ) kаttа аmаliy аhаmiyаtgа egаdir. Bu mаsаlаni hаl qilish uchun DNShning “murаkkаbligini” ifоdаlоvchi L(D) sоddаlik indeksi tushunchаsini kiritаmiz. L(D) funksiоnаl uchun quyidаgi аksiоmаlаrni bаjаrilishini tаlаb qilinаdi: I. Mаnfiy emаsligi hаqidаgi аksiоmа. Hаr qаndаy DNSh uchun L(D )≥ 0 10 II. Mоnоtоnligi hаqidаgi аksiоmа (kо‘pаytmаgа nisbаtаn). АgаrD= D1∨ xi σiK1 bо‘lsа, u hоldа L(D )≥ L(D1∨ K 1) (1.7) III. Qаvаriqligi hаqidаgi аksiоmа (qо‘shishgа nisbаtаn). Аgаr D = D 1∨ D 2 vа D 1∧ D 2≡ 0 bо‘lsа, u hоldа L(D )≥ L(D1)+L(D2) . (1.8) IV. Invаriаntlik hаqidаgi аksiоmа (izоmоrfizmgа nisbаtаn). Аgаr R1 DNSh R DNShdаn о‘zgаruvchilаrni qаytа nоmlаsh (аynаn tenglаshtirishsiz) usuli bilаn hоsil qilingаn bо‘lsа, u hоldа L(D1)= L(D ). Diz’yunktiv nоrmаl shаkllаr uchun sоddаlik indekslаri deb аtаluvchi quyidаgi belgilаshlаrni kiritаmiz. 1. Lh(D) – berilgаn D DNShdаgi о‘zgаruvchilаr hаrflаrining sоni. 2. Lk(D) – berilgаn D DNShdаgi elementаr kоn’yunksiyаlаr sоni. 3. Li(D) – berilgаn D DNShdаgi inkоr ( ¬¿¿ ) simvоllаri sоni. Lh(D) , Lk(D) vа Li(D ) indekslаr yuqоridа keltirilgаn аksiоmаlаrni qаnоаtlаntirаdi. 1.2- m i s о l . 1.1- misоldаgi D1 vа D2 DNShlаr berilgаn bо‘lsin. Rаvshаnki, Lh(D1)=15 vа Lh(D2)=3 , yа’ni D2 DNSh о‘zgаruvchilаr hаrflаrining sоni indeksigа nisbаtаn D1 DNShgа qаrаgаndа sоddаrоqdir. D1 vа D2 DNShlаr uchun Lk(D1)=5 vа Lk(D2)= 2 bо‘lgаni uchun D2 DNSh elementаr kоn’yunksiyаlаr sоni indeksigа nisbаtаn hаm D1 DNShgа qаrаgаndа sоddаrоqdir. Li(D1)=6 vа Li(D2)=2 , yа’ni D2 DNSh inkоr simvоllаri sоni indeksi uchun hаm D1 DNShgа nisbаtаn sоddаrоq ekаn. 11 Mа’lumki,{x1,x2,...,xn} о‘zgаruvchilаr tо‘plаmidаn 3n tа elementаr kоn’yunksiyа tuzish mumkin (“bо‘sh” kоn’yunksiyаgа 1 kоnstаntа mоs qilib qо‘yilgаn). Bundаn о‘z nаvbаtidа {x1,x2,...,xn} tо‘plаm elementlаridаn 23n tа diz’yunktiv nоrmаl shаkl tuzish mumkinligi kelib chiqаdi. 1.3- t а ’ r i f . Аgаr f(x1,x2,...,xn) funksiyаni reаlizаtsiyа qiluvchi DNSh L(D) indeksgа nisbаtаn minimаl bо‘lsа, u hоldа bundаy DNSh L gа nisbаtаn minimаl DNSh, Lk indeksgа nisbаtаn minimаl bо‘lgаn DNSh eng qisqа diz’yunktiv nоrmаl shаkl deb аtаlаdi. Bundаn keyin Lh indeksgа nisbаtаn minimаl bо‘lgаn DNShni minimаl diz’yunktiv shаkl deb аtаymiz. 1.3- m i s о l . 1.1- misоldаgi D1 vа D2 DNShlаrni tаhlil qilаmiz. D2 DNSh minimаl DNShdir, chunki ushbu DNSh оrqаli ifоdаlаngаn f(x1,x2,x3) funksiyаning x1,x2,x3 аrgumentlаri muhim (sоxtа emаs) аrgumentlаrdir. Shuning uchun uni uchtаdаn kаm hаrf bilаn ifоdаlаsh mumkin emаs. D2 DNSh eng qisqа DNShdir, chunki ushbu DNSh bilаn ifоdаlаngаn f(x1,x2,x3) funksiyа hаr qаndаy elementаr kоn’yunksiyаdаn fаrq qilаdi. D2 DNSh Li indeksgа nisbаtаn hаm minimаl DNShdir, chunki ushbu DNSh bilаn ifоdаlаngаn f(x1,x2,x3) funksiyа x2 vа x3 о‘zgаruvchilаri bо‘yichа о‘suvchi funksiyа emаs vа demаk, uni ikkitа inkоrdаn kаm inkоr qаtnаshgаn DNSh kо‘rinishidа ifоdаlаsh mumkin. Shundаy qilib, аsоsiy muаmmо mаtemаtik mаntiqning ixtiyоriy f(x1,x2,...,xn) funksiyаsi uchun L indeksgа nisbаtаn minimаl diz’yunktiv nоrmаl shаklni tоpishdаn ibоrаtdir. Bu muаmmо mаtemаtik mаntiq funksiyаlаrini minimаllаshtirish muаmmоsi deb аtаlаdi. 12 1.2. Mantiqiy funksiyalarni diz’yunktiv normal shaklni hosil qilish. 1.4-ta’rif. Elementar mulohazalar yoki ularning inkorlarini kon’yunksiya amali orqali bog’lanishidan hosil bo’lgan ifodaga elementar kon’yunksiya deyiladi. Elementar konyunksiyani formula ko’rinishida ifodalash uchun quyidagi belgilashni kiritamiz: xσ= { x ,agar σ= 1 ¯x ,agar σ= 0 (1.9) Endi, (1.9) ga asosan elementar kon’yunksiyani (e.k.) formula ko’rinishida quyidagicha ifodalash mumkin: K = x1 σ1x2 σ2… xn σn , bunda σi= {0,1 } , i= 1,2 ,… ,n (1.10) 1.4-misol: (((x→ y)→ z)|y)∨ (x↔ z) DNSh ko’rinishiga keltirish. Yechimi: Quyidagi ayniyatlardan foydalanamiz: x→ y= ¯x∨ y (a) x|y= x∧ y= ¯x∨ ¯y (b) x↔ y= ¯x¯y∨ xy (c) x∨ y= ¯x¯y (d) x∨ x= x (e) ¯x∨1=1,x∨1=1 (f) ¯x∨ x= 1,x∧ 1= 1 . (j) Bu formulalarni ketma-ket qo’llab quyidagiga ega bo’lamiz: - (x→ y)→ z= (¯x∨ y)∨ z - ((¯x∨ y)∨ z)|y=((¯x∨ y)∨ z)∨ ¯y=(¯x∨ y)∧ ¯z∨ ¯y= (¯x∨ y)∧ ¯z∨ ¯y= ¯x¯z∨ y¯z∨ ¯y - ¯x¯z∨ y¯z∨ ¯y∨ xz ∨ ¯x¯z= y¯z∨ ¯y∨ xz ∨ ¯x¯z Distributivlik va yutilish qonunini qo’llab: 13 a)x∨ yz =(x∨ y)(x∨ z) d) y¯z∨ ¯y= (¯y∨ y)(¯y∨ ¯z)= ¯y∨ ¯z e) ¯z∨ xz = (¯z∨ x)(¯z∨ z)= ¯z∨ x i) ¯z∨ ¯x¯z= ¯z(¯x∨ 1)= ¯z∧ 1= ¯z j) y¯z∨ ¯y∨ xz ∨ ¯x¯z= ¯y∨ ¯z∨ x . Bizga A(x1,...,xn) formula berilgan bo’lsa uning DNSh sini quyidagi ko’rinishda yozish mumkin: A(x1,...,xn)= ¿i=1 m Ki , bunda σi= {0,1 } , i= 1,2 ,… ,n (1.11) 1.5- ta’rif. Elementar kon’yunksiyada har bir o’zgaruvchi bir martadan ortiq (yoki o’zi, yoki inkori) qatnashmasa, bunday elementar kon’yunksiya to’g’ri elementar kon’yunksiya deyiladi. 1.6-ta’rif. To’g’ri elementar kon’yunksiyada formulaning har bir x1,x2,… ,xn o’zgaruvchisi(yoki o’zi, yoki inkori) ishtirok etsa, bunday elementar kon’yunksiya x1,x2,… ,xn o’zgaruvchilarga nisbattan to’liq elementar kon’yunksiya deyiladi. 1.7- ta’rif. DNSh ifodasida barcha elementar kon’yunksiyalar x1,x2,… ,xn o’zgaruvchilarga nisbattan to’liq va to’g’ri bo’lib, takrorlanuvchilari bo’lmasa mukammal diz’yunktiv normal shakl (MDNSh) deyiladi. А(x1,x2,… ,xn)= ¿ (σ1,σ2,…,σn) А(σ1,σ2,…,σn)=1 x1σ1x2σ2… xnσn (1.12) 0 dan tashqari istalgan А(x1,x2,… ,xn) formulani mukammal diz’yunktiv normal shaklga keltirish mumkin. 1.5-misol: (x↔ y)∨ (y↔ z) MDNSh ko’rinishiga keltiring Yechimi: 1-usul (jadval usuli): MDNSh ifodasini aniqlashning jadval usuli quydagicha: 14 1. berilgan formulaning chinlik jadvali tuziladi (1.2-jadval); 2. chinlik jadvalidan funksiyaning 1 ga teng bo’lgan qiymatlari to’plamini(σ1,σ2,… ,σn) ajratib olinadi; 3. har bir ajratib olingan qiymatlari to’plamiga mos elementar kon’yunksiyalar tuziladi; 4. hosil bo’lgan elementar kon’yunksiyalar diz’yunksiya amali bilan bog’lanadi. 15 1.2-jadvalx y z x⇔ y y⇔ z (x⇔ y)∨ (y⇔ z) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 (x↔ y)∨(y↔ z)= = x0y0z0∨ x0y0z1∨ x0y1z1∨ x1y0z0∨ x1y1z0∨ x1y1z (1.9) formulaga ko’ra quyidagini hosil qilamiz: (x↔ y)∨ (y↔ z)= ¯x¯y¯z∨ ¯x¯yz∨ ¯x yz ∨ x¯y¯z∨ xy { ¯z∨ xyz ¿ 2-usul (analitik usul): ( с ) formulani qo’llab quyidagiga ega bo’lamiz: (x↔ y)∨(y↔ z)= xy ∨¯x¯y∨ yz ∨ ¯y¯z endi (o) formuladan foydalanib MDNSh ga keltiramiz: xy (z∨ ¯z)∨ ¯x¯y(z∨ ¯z)∨ yz (x∨ ¯x)∨ ¯y¯z(x∨ ¯x)= =xyz∨xy { ¯z∨¯x¯yz∨¯x¯y¯z∨xyz∨¯xyz∨x¯y¯z∨¯x¯y¯z=¿=xyz∨xy { ¯z∨¯x¯yz∨¯x¯y¯z∨¯xyz∨x¯y¯z¿¿¿ 1.3. Kon’yunktiv normal shaklni hosil qilish. 1.8-ta’rif. Elementar mulohazalar yoki ularning inkorlarini diz’yunksiya amali orqali bog’lanishidan hosil bo’lgan ifodaga elementar diz’yunksiya deyiladi. D = x1 σ1∨ x2 σ2¿… ∨ xn σn (1.13) 16 1.9-ta’rif. Elementar diz’yunksiyalarni kon’yunksiya amali orqali bog’lanishidan hosil bo’lgan ifodaga kon’yunktiv normal shakli (KNSh) deyiladi. A(x1,...,xn)= ¿i=1 m Di (1.14) 1.6-misol: (x→ y)∨ (x↔ z) KNSh ko’rinishiga keltiring Yechimi: (a) va ( с ) formulalardan foydalanib berilgan formulani quyidagi ko’rinishga keltiramiz: (x→ y)∨ (x↔ z)= ¯x∨ y∨ xz ∨ ¯x¯z Yutilish q o id a sig a k o’ r a, ¯x∨ ¯x¯z= ¯x(1∨ ¯z) v a 1∨ ¯z= 1,¯x∧ 1= ¯x ek a nligini his o bg a o lib quyid a gig a eg a b o’ l a miz ¯x∨ y∨ xz . Distrubutivlik qoidasidan foydalanib shakl almashtiramiz ¯x∨ xz = (¯x∨ x)(¯x∨ z)= 1∧ (¯x∨ z)= ¯x∨ z n a tij a d a (x→ y)∨ (x↔ z)= ¯x∨ y∨ z . 1.10- t a’ rif . Element a r diz ’ yunksiy a d a h a r bir o’ zg a ruvchi bir m a rt a d a n o rtiq ( y o ki o’ zi , y o ki ink o ri ) q a tn a shm a s a, bund a y element a r diz ’ yunksiy a t o’ g ’ ri element a r diz ’ yunksiy a deyil a di . 1.11- t a’ rif . T o’ g ’ ri element a r diz ’ yunksiy a d a funksiy a ning h a r bir x1,x2,… ,xn o’ zg a ruvchisi ishtir o k ets a, bund a y element a r diz ’ yunksiy a x1,x2,… ,xn o’ zg a ruvchil a rg a nisb a tt a n t o’ liq element a r diz ’ yunksiy a deyil a di . 1.12- t a’ rif . KNSh if o d a sid a b a rch a element a r diz ’ yunksiy a l a r x1,x2,… ,xn o’ zg a ruvchil a rg a nisb a tt a n t o’ liq v a t o’ g ’ ri b o’ lib , t a kr o rl a nuvchil a ri b o’ lm a s a muk a mm a l k o n ’ yunktiv n o rm a l sh a kl ( MKNSh ) deyil a di . А(x1,x2,… ,xn)= ¿ (σ1,σ2,…,σn) А(σ1,σ2,…,σn)=0 (x1σ1¿x2σ2¿… ∨ xnσn) (1.15) 17 1 konstantadan tashqari istalgan А(x1,x2,… ,xn) formulani mukammal kon’yunktiv normal shaklga keltirish mumkin. 1.7-misol: (x+ y)(z→ x) MKNSh ko’rinishiga keltiring Yechimi: 1 usul (jadval usuli): MKNSh ifodasini aniqlashning jadval usuli quydagicha: 1. berilgan formulaning chinlik jadvali tuziladi (1.3-jadval); 2. chinlik jadvalidan formulaning 0 ga teng bo’lgan qiymatlari to’plamini (σ1,σ2,… ,σn) ajratib olinadi; 3. (1.14) ga ko’ra har bir ajratib olingan qiymatlari to’plamiga mos elementar diz’yunksiyalar tuziladi; 4. hosil bo’lgan elementar diz’yunksiyalar kon’yunksiya amali bilan bog’lanadi. 1.3-jadval x y z x+y z⇒ x (x+ y)(z⇒ x) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 (x+y)(z→ x)= = (x0∨ y0∨ z0)(x0∨ y0∨ z1)(x0∨ y1∨ z1)(x1∨ y1∨ z0)(x1∨ y1∨ z1)= = (x∨ y∨ z)(x∨ y∨ ¯z)(x∨ ¯y∨ ¯z)(¯x∨ ¯y∨ z)(¯x∨ ¯y∨ ¯z) . 2- usul ( analitik usul ) : 18 (x+y)(z→ x)= (¯xy∨ ¯yx)(¯z∨ x)= = (¯x∨ ¯y)(x∨ y)(¯x∨ x)(¯y∨ y)(¯z∨ x)= = (¯x∨ ¯y)(x∨ y)(x∨ ¯z)= = (¯x∨ ¯y∨ z¯z)(x∨ y∨ z¯z)(x∨ ¯z∨ y¯y)= =(¯x∨ ¯y∨ z)(¯x∨ ¯y∨¯z)(x∨ y∨ z)(x∨ y∨¯z)(x∨ y∨¯z)(x∨ ¯y∨¯z)= = (¯x∨ ¯y∨ z)(¯x∨ ¯y∨ ¯z)(x∨ y∨ z)(x∨ y∨ ¯z)(x∨ ¯y∨ ¯z). Muk a mm a l dizyunktiv n o rm a l sh a kl ( MDNSH ) v a muk a mm a l k o nyunktiv n o rm a l sh a kl ( MKNSH ) quyid a gi xususiy a tl a rg a eg a: 1. Tarkibida ikkita bir xil elementar kon’yunksiyalar(elementar diz’yunksiyalar) mavjud bo’lmaydi. 2. Birorta ham elementar kon’yunksiyada (elementar diz’yunksiyada) ikkita bir xil o’zgaruvchi qatnashmaydi. 3. Elementar kon’yunksiyada (elementar diz’yunksiyada) birorta o’zgaruvchi o’zining inkori bilan birgalikda qatnashmaydi. 4. To’liq elementar kon’yunksiyada (elementar diz’yunksiyada) formulaga kiruvchi barcha xi o’zgaruvchi, yoki uning inkori bo’lgan xi o’zgaruvchi qatnashadi. 1.4. Mulohazalar algebrasi formulasini qisqartir i lgan dizyunktiv normal shaklni hosil qilish usullari. O’ziga ekvivalent bo’lgan barcha diz’yunktiv normal shakllarga nisbattan eng kam belgilarga ega bo’lgan diz’yunktiv normal shakl minimal diz’yunktiv normal shakl deyiladi. Agar DNShda belgilar sonini aniqlashda xi simvol formulada ikki marta qatnashsa, ikki marta ham sanaladi. To’g’ri elementar konyunksiyaning rangi deb unga kiruvch i belgilar soniga aytiladi. 19 Har bir А(x1,x2,… ,xn) formulaga uning chi n lik to’plami deb ataluvchi N f= {(α1,α2,… ,αn)|А (α1,α2,… ,αn)= 1} qism to’plam mos keladi. Bizga А= K 1∨ K 2∨ … ∨ K n DNSh berilgan bo’lsin, bu yerda Ki - elementar konyunksiyalar. 1.13-ta’rif. r -rangli K elementar kon’yunksiyaga mos bo’lgan NK qism to’plam r rangli interval deb nomlanadi. А formulaning har bir DNSh ko’rinishiga N K1,NK2,… ,NKn intervallar bi l an berilgan NKi⊆N f shartni qanoatlantiruvchi N f= NK1∪ N K2¿… ∪ N Kn qoplama mos keladi. 1.14-ta’rif. Bul funksiyasi uchun N K⊂N K'⊆N f shartni bajaruvchi interval mavjud bo’lmasa, N K⊆ N f interval maksimal interval deb ataladi. Agar NK1,NK2,… ,NKm intervallar Nf to’plamning barcha maksimal intervallari bo’lsa, u holda N f= NK1∪ N K2¿… ∪ N Km bo’ladi. 1.14-ta’rif. f funksiyaning Nf qism to’plami qobig’iga mos bo’lgan barcha maksimal intervallarga mos tuzilgan K1∨K2∨… ∨ Km DNSh, qisqartirilgan DNSh deyiladi. Istalgan Bul f funksiyasini qisqartirilgan DNSh sini hosil qilish mumkin. Buning uchun bir qancha algoritmlar mavjud. Jadval usulida qisqartirilgan DNSh ni aniqlash algoritmini ko’rib chiqamiz: 1.8-misol. f(x1,x2,x3)=¯x2x3∨ ¯x1x3∨ x1x2 funksiyaning qisqartirilgan DNSh sini hosil qilish. 20 0 1x 3x 2x  1,1,0  1,1,1  0,1,1  1,0,1  1,0,0 1.1-shakl. Berilgan shaklga asosan chinlik to’plamini aniqlab olamiz N f={(1,1,0 );(1,1,1 );(0,0,1 );(1,0,1 );(0,1,1 )} . Bunda, NK1={(0,0,1 );(0,1,1 );(1,1,1 );(1,0,1 )} va NK2={(1,1,0 );(1,1,1 )} -intervallar maksimal intervallardir. Shuning uchun ta’rifga ko’ra f= K 1∨ K2= x3∨ x1x2 - qisqartirilgan DNSh. Bleyk usul: 1) Berilgan funksiyani DNSh ko’rinishiga keltiramiz; 2) xK 1∨ ¯xK2= xK 1∨ ¯xK2∨ K1K2 umumlashgan birlashtirish qoidasini qo’llaymiz; 3) K1∨K1K2= K1 yutilish qonunini qo’llaymiz. 1.9-misol. f(x1,x2,x3)= x1x2∨ ¯x2x3∨ ¯x1x3 funksiyani qisqartirilgan DNSh ga keltirish. Umumlashgan birlashtirish qonunini qo’llab: x1x2∨ ¯x1x3∨ x2x3∨¯x2x3∨ x3∨ x1x3 ni hosil qilamiz. Yutilish qonunini qo’llab x1x2∨ x3 ga ega bo’lamiz. Nelson usuli : 1) Berilgan funksiyani KNSh ga keltiramiz; 2) distrubutivlik qonunini qo’llab qavslarni ochamiz; 3) yutilish qonunini qo’llaymiz. 21 1.10-misol. f(x,y,z)= (x∨ y)(¯x∨ y∨ z) formulaning qisqartirilgan DNSh sini hosil qilish. Formulaga distrubutivlik qonunini qo’llab qavslarni ochgach x¯x∨ xy ∨ xz ∨ y¯x∨ yy ∨ yz ko’rinishga keladi. x¯x=0 , yy = y ekanligidan, xy ∨ xz ∨ y¯z∨ y∨ yz ga ega bo’lamiz. Yutilish qoidasini qo’llab qisqartirilgan DNShga ega bo’lamiz: xz ∨ y Mak-Klaski usuli . 1.11-misol. Qiymatlar vektori ko’rinishda berilgan f(x,y,z,u)= (1001100111010011 ) funksiyani chinlik jadvalini quyidagi ko’rinishda yozish mumkin: xyzu f(x,y,z,u) 1 0000 1 2 0001 0 3 0010 0 4 0011 1 5 0100 1 6 0101 0 7 0110 0 8 0111 1 9 1000 1 10 1001 1 11 1010 0 12 1011 1 13 1100 0 14 1101 0 15 1110 1 16 1111 1 22 Funksiyani qisqartirilgan DNSh sini hosil qilish uchun quyidagi qadamlarni bajaramiz: 1. funksiyaning f(α1,α2,α3,α4)=1 qiymatlari to’plamini ajratib olamiz; 2. qiymatlar satridagi birlar soni bo’yicha guruhlab tartiblab yozamiz; 3. oddiy birlashtirish xK ∨ ¯xK = K va K1∨K1K2= K1 yutilish qoidalarini qo’llaymiz. a) funksiyaning birga teng bo’lgan qiymatlari satri: 0000 0011 0100 0111 1000 1001 1011 1110 1111 b) qiymatlar satrini tartiblash c) yutilish qoidasini qo’llash: 1. 0000 0-00 (1,2) 2. 0100 -000 (1,3) 3. 1000 100- (3,5) 4. 0011 0-11 (4,6) 5. 1001 -011 (4,7) 6. 0111 10-1 (5,7) 7. 1011 -111 (6,9) 23 8. 1110 1-11 (7,9) 9. 1111 111- (8,9) d) “–“ ga nisbatan tartiblab va birlashtirish: 1. -000 -000 -000 2. -011 --11 (2,3) 0-00 3 . -111 0-00 (5,6) birlashtiramiz 10-1 4. 0-00 --11 100- 5. 0-11 10-1 111- 6 1-11 100- --11 7. 10-1 111- 8. 100- 9. 111- Hosil bo’lgan intervallarda 1 ni o’zgaruvchiga va 0 ni o’zgaruvchi inkoriga almashtirsak DNSh=yzu∨ xzu∨ xyu∨ xyz∨ xyz ∨ zu hosil bo’ladi. Maksimal intervallar: Nk1={(0,0,0,0 ),(1,0,0,0 )},.k1= yzu Nk2={(0,0,0,0 ),(0,1,0,0 )},.k2= xzu Nk3={(1,0,0,1 ),(1,0,1,1 )},.k3= xyu Nk4={(1,0,0,0 ),(1,0,0,1 )},.k4=xyz Nk5={(1,1,1,0 ),(1,1,1,1 )},.k5=xyz Nk6={(0,0,1,1 ),(0,1,1,1 ),(1,0,1,1 ),(1,1,1,1 )},.k6=zu 1.4. Mulohazalar algebrasi formulasini minimal dizyunktiv normal shaklni hosil qilish usullari. Minimal DNSh, qisqartirilgan DNSh dan ayrim elementar konyunksiyalarni chetlatish yo’li bilan hosil qilinadi. 24 Mantiq algebrasi funksiyasi f(x1,x2,...,xn) ni minimallashtirish (minimizatsiyalash) muammosiga ekvivalent bo‘lgan qoplamalar haqidagi geometrik masala quyidagicha qo‘yiladi. Berilgan N f= Nk1∪ N k2¿...∪ Nks to‘plamning Nk1,Nk2,...,Nks ( Nkj⊆N f , j=1,2 ,...,s ) intervallardan iborat shunday qobig‘ini topish kerakki, uning r rangi eng kichik bo‘lsin, ya’ni qaralayotgan masala uchun (1.16) ni topish masalasiga keladi. to‘plamning Nk1,Nk2,Nk3,Nk4,Nk5,Nk6 maksimal intervallardan iborat bo‘lgan qoplamadan ayrim maksimal intervallarni chetlashtirganimizda, qolgan qismi yana ning qobig‘i bo‘ladimi yoki yo‘qmi degan savolga javob berish lozim. 1 . 1 5 - t a ’ r i f . Agar Nk1,Nk2,...,Nkm maksimal intervallardan iborat qobiq uning tarkibidan istalgan maksimal intervalni (Nkj,j=1,2 ,...,m) chetlashtirganimizda, qolgan qismi ning qobig‘i bo‘la olmasa, u holda bu qobiq to‘plamning keltirilmaydigan qoplami deb ataladi. 1 . 1 3 - t a ’ r i f . to‘plamning keltirilmaydigan qobig‘iga mos bo‘lgan DNSh tupikli diz’yunktiv normal shakl deb ataladi (geometrik ma’noda). Ixtiyoriy minimal DNSh tupikli DNSh bo’ladi. Bul funksiyalarini minimallashtirish bosqichlari quyidagicha: a) barcha maksimal intervallar ajratilib qisqartirilgan DNSh tuziladi; b) barcha tupikli DNShlar aniqlanadi ; c) tupikli DNShlar orasidan minimal DNSh ajratib olinadi. Tupikli DNShlarni qurish algoritmi: 1. А(x1,x2,… ,xn) formulani qisqartirilgan DNSh shakliga keltiramiz; 2. Nf chinlik to’plamidagi har bir aj ( j=1,2 ,… ,K ) uchun Kij(aj)=1 25 (i=1,2 ,… ,t ) bo’lgan Kij,… ,Ktj elementar kon’yunksiyalarni ajratamiz; 3. aniqlangan Kij,… ,Ktj elementar kon’yunksiyalardan quyidagicha ifodani tuzib olamiz: (K11∨ K12∨… ∨ K1t)(K21∨ K22∨… ∨ K2t)… (K K1∨ KK2∨… ∨ KKt) ( 1.17 ) 4. (1.17) if o d a g a distrubutivlik v a yutilish q o nunini q o’ ll a sh n a tij a sid a quyid a gig a eg a b o’ l a miz ¿Ki1Ki2… Kim 5. hosil bo’lgan har bir Ki1∨ Ki2∨… ∨ Kim DNSh f(x1,x2,… ,xn) funksiyaning tupikli DNSh si bo’ladi. 1.12-misol. А (x,y,z)= (01111110 ) chinlik to’plami bilan berilgan formulaning barcha tupikli DNSh larini topamiz. Nelson usulini qo’llab qisqartirilgan DNSh ko’rinishini topamiz. Buning uchun MKNSh ko’rinishiga keltirib olamiz: (x∨ y∨ z)(¯x∨ ¯y∨ ¯z) . Distrubutivlik qonunini qo’llash orqali quyidagiga ega bo’lamiz: x¯y∨ x¯z∨ ¯xy∨ y¯z∨ z¯x∨ z¯y . K1= x¯y , K 2= x¯z , K 3= ¯xy , K4= y¯z , K5= z¯x , K6= z¯y belgilash kiritib olamiz. N f= {(0,0,1 );(0,1,0 );(0,1,1 );(1,0,0 );(1,0,1 );(1,1,0 )} . (1.17) ko’rinishdagi ifodani tuzib olamiz va distributivlik va yutulish qoidalarini qo’llaymiz: (K5∨ K6)(K3∨ K4)(K3∨ K5)(K1∨ K2)(K1∨ K6)(K2∨ K4)= =(K5∨K3K6)(K4∨K2K3)(K1∨K2K6)= ¿K1K4K5∨K1K2K3K5∨¿K1K3K4K6∨K1K2K3K6∨ ¿K2K4K5K6∨K2K3K5K6∨K2K3K4K6∨¿¿ ¿K2K3K6=K1K4K5∨K1K2K3K5∨K1K3K4K6∨K1K2K3K6∨K2K4K5K6∨K2K3K6 Shunday qilib, А(x,y,z) formula 6 ta tupikli DNSh ga ega D1= K1∨ K4∨ K5=x¯y∨ y¯z∨z¯x 26 D2= K1∨ K2∨ K3∨K5= x¯y∨ x¯z∨¯xy∨ z¯x D3=K1∨ K2∨K4∨ K6=x¯y∨¯xy∨ y¯z∨ z¯y D4= K1∨K2∨K3∨K6=x¯y∨x¯z∨¯xy∨z¯y D5= K2∨ K4∨ K5∨ K6= x¯z∨ y¯z∨ z¯x∨ z¯y D6= K2∨ K3∨ K6= x¯z∨ ¯xy∨ z¯y Uladan ikkitasi D1 va D6 lar eng kam belgiga ega bo’lgani uchun ta’rifga ko’ra minimal DNSh. Minimal DNSh ni topishning implikantlar matritsasi (Mak-Klaski) usuli. f(x1,x2,… ,xn) Bul funksiyasi uchun f= K1∨ K2∨… ∨ Kt qisqartirilgan DNSh berilgan bo’lsin. Bu funksiya uchun implikantlar matritsasini tuzib olamiz, ushbu matritsaning satrlariga K1,K2,… ,Kt elementar kon’yunksiyalar, ustunlariga N f= {~a1,… ~ap} qiymatlarini qo’yamiz. Har bir Ki uchun Kij(aj)=1 ni qanoatlantiruvchi ~aj qiymatlar to’plamini aniqlaymiz. Matrisada ularning kesishish katagiga + belgisini qo’yamiz. 1.13-misol . А (x,y,z)= (x∨ y∨ z)(¯x∨ ¯y∨ z) formulani minimal DNSh ko’rinishiga keltirish. 27 ~a1 ~a2 … ~aj … ~ap K1 K2 … Ki + … Kt Berilgan misolga Nelson usulini qo’llab quyidagi qisqartirilgan DNSh ni hosil qilamiz:x¯y∨ x¯z∨ ¯xy∨ y¯z∨ z¯x∨ z¯y Endi implikantlar matritsasini tuzib olamiz: Tupikli DNSh qurishning 4-6 bosqichlarini qo’llab ikkita minimal DNSh ga ega bolamiz: x¯y∨ y¯z∨ z¯x , x¯z∨¯xy∨ z¯y . 1 . 1 4 - m i s o l . N А2={(0,0,0 ),(0,0,1 ),(1,0,1 ),(1,1,1 ),(1,1,0 ),(0,1,0 )} to‘plamga mos А2(x1,x2,x3) formulaning MKNShni 0 ga teng bo’lgan qiymatlaridan foydalanib yozamiz: А2(x1,x2,x3)=(x1∨ x2∨ x3)(x1∨ x2∨ x3) . Algoritmning 2-va 3-qadamlarini bajaramiz: (x1∨ x2∨ x3)(x1∨ x2∨ x3)= x1x1∨ x1x2∨ x1x3∨ x1x2∨ x2x2 ¿x2x3∨ x1x3∨ x2x3∨ x3x3= x1x2∨ x1x3∨ x1x2∨ x2x3∨ x1x3∨ x2x3 . Q is qa rtirilg a n DNSh q uyid a gi k o‘ rinishd a b o‘ l a di : Ds(f2)x1x2∨ x1x3∨ x1x2∨ x2x3∨ x1x3∨ x2x3 . 1 . 1 5 - m i s o l . Quyid a gi f o rmul a berilg a n b o‘ lsin : А1(x1,x2,x3)= x1x2x3∨ x1x2x3∨ x1x2x3∨ x1x2x3∨ x1x2x3∨ x1x2x3 . Bu formulaga N А1={(0,0,0 ),(0,1,1 ),(0,1,0 ),(1,0,1 ),(1,1,0 ),(1,1,1 )} 28 (0,0,1 ) (0,1,0 ) (0,1,1 ) (1,0,0 ) (1,0,1 ) (1,1,0 ) x¯y + + x¯z + + ¯xy + + y¯z + + z¯x + + z¯y + + to‘plam mos keladi. Formulaning MKNSh ko‘rinishif1(x1,x2,x3)=(x1∨ x2∨ x3)(x1∨ x2∨ x3) . Algoritmning 2-va 3-qadamlarini bajaramiz: (x1∨ x2∨ x3)(x1∨ x2∨ x3)= x1x1∨ x1x2∨ x1x3∨ x1x2∨ ¿¿ ¿x2x2∨ x2x3∨ x1x3∨ x2x3∨ x3x3= = x1∨ x1x2∨ x1x3∨ x1x2∨ x2∨ x2x3∨ x1x3∨ x2x3= = x1∨ x1x3∨ x2∨ x2x3∨ x1x3∨ x2x3= = x1∨ x2∨ x1x3∨ x2x3= x1∨ x2 . Dem a k , f o rmul a ning q is qa rtirilg a n v a minim a l DNSh si q uyid a gich a b o‘ l a di : D s(f1)= x1∨ x2 . I - Bobning asosiy xulosalari:  mantiq algebrasi funksiyalarini minimallashtirish muammosining dolzarbligi va muammoni hal qilish mazmuni yoritildi;  diz’yunktiv normal shaklni soddalashtirish algoritmi hamda minimallashtirish masalasining geometrik tarzda qo‘yilishi ko’rsatildi;  qisqartirilgan diz’yunktiv normal shaklni hosil qilish usullari misollar asosida bayon etildi;  tupikli diz’yunktiv normal shakllarni hosil va minimal DNSh ni aniqlash usullari misollar asosida bayon etildi. 29 II-BOB. TO’LIQ ANIQLANMAGAN M A NTIQIY FUNKTSIY A NI MINIM A LL A SHTIRISH MUAMMOSI . 2.1. Bul funktsiyalarning metrik o’lchamlari [5]. Mantiqiy funktsiyalarni ifodalanishining mukammal normal shakllari mantiqiy funktsiyalarning aniq ifodasini beradi, lekin ba'zida ular juda murakkab. Shuning uchun, MDNSh yoki MKNSh sifatida ifodalangan mantiqiy funktsiyalar uchun minimallashtirish muammosi paydo bo'ladi. Mantiqiy funktsiyaning soddalik (yoki murakkablik) indeksi L(R) barcha DNFlar to'plamida aniqlangan va quyidagi xususiyatlarga javob beradigan funktsiyadir: 1) Manfiymas lik xususiyati: ∀ R= D NSh L(R)>0 ; 2) Monotonlik xususiyati: agar R= R'∨ xi σiK ' , bo’lsa, bu yerda K' - elementar konyuksiya, L(R)≥ L(R'∨ K ') bo’ladi. 3) Qavariq lik xususiyati: R= R1∨ R2,R1R2= 0⇒ L(R)≤ L(R1)+L(R2) 4) Invariantlik xususiyati: agar DN Sh = R1 DN Sh = R2 dan o'zgaruvchilar- ni q a yt a n o ml a sh orqali h o sil qiling a n bo'lsa, u holda L(R1)= L(R2) . Misollar. 1) LБ(R) - R yozuvida uchraydigan belgilar soni. Belgi deganda o'zgaruvchining belgisi yoki uning inkori tushuniladi, agar x1 o'zgaruvchisi formulaga m marta kiritilgan bo'lsa, unda x1 formulada m marta borligini bildiradi. Misol uchun, ifodada x1x2x3∨ x2x3 o'zgaruvchilar soni 3 ga, belgilar soni esa 5 ga teng, ya'ni belgilar soni o'zgaruvchilarning ishtiroki soniga teng. 2) LK(R) - R tarkibiga kiruvchi elementar konyunksiya soni ga teng. 30 3) L0(R) - R yozuvida uchraydigan inkor belgilar soni. Ko'rsatilgan indekslarning har biri yuqorida sanab o'tilgan xususiyatlarni qanoatlantiradi. Misol. Agar f(x1,x2,x3)=(11000101 ) funksiya vektori ko’rinishda berilgan bo'lsin. Shunda u MDNSh shaklda yozilishi mumkin. f(x1,x2,x3)= R1= x1x2x3∨ x1x2x3∨ x1x2x3∨ x1x2x3 Bu funktsiyani soddalashtirish mumkin f= x1x2(x3∨ x3)∨ x1x3(x2∨ x2)= x1x2∨ x1x3= R2 Keling , R1 va R2 uchun soddalashtirish indekslarini hisoblaylik. LБ(R1)=12 , LБ(R2)= 4 ; LK(R1)= 4 , LK(R2)= 2 ; L0(R1)=6 , L0(R2)= 2 . Demak, R2 barcha uchta indekslik ko’rsatkichlari uchun R1 dan soddaroqdir . Berilgan mantiqiy funktsiyani minimallashtirish vazifasi uni eng kichik soddalik indeksiga ega bo'lgan dizyunktiv (yoki konyunktiv) normal shaklda ifodalashdan iborat. Soddalik indeksi sifatida eng ko'p qo’llaniladigan LБ(R) indeksidir . 2.2. Bleyk usulida qisqartirilgan DNSh ni hosil qilish usuli [3]. Qisqartirilgan DNSh, MDNSh ga qaraganda kamroq belgilarni o'z ichiga oladigan ko’rinishdir. Agar MDNSh da barcha mumkin bo'lgan birlashtirish amallari va keyin barcha mumkin bo'lgan yutilish amallari bajarilsa, natijada qisqartirilgan DNSh ko'rinishiga ega bo'ladi. Bleyk usuli umumlashgan birlashtirish va yutilish amallariga asoslangan. Yutilish amallari: x1(x1∨ x2)= x1 , x1∨ x1x2= x1 x1(x1∨ x2)= x1x2 , x1∨ x1x2= x1∨ x2 31 x1(x1∨ x2)= x1x2 , x1∨ x1x2= x1∨ x2 x1(x1∨ x2)= x1 x1∨ x1x2= x1 Ikkinchi ustundagi formulalar qo’shmalik prinsipidan foydalangan holda birinchi ustundagi formulalardan hosil qilinadi. Birlashtirish amallari: xy ∨ xy= x . Umumlashgan birlashtirish amallari: xz ∨ yz∨ xy = xz ∨ yz : Misol. Bleyk usuli yordamida qisqartirilgan DNSh hosil qilish: 1) f= x1x2∨ x1x3∨ x2x3 . f= x1x2∨ x1x3∨ x2x3=|x1x2∨ x1x3= x1x2∨ x1x3∨ x2x3, x2x3∨ x2x3= x2x3∨ x2x3∨ x3(umumlashgan birlashtirish amaliga muvofiq |= x1x2∨ x1x3∨ x2x3∨ x2x3∨ x3= ¿x1x2∨ x1x3∨ x3∨ x2x3∨ x3∨ x2x3∨ x3= ¿x1x2∨ x3(x1∨ 1)∨ x3(x2∨ 1)∨ x3(x2∨ 1)= x1x2∨ x3 Bull funktsiyalarni Kvayna-Mak-klaski usuli bilan minimallashtirish. Funksiya f(x1,x2,...,xn) J(xi1,xi2,...,xik) implikanti x1,x2,...,xn o’zgaruvchilar va ularning inkorlari konyunksiyasidan iborat bo’lib, quyidagi xususiyatlarga ega: 1) Agar x1,x2,...,xn larning ba’zi qiymat to'plamida J implikant 1 qiymatini qabul qilsa, u holda f ham 1 qiymatni qabul qiladi. 2) Agar J dan kamida bitta o’zgaruvchi chiqarib tashlansa 1) xususiyat bajarilmaydi. 2.1. Misol. f(x1,x2,x3)= ¿(0,1,3 )= x1 x2 x3∨ x1 x2x3∨ x1x2x3 bo’lsa u (0,0,0), (0,0,1), (0,1,1) to'plamlarda f= 1 bo’ladi . Masalan, J= x1 x2 bo’lsa (0,0,0), (0,0,1) qiymatlar to'plamida J=1 bo’ladi. Ushbu to'plamda f=1 , ya'ni. 1) shart bajariladi. 32 Faraz qilaylik α qiymatlar to’plamida f= 1 bo’lsin. Agar α da J=1 bo’lsa, u holda imlikanta funksiyaning ushbu chinlik to’plamini qoplaydi deyiladi. Qisqartirilgan DNSh - f funktsiyaning barcha implikantlarining dizunksiyasidan iborat. Darhaqiqat, barcha implikantlarning dizyunksiyasi to'liq implikantalar tizimidan funksiya 1 ga teng bo'lgan to'plamlarda 1 ga teng, (implikantning ta'rifiga ko'ra J (α)= 1⇒ f(α)= 1 ) va funktsiya nolga teng bo'lgan to'plamlarda nolga teng. ya'ni, qisqartirilgan DNSh qiymati xususiyatlari va f ning qiymatlari xususiyati bilan bir xil. Qisqartirilgan DNSh, MDNSh ga qaraganda kamroq belgilarni o'z ichiga oladi. Biroq ko'p hollarda, ba'zi implikantlar boshqa implikantlarning dizyunksiyalari tomonidan yutilishi mumkinligi sababli belgilar sonini yanada kamaytirish mumkin. Funksiyaning implikantalar to’plami keltirilgan deyiladi, agarda undan birorta imlikantani chetlatish mumkin bo’lmasa. Tupikli DNSh – deb funksiyaning keltirilgan implikantalar to’plami dizyunksiyasiga aytiladi. Tupikli DNSh - bu qisqartirilgan DNSh dan olingan ifoda bo'lib, uni DNSh ko’rinishda boshqa soddalashtirib bo'lmaydi. Minimal DNSh - bu eng kam sonli belgilardan tashkil topgan tupikli DNSh. Qisqartirilgan DNSh ning bir nechta tupikli DNSh va bir nechta minimal DNSh si bo'lishi mumkin. Berilgan funksiyani minimallashtirish jarayonini quyidagi sxema ko’rinishda ifodalash mumkin: 33 2.2-misol.f= ¿(2,3,9 ,10 ,11 ,12 ,13 ,14 )x1x2x3x4= K2¿K 3¿K 9¿...∨ K14= = x1 x2 x3x4∨ x1 x2 x3x4∨ ...= R. f= ¿(2,3 ,11 8,12 8,13 8,14 8,15 8,16 8)x1x2x3x4 LБ= 24 Qisqartirilgan DNSh hosil qilish ax ∨ a x= a birlashtirish qonuniga asoslanadi. Berilgan funksiyani qisqartirilgan DNSh sini hosil qilish uchun, uning chinlik to’plamini birlar soni o’sib borish tartibida joylashtiramiz. Bunda, faqat birlar soni bittaga farq qiladigan qiymatlarga mos konyunksiyalar uchun birlashtirish amalini qo’llash mumkin. I-bosqich. Izoh: Birlashtirish amalida qo’llanilmagan qiymatlar J imlikanta sifatida belgilangan, * bilan birlashtirish amali qo’llanilgan qiymatlar belgilangan. 2.1-jadval 34 Quyidagi 2.1-jadvalda, qisqartirilgan DNSh hosil qilish bosqichlari tasvirlangan. 1-ustunda bosqichlar belgisi, 2-ustunda tartiblangan chinlik to’plami, 3-ustunda ikkilik qiymatlarning 8 lik va 10 lik kodi, 4-ustunda chinlik to’plamidagi birlashtirish amali qo’llanilgan juftliklar, 5,7-ustunlarda birlashtirish natijasi, 6,8-ustunlarda hosil bo’lgan imlikantalar yozilgan. Hosil qilingan imlikantalar:J1= x2x3 , J2= x1x2x4 , J3= x1x3x4 , J4= x1x3x4 , J5= x1x2x3 , J6= x1x2x4 . Qisqartirilgan DNSh f= J1∨ J2∨ J3∨ J4∨ J5∨ J6 , uning uzunligi 17 belgidan iborat. 35N Guruh Lar Setlar N O’rnatish 1 0010 * 2 * 2,3 001– * 2,3, .10,11 –01– J1 2,10 –010 * 2,10, 3,11 –01– J1 2 0011 * 3 * 3,11 –011 * 1001 * ( 118 ) 9 * 9,11 10–1 J2 1010 * (12 8) 10 * 9,13 1–01 J3 1100 * ( 148 )12 * 10,11 101– * 10,14 1–10 J4 12,13 110– J5 12,14 11–0 J6 3 1011 * ( 138 )11 * 1101 * ( 158 ) 13 * 1110 * (16 8) 14 * 2.2-shakl 2.2-shaklda implikantalar va birlashtirilgan qiymatlar to'plamlari ko'rsatilgan. II- bosqich - tupikli DNSh ni hosil qilish. Buning uchun implikantalar jadvalini yaratishimiz kerak. Bu jadvalning satrlarida funksiya implikantlari, ustunlari esa funksiya chinlik to’plami yoziladi. Har bir implikant MDNSh dagi ba'zi bir qismlarni ifodalab, chinlik to’plamining ba’zi elementlarini qoplaydi. Implikant yoziladigan qator va implikant qismi bo'lgan tegishli qiymatlar ustunlari kesishmasiga ,, + ” qo'yiladi. Tupikli DNShlar – chinlik to’plamining barcha elementlarini qamrab oluvchi implikantlarning dizyunktsiyalari, ya'ni, jadvalda barcha ustunlarda kamida bitta plus belgisi bo’lgan qatorlarni tanlashingiz kerak. Ko'rinib turibdiki, tanlangan qatorlar tizimi, albatta, ustunda yagona bo'lgan plyuslarni o'z ichiga olgan qatorlarni o'z ichiga olishi kerak. Bunday satrlar bazis deyiladi . Asosiy qatorlardagi oddiy implikantalar ko'rib chiqilayotgan funksiyaning o'zagini tashkil qiladi. Ushbu implikantalarga mos keladigan qatorlardagi plyuslarni aylanaga olamiz. Qolgan implikantalardan barcha bo'sh ustunlarni qoplaydiganlarning minimal sonini tanlaymiz. 2.2- jadval 36 1 2 3 4 5 6 7 8 001 0 001 1 100 1 101 0 110 0 101 1 110 1 111 0J1 – 01– ⊕ ⊕ + + J2 1 0–1 + + J3 1 –01 + + J4 1 –10 + + J5 1 10– + + J6 1 1–0 + + B a rch a tupikli DNSh J1 ni o' z ichig a o lishi ker a k , a ks h o ld a birinchi ikkit a ustun q o pl a nm a ydi . Shuning uchun birinchi qator bazisli qatordir va implikant J1 funktsiyaning yadrosini tashkil qiladi. Ushbu tanlov bilan yana ikkita ustun avtomatik ravishda qoplanadi. Tupikli imlikantalar: J1∨ J3∨ J6= x2 x3∨ x1x3x4∨ x1x2x4 ( LБ= 8) J1∨ J3∨ J5∨ J4= x2 x3∨ x1x3x4∨ x1x2x3∨ x1x3x4 ( LБ= 11) J1∨ J3∨ J5∨ J6= x2 x3∨ x1x3x4∨ x1x2x3∨ x1x2x4 ( LБ= 11) J1∨ J2∨ J6∨ J5= x2 x3∨ x1x2x4∨ x1x2x4∨ x1x2x3 ( LБ= 11) J1∨ J2∨ J6∨ J3= x2 x3∨ x1x2x4∨ x1x2x4∨ x1x3x4 ( LБ= 11) 37 J1∨ J2∨ J5∨ J6= x2 x3∨ x1x2x4∨ x1x2x3∨ x1x2x4( LБ= 11) J1∨ J2∨ J5∨ J4= x2 x3∨ x1x2x4∨ x1x2x3∨ x1x3x4 ( LБ= 11) Rasmda barcha Tupikli DNSh lar ko'rsatilgan: 2.3-shakl Barcha tupikli DNSh lar orasida biz eng kichik uzunlikdagi DNSh ni tanlaymiz: MDNSh: f(x1,x2,x3,x4)= J1∨ J3∨ J6= x2 x3∨ x1x3x4∨ x1x2x4 38 2.3. Qisman aniqlangan mantiqiy funktsiyalarni minimallashtirishning mohiyati. Ta'rif. Mantiqiy funktsiya (taklif mantiqiy formulasi) F, agar F funktsiyasiga kiritilgan o'zgaruvchilar qiymatlarining barcha mumkin bo'lgan to'plamlari uning qiymatlari berilmagan bo'lsa, qisman (hamma joyda emas) aniqlangan deb ataladi. Dizyunktiv normal shakllar (DNSh) sinfida qisman aniqlangan funktsiyalarni minimallashtirish algoritmi quyidagi bosqichlarni o'z ichiga oladi. 1-qadam. F mantiqiy funksiyasini aniqlanmagan o zgaruvchan qiymatlarʻ to plamida nol bilan kengaytiramiz. Olingan mantiqiy funktsiya ʻ F0 bilan belgilanadi. 2-qadam F0 mantiqiy funksiyasining mukammal diz’yunktiv normal shaklini (MDNSh) tuzamiz. 3-qadam F mantiqiy funktsiyasini aniqlanmagan o'zgaruvchan qiymatlar to'plamidagi birliklarga kengaytiramiz. Olingan mantiqiy funktsiyani F1 bilan belgilaymiz. 4-qadam F1 funksiyasining qisqartirilgan DNSh ni tuzing. F1 funksiyasining qisqartirilgan DNSh shartlarini istalgan tartibda raqamlaymiz. 5-qadam.F0 funktsiyasining SDNSh shartlarini va F1 funktsiyasining qisqartirilgan DNSh shartlarini raqamlar bilan birga birinchisi ustunga yozamiz. Agar kamaytirilgan DNSh funktsiyasining F1 muddati to'liq 0 funktsiyasining qisqartirilgan DNSh terminiga kiritilgan bo'lsa, u holda tegishli satr va ustunning kesishmasida F 1 funktsiyaning qisqartirilgan DNSh muddatining sonini yozamiz. 39 6-qadam. Quyidagi qoida bo'yicha panjara ifodasini tuzamiz: implikant jadvalining har bir ustunida 5-bandda olingan raqamlarni diz'yunksiya belgisi bilan bog'laymiz va bu diz'yunktsiyalarning birikmasini olamiz. 7-qadam. Qavslarni panjara ifodasida kengaytiramiz va agar kerak bo'lsa, assimilyatsiya qoidasidan foydalanamiz. 8-qadam . F mantiqiy funktsiyasining qisqartirilgan DNSh ga to'g'ri keladi. Mantiqiy F funktsiyasining qisqartirilgan DNSh ni tiklash uchun raqamlari hosil bo'lgan ifodada ko'rsatilgan atamalarning diz'yunktsiyalarini olish kerak. 9-qadam. F funktsiyasining qisqartirilgan DNShlaridan F funktsiyasining minimal DNShlarini tanlaymiz. Mantiqiy funktsiyalar uchun qisqartirilgan va minimal DNShlarni qurish misoli. Misol. Qisman aniqlangan mantiqiy funktsiya F = (1110**01) uchun qisqartirilgan va minimal DNShlarni oling. Yechim. Qisman aniqlangan mantiqiy funktsiya F = (1110**01) ning qisqartirilgan va minimal DNShlarini olish uchun biz DNSh sinfidagi qisman aniqlangan mantiqiy funktsiyalar uchun minimallashtirish algoritmidan foydalanamiz, tavsifi yuqorida ko'rsatilgan. F = (1110**01) quyidagi haqiqat jadvali sifatida yozamiz:F ,F0,F1 Haqiqat jadvalidagi * o'rniga 0 ni yozamiz. f 0 ( x , y , z ) funksiyani olamiz (quyidagi jadvalning 5-ustunida ko'rsatilgan). f 1( x , y , z) funksiyasini olamiz (quyidagi jadvalning 6-ustunida ko'rsatilgan). 40 2.3-jadval F = (1110**01) mantiqiy funktsiya uchun o'zgartirilgan haqiqat jadvallari f 0 ( x , y , z ) funksiyaning SDNSh ni quramiz :f0(x,y,z)= xyz∨ xyz∨ xyz∨ xyz f0 mantiqiy funktsiyaning mukammal diz'yunktiv normal shakli. f 1( x , y , z ) funksiyaning mukammal kon’yunktiv normal shaklini (MKNSh) tuzamiz : f1(x,y,z)=(x∨ y∨ z)(x∨ y∨ z). f1 mantiqiy funktsiyaning mukammal kon'yunktiv normal shakli f 1( x , y , z) ifodasidagi qavslarni ochamiz va ekvivalent transformatsiyalarni bajaramiz. f 1( x , y , z ) funksiyaning quyidagi qisqartirilgan DNSh ni olamiz: (x∨y∨z)(x∨y∨z)=xx∨yx∨zx∨xy∨yy∨zy∨xz∨yz∨zz≡¿¿(0∨yx∨zx∨xy∨y∨zy∨xz∨yz∨0≡¿¿zx∨y∨xz−qisqartiri lganDNSh f1(x,y,z) Mantiqiy funktsiya f1 ning qisqartirilgan diz'yunktiv normal shaklini qurish Quyidagi qamrov jadvalini tuzamiz: 41 Mantiqiy funktsiya F = (1110**01) uchun imlikant jadvali Biz panjara ifodasini yozamiz, uni qavslarni ochish orqali o'zgartiramiz, biz 8-bosqichdagi tavsifga muvofiq tiklanadigan yagona atamani olamiz, biz olamiz:(1∨ 2)213 = 1213 ∨ 2213 = 123 ∨ 213 = 123 = zx∨ y∨ xz . F = (1110**01) mantiqiy funktsiya uchun qisqartirilgan DNShni qurish. Qisman aniqlangan mantiqiy funktsiya F = (1110**01) ning qisqartirilgan DNShsi topildi. Ushbu noyob qisqartirilgan DNSh, shuningdek, qisman aniqlangan mantiqiy funktsiya F = (1110**01 ) uchun minimal DNSh hisoblanadi. 2.4. To’liq aniqlanmagan Bul funksiyalarni minimallashtirishning dekompozitsiya usuli [5]. Ushbu bo’limda qisman aniqlangan mantiqiy funktsiyalarni minimallashtirish muammosini ko'rib chiqiladi. Ba'zi amaliy vazifalarda mantiqiy funksiya qiymatlar to'plamining ba’zi bir elementlarida aniqlanmagan bo’lishi mumkin. Agar ushbu qiymatlar o'rganilayotgan muammoda hech qanday rol o'ynamasa, u holda bu to'plamda aniqlangan funktsiyani minimal normal shaklni, ya'ni eng kam belgilarga ega bo'lgan shaklga keladigan tarzda davom ettirish mumkin [1]. Masalan, quyidagi 01x111x011x010x0 ketma-ketlikda berilgan funktsiyani ko'rib chiqamiz. 42 01x111x011x010x0, bu yerda x funktsiya ushbu qiymatlar to'plamida aniqlanmaganligini anglatadi. Bu funktsiyani nolga kengaytirishni ko’rib chiqamiz [2]. Minimal dizyunktiv normal shaklni (DNSh) topish uchun avval berilgan mantiqiy funktsiyaning implikantlarini aniqlashimiz kerak. h = h (x1, ..., x n) funksiya f = f (x1, ..., x n) funksiyasining implikantasi bo’ladi, agar h ham f ning qiymatlari birga teng yoki aniqlanmagan qiymatlarida shunday qiymatlar qabul qilsa: h ≤ f bo’lsa. Funksiyani bo’laklash daraxti yordamida minimallashtirishni amalga oshiramiz [3]. Keyingi usulda k o‘zgaruvchidan iborat f funksiyaning barcha 2k mumkin bo‘lgan bo’laklanishlardan iborat daraxt yasash va daraxtning har bir tugunida ¿ amalini qo‘llashdan iborat. Daraxtning nolinchi pog’onali bo’laklanishi D = f bo’ladi. Daraxtning birinchi pog’onali bo’laklanishi D1, D2, D 3, D 4 dan iborat bo'ladi . 01011100 D1: ∧ 11001000 g 1= 01001000 01011100 D2 : ∧ 11001000 g 2= 01001000 01111110 D 3 : ∧ 01000000 g 3= 01000000 00101010 D 4: ∧ 11101000 g 4= 00101000 Ikkinchi pog’onali bo’laklanishi: 0100 D12 : ∧ 1000 g 12= 0000 0110 D13 : ∧ 0000 g13= 0000 0010 D14 : ∧ 1000 g 14= 0000 0110 D23 : ∧0000 g 23= 0000 43 0010 D24 : ∧ 1000 g 24= 0000 0110 D34 : ∧ 0000 g 34= 0000 Keyingi bo’laklanishda barcha g funktsiyalar 00 ga teng bo'ladi, shuning uchun uchinchi pog’onani qurishning hojati yo'q. Natijada 7 ta oddiy implikanta hosil bo’ldi: x 2 x 3 x 4 , x 2 x 3 x 4 , x 1 x 3 x 4 , x 1 x 3 x 4 , x 1 x 2 x 4 , x 2 x 3 x 4 , x 2 x 3 x 4 . Endi imlikanta jadvalini tuzamiz: 2.3-jadval 0001 0011 0100 0101 1000 1001 1100 x 2 x 3 x 4 * * x 2 x 3 x 4 * * x 1 x 3 x 4 * * x 1 x 3 x 4 * * x 1 x 2 x 4 * * x 2 x 3 x 4 * * x 2 x 3 x 4 * * Agar biron bir ustunda faqat bitta belgi bo'lsa, unda tegishli qatordagi implikant muhim ahamiyatga ega v a u a lb a tt a minim a l shaklga kiradi, shuning uchun unga mos keladigan ustunlar va satrlarni keyingi b o sqichd a n chiqarib tashlash mumkin. Natijada jadval quyidagi shaklni oladi : 2.4- jadval 0100 0101 1000 1001 1100 x 2 x 3 x 4 * x 2 x 3 x 4 * * x 1 x 3 x 4 * 44 x 1 x 3 x 4 * * x 2 x 3 x 4 * * x 2 x 3 x 4 * * Jadvaldan satrlar bilan ustunlarni qoplash uchun quyidagi cheklovlar tizimini hosil qilamiz: { U 1 + U 5 ≥ 1,¿{ U 3 + U 5 ≥1,¿{ U 4 + U 6 ≥ 1¿{ U 1 + U 6 ≥ 1,¿¿¿¿ , L = U 1 + U 2 + U 3 + U 4 + U 5 + U 6 . Butun sonli dasturlashning tegishli muammosini hal qilib, biz 4-, 5- va 6- th implikantlar minimal KNSh ga kirishini aniqlaymiz. Oldin chiqarib tashlangan muhim implikantni qo'shamiz va natijada minimal DNSh quyidagi shaklga ega bo'ladi: x 1x3x4∨ x2x3x4∨ x2x3x4∨ x1x2x4 . Endi berilgan funktsiyani [2] birlik qiymat bo'yicha davom ettirish uchun bo’laklash daraxtini quramiz. Daraxtning nolinchi pog’onali bo’laklanishi D q= f bo’ladi. Daraxtning birinchi pog’onali bo’laklanishi D1, D2, D 3, D 4 quyidagicha bo'ladi: 01111110 D1: v 11101010 g 1= 01101010 ; 01011110 D 2 : v 11001000 ; g 2= 01101010 01111110 D 3: v 11101010 g 3= 01101010 01111111 D 4 : v 11101000 g 4= 01101000 Ikkinchi pog’onali bo’laklanishi: 45 0110 D12 : v 1010 g 12= 0010 0110 D13 : v 1010 g 13= 0010 0111 D14 : v 1000 g 14=0000 0110 D23 : v 1010 g 23= 0010 0111 D24 : v 1000 g 24= 0000 0110 D34 : v 1000 g 34= 0000 Natijada quyidagi oddiy imlikantalar hosil bo’ladi: x2x3x4,x3x4, x2x4, x1x3x4,x1x4, x1x2x4,x1x2x3, x1x2x3, x1x2x3 Imlikantalar jadvali quyidagi shaklda bo'ladi: 2.5-jadval 0001 0011 0100 0101 1000 1001 1100 x 2 x 3 x 4 * * x 3 x 4 x 2 x 4 * * x 1 x 3 x 4 * * x 1 x 4 * * x 1 x 2 x 4 * * x 1 x 2 x 3 * x 1 x2x 3 * * x 1 x 2 x 3 * * 46 { U 6 + U 7 ≥ 1,¿{ U 4 + U 8 ≥ 1 ¿{ U 5 + U 9 ≥ 1,¿{ U 1 + U 9 ≥ 1,¿¿¿¿ L = U 1 + U 2 + U 3 + U 4 + U 5 + U 6+U 7+U 8+U 9. Butun sonli dasturlashning tegishli muammosini hal qilib, biz minimal shakldagi quyidagi DNSh ga ega bo'lamiz: x1x2x4∨ x1x2x3∨ x1x2x3∨ x2x4 . Shunday qilib, minimal DNSh funktsiyani barcha noaniq qiymatlarini birlik qiymatlarga davom ettirish orqali olinishi mumkin. Ushbu usul bilan olingan implikantlardan faqat belgilangan to'plamlarni qamrab oladigan implikantlarni minimal shaklga kiritish kerak. Bu implikant jadval yordamida amalga oshirilishi mumkin. Qisman aniqlangan mantiqiy funktsiyaning minimal kon'yunktiv shaklini (KNSh) hosil qilish xuddi shunday tarzda amalga oshiriladi, faqat kengaytma bir qiymatlar bo’yicha emas, balki nollar bilan amalga oshiriladi. 2.4. To’liq aniqlanmagan mantiqiy funksiyalarni minimallashtirish uchun takomillashtirilgan Mak-Klaski usuli [13] . Bizga 2.6-jadval ko’rinishda f(x1,x2,...,xn) funksiya qiymatlar jadvali berilgan bo’lsin. 2.6-jadval x1,x2,...,xn f(x1,x2,...,xn) 47 0 0 … 0 0 0 … 1 …. …. …. …. 1 1 … 1α1 α2 …. …. …. …. α2n bu erda, α i ∈ ¿ ¿ . Birlik I a interval maksimal deyiladi uni qamrab oluvchi boshqa I b inerval mavjud bo’lmasa [13]. f funksiyani maksimal birlik intervaliga mos keluvchi konyunksiyasi oddiy implikanta deyiladi [13]. Barcha oddiy implikantalar dizyunksiyasidan iborat dizyunktiv normal shaklga (DNSh) qisqartirilgan DNSh deyiladi. Quyidagi xususiyatlarga ega to’liq aniqlanmagan f(x1,x2,...,xn) funksiyani ko’rib chiqamiz: 1. O’zgaruvchilar soni n yetarlicha katta; 2. funksiyaning birlik qiymatlar to’plami V1 va nol qiymatlar to’plami V0 larning birlashmasi quvvati 2 n dan ancha kichik; 3. funksiyaning birlik qiymatlar to’plami V1 va nol qiymatlar to’plami V0 ikkilik intervallar ko’rinishda berilgan. To’liq aniqlanmagan mantiqiy funksiyani qisqartirilgan DNSh sini aniqlash uchun farqlash jadvalini tuzamiz. Maksimal intervallarni aniqlash farql a sh jadvalida satrlar bilan ustunlarni qoplash masalasiga keltiriladi. Quyidagicha aniqlangan funksiyani minimal DNSh sini aniqlash masalasini ko’ramiz: f ( x 1 , x 2 , ... , x n ) = { ¿ 1 β 1 , . . . . β p 1 intervallarda , ¿ 0 γ 1 , . . . , γ p 2 intervallarda . 48 bu erda , βi∈{0,1−},i=1,p1,γi∈{0,1− },j=1,p2, Maksimal intervallar to’plamini aniqlash uchun, satrlari t1t2,....,tp1 ko’rinishda belgilangan β1,β2,....βp1 birlik intervallarning har biri uchun farqlar jadvalini tuzamiz. 49 2.7-jadval. bunda,rij -lar quyidagi qoidaga asosan hisoblanadi: 0  0=0 0  1=1 0  -=0 1  0=1 1  1=0 1  -=0 -  0=0 -  1=0 -  -=0. (2.1) Birinchi qo’shiluvchi sifatida birlik intervalning i -razryadi va ikkinchi qo’shiluvchi sifatida nol intervalning i - razryadi olinadi. 2.8-jadval. Maksimal interval Birlik interval β1 ρ2 … βp1 U 1 1 0 … 1 U1 0 1 … 0 … … … … … U p3 0 0 … 1 Farqlar jadvali yordamida nol intervallarni birlik intervallar qoplamasi aniqlanadi. Nol intervallarni qoplaydigan birlik interval elementlaridan 50Birlik intervallar Nol intervallar γ1 γ2 …. j γp2 (t1) β1 (t1) β1 …. …. i …. (tp1) βp1 rij maksimal interval hosil qilinadi. Barcha maksimal intervallar to’plami qisqartirilgan DNSh oddiy implikantalariga mos keladi [13]. Implikantalar jadvaliga asosan maksimal intervallar bilan birlik intervallarni turlicha qoplamasini hosil qilamiz. Ushbu qoplamalar keltirilmaydigan(soddalashmaydigan) qoplama dep atalib tupikli DNSh ga mos keladi. Ushbu usulni qo’llanilishini ko’rsatish uchun quyidagi misolni ko’rib chiqamiz. 2.3-Misol. Berilgan to’liq aniqlanmagan funksiya:f(x(n)= (10 − − 01100 − 1100 − 1) 2n= 24= 16 n= 4 x1x2x3x4 f(x1,x2,x3,x4) 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 - - 0 1 1 0 0 - 1 1 0 0 - 1 51 Berilgan funksiyaning qiymatlar to’plamining qism to’plamlari:V1={0000 ,0101 ,0110 ,1010 ,1011 ,1111 } V0={0001 ,0100 ,0111 ,1000 ,1100 ,1101 } Dastlab V 1 top’lamni maksimal intervallarini aniqlaymiz: 0000∗¿¿0101∗¿¿0110∗¿¿1010 1011 1111 Oddiy birlashtirish amalini qo’llab quyidagini hosil qilamiz. {0000∗¿{0101 ¿{0110 ¿{101−¿¿¿¿ Keyin esa V 0 to’plamni maksimal intervallarini aniqlaymiz : 0001 ∗ 0100 1000 1100 0111 ∗¿¿1101 Bu intervallar uchun ham birlashtirish usulini qo’llaymiz va quyidagi ko’rinishga keltiramiz. {0111¿{0001¿{−100¿{1−00¿¿¿¿ 52 (2.1)-qoida asosida birlik va nollik qiymatlarni farqlovchi amallarni bajaramiz.0000 α1 0101 α2 0110 α3 101 − α4 1− 11 α5 0 111 β1 0001 β2 − 100 β3 1− 00 β4 110 − β5 0000 0111 0111 0000 0001 0001 0000 −100 0100 0000 1−00 1000 0000 110 − 1100 V 1 n i n g b i r i n c h i e l e m e n t i V 0 n i n g b i r i n c h i e l e m e n t i u c h u n f a r q l a n i s h j a d v a l i : α1 x1x2x3x4x5 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 F a r q l a n i s h j a d v a l i g a k o ’ r a a n i q l a n g a n m a k s i m a l i m p l i k a n t a : V 1 n i n g i k k i n c h i e l e m e n t i V 0 n i n g h a r b i r e l e m e n t i u c h u n f a r q l a n i s h j a d v a l i : x1x2−x4 0101 0111 0010 0101 0001 0100 0101 −100 0001 0101 1−00 1001 0101 110 − 1000 α2 x1x2x3x4x5 0 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 53 F a r q l a n i s h j a d v a l i g a k o ’ r a a n i q l a n g a n m a k s i m a l i m p l i k a n t a l a r :x1x2x3x4 V 1 n i n g u c h i n c h i e l e m e n t i V 0 n i n g h a r b i r e l e m e n t i u c h u n f a r q l a n i s h j a d v a l i 0110 0111 0001 0110 0001 0111 0110 −100 0010 0110 1−00 1010 0110 110 − 1010 α3 x1x2x3x4 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 0 F a r q l a n i s h j a d v a l i g a k o ’ r a a n i q l a n g a n m a k s i m a l i m p l i k a n t a l a r : − − x3x4 V 1 n i n g t o ’ r t i n c h i e l e m e n t i V 0 n i n g h a r b i r e l e m e n t i u c h u n f a r q l a n i s h j a d v a l i 101 − 0111 1100 101 − 0001 1010 101 − −100 0110 101 − 1−00 0010 101 − 110 − 0110 α4 x1x2x3x4 1 0 1 - 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 54 F a r q l a n i s h j a d v a l i g a k o ’ r a a n i q l a n g a n m a k s i m a l i m p l i k a n t a : x1− x3− , − x2x3− . V 1 n i n g b e s h i n c h i e l e m e n t i V 0 n i n g h a r b i r e l e m e n t i u c h u n f a r q l a n i s h j a d v a l i 1−11 0111 1000 1−11 0001 1010 1−11 −100 0011 1−11 1−00 0011 1−11 110 − 0010 α4 x1x2x3x4 1 - 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 55 F a r q l a n i s h j a d v a l i g a k o ’ r a a n i q l a n g a n m a k s i m a l i m p l i k a n t a :x1− x3− A l g o r i t m n i i s h l a s h i n a t i j a s i d a q u y i d a g i m i n i m a l D N S h a n i q l a n a d i : −− x3x4 0 01 0 0 110 10 10 111 0 x1− x3− 1 010 10 11 111 0 111 1 − x2x3− 0010 001 1 101 0 1011 x1x2x3x4 00 00 00 00 00 00 00 00 x1x2x3x4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 N a t i j a d a m i n i m a l D N S h n i t o p i s h f o r m u l a s i q u y i d a g i c h a b o ’ l a d i . − − x3x4 ¿ x1− x3− ¿ − x2x3− ¿ x1x2x4 ¿ x1x2x3x4 B u m a s a l a d a d i s k r e t q u r i l m a l a r n i s i n t e z q i l i s h d a t o ’ l i q a n i q l a n m a g a n q i y m a t l a r k i r i t i l a d i . A n i q l a n m a g a n q i y m a t l a r i n i a n i q l a n a d i v a b i t t a m i n i m a l D N S h n i h o s i l q i l i n a d i . B u b i t t a m i n D N S h y e t a r l i . B u n d a n k o ’ r i n i b t u r i b d i k i b e r i l g a n f u n k s i y a n i a n i q l a n m a g a n q i y m a t l a r i n i q u y i d a g i c h a t o ’ l d i r i s h m u m k i n : 56 x1x2x3x4 f(x1,x2,x3,x4) 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 - 1 - 1 0 1 1 0 0 - 0 1 1 0 0 - 1 1 I I - B o b n i n g m u h i m x u l o s a l a r i : 1. Bull funktsiyalarni minimallashtirishning muammolari, qo’llaniladigan qoida va usullar hamda ularning xossalari bayon etildi. 2. Qisman aniqlangan Bull funksiyalarini minimallashtirish muammosi tahlil qilindi, qo’llaniladigan amallarning muhim jihatlari ko’rsatildi. 3. Bull funktsiyalarni Kvayn-Mak-Klaski usulini qisman aniqlangan funksiyalarni minimallashtirishga tadbiqi ko’rsatildi. 57 III-BOB. TO’LIQ ANIQLANMAGAN BULL FUNKSIYALARINI MINIMALLASHTIRISH DASTURIY TA’MINOTI NING TAVSIFI Ushbu bobda, mantiqiy formulani komputerda tahli qilish uchun uning grammatik ta’rifi , tahlil qilish va qayta ishlash algoritmlari, to’liq aniqlanmagan funksiyani minimallashtirishni dasturiy ta’minoti tavsifi beriladi. 3.1. Mantiqiy for m ula tushu n chasi va u n i n g grammatik tasnifi. M a n tiqiy o’zgaruvchi deb shu n day o’zgaruvchiga aytiladiki , u faqat ikki xil m a n tiqiy ifoda n i qabul qiladi , ya’ n i FALSE yoki TRUE . M a n tiqiy fu n ksiya f(x 1 , ... , x n ) quyidagicha tasvirlaydi: f:{FALSE , TRUE} n {FALSE , TRUE}. M a n tiqiy fu n ksiya berilishi n i n g ya n a bir usuli — bu m a n tiqiy for m ulalar n i m etali n gvistik for m ulalar ko’ri n ishida yozilishidir. M a n tiqiy for m ulalar n i n g gra mm atik yozilish tili quyidagi ko’ri1ishda bo’ladi: { m a n tiqiy-for m ula::= ko n ‘yu n ksiya OR probel m a n tiqiy-for m ula} ko n ‘yu n ksiya::={kupaytirish kupaytirish A N D probel ko n ‘yu n ksiya} kupaytirish::={ N OT probel kupaytirish o’zgaruvchi m a n tiqiy-for m ula TRUE probel FALSE probel} o’zgaruvchi::=harf probel probel::={probel-belgii probel-belgii probel} Ikki m a n tiqiy formula ekvivalent deyiladi , agar ixtiyoriy qiy m atlar to’pla m i uchu n, qaysiki u n ga kiruvchi o’zgaruvchilar n i n g qiy m atlari m os kelsa , ya’ n i agar ular bir xil m a n tiqiy fu n ksiya n i bersa. 58 α— ifodala n uvchi m a n tiqiy for m ula , u α da n m aksi m al bitta probelga farq qiladi.  —m a n tiqiy-for m ula  m a n tiqiy for m ula n i qis m iy(ichki) for m ulasi deyiladi , agar u quyidagi shartlarda n hech bo’l m aga n da bittasi n i qa n oatla n tirsa: a) α=β ; b) α =  OR  , bu yerda  -ko n ‘yu n ksiya ,  -esa m a n tiqiy for m ula ,  -  yoki  lar n i n g biri n i n g qis m iy for m ulasi; c) α =  A N D  , bu yerda  - ko’paytuvchi ,  - esa ko n ‘yu n ksiya ,  -  yoki  n i n g qis m iy for m ulasi; d)  =(  ) ,  - esa  - for m ula n i n g qis m iy for m ulasi; e) α = N OT  , bu yerda  - ko’paytuvchi ,  - for m ula esa  - ko’paytuvchi n i n g qis m iy for m ulasi n i bildiradi; M a n tiqiy fu n ksiyalar n i berilishi n i n g ya n a bir usuli — bu ular n i Diz’yu n ktiv N or m al Shakl (D N Sh) deb n o m la n uvchi ko’ri n ishda yozilishidir. D N Sh gra mm atik tilda quyidagicha yoziladi: D N Sh::={FALSE probel ele m e n tar-ko n ‘yu n ksiya ele m e n tar-ko n ‘yu n ksiyaOR probel D N Sh} ele m e n tar-ko n ‘yu n ksiya::= { ele m e n tar-ko’paytuvchi ele m e n tar-ko’paytuvchi ele m e n tar-ko n ‘yu n ksiya} ele m e n tar-ko’paytuvchi::={o’zgaruvchi N OT probel o’zgaruvchi} o’zgaruvchi::=harf probel probel::={probel-belgii probel-belgii probel} U m u m a n D N Sh da for m ula tuzish uchu n berilga n m a n tiqiy fu n ksiyalar n i n g ket m a-ket har birida n so’ n g ele m e n tar ko’paytirish — A N D operatsiyasi n i qo’yish kerak.. 59 D N Sh to’g’ri deyiladi , agar har bir ele m e n tar ko n ‘yu n ksiyada ha mm a o’zgaruvchi harflar bir m artada n qat n ashsa , ya’ n i ele m e n tar m ulohazalar bir m artada n qat n ashsa. To’g’ri D N Sh  m uka mm al D N Sh ( M D N Sh) deyiladi , agar D N Sh  da bir xil ele m e n tar ko n ‘yu n ksiyalar uchra m asa. Ke n gaytirilga n ( m a n tiqiy) for m ulalar n i n g ifodala n ishi m a n tiqiy for m ulalar n i n g qo’shi m cha si n taktik qoidalar bila n ifodala n ishi: ke n gaytirilga n - for m ula::= { m a n tiqiy-for m ula m a n tiqiy-for m ula{ =  +} ke n gaytirilga n -for m ula} va qo’shi m cha ko’paytirish qoidasi orqali ko’paytuvchi n i n g ifodala n ishi: ko’paytuychi::={ N OT probel ko’paytuvchi TRUE probel FALSE probel (ke n gaytirilga n -for m ula)} Shunday qilib , N OT , A N D va OR operatsiyalariga qaraga n da  , = va + m a n tiqiy operatsiyalar kuchsizroq ishlaydi , ya’ n i ular qavs ichidagi operatsiyalarda keyi n gi n avbatda bajariladi. Bu operatsiyalar n i hisoblash qoidasi quyidagicha: (  )=(  V  ) , (  =  )=(  &  ) V (  &  ) va  +  =(  &  ) V (  &  )  - m a n tiqiy for m ulalar n i n g ifodala n ish qoidasi n i bildiradi , bu yerda  ,  - bir-biriga te n g bo’l m aga n m a n tiqiy for m ulalar.  ga asosa n  - m a n tiqiy for m ula  ga qis m iy for m ula bo’lsa ,   ga aksla n tiradi. Agar  o’zida  for m ula n i aks ettir m asa , u holda aytishi m iz m u m ki n ki ,   ga tegishli e m as. Qoidalar sxe m asi cheksiz qoidalar to’pla m i n i yozish uchu n, berilga n lar n i for m ulirovka qilish uchu n qo’lla n iladi. Qoidalar sxe m asi o’zgaruvchilar bila n birga m avjud si n taktik tushu n chalar: m a n tiqiy-for m ula , ko n ‘yu n ksiya , ko’paytirish , o’zgaruvchi n o m lari yoziladi. Shu n day qilib , m asala n : ko n ‘yu n ksiya A N D ko n ‘yu n ksiya  ko n ‘yu n ksiya qoidalar sxe m asi cheksiz qoidalar to’pla m i n i bildiradi , bu sxe m alar bir vaqt n i n g o’zida ko n ‘yu n ksiya n i 60 al m ashtirib , boshqa bir qa n daydir ko n ‘yu n ksiya n i hosil qilish m u m ki n, ya’ n i bu qoidalar to’pla m i quyidagilar n i o’z ichida saqlaydi: TRUE A N D TRUE  TRUE X A N D X-^X , (X OR Y) A N D (X OR Y)  (X OR Y). F- m a n tiqiy frag m e n t X={x 1 , ... , x n } m a n tiqiy o’zgaruvchilar n i n g alfaviti orqali a n iq uchlar to’pla m i bila n beriladi , har bir uchda n “+” va “-” belgilari bila n belgila n ga n qa n daydir ikkita yoylar chiqadi.Har bir yuqori uchlar{0 , 1 , ... , 9}so n larida n birortasi bo’lsi n, yuqori bo’l m aga n uchlar X da n oli n ga n belgilar blia n belgila n adi. Yuqori uchlar n i belgilovchi belgilar u n i n g sharti n i ifodalaydi. Frag m e n t n i n g uchlarida n biri boshla n gich shart deb oli n adi. X da n oli n ga n m a n tiqiy o’zgaruvchilar n i n g chi n lik xususiyati I:X  {FALSE , TRUE} belgilash n i kirita m iz. U holda F n i n g boshla n gich uchida n chiquvchi  1 yul berilga n bo’ladi va u quyidagi talablar bila n a n iqla n adi: agar uchlar sharti I da chi n bo’lsa , u holda yo’l shu uchda n plyus-strelkaga to m o n ketadi , aks holda esa yo’l m i n us-strelka to n o n ga ketadi. Ikki m a n tiqiy frag m e n t ekvivale n t deyiladi , agar I n i n g ixtiyoriy 2 ta  1 1 va  1 2 yo’llari biri n chi va ikki n chi m a n tiqiy frag m e n tda bir vaqt n i n g o’zida cheksiz bo’lsa , yoki yuqori uchlarda bir xil belgi bila n tugasa . M a n tiqiy frag m e n t F erki n deyiladi , agar F da n boshla n ib , har xil tugalla n uvchi yo’l X da n oli n ga n o’zgaruvchilar n i n g chi n lik xususiyati n i a n iqlay olsa. Frag m e n t bo’sh bo’ladi , agar ixtiyoriy I da  1 yo’l tuga m asa , ya’ n i cheksiz davo m etsa. Frag m e n t total deyiladi , agar I da  1 yo’l tugasa , ya’ n i boshla n gich uchda n biro n -bir yuqoridagi uchga bora olsa. Total m a n tiqiy frag m e n t F n i n g har bir yuqori uchi “0” yoki “1” so n larida n birortasi bila n belgila n ga n bo’lsa , bu frag m e n t X n i n g o’zgaruvchilarida n oli n ga n f ф - m a n tiqiy fu n ksiya n i beradi. Biz shu n da va faqat shu n da f ф (I(x 1 ) , ... , I(x n ))=TRUE bo’ladi , deb ayta ola m izki , qacho n ki  1 yuqori uchda 1 belgisi bila n tugasa. Total m a n tiqiy 61 frag m e n t va m a n tiqiy for m ula ekvivale n t deyiladi , agar ular bitta fu n ksiya n i bersa. Oddiy ifodala n ish tushu n chasi n i n g si n taktik tahlili quyidagi gra mm atika yorda m ida yoziladi: oddiy-ifodala n ish::={ifoda ifoda {V} N OT (oddiy-ifodala n ish)} ifoda::={ko’paytuvchi ko’paytuvchi  ifoda} ko’paytuvchi::={ m a n tiqiy-o’zgar m as ide n tifikator (oddiy-ifodala n ish)} m a n tiqiy-o’zgar m as::={TRUE  FALSE belgisizlar raqa m i} ide n tifikator::={harf ide n tifikator-harf ide n tifikator-raqa m } Oddiy ifodala n ish daraxti n i quyidagicha qurish m u m ki n : 1). Oddiy ifodala n ish daraxti-   -ifodalar daraxti bo’ladi , agar  -ifoda  =  bo’lsa; bu yerda  - bu “V” yoki “  ” ,  - ifoda ,  - esa oddiy ifodala n ish ;  - daraxt n i n g ildizi  - belgii bila n belgila n ga n uch bo’ladi , u n i n g chap to m o n i —  - ifoda daraxt n i n g ildizi , o’ n g to m o n i —  - oddiy ifodala n ish daraxt n i n g ildizi bo’ladi. 2).  -ifodalar daraxti  - ko’paytuvchi daraxti bo’ladi , agar  - ko’paytuvchi ,  =  bo’lsa; bu yerda  - (*) operatsiyasi belgii ,  - ko’paytuvchi ,  - esa ifoda , u n da  - daraxt n i n g ildizi  - operatsiya bila n belgila n ga n uch bo’ladi , u n i n g chap to m o n i —  - ko’paytuvchi daraxti n i n g ildizi , o’ n g to m o n i esa —  - ifoda (ter m ) daraxt n i n g ildizi bo’ladi. 3).  - ko’paytuvchi daraxti  - oddiy ifodala n ish daraxti bo’ladi , agar  =(  ) bo’lsa; agar  - ide n tifikator yoki m a n tiqiy o’zgar n as bo’lsa , u holda u haqiqiy uchda n tuziladi;  - bila n belgila n adi , yo n to m o n lari yo’q. 62 3.2. Mantiqiy ifodalarni tahlil qilish algorit m lari. Mantiqiy for m ulalarni tahlil qilishda quyidagi asosiy qoidalar va sxemalar qo’llaniladi: Shakl o’zgartirishga tegishli bo’lga n for m ulalar n i soddalashtirish n i sxe m a bila n berilish qoidalari n i qaray m iz: N OT TRUE  FALSE , N OT FALSE  TRUE , TRUE A N D ko n ‘yu n ksiya  ko n ‘yu n ksiya , ko n ‘yu n ksiya A N D TRUE  ko n ‘yu n ksiya , TRUE OR for m ula  TRUE , FALSE A N D ko n ‘yu n ksiya  FALSE , for m ula OR TRUE  TRUE , ko n ‘yu n ksiya A N D FALSE  FALSE , FALSE OR for m ula  for m ula , for m ula OR FALSE  for m ula , N OT (for m ula1 A N D for m ula2)  N OT for m ula1 OR N OT for m ula2 , N OT (for m ula1 OR for m ula2)  N OT for m ula1 A N D N OT for m ula2 , o’zgaruvchi1 OR o’zgaruvchi1 A N D o’zgaruvchi2  o’zgaruvchi2 , N OT ( N OT for m ula )  for m ula , o’zgaruvchi OR o’zgaruvchi  o’zgaruvchi , o’zgaruvchi A N D o’zgaruvchi  o’zgaruvchi , N OT o’zgaruvchi A N D o’zgaruvchi  o’zgaruvchi . Ko’pgi n a for m ulalar1i n g ichki tasvirla n ishi bila n m asala n i n g bu yechi m i ildizli daraxt bo’ladi. Faraz qila m iz , oli n ga n for m ulaga u n i ildizli daraxt ko’ri n ishida F-ildiz bila n tasvirlash a m alga oshdi. U holda u n i n g soddalashtirilishi n i bu daraxtda n o’tish n i n g qa n daydir eslatilga n algorit m ik tili m odifikatsiyasi yorda m ida realizatsiya qilish n u n ki n . M odifikatsiya daraxtda n o’tish n i n g qurilishiga bog’liq bo’ladi. Rekursiy a l a r n i n g ijr o etilish i m k o n iy a ti m a vjud b o’ ls a , bu n d a y o’ tish n i rekursiv pr o tsedur a y o rd a m id a y o zish m u m ki n . 63 3.3. M a n tiqiy ifodalar n i soddalashtirish algorit m i. 1. Har bir daraxt ta n asi n i soddalashtirish n i n g ildizda n F - uchga borish n i realizatsiya qilish. 2. For m ulalashtirilga n shartlar ro’yxatida n tasvirla n ish qoidalari n i F- ga qo’llash. Eslata m izki , soddalashtirishlar ro’yxatida n tasvirla n ish qoidalari n i n otrivial qo’llash shu n da m u m ki n bo’ladi , qacho n ki hech bo’l m aga n da bitta daraxt ta n asi TRUE yoki FALSE o’zgar m aslarga soddalashsa. Har xil for m ulalar uchu n algorit mn i m aqsadga m uvofiq qo’lla n ilishi n i shu n day belgi bila n tasvirlay m iz va for m ulalar- ro’yxatiga tushu n cha bera m iz: for m ulalar-ro’yxati::={ m a n tiqiy-for m ula m a n tiqiy-for m ula , for m ulalar- ro’yxati} Tushu n arliki , agar for m ula n i n g yozilishida xatolar uchrasa , u n i soddalashtirish m u m ki n bo’l m ay qoladi. Shu n i n g uchu n qayta ishla n ga n dasturlar n i n g isho n chliligi n i ta’ m i n lash uchu n , u n i n g si n taktik to’g’riligi n i ko’rib chiqish kerak. Agar for m ula yozishda xatoga yo’l qo’yilsa , u holda quyidagi a m al n i bajarish kerak (bu a m al n i ERROR protsedurasida keltira m iz). 1). Xatoga m os keluvchi xabar n i chop etish; 2). Xato for m ulalar n i n g ha mm a belgilari n i o’tkazib yuborish; 3). Global m a n tiqiy o’zgaruvchi (u n i CO N TI deb atay m iz) uchu n shu n day fakt n i esda saqlash kerakki , bu o’zgaruvchi soddalashtirishda boshqa protseduralar ishi n i davo m ettira ol m asa , for m ulada xato m avjud bo’ladi. Shu n day qilib , m asala tahlili n atijasida biz quyidagi yechi m algorit m iga kela m iz: REPEAT CO N TI:=TRUE; ‘FOR M ULA N I N G BERILISHI:’ M AT N I N I CHOP ETISH; M AT N FOR M ULALARI VA U N I CHIQARISH N I O’QISH , ICHKI N A M OISH N I TARJI M A VA SI N TAKTIK TAHLILI; 64 IF FOR M ULALAR A N D N OT VA EOF DA N SO’ N G VERGUL BO’L M ASA THE N ERROR (‘AJRATUVCHI VERGUL M AS’) ; IF CO N TI THE N BEGI N DARAXT N I N G SODDALASHTIRISH FOR M ULALARI; ‘FOR M ULA N I SODDALASHTIRISH’ M AT N I N I CHOP ETISH; M AT N FOR M ULALARI N I U N I N G DARAXTI BO’YLAB CHIQARISH; E N D U N TIL EOF [1]. M a n tiqiy ifoda n i hisoblash n i qisqa yozuvlar bila n tasvirlovchi algorit mn i qaray m iz , bu n i n g uchu n I - ko’rsatkichli opera n dlar steki ( S O ) qo’lla n iladi , agar I - ko’rsatkich 1 ga te n g bo’lib , opera n dlar steki oli n adiga n holatlarda bo’sh bo’lsa , biri n chi ozod ishchi o’zgaruvchi n i n g tartibi j=1 bo’ladi. M a n tiqiy ifoda n i hisoblash n i n g algorit m i quyidagicha tuziladi: 1. Ifodalash n i n g qisqa yozuvida n n avbatdagi S - belgi n i olish; 2. Agar S - opera n d bo’lsa , u holda S n i CO[i] ga olib borish , i:=i+1 ga oshirish va 1 - ba n dga qaytish; aks holda 3 - ba n dga o’tish; 3. Agar S operatsiyalar belgisi bo’l m asa , 4 - ba n dga o’tish; aks holda , S R - operatsiya n i n g belgisi bo’lsa , quyidagi n i bajarish: 3 A. CO[i -k] , ... , CO[i -1] stek ele m e n tlari ichida ( k - R operatsiyadagi opera n dlar so n i) I - m i n i m al tartib bila n ishchi o’zgaruvchi n i topish. Agar qaralayotga n stek ele m e n tlari ichida ishchi o’zgaruvchi bo’l m asa , I = j ta’ m i n la n si n . 3 B. Ta m i n lash operatori n i n g m ashi n a ko m a n dalari n i yozish rj=R(CO[i -k] , ... , CO[i -1]) bu yerda R(x1 , ... , xk) — x1 , ... , xk opera n dlar orqali R - operatsiyada n oli n ga n n atija. 3 C. CO[i -k] da n r1 belgi n i olish. 3 D. i:=i+1 va j:=I+1 ta’ m i n la n si n . 1 - ba n dga qaytish. 65 4. Ifoda yozilishi o’chirilga n bo’lsa , hisoblash tugatiladi.Opera n dlar steki faqat r1 o’zgaruvchida n iborat bo’ladi, aks holda xatolar haqidagi m a’lu m otlar n i xatolar jadvaliga yozish kerak bo’ladi. M a n tiqiy ifoda xuddi belgilar n i n g kiruvchi qatorlari deb qaraladi , kiruvchi qatorlar chapda n -o’ n gga qarab yu n alga n bo’ladi.Opera n dlar chiquvchi qatorlarga yoziladi. Belgilar esa opera n dlar steki boshiga operatsiyalar n i joylashtiradi. Agar kiruvchhii belgi n olga te n g bo’lsa , ya’ n i stek uchiga yu n aluvchi belgi xususiyati n olga te n g bo’lsa , u n da stek uchiga ya n gi belgi qo’shiladi , boshqa hollarda stekda n “chiqarib tashla n adi” va chiquvchi qatorga belgi yoziladi. Asosiy aha m iyatga ega qavslar ustida qayta ishlash. Oddiy ochiq qavs “asosiy” n ol xususiyatga ega , shu n chaki , stek uchiga yoziladi va hech qa n day belgi n i chiqarib tashla m aydi. Oddiy yopilga n qavs esa ha mm a belgilar n i chiqarib tashlash n i chaqiradi to u n ga yaqi n roq ochiq qavs tugagu n cha. Stekda yopilga n qavs yozil m aydi. Ochiluvchi va yopiluvchi qavslar xuddi o’zaro yo’qotiladi va chiquvchi qatorga olib bor m aydi. Kiruvchi qatorlar n i n g ha mm a belgilari n i ko’rib chiqilga n da n so’ n g stekda qolga n belgilar chiqarib tashla n adi va chiquvchi qatorga yoziladi. 66 3.4. Dasturiy ta’minot tavsifi va undan foydalanish [7,13]. Dasturiy ta’minotni n g asosiy mazmuni quyidagidan iborat:  To’liq aniqlanmagan mantiqiy funksiya termlari (elementar konyunksiya yoki dizyunksiya) unga mos ikkilik kod shaklida kiritiladi;  Kiritilgan qiymatlar tekshiriladi ya’ni bull qiymatlaridan 0, 1, va ( – ) dan iborat bo’lishi kerak.  Berilgan funksiyaning qiymatlar to’plamining qism to’plamlari V 0 va V 1 lar aniqlanadi:  Bu V 0 va V 1 lar qism to’plamlari birlar va nollar ishtiroki soniga nisbatan guruhlarga ajratiladi;  V 0 dagi va V 1 dagi kombinatsiyalar ishlab chiqiladi.  V 0 va V 1 lar qism to’plamlari uchun birlashtirish amalini qo’llash uchun mumkin bo’lgan barcha solishtirishlar bajariladi;  V 1 ning birlashtirish amali natijasida hosil bo’lgan elementlarining har bir elementi va V 0 ning birlashtirish amali natijasida hosil bo’lgan elementlariga qo’shish amali bajariladi ;  Minimal dizyunktiv normal shaklni topish formulasi aniqlanadi .  Dasturga kiritilgan nomalum qiymatlar ya’ni chiziqchalar aniqlab beriladi. Kvayn – Mak-Klaski usulini takamillashtirgan holda to’liq aniqlanmagan funksiyalarni minimallashtirish dasturni ko ’ rib o’tdik. Dasturning muhim jihati ham yangiligi shundan iboratki bunda Mak-klaski usulida n ortishi bilan hisoblash murakkablashadi bizni dasturda shu muammoni hal qilishga yordam beradi . Bu dasturda kiritilgan to’liq aniqlanmagan qiymatlarni aniqlab b eradi va minimal DNShni formulasini topib beradi . Kvayn – Mak-Klaski usulining takomillashtirgan muhim jihatlarini 3.1-jadval asosida berilgan f funksiyani minimallashtirish jaroyonida ko’ramiz. 67 3.1 - jadval x 1 x 2 x 3 x 4 f 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0 - 1 - 1 - - 0 1 - - 0 - 0 - 1 Kvayna-Makklaski usulini takomillashtirgan holda tuzilgan algoritmi bo’yicha dasturini tuzib olamiz. Diskret qurilmalarni sintez qilish masalasida ularning ishlash faoliyatini mantiqiy funksiyalar sistemasi yordamida ifodalanadi. Bunda, kirish signallarining ba’zi qiymatlarida mantiqiy funksiyaning qiymati aniqlanmay qolishi mumkin. Bunday jarayonni ifodalovchi mantiqiy funksiya qisman yoki to’liq aniqlanmagan mantiqiy funksiya deyiladi. Kirish signallarini ma’lum bir qiymatlarini tanlash asosida funksiyani davom ettirish, ya’ni noaniqliklarini aniqlashtirishtiramiz. Minimal DNShning bitta qiymati topiladi va bu yetarli hisoblanadi. To’liq aniqlanmagan mantiqiy funksiyani minimalashtirish algoritmi sxemasi: 68 3.1-shakl Quyidagi algoritm sxemasi yordamida dastur tuzib olamiz. Dasturimiz quyidagi qadamlardan iborat bo’ladi. To’liq aniqlanmagan mantiqiy funksiya kiritiladi. Kiritilgan funksiya filtirlanadi. 69To’liq aniqlanmagan funksiyani kiritish N Natija va yechilish qadamlari chiqaradigan qilishFunksiyani to’la aniqlanadiChinlik jadvalini hosil qilish kbd Kvayna-Mak-klaski algoritmi bo’yicha minimal DNSh ni topish i Malumotlar filtirlanadi 3.1-rasm 1-qadamda. Berilgan funksiyaning qiymatlar to’plamining qism to’plamlari: V0 ning to’plamlari aniqlanadi. V0={0000, 0111, 1011, 1101} 3.2-rasm 2-qadam. Berilgan funksiyaning qiymatlar to’plamining qism to’plamlari: V 1 ning to’plamlari aniqlanadi. V 1 ={0010, 0100, 1000, 1111} 70 3.3-rasm 3-qadam. V 0 to’plamdagi har bir elementning 1 lar soni bo’yicha yoziladi. 3.4-rasm 4-qadam. V 1 to’plamdagi har bir elementning 1 lar soni bo’yicha yoziladi. 71 3.5-rasm 5-qadam. V 0 dagi kombinatsiyasi birlar soni bo’yicha yozib olinadi. 3.6-rasm 6-qadam. V 1 dagi kombinatsiyasi birlar soni bo’yicha yozib olinadi. 72 3.7-rasm 7-qadam.V 1 ning kombinatsiyadan hosil bo’lgan mos elementlariga V 0 ning har bir elementi qo’shib chiqiladi. 3.8-rasm 8-qadam. Minimal funksiyani topish formulasi aniqlanadi. 73 3.9-rasm 9-qadam. Topilgan minimal DNSh formulasi yuqorida ko’rinib turadi. 3.10-rasm 9-qadam. Funksiyani to’la aniqlangan qiymatlari ekranda ko’rinadi. 74 3.11-rasm 75 3.5. Dasturiy ta’minotni tadbiqi. Malumotlarni kiritish. Bizga n ta kirish qismi va 1 ta chiqishga ega bo’lgan diskret qurilmani loyilash kerak bo’lsin. Har bir kirish kanaliga 0 yoki 1 signali kiritilishi mumkin. Har bir kirish signallari to’plamiga diskret qurilma chiqishida 0,1 signali yoki ,, - “, ya’ni chiqish signali aniqlanmay qolishi mumkin. Bunday diskret qurilmani 3.4- r a sm . K o’ rinishd a t a svirl a sh mumkin v a qurilm a ni t o’ liq a niql a nm a g a n Bull funksiy a si o rq a li if o d a l a sh mumkin . 3.4-rasm ko’rinishidagi qurilma mantiqiy element deb ataladi. Mantiqiy element to’rtburchak ko’rinishida ifodalanib, to’rtburchak ichiga unga mos elementar funksiya yoziladi. Quyidagi 3.5-rasmda diskret qurilmalarni loyilashda qo’llaniladigan mantiqiy elementlar keltirilgan: Funksiya Chizmasi Funksiya Chizmasi¯x x 1 x 2 x1∨x2 x 1 ⇒ x 2 76 x 1 ⇔ x 2x1+x2 x1∨ x2 x1↑ x2 Ushbu m a ntiqiy elementl a rni birini chiqishini b o shq a sini kirishi bil a n b o g ’ l a b mur a kk a b diskret qurilm a h o sil qilish mumkin . Hosil qilingan murakkab qurilmaga qandaydir f(x1,x 2,… ,x n) mantiqiy funksiya mos keladi. Masalan, quyidagi mantiqiy sxemaga, f(x1,x 2,x 3,x 4)= (x1∨ x2)+(x3⇒ x4) funksiya mos keladi. 77 Xuddi shuningdek, berilgan mantiqiy funksiyaga mos sxemani ham hosil qilish mumkin. Masalan, berilgan f( x 1 , x 2 , x 3 ) = x 1 x 2 ∨ ( ¯x 3 ⇒ x 2 ) funksiyaga quyidagi sxema mos keladi: Ikkilik s o nni x k v a y k r a zry a dl a rini q o’ shib P k -1 kichik r a zry a dini k - r a zry a dg a sur a dig a n bir r a zry a dli ikkilik summ ator ni m a ntiqiy sxem a sini h o sil qilishni k o’ rib chiq a miz . S k - h o sil qilin a dig a n yig ’ indi , P k es a k a t a r a zry a dni surilishi b o’ lsin , und a quyid a gi chinlik j a dv a lini tuzish mumkin : xk yk Pk−1 Sk Pk 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 78 1 1 0 0 1 1 1 1 1 1 Ushbu chinlik jadvalidan Sk= xk ykPk-1 ∨ xk y k P k-1 ∨ xk y k P k-1 P k = x k y k P k − 1 ∨ x k y k k P k − 1 ∨ x k y k P k ∨ x k y k P k = x k y k ∨ ( x k ∨ y k ) P k − 1 fun ksiyalarni hosil qilamiz. Ushbu summatorga mos sxemani hosil qilish uchun avval S k , P k , funksiyalarni soddalashtirish lozim. S k , funksiyani soddalashtirish uchun P k minimal o’zgaruvchi sifatida qarab II-bobda berilgan usullardan foydalansak natijada ortiqcha qiymatlar satriga ega quyidagi jadval hosil bo’ladi: x k yk P k − 1 Pk Sk 0 0 0 0 0 0 0 0 1 - 0 0 1 0 1 0 0 1 1 - 0 1 0 0 1 0 1 0 1 - 0 1 1 0 - 0 1 1 1 0 1 0 0 0 1 1 0 0 1 - 1 0 1 0 - 1 0 1 1 0 1 1 0 0 - 1 1 0 1 0 1 1 1 0 - 1 1 1 1 1 79 Bu jadvaldan, Sk= xkykPk−1Pk∨xkykPk−1Pk∨xkykPk−1Pk∨xkykPk−1Pk hosil qilamiz. Ifodani soddalashtirib quyidagini hosil qilamiz: Sk=x kPk∨ ykPk∨ Pk-1 P k∨ xk y k P k-1 = (xk∨ yk∨ P k-1 )Pk∨ xk y k P k-1 bunda P k=x k y k∨ (xk∨ yk) P (k-1 )+ x kykpk-1 Endi mantiqiy sxemani tuzamiz: 80 XULOSA Dissertatsiya ishida mantiqiy funksiyalarni minimallashtirishning Mak- Klasku usulini takomillshtirib to’liq aniqlanmagan mantiqiy funksiyalarni minimallashtirishni amalga oshorish algoritmi va dasturiy ta’minotini ishlab chiqib, tanib olish va diskret qurilmalarni sintezlas h masalalarida qo’llashda iborat bo’lib, tadqiqot maqsadini amalga oshirish uchun us hbu vazifalar bajarilgan: 1. mantiqiy funksiyalarni minimallashtirish muammosi uni hal qilish bosqichlari ni tahlili; 2. mantiqiy funksiyalarni minimallashtirish m asala si ni yechish bilan bog’liq qoid a l a rni t a hlili ; 3. to’liq a niql a nm a g a n m a ntiqiy funksiy a l a rni minim a ll a shtirish a lgoritml a rini t a hlili; 4. t a hlil n a tij a l a rig a ko’r a hisobl a sh a lgoritmini ishl a b chiqish; 5. to’liq a niql a nm a g a n m a ntiqiy funksiy a l a rni minim a ll a shtirish a lgoritmi uchun d a sturiy t a ’minot y a r a tish; 6. dasturiy t a ’minotd a n foyd a l a nishning jih a tl a rini ko’rs a tildi. Tadqiqotning ilmiy yangiligi: dissertatsiyada to’liq aniqlanmagan mantiqiy funktsiyalarni minimallashtirishning Mak-klaski usulini takomillashtirilgan holda to’liq aniqlanmagan mantiqiy funktsiyalarni minimallashtirish algoritmi yaratilgan. Tadqiqotning amaliy ahamiyati: mantiqiy qarorlarni qabul qilish jarayonini tahlil asosida qiymati mavhum bo’lgan mantiqiy parametrlarni qiymatini aniqlashtirish, dasturiy ta’minotidan diagnostik tahlilni amalga oshirisda foydalanish mumkin. 81 FOYDALANILGAN ADABIYOTLAR RO’YXATI 1. H.T.To’rayev. I. Azizov. Matematik mantiq va diskret matematika, darslik, Toshkent, “Tafakkr-Bo’stoni”, 2011 y, [43-104]. 2. A.V. Kabulov, E. Urunbaev, I.I. Qalandarov, A.O. Ashurovlarnig “ Метoды синтезa oптимaльных кoрректoрoв эвристических aлгoритмoв нa oснoве функций k– знaчнoй лoгики ”. Тoшкент, Издaтельствo «Нaвруз» 2020. 3. Лютикoвa Л.A. и другие . Пoиск лoгических зaкoним ернoстей в дaнних с испoльзoвaнием сигмa-пи нейрoнних сетей . Ж: Прoгрaммирoвение системи и вичислительние метoди, 2017-3 т. 4. Журaвлев Ю.И. и другие . Aлгoритми aлгебрaическoй и лoгическoй кoррекции, и их при менения . Ж: Дискретний aнaлиз и вичеслительние метoди, 2012-4 т. 5. Прихoжиий A. A. Чaетичнo oпредленние лoгически системи и aлгoритми.Мoнoгрaфия. Минек, БНТУ, 2013. 6. Б. Н. Ивaнoв. Дискретнaя мaтемaтикa. Aлгoритмы и прoгрaммы. Учебнoе пoсoбие.-М.:Лaбoрaтoрия Бaзoвых Знaний, 2003, 288с. 7. Дискретнaя мaтемaтикa для прoгрaммистoв / Ф. A. Нoвикoв –СПб: Питер 2000. 304-с. 8. В.Н.Кaсянoв, В.К.Сaбелфелд. Сбoрник зaдaний пo прaктикуму нa ЕВМ, Учебнoе пoсoбие, Мoсквa, Нaукa, 1986 г, [184-233]. 9. Гaврилoв A.В. Системы искусственнoгo интеллектa. Ч.1. - Учебнoе пoсoбие, Нoвoсибирск: НГТУ, 2000. 10. Гaврилoвa Т.A., Хoрoшевский В.Ф. Бaзы знaний интеллектуaльных систем. - СпБ, Питер, 2000. 11. Oкулoв С. М. Прoгрaммирoвaние в aлгoритмaх / С. М. Oкулoв. — М.: БИНOМ. Лaбoрaтoрия знaний, 2004. — 341 с: ил. 12. R .SH. Mamatmurodov , J.M.Berdalov . Пр o изв o дн a я булев o й функции // “Zamonaviy axborot, kommunikatsiya texnologiyalari va at-ta’lim tatbiqi 82 muammolari” mavzusidagi respublika ilmiy-amaliy anjumani ma’ruzalar to‘plami. 7-8 aprel Toshkent 2023-yil 7-8 aprel , [ 284 - 286 ] 13. N.Abdirofiyev, R .SH. Mamatmurodov, M.Salimova . Метoд тaблицы рaзличии минимизaция слaбo oпределенные булевые функций. // “Zamonaviy axborot, kommunikatsiya texnologiyalari va at-ta’lim tatbiqi muammolari” mavzusidagi respublika ilmiy-amaliy anjumani ma’ruzalar to‘plami. 7-8 aprel Toshkent 2023-yil 7-8 aprel , [ 318 - 320 ] Internet sahifalar 1. http:// www.ziyonet.uz 2. http:// www.tuit.uz 3. http:// www.etuit.uz 4. http://www.delphi.support.uz/ 5. http:// www.delphi-manual.ru/ 6. http://www.embarcadero.com 7. http://www.camtasia-studio.ru.softonic.com/ 83

To‘liq aniqlanmagan bull funksiyasini minimallashtirish algoritmi va dasturiy ta’minoti

Купить