Mantiqiy funksiyalarning formulalar bilan ifodalanishiga quyidagi “muhandislik-konstruktiv” ma’no berilishi mumkin. Biz o'zboshimchalik bilan belgilangan to'plam ustidagi formulani "qora quti" sifatida ko'rib chiqamiz, o'zgaruvchan qiymatlarning barcha mumkin bo'lgan to'plamlari kiritiladigan qurilmaning bir turi va formula bilan ifodalangan funktsiya qiymatlari. chiqishda paydo bo'ladi (6.22-rasm).
"Qora quti" qanday ishlashini tushunish uchun biz kichik formulalardan formula yaratish jarayonini tahlil qilishimiz kerak. "Asosiy" kichik formulalarga o'tish, ya'ni. to'plamning elementlari , biz "g'ishtlarga", "qora quti" yig'ilgan tizimli elementlarga kelamiz, bu funktsiyani hisoblab chiqadi . “Asosiy”ning har bir funksiyasi “qora quti”mizning eng kichik struktura birligi hisoblangan tegishli “tugun” tomonidan hisoblab chiqiladi va uning ichki tuzilishi endi tahlil qilinmaydi.
6.22-misol. Keling, standart asosni to'plam sifatida tanlaymiz. Keyin funktsiyani (ekvivalentlikni) ifodalovchi standart asos bo'yicha formula quyidagicha tuziladi:
Ushbu formula bo'yicha hisoblash (va uni standart asosning elementlaridan qurish jarayoni) rasmda ko'rsatilganidek, sxematik tarzda tasvirlanishi mumkin. 6.23.
O'zgaruvchi (aniqrog'i, bu o'zgaruvchining qiymati) inverter (6.24-rasm, a) deb ataladigan strukturaviy elementning kirishiga va inkorni hisoblashga beriladi. İnvertorning chiqishidan olib tashlangan inkor, ya'ni. funktsiyasi , konyunktorning kirishlaridan biriga beriladi (6.24.5-rasm), uning ikkinchi kirishi o'zgaruvchi bilan ta'minlanadi. Funktsiya konyunktorning chiqishida paydo bo'ladi. Funktsiyani hisoblash ham xuddi shunday kuzatilgan. Bu funksiyalarning ikkalasi disjunktorning kirishlariga beriladi (6.24-rasm, s), uning chiqishidan funksiya olib tashlanadi (bu yig'indisi moduli 2 :) dan boshqa narsa emas). Va nihoyat, bu funktsiya inverterning kirishiga beriladi, uning chiqishida funktsiya (ekvivalentlik) allaqachon olingan.
Shunday qilib, biz "sxema" g'oyasiga keldik - har biri "asosiy" mantiqiy funktsiyalardan birini hisoblaydigan strukturaviy elementlardan yig'ilgan ba'zi formulalar bilan ifodalangan mantiqiy funktsiya kalkulyatorining matematik modeli. Umumiy holatda "sxema" mantiqiy operatorni hisoblab chiqadi va bu operatorning har bir koordinata funktsiyasi sxemaning chiqishlaridan biridan olinadi.
Matematik nuqtai nazardan, "sxema" yo'naltirilgan grafikning maxsus turi sifatida ta'riflanadi, unda cho'qqilar ham, yoylar ham ba'zi belgilar bilan ta'minlangan.
Belgilashni kiritamiz: agar mantiqiy funktsiyalar to'plami bo'lsa, biz o'zgaruvchilarning barcha funktsiyalaridan iborat bo'lgan kichik to'plam bilan belgilaymiz.
Ta'rif 6.14. To'plamlar: (Mantiqiy funktsiyalar) va (Mantiqiy o'zgaruvchilar) o'zgarmas bo'lsin.
Funktsional elementlarning bazis ustidagi sxemasi (CFE) yoki oddiygina bazis ustidagi sxema, shuningdek (F,X) sxemasi kontursiz yo‘naltirilgan grafik (ya’ni tarmoq) bo‘lib, uning har bir uchi quyidagi belgilar bilan belgilanadi. to'plamning elementlaridan biri, shunda quyidagilar to'g'ri bo'ladi: talablar:
1) tarmoqning har bir kirishi yoki dan ba'zi o'zgaruvchisi yoki dan ba'zi bir doimiysi bilan etiketlanadi;
2) agar tarmoqning v cho‘qqisi o‘zgaruvchilar funksiyasi (ya’ni ) bilan belgilangan bo‘lsa, uning kirish yarim gradus ga teng bo‘ladi va cho‘qqiga kiruvchi yoylar to‘plamida (birga bir) raqamlash beriladi, bunda har bir yoy 1 dan ga qadar raqam oladi.
Sxemalarni tasvirlashda kirishlar doiralar bilan, kirish bo'lmagan cho'qqilar esa uchburchaklar bilan ko'rsatiladi, ularning ichiga berilgan cho'qqini belgilovchi funktsiyaning belgilanishi yoziladi. Chiqish joylari "chiqish" strelkalari bilan belgilanadi. Shaklda. 6.25 SFE asosini ko'rsatadi.
Agar asos nazarda tutilgan bo'lsa, biz shunchaki "sxema" deb aytamiz. Bundan tashqari, agar o'zgaruvchilar to'plami "bir marta va umuman" sobit bo'lsa va turli xil sxemalarni ko'rib chiqayotganda, biz faqat funktsiyalar to'plamini o'zgartiramiz, keyin formula va superpozitsiya tushunchalarini ma'lum asosda kiritganimizda bo'lgani kabi, biz SFE haqida so'z boradi, har safar o'rnatish bir marta belgilangan o'zgaruvchilar to'plamidir, bu esa (agar bu aniqlikka zarar bermasa) eslatilmaydi.
Keling, induksiya orqali sxema cho'qqisi bilan hisoblangan mantiqiy funktsiya tushunchasini aniqlaylik.
Ta'rif 6.15. Bazis ustida SFE berilgan bo'lsin, uning uchlari to'plami.
1. Har bir SFE kiritishi u etiketlangan mantiqiy funktsiyani (ya'ni, ba'zi o'zgaruvchi yoki doimiy) hisoblaydi deb taxmin qilinadi.
2. Agar cho'qqi funksiya bilan belgilangan bo'lsa, unga kiruvchi raqam bilan yoy funktsiyani hisoblaydigan cho'qqidan keladi, keyin v tepasi superpozitsiyani hisoblaydi.
Shunday qilib, agar CFE ustidagi har bir cho'qqi ba'zi funktsiyani hisoblasa, u holda funktsiya o'zgaruvchilari o'rniga qo'yilgan funktsiyalarni ro'yxatga olish tartibi, umumiy holda, muhim ahamiyatga ega. Agar o'zgaruvchilarning ixtiyoriy almashtirilishida o'z qiymatini saqlab qolsa, o'zgaruvchilarning mantiqiy funktsiyasini kommutativ deb atash tabiiydir. Bunday holda, biz bunday funktsiya bilan belgilangan sxema cho'qqisiga kiruvchi yoylarni raqamlash haqida qayg'urmasligimiz mumkin.
6.23-misol. Keling, rasmda SFEni ko'rib chiqaylik. 6.25. Cho'qqilar va SFE ning kirishlari. Bu uchlari mos ravishda va funksiyalarini hisoblab chiqadi. Keyin cho'qqi , shuningdek, 6.15 ta'rifiga ko'ra, tepalik funktsiyani (Scheffer zarbasi) hisoblaydi va cho'qqi (tarmoq chiqishi) funktsiyani hisoblab chiqadi, ma'lumki, bu birikmaga teng.
SFE shaklda ko'rsatilgan. 6.26 ikkita chiqishga ega, hisoblash funktsiyalari va .
Ta'rif 6.16. SFE tomonidan asos bo'yicha hisoblangan mantiqiy funktsiya uning har qanday chiqishi bilan hisoblangan funktsiyadir.
Shunday qilib, SFE qancha mantiqiy funktsiyaga ega bo'lsa, shuncha ko'p hisoblaydi. Shaklda SFE. 6.25 bitta funktsiyani hisoblaydi va shakldagi SFE. 6.26 - ikkita.
Umumiy holatda, agar m chiqishga ega bo'lgan bazis ustidagi kontaktlarning zanglashiga olib kirishlari uchun yorliqlar bo'lib xizmat qiladigan barcha o'zgaruvchilar to'plami bo'lsa, CFE mantiqiy kubni Boole kubiga xaritalashni aniqlaydi, ya'ni. mantiqiy operator.
Izoh 6.10. Ba'zi hollarda, berilgan CFE tomonidan hisoblangan funksiya bir oz boshqacha aniqlanadi, chunki u tanlangan CFE cho'qqilarining kichik to'plamidan istalgan cho'qqi tomonidan hisoblangan funktsiyadir. Xususan, bu chiqishlar bo'lishi mumkin. Har qanday holatda, keling, sxemaning tanlangan (hozirgi ko'rsatilgan ma'noda) uchlaridan "chiqish" o'qini chizishga rozi bo'laylik.
Shunday qilib, funktsional elementlarning har bir sxemasi qandaydir mantiqiy operatorni hisoblab chiqadi, xususan, sxemaning chiqishlari soni 1 bo'lsa, u holda u qandaydir mantiqiy funktsiyani hisoblaydi.
Buning aksini ham isbotlash mumkin: har qanday mantiqiy operator uchun SFE baza asosida tuzilishi mumkin, bu operatorni hisoblaydigan to'liq to'plam bu erda.
6.24-misol. Jadvalni mantiqiy operatorga moslashtiramiz (6.9-jadval).
Jadvaldan buni ko'rish oson (funktsiya o'zgaruvchilarning ko'pchilik funktsiyasidan boshqa narsa emas va u uchun minimal DNF yuqorida yozilgan, 6.12-misolga qarang). Funktsiyani Jegalkin asosida ifodalaylik. De Morgan qonunlaridan foydalanib, biz olamiz
Buni hisobga olsak, bizda bo'ladi
(esda tutingki, har qanday juft sonli hadlarning yig'indisi 2 moduli 0 ga teng). Shunday qilib,
Jadvalda ko'rsatilgan mantiqiy operator uchun SFE. 6.9, Jegalkin asosidagi shaklda ko'rsatilgan. 6.27.
SPVni loyihalashda uning murakkabligi deb ataladigan raqamli parametrni yodda tutish foydali bo'ladi.
SFE ning murakkabligi uning kirish nuqtasi bo'lmagan uchlari sonidir.
Shaklda ko'rsatilgan. 6.27 Zhegalkin asosidagi CFE 5 murakkablikka ega.
Keling, standart asosda bir xil operator uchun CFE ni ko'rib chiqaylik. Jadvalga ko'ra (6.9-jadvalga qarang), biz funktsiya uchun SDNF quramiz
Ushbu funktsiya uchun Karno xaritasi rasmda ko'rsatilgan. 6.28 uni minimallashtirish mumkin emasligini ko'rsatadi (aniqrog'i, yuqorida yozilgan SDNF bu funktsiya uchun minimal DNF).
Ammo siz boshqa yo'l bilan borishingiz mumkin. Jadvalni ko'rib chiqishimiz mumkin. 6.9 qisman mantiqiy funktsiyani belgilaydigan jadval sifatida. Rasmda ko'rsatilgan Carnot xaritasi* bo'yicha ushbu funktsiyani minimallashtirish. 6.29, biz olamiz
*Ushbu xaritada funksiya 0 qiymatini oladigan to‘plamlarni tegishli katakchalarga nol qo‘yish orqali aniq belgilab oldik. Shunday qilib, biz yana bir bor e'tiborni nollarni tire bilan aralashtirib yubormaslik kerakligiga qaratmoqchimiz: qisman funktsiyani belgilaydigan xaritaning katakchasidagi chiziqcha bu to'plamda funktsiyaning qiymati aniqlanmaganligini anglatadi, ya'ni. 0 ham, 1 ham emas.
Ko'rib chiqilayotgan mantiqiy operator uchun standart asos bo'yicha SFE rasmda ko'rsatilgan. 6.30. Ushbu CFE ning murakkabligi 11. Funktsiyani baholaydigan tugun chiqish emasligini unutmang.
Ushbu misolda muhokama qilingan mantiqiy operator uchta bir xonali atamaning ikki xonali yig'indisini (modul 2) hisoblab chiqadi. Buni bir bitli ikkilik qo'shimchalar - ko'p bitli ikkilik qo'shimchalarning funktsional bloki - ikki atama uchun ham hisoblash mumkin. Keyin r/1 funktsiyasi eng muhim bitga "tashuvchi signal" sifatida talqin qilinadi. Shaklda. 6.31-rasmda ikkita uch xonali ikkilik sonlarning yig'indisini hisoblaydigan uchta SFEning (masalan, 6.30-rasmda ko'rsatilgandek) "ulanish" ko'rsatilgan. Eng kam ahamiyatli bit uchun qo'shimchaning uchinchi kirishiga doimiy 0 qo'llaniladi va eng muhim bitning "tashuvchi signali" yig'indining eng muhim biti bo'lib, u umumiy holatda to'rt xonali son bo'ladi. .
Mantiqiy funksiyalarning formulalar bilan ifodalanishiga quyidagi “muhandislik-konstruktiv” ma’no berilishi mumkin. Biz F(x 1 ,..., xn) formulasini baʼzi bir oʻzboshimchalik bilan oʻrnatilgan F toʻplamini “qora quti” sifatida, kirishda barcha mumkin boʻlgan oʻzgaruvchan qiymatlar toʻplamini va qiymatlarni qabul qiluvchi qurilma turi sifatida koʻrib chiqamiz. Ushbu to'plamlarga mos keladigan f funktsiyasi F formulasi bilan ifodalangan chiqishda paydo bo'ladi (6.22-rasm).
"Qora quti" qanday ishlashini tushunish uchun biz kichik formulalardan formula yaratish jarayonini tahlil qilishimiz kerak. "Asosiy" kichik formulalarga o'tish, ya'ni. F to'plamining elementlari, biz f funktsiyasini hisoblaydigan "qora quti" yig'ilgan "g'ishtlarga", strukturaviy elementlarga kelamiz. "Asosiy" F ning har bir funksiyasi bizning "qora quti" mizning eng kichik tarkibiy birligi hisoblangan tegishli "tugun" tomonidan hisoblanadi va uning ichki tuzilishi endi tahlil qilinmaydi.
6.22-misol. Keling, F to'plami sifatida standart bazani tanlaylik. Keyin ~ (ekvivalentlik) funktsiyasini ifodalovchi standart asos ustidagi formula quyidagicha tuziladi:
Ushbu formula bo'yicha hisoblash (va uni standart asosning elementlaridan qurish jarayoni) rasmda ko'rsatilganidek, sxematik tarzda tasvirlanishi mumkin. 6.23.
O'zgaruvchi x 1 (aniqrog'i, bu o'zgaruvchining qiymati) inverter (6.24-rasm, a) deb ataladigan strukturaviy elementning kirishiga va inkorni hisoblashga beriladi. Invertorning chiqishidan olib tashlangan x 1 inkori, ya'ni. x 1 funktsiyasi, konyunktorning kirishlaridan biriga beriladi (6.24-rasm, b), ikkinchi kirishi x 2 o'zgaruvchisi bilan ta'minlanadi. Konyunktorning chiqishida x 1 x 2 funksiyasi paydo bo'ladi. Xuddi shunday x 1 x 2 funksiyaning hisobi ham kuzatiladi.Bu funksiyalarning har ikkalasi disjunktorning kirishlariga beriladi (6.24-rasm, s), uning chiqishidan x 1 x 2 ∨ x 1 x 2 funksiyasi chiqadi. o'chiriladi (bu 2 yig'indisi modulidan boshqa narsa emas: x 1 ⊕ x 2). Va nihoyat, bu funktsiya inverterning kirishiga beriladi, uning chiqishida ~ (ekvivalentlik) funktsiyasi allaqachon olingan. #
Shunday qilib, biz "sxema" g'oyasiga keldik - har biri "asosiy" mantiqiy funktsiyalardan birini hisoblaydigan strukturaviy elementlardan yig'ilgan ba'zi formulalar bilan ifodalangan mantiqiy funktsiya kalkulyatorining matematik modeli. Umumiy holatda "sxema" mantiqiy operatorni hisoblab chiqadi va bu operatorning har bir koordinata funktsiyasi sxemaning chiqishlaridan biridan olinadi.
Matematik nuqtai nazardan, "sxema" yo'naltirilgan grafikning maxsus turi sifatida ta'riflanadi, unda cho'qqilar ham, yoylar ham ba'zi belgilar bilan ta'minlangan.
Belgilanishni kiritamiz: agar F mantiqiy funktsiyalar to'plami bo'lsa, u holda F (n) orqali biz F ning n ta o'zgaruvchining barcha funktsiyalaridan iborat (n≥0) kichik to'plamini belgilaymiz.
Ta'rif 6.14. To'plamlar o'zgarmas bo'lsin: F (mantiqiy funktsiyalar) va X (mantiqiy o'zgaruvchilar).
Funktsional elementlarning asos bo'yicha sxemasi F ∪ X (S F E), yoki oddiygina F ∪ X asosi ustidagi qisqarish, shuningdek, (F,X)-sxema, kontursiz yo'naltirilgan grafik (ya'ni, tarmoq) deb ataladi, uning har bir uchi quyidagi belgilar bilan belgilanadi. FU X to'plamining elementlaridan biri quyidagi talablarga javob beradi:
- tarmoqning har bir kirishi yoki X dan bir oz o'zgaruvchi bilan yoki F (0) dan ba'zi bir konstanta bilan etiketlanadi;
- agar tarmoqning v cho‘qqisi n ta o‘zgaruvchining f funksiyasi (ya’ni, f ∈ F (n)) bilan belgilansa, u holda uning darajasi n ga teng, v cho‘qqisiga kiruvchi yoylar to‘plamida esa ( birma-bir) raqamlash shundayki, har bir yoy 1 dan n gacha raqam oladi.
Agar asos nazarda tutilgan bo'lsa, biz shunchaki "sxema" deb aytamiz. Bundan tashqari, agar o'zgaruvchilar to'plami "bir marta va hamma uchun" qat'iy belgilangan bo'lsa va turli sxemalarni ko'rib chiqayotganda, biz faqat F funktsiyalar to'plamini o'zgartiramiz, u holda formula va superpozitsiya tushunchalarini berilgan asosda kiritganimizda bo'lgani kabi, Biz har bir vaqtni belgilashda F asosi bo'yicha CFE haqida gaplashamiz, bu X o'zgaruvchilarning bir marta belgilangan to'plamini nazarda tutadi, (agar u aniqlikka zarar bermasa) eslatilmaydi.
Endi biz tushunchani induksiya orqali aniqlaymiz mantiqiy funktsiya sxemaning tepasi tomonidan hisoblangan .
Ta'rif 6.15. SFE berilsin S F ∪ X asosi ustida, uning cho'qqisi to'plami V bo'ladi.
- Har bir SFE kiritishi u etiketlangan mantiqiy funktsiyani (ya'ni, ba'zi o'zgaruvchi yoki doimiy) hisoblaydi deb taxmin qilinadi.
- Agar v ∈ V cho‘qqisi f ∈ F (n) funksiya bilan belgilansa, unga kiruvchi i (1≤i≤n) raqamiga ega yoy gi funksiyasini hisoblaydigan ui ∈ V cho‘qqisidan keladi, u holda v cho‘qqisi hisoblaydi. superpozitsiya f(g 1 , ...,gn).
Shunday qilib, agar F ustidagi har bir CFE cho'qqisi qandaydir funktsiyani hisoblasa, u holda f funktsiyaning o'zgaruvchilari o'rniga qo'yilgan g 1 , ...,g n funktsiyalari ro'yxatga olish tartibi umumiy ahamiyatga ega. n ta o'zgaruvchidan iborat bo'lgan mantiqiy funktsiya f o'zgaruvchilarning ixtiyoriy almashtirilishida o'z qiymatini saqlab qolsa, uni kommutativ deb atash tabiiy. Bunday holda, biz bunday funktsiya bilan belgilangan sxema cho'qqisiga kiruvchi yoylarni raqamlash haqida qayg'urmasligimiz mumkin.
6.23-misol. Keling, rasmda SFEni ko'rib chiqaylik. 6.25. v 1 va v 2 uchlari SFE ning kirishlari hisoblanadi. Bu uchlari mos ravishda x va y funksiyalarini hisoblab chiqadi. Keyin v 3 cho'qqisi, shuningdek, v 4 cho'qqisi, 6.15 ta'rifiga ko'ra, x|y funksiyasini (Sxeffer zarbasi) va v 5 cho'qqisi (tarmoq chiqishi) (x|y)l() funktsiyasini hisoblaydi. x|y), bu x · y birikmasiga teng ekanligi ma'lum.
SFE shaklda ko'rsatilgan. 6.26, (x|x)|(y|y) = x ∨ y va (x|y)|(x|y) = x·y funktsiyalarini hisoblaydigan ikkita chiqishga ega.
Ta'rif 6.16. SFE tomonidan hisoblangan mantiqiy funktsiya F ∪ X asosi bo'yicha, har qanday chiqishi bilan hisoblangan funktsiya.
Shunday qilib, SFE aniq stmko mantiqiy funktsiyalarni hisoblab chiqadi, qancha natijalarga ega. Shaklda SFE. 6.25 bitta funktsiyani hisoblaydi va shakldagi SFE. 6.26 - ikkita.
Umuman olganda, agar (x 1 ,..., x n ) kontaktlarning zanglashiga olib kirishlari uchun yorliq boʻlib xizmat qiluvchi barcha oʻzgaruvchilar toʻplami boʻlsa. S m chiqishga ega bo'lgan F ∪ X asosida, CFE S mantiqiy kubning ko'rinishini belgilaydi B n mantiqiy kubga B m , ya'ni. mantiqiy operator.
Izoh 6.10. Ba'zi hollarda, berilgan CFE tomonidan hisoblangan funksiya bir oz boshqacha aniqlanadi, chunki u tanlangan CFE cho'qqilarining kichik to'plamidan istalgan cho'qqi tomonidan hisoblangan funktsiyadir. Xususan, bu chiqishlar bo'lishi mumkin. Har qanday holatda, keling, sxemaning tanlangan (hozirgi ko'rsatilgan ma'noda) uchlaridan "chiqish" o'qini chizishga rozi bo'laylik. #
Shunday qilib, funktsional elementlarning har bir sxemasi qandaydir mantiqiy operatorni hisoblab chiqadi, xususan, sxemaning chiqishlari soni 1 bo'lsa, u holda u qandaydir mantiqiy funktsiyani hisoblaydi.
Buning aksini ham isbotlash mumkin: har qanday mantiqiy operator uchun SFE F bazis ustida tuzilishi mumkin, bu erda F berilgan operatorni baholovchi to'liq to'plamdir.
y 1 funksiyani Jegalkin asosida ifodalaylik. De Morgan qonunlaridan foydalanib, biz olamiz
(esda tutingki, har qanday juft sonli hadlarning yig'indisi 2 moduli 0 ga teng).
y 1 \u003d x 1 x 2 ⊕ x 1 x 3 ⊕ x 2 x 3 \u003d x 1 x 2 ⊕ x 3 (x 1 ⊕ x 2).
Jadvalda ko'rsatilgan mantiqiy operator uchun SFE. 6.9, Jegalkin asosidagi shaklda ko'rsatilgan. 6.27.
SPVni loyihalashda uning murakkabligi deb ataladigan raqamli parametrni yodda tutish foydali bo'ladi.
SFE ning murakkabligi uning kirish bo'lmagan uchlari soni.
Shaklda ko'rsatilgan. 6.27 Zhegalkin asosidagi CFE 5 murakkablikka ega.
Keling, standart asosda bir xil operator uchun CFE ni ko'rib chiqaylik.
Jadvalga muvofiq (6.9-jadvalga qarang), biz y 2 funktsiyasi uchun SDNF ni quramiz:
y 2 \u003d x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3 ∨ x 1 x 2 x 3.
Ushbu funktsiya uchun Karno xaritasi rasmda ko'rsatilgan. 6.28 uni minimallashtirish mumkin emasligini ko'rsatadi (aniqrog'i, yuqorida yozilgan SDNF bu funktsiya uchun minimal DNF). Ammo siz boshqa yo'l bilan borishingiz mumkin. Jadvalni ko'rib chiqishimiz mumkin. 6.9 qisman mantiqiy funktsiyani belgilovchi jadval sifatida y 2 = y 2 (x 1 x 2 x 3 y 1). Ushbu funktsiyani minimallashtirish orqali
Karno xaritasi* rasmda tasvirlangan. 6.29, biz olamiz
* Ushbu xaritada biz mos keladigan katakchalarga nol qo'yish orqali funktsiya 0 qiymatini oladigan to'plamlarni belgilab oldik. Shunday qilib, biz yana bir bor e'tiborni nollarni tire bilan aralashtirib yubormaslik kerakligiga qaratmoqchimiz: qisman funktsiyani belgilaydigan xaritaning katakchasidagi chiziqcha bu to'plamda funktsiyaning qiymati aniqlanmaganligini anglatadi, ya'ni. 0 ham, 1 ham emas.
y 2 \u003d x 1 x 2 x 3 ∨ y 1 (x 1 ∨ x 2 ∨ x 3).
Ko'rib chiqilayotgan mantiqiy operator uchun standart asos bo'yicha SFE rasmda ko'rsatilgan. 6.30. Ushbu CFE ning murakkabligi 11. E'tibor bering, y 1 funktsiyasini hisoblaydigan tugun chiqish emas.
Ushbu misolda muhokama qilingan mantiqiy operator uchta bir xonali atamaning ikki xonali yig'indisini (modul 2) hisoblab chiqadi. Buni bir bitli ikkilik qo'shimchalar - ko'p bitli ikkilik qo'shimchalarning funktsional bloki - ikki atama uchun ham hisoblash mumkin. Keyin y 1 funksiyasi yuqori tartibli "tashuvchi signal" sifatida talqin qilinadi. Shaklda. 6.31-rasmda ikkita uch xonali ikkilik sonlarning yig'indisini hisoblaydigan uchta SFEning (masalan, 6.30-rasmda ko'rsatilgandek) "ulanish" ko'rsatilgan. Eng kam ahamiyatli bit uchun qo'shimchaning uchinchi kirishiga doimiy 0 qo'llaniladi va eng muhim bitning "tashuvchi signali" yig'indining eng muhim biti bo'lib, u umumiy holatda to'rt xonali raqam bo'ladi. .
Izoh 6.11. Agar biz SFE ni standart asosda loyihalashtirayotgan bo'lsak va uning murakkabligini minimallashtirishni istasak, avvalo mos keladigan minimal DNF ni qurishimiz kerak. Bunday holda, biz DNFning o'zi minimallashtiriladigan yana bir mezonni hisobga olishimiz mumkin - inkorlar soni. Barcha minimal (6.6 ta'rifi ma'nosida) DNFlar orasida inkor belgisi ostida o'zgaruvchilarning paydo bo'lish soni eng kichik bo'lganlarini tanlash kerak. Minimal DNF bo'yicha quriladigan CFE ning murakkabligi nuqtai nazaridan, bu "invertorlar" sonini - inkor qilish funktsiyasi bilan belgilangan CFE tepaliklarini minimallashtirishni anglatadi.
Masalan, Karno xaritasi (6.32-rasm) tomonidan berilgan funksiya uchun x 1 x 2 x 4 va x 1 x 3 x 4 oddiy implikantlardan iborat yadroga oddiy implikant x 2 x 3 x 4 qo'shilishi kerak. , va x 1 x 2 x 3 emas, chunki unda inkorlar mavjud emas.
Hajmi: px
Taassurotni quyidagi sahifadan boshlang:
transkript
1 Ma'ruza 2. Funktsional elementlarning (SFE) qandaydir asosda sxemalari. Sxemaning murakkabligi va chuqurligi. Misollar. DNF tomonidan SFE sintezi usuli. Ma’ruzachi – dotsent Svetlana N. Selezneva Diskret matematikadan ma’ruzalar 2. 1-kurs, 141-guruh Lomonosov ma'ruzalari saytida
2 Funktsional elementlardan sxemalar Funktsional elementlardan sxemalarni qandaydir asosda aniqlaylik. B = (g 1 (x 1,..., x n1),..., gs (x 1,..., x ns)) mantiqiy funktsiyalarning ba'zi to'plami berilsin, P 2, bu erda n 1, .. ., ns 0. Bu to‘plamni bazis deb ataymiz. E'tibor bering, bu asos tushunchasi mantiq algebrasida ko'rib chiqilgan P 2 asos tushunchasi bilan hech qanday aloqasi yo'q. Qoida tariqasida, biz standart asosni ko'rib chiqamiz B 0 = (x&y, x y, x).
3 Funksional elementlar sxemasining ta’rifi B 0 = (x&y, xy, x) asosidagi funksional elementlar sxemasi (SFE) 1) yo‘naltirilgan asiklik grafik G = (V, E), har bir cho‘qqisi v V bo‘ladi. ikki (d (v) 2) dan oshmaydigan d (v) darajasiga ega; 2) 0 (d (v) = 0) ga teng darajali har bir v uchi kirish (yoki sxema kiritish) deb ataladi va unga ba'zi mantiqiy o'zgaruvchi x i tayinlanadi; 3) barcha boshqa uchlari (kirishlardan tashqari) sxemaning ichki uchlari deyiladi;
4 Funktsional elementlardan sxemani aniqlash (davomi) 4) 1 (d (v) = 1) ga teng darajali har bir v uchiga (funktsional) inkor elementi beriladi; barcha bunday cho'qqilar invertorlar deb ataladi; 5) 2 ga teng (d (v) = 2) ga teng bo'lgan har bir v cho'qqisiga (funktsional) birikma elementi & yoki (funktsional) ajratish elementi tayinlanadi; bog‘lovchining elementlari biriktirilgan barcha cho‘qqilar bog‘lovchilar, ayiruvchining elementlari biriktirilgan barcha cho‘qqilar ayiruvchi deyiladi;
5 Funksional elementlardan sxema ta’rifi (davomi) 6) qo’shimcha ravishda ba’zi cho’qqilarga y 1,..., y m juftlik bilan har xil chiqish o’zgaruvchilari tayinlanadi. Agar kirishlari faqat x 1,..., xn oʻzgaruvchilari va chiqish oʻzgaruvchilari y 1,..., ym boʻlgan CFE S berilgan boʻlsa, biz bu CFEni S(x 1,.) bilan belgilaymiz. .., xn ; y 1,...,ym).
6 SFE misoli 1-misol. SFE S(x 1, x 2, x 3 ; y 1, y 2, y 3):
7 SFE misoli 1-misol. Qoida tariqasida, SFE quyidagicha tasvirlangan S(x 1, x 2, x 3; y 1, y 2, y 3):
8 CFE ning murakkabligini aniqlash CFE S ning murakkabligi L (S) - bu CFE ning ichki uchlari soni, ya'ni. SFE S dagi funktsional elementlarning soni.
9 SPE ning murakkabligi 2-misol. SPE S ning murakkabligi:
10 CFE cho'qqisining chuqurligini aniqlash Induksiya yo'li bilan CFE S da v cho'qqisining chuqurligini d(v) aniqlaymiz. 1. Induksiya asoslari. SPS ning har bir v kirishi 0 ga teng chuqurlikka ega: d(v) = Induktiv o'tish. 1) Agar v 1 uchidan yoy invertor v CFE S ga olib borsa, u holda d(v) = d(v 1)) Agar v 1 va v 2 uchlaridan yoylar konyunktor yoki v CFE S ajratgichga olib borsa, u holda d. (v) = max(d(v 1), d(v 2)) + 1. CFE S ning chuqurligi D(S) uning uchlari chuqurliklarining maksimali.
11 SPE chuqurligi 3-misol. SPE cho‘qqisining chuqurligi S va SPE chuqurligi S:
12 SFE ning ishlashini aniqlash SFE ning har bir cho'qqisida ma'lum mantiqiy funktsiya amalga oshiriladi (yoki hisoblab chiqiladi). Induksiya orqali biz CFE S ning v tepasida amalga oshiriladigan mantiqiy funktsiyani aniqlaymiz. 1) Agar v kirish cho'qqisi bo'lsa va unga xi o'zgaruvchisi tayinlangan bo'lsa, fv = xi funksiya v cho'qqisida amalga oshiriladi. . 2) Agar v 1 uchidan yoy invertor v ga olib kelsa va f v1 funksiyasi v 1 cho’qqisida amalga oshsa, f v = f v1 funksiya v cho’qqisida amalga oshadi. 3) Agar v 1 va v 2 uchlaridan yoylar konyunktorga (yoki ajratuvchiga) v olib kelsa va f v1 va f v2 funksiyalari mos ravishda v 1 va v 2 uchlarida amalga oshirilsa, fv = f v1 &f funksiyasi. v2 (mos ravishda fv = f v1 f v2).
13 SFE ning ishlashi SFE S(x 1,..., xn ; y 1,..., ym) mantiqiy funktsiyalar tizimini FS = (f 1,..., fm ) amalga oshiradi, deb ishoniladi. uning chiqish uchlarida y 1,..., ym.
14 SFE ning ishlashi 4-misol. SFE S tepalarida amalga oshirilgan mantiqiy funktsiyalar: F S = (x 3, x 1 x 2, x 1 x 2 x 3).
15 Chiziqli dastur B 0 = (x&y, xy, x) asosidagi x 1,..., xn kirishlari bo‘lgan chiziqli dastur z 1, z 2,..., zt ketma-ketlik bo‘lib, unda har bir j soni uchun , j = 1,..., t, 1) yoki zj = xi ; 2) k uchun yoki z j = z k< j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.
16 CFE va chiziqli dasturlar CFEda hisoblashni chiziqli dastur shaklida qayta yozish mumkinligi aniq. Va aksincha, har bir chiziqli dastur ma'lum bir CFE sifatida ifodalanishi mumkin.
17 SFE va chiziqli dasturlar 5-misol. SFE S z 1 = x 1 &x 2, z 2 = x 3, z 3 = z 1 z 2 chiziqli dasturga mos keladi.
18 SFE va ularning xarakteristikalari Funktsional elementlarning sxemalari hisoblash modelidir. Biz kiritgan SPE xarakteristikalari hisoblash samaradorligining turli jihatlarini ko'rsatadi. SFE ning murakkabligi ketma-ket hisoblash vaqtiga to'g'ri keladi. SPE ning chuqurligi parallel hisoblash vaqtiga to'g'ri keladi. CFEda bir xil chuqurlikdagi cho'qqilarning maksimal soni parallel hisoblashda protsessorlar soniga to'g'ri keladi.
19 Misol: ikki bit yig'indisi 6-misol. Ikki bit x va y yig'indisini amalga oshiradigan (hisoblaydigan) standart asosda SFE quring. Yechim. Ikkita x va y bitlar yig’indisi jadvalini yozamiz. Bu yig'indi ikkita ikkilik raqamga ega bo'lgan son bo'lishi mumkin, shuning uchun biz ikkita mantiqiy o'zgaruvchini kiritamiz z 0, z 1 shundayki, x + y = 2z 1 + z 0: x y z 1 z
20 Misol: ikki bit yig'indisi Yechim (davomi). U holda z 0 = x y, z 1 = xy bo'ladi. X y = (x y) (x y) ekanligini hisobga olsak, biz CFE ni olamiz: L(S 1) = 3 va D(S 1) = 3 ekanligi aniq.
21 ixtiyoriy asosda CFE Xuddi shunday, ixtiyoriy asosda CFE B P 2 tushunchasi kiritilgan.
22 Misol: uch bit yig'indisi 7-misol. P2 2 (ya'ni ikkita o'zgaruvchiga bog'liq bo'lgan barcha mantiqiy funktsiyalardan) asosida uchta x, y va z bitlarining yig'indisini amalga oshiruvchi (hisoblab) SFE ni tuzing.
23 Misol: uch bit yig'indisi Yechim. 6-misolga o'xshab, uchta bit x, y va z yig'indisi jadvalini yozamiz. Bu yig'indi ikki ikkilik raqamga ega bo'lgan son ham bo'lishi mumkin, shuning uchun biz ikkita mantiqiy o'zgaruvchini u 0, u 1 kiritamiz, shunday qilib x + y + z = 2u 1 + u 0: x y z u 1 u
24 Misol: uch bit yig'indisi Yechim (davomi). U holda u 0 = x y z, u 1 = xy xz yz. xy xz yz = xy z(x y) ekanligini hisobga olsak, biz CFE ni olamiz: L(S) = 5 va D(S) = 3 ekanligini ko'ramiz.
25 CFE ning mantiqiy funksiyasini amalga oshirish B 0 = (x&y, x y, x) asosida CFE ning ixtiyoriy Boole funksiyasini (yoki mantiqiy funktsiyalar tizimini) amalga oshirish mumkinmi? mumkin. Buni qanday oqlash mumkin? Masalan, ha. Chunki (x&y, x y, x) P 2 da to‘liq sistema bo‘lib, ixtiyoriy mantiqiy f funktsiyani faqat konyunksiya, dis’yunksiya va inkor orqali formula bilan ifodalash mumkin. Misol uchun, mukammal DNF shaklida, agar f 0 bo'lsa va x & x shaklida, agar f = 0 bo'lsa. Va keyin, ushbu DNF (formula) dan foydalanib, tegishli CFE ni tuzing. Mantiqiy funksiyalar uchun SFE qurishning bu usuli DNF sintez usuli deb ataladi.
26 CFE ning DNF orqali sintezi Va mantiqiy funktsiya f (x 1,..., x n) uchun DNF tomonidan CFE S n ta o'zgaruvchiga qarab qanday murakkablikka ega bo'ladi? f funktsiyasi uchun mukammal DNF ko'pi bilan 2 ta elementar birikmani o'z ichiga oladi. Har bir elementar birikma n ta o‘zgaruvchining birikmasi yoki ularning inkori hisoblanadi.
27 DNF orqali SFE sintezi Shuning uchun sxemada quyidagilar bo'ladi: x 1,..., x n o'zgaruvchilarning barcha inkorlarini amalga oshirish uchun n ta invertor; (n 1) konyunktor orqali ko‘pi bilan 2 n ta elementar bog‘lanishning har birini mukammal DNFda amalga oshirish; DNF elementar birikmalarining diszyunksiyasini amalga oshirish uchun eng ko'p (2 n 1) disjunktor. Biz L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n ni olamiz.
28 Mantiqiy funktsiyaning murakkabligi CFE sinfidagi f (x 1,..., x n) mantiqiy funksiyaning L(f) murakkabligi f funksiyani amalga oshiradigan barcha CFElar orasidagi minimal murakkablikdir. Shunday qilib, biz teoremani isbotladik: Teorema 1. Ixtiyoriy f (x 1,..., x n) P 2 funksiya uchun L(f) n 2 n + n to‘g‘ri.
29 Mustaqil yechish uchun masalalar 1. Mantiqiy funktsiya f (x 1, x 2, x 3) = () uchun standart murakkablik asosida CFE quring. Mantiqiy funktsiya f (x 1, x 2, x 3) = (), standart murakkablik asosida CFE quring. Mantiqiy funktsiya f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4 uchun standart chuqurlik asosida SFE quring. standart asosda L(xy) = 4.
30 4-ma'ruza uchun adabiyotlar 1. Yablonskiy S.V. Diskret matematikaga kirish. M .: Oliy maktab, V qism, ch. 2, Gavrilov G.P., Sapozhenko A.A. bilan. Diskret matematikadan topshiriq va mashqlar. Moskva: Fizmatlit, Ch. X 1.1, 1.5, 1.7, 1.17, 1.18.
31 Ma’ruza yakuni 4
Ma'ruza: Kechikishli funksional elementlar sxemalari (SFES), ularni xaritalashning avtomatizmi. KAV EIZ vakolatxonasi. CAVni soddalashtirish. CAV holatlarining o'ziga xosligi va farqlanmasligi. Mur teoremasi
Ma'ruza: n o'lchamli kubni zanjirlarga bo'lish haqidagi Ansel teoremasi. Mantiq algebrasining monoton funksiyalar soni haqidagi teorema. Mantiq algebrasining monoton funksiyalarini ochish teoremasi. Ma'ruzachi - dotsent Selezneva Svetlana
Ma'ruza: Chiqishli chekli avtomatlar (KAV). Avtomat funksiyalari, ularni tayinlash usullari. Davriy ketma-ketlikni avtomat funksiyalar bilan o'zgartirish haqidagi teorema. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva
Ma'ruza: Qisman tartiblangan to'plamlar (POS). CHUM diagrammasi. Maksimal, minimal, eng katta va eng kichik elementlar. Zanjirlar va piyodalarga qarshi zanjirlar, vabo oxirining uzunligi va kengligi. PLni antizanjirlarga bo'lish teoremasi.
Ma’ruza 2. Binom koeffitsientlarining xossalari. Xulosa va funksiyalarni hosil qilish usuli (yakuniy holat). Polinom koeffitsientlari. Binom va polinom koeffitsientlari uchun taxminlar. Hisob-kitoblar miqdori
Ma'ruza: P k da to'liqlikni tan olish algoritmi. yopiq darslar. To'plamlarni saqlaydigan va bo'limlarni saqlaydigan funktsiyalar sinflari, ularning yopiqligi. Kuznetsovning funksional to‘liqlik haqidagi teoremasi. Oldindan to'ldirish darslari.
Ma’ruza 2. Kombinatorika. Binom koeffitsientlarining xossalari. Yig'indilarni sanash va funksiyalarni hosil qilish usuli. Polinom koeffitsientlari. Binom va polinom koeffitsientlari uchun taxminlar. Asimptotik
Ma’ruza: Cheklangan qiymatli funksiyalar. Elementar k qiymatli funksiyalar. k-qiymatli funksiyalarni ko'rsatish usullari: jadvallar, formulalar, 1 va 2-shakllar, ko'phadlar. To'liqlik. Post tizimining to'liqligi haqidagi teorema. Webb funktsiyasi.
Ma'ruza 3. Takroriy munosabatlar bilan aniqlanadigan ketma-ketliklar. Bir jinsli va bir jinsli chiziqli takroriy tenglamalar (LORU va LNRU). LORU va LNRUning umumiy qarorlari. Ma'ruzachi - dotsent Selezneva Svetlana
Ma’ruza 15. Cheklangan qiymatli mantiqning funksiyalari. k-qiymatli mantiqning elementar funksiyalari. k-qiymatli mantiqiy funksiyalarni ko'rsatish usullari: jadvallar, formulalar, I va II shakllar, ko'phadlar. To'liqlik. Ma'ruzachi - dotsent Selezneva
Ma’ruza: Cheklangan qiymatli mantiqning funksiyalari. k-qiymatli mantiqning elementar funksiyalari. k-qiymatli mantiqiy funksiyalarni ko'rsatish usullari: jadvallar, formulalar, I va II shakllar, ko'phadlar. To'liqlik. Ma'ruzachi - dotsent Selezneva Svetlana
Ma'ruza: CCMda Möbius funktsiyasi. n o'lchovli kubda Möbius funktsiyasi. Möbius inversiya formulasi. Inklyuziya-tashqariga qo'yish printsipi. Almashtirish-buzilishlar sonini hisoblash muammosi. Ma'ruzachi - dotsent Selezneva Svetlana
Ma’ruza 2. Binom koeffitsientlarining xossalari. Funksiyalarni yaratish usuli, summalarni hisoblash va shaxsni tasdiqlash. Polinom koeffitsientlari. Inklyuziya-tashqariga qo'yish printsipi. Ma'ruzachi - dotsent Selezneva Svetlana
Ma'ruza: Muhim funktsiyalar. Muhim funktsiyalar bo'yicha uchta lemma. Yablonskiyning to'liqlik mezoni. Slupetskiy to'liqlik mezoni. Schaeffer funktsiyalari. Ma'ruzachi dotsent Svetlana Nikolaevna Selezneva [elektron pochta himoyalangan]
Ma’ruza: Asosiy kombinator sonlar. Kombinator sonlar uchun taxminlar va asimptotiklar. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva, M.V. nomidagi Moskva davlat universiteti CMC fakulteti. Lomonosov ma'ruzalari http://mk.cs.msu.su saytida
Ma'ruza: Binom koeffitsientlarining xossalari. Xulosa va funksiyalarni hosil qilish usuli (yakuniy holat). Polinom koeffitsientlari. Binom va polinom koeffitsientlari uchun taxminlar. Binomiya yig'indilari uchun taxminlar
Ma'ruza: Chiqishli chekli avtomatlar. Davriy ketma-ketliklarni chiqish bilan chekli avtomatlar orqali o'zgartirish. Chiqish bilan chekli avtomatlarda holatlarning farqlanishi. Mashinalarni soddalashtirish. O'qituvchi Selezneva
Ma'ruza: O'rnatilgan qopqoq va matritsa qopqog'i. Gradient qoplamasi. Gradient qoplama lemmasi. n o'lchamli kubning soyali to'plamining kardinalligi uchun taxminlar. Funksiyalarning polinom normal shakllari uzunligini hisoblash
Ma'ruza 5. O'rnatilgan qopqoq va matritsa qopqog'i. Gradient qoplamasi. Gradient qoplama lemmasi. Boole kubining soyali to'plamining kardinalligi uchun taxminlar. Ko'pnomli mantiqiy normal shakllari uzunligi uchun taxminlar
Ma'ruza 3. Takroriy munosabatlar bilan aniqlanadigan ketma-ketliklar. Bir jinsli va bir jinsli chiziqli takroriy tenglamalar (LORU va LNRU). LORU va LNRUning umumiy qarorlari. Misollar O'qituvchi - dotsent Selezneva
Ma’ruza 3. To‘plamlardagi munosabatlar. Xususiyatlari. Kiritish-istisno qilish formulasi. Ekvivalentlik munosabati. Qisman tartib munosabati. Ma'ruzachi - dotsent Svetlana N. Selezneva Diskret modellar bo'yicha ma'ruzalar.
Ma'ruza 4. Ko'p qiymatli mantiqning xususiyatlari. Yopiq sinf, yopiq sinf asosi. Yanov va Muchnikning ko'p qiymatli mantiqlarda asossiz yopiq sinflar va hisoblanuvchi yopiq sinflarning mavjudligi haqidagi teoremalari.
Leksiya. Tabiiy argumentning funktsiyalari (ketma-ketlik). Bir jinsli va bir jinsli chiziqli takroriy tenglamalar (LORU va LNRU). LORU va LNRUning umumiy qarorlari. Misollar O'qituvchi - dotsent Svetlana Selezneva
Ma’ruza: Grafikning xromatik soni. Ikki rangli grafik uchun mezon. Grafikning xromatik sonining yuqori va pastki chegaralari haqidagi teoremalar. Ma'ruzachi - dotsent Svetlana N. Selezneva Diskret modellar bo'yicha ma'ruzalar.
Ma'ruza: Grafiklar va tarmoqlar. Q qirrali psevdograflar sonining taxmini. Q qirrali daraxtlar sonining taxmini. Planar grafiklar. Planar grafiklar uchun Eyler formulasi. Planar grafiklarda qirralarning eng ko'p soni. tekisliksizlik
Ma’ruza 1. Kombinatorika. Joylashtirishlar, almashtirishlar, takrorlashlar bilan joylashtirishlar, kombinatsiyalar, takroriy birikmalar. Ularning soni. Ma’ruzachi – dotsent Svetlana N. Selezneva “Matematik kibernetika” kafedrasi.
Ma'ruza: Ketma-ketliklar. Bir jinsli va bir jinsli bo'lmagan chiziqli takroriy tenglamalar. Chiziqli takrorlanuvchi bir jinsli va bir jinsli bo'lmagan tenglamalarning umumiy yechimlari. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva
Ma'ruza 8. Bo'yash sahifalari. Guruhga nisbatan rang berishning tengligi. Funktsiyalarni yaratish. Raqamlar uchun ro'yxatga olish qatori va funksiyalar uchun sanab qator. Poya teoremasi. O'qituvchi Selezneva Svetlana Nikolaevna
Ma'ruza: Rang berish. Permutatsiya guruhiga nisbatan ranglarning ekvivalentligi. Polya teoremasi (maxsus holat). Funktsiyalarni yaratish. Raqamlar uchun ro'yxatga olish qatori va funksiyalar uchun sanab qator. Teorema
Ma’ruza 2. Konyunktiv normal shakllar. Implicent, funktsiyaning oddiy implisensi. Mantiq algebrasining qisqartirilgan CNF funktsiyalari. Qisqartirilgan CNFni qurish usullari. O'qituvchi Selezneva Svetlana Nikolaevna [elektron pochta himoyalangan]
VLSI ning matematik modellari va mantiqiy sintez usullari 2015 yil kuz 4-ma'ruza Ma'ruza rejasi Kombinatsion mantiqiy sxemalarni mantiqiy optimallashtirish Mantiq algebrasi (FAL) funktsiyalarini ifodalashning turli usullari.
Ma'ruza: Deterministik bo'lmagan chekli avtomatlar (NFA). Cheklangan deterministik va chekli deterministik bo'lmagan avtomatlar tomonidan ruxsat etilgan so'zlar to'plami sinflarining mos kelishi haqidagi teorema. Jarayon
Ma'ruza 1. Tanlovlar. Joylashtirishlar, almashtirishlar, takrorlashlar bilan joylashtirishlar, kombinatsiyalar, takroriy birikmalar, ularning soni. Misollar. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva Diskret kursi bo'yicha ma'ruzalar.
Ma'ruza 1. Kombinator ob'ektlar: tanlash, joylashtirish, almashtirish, takrorlash bilan joylashtirish, birikmalar, takroriy birikmalar, ularning soni. Kombinator sonlar: faktorial, kamayuvchi faktorial, binomli
4-MA'RUZA FUNKSIONAL ELEMENTLARDAN Sxemalar 1. Asosiy ta'riflar Eng avvalo kompozitsiyani ko'rib chiqish kerak. Funktsiyani kirish va chiqishga ega bo'lgan "qora quti" sifatida ko'rsatish mumkin. Mayli
Ma'ruza 2. P k da to'liqlikni tan olish algoritmi. Kuznetsov teoremasi. yopiq darslar. To'plamni saqlaydigan funksiyalar sinflari. Bo'limni saqlaydigan funktsiyalar sinflari. Oldindan to'ldirish darslari. O'qituvchi Selezneva
Ma'ruza 3. Jegalkin ko'phad. Jegalkin funktsiyasining ko'phadini qurish usullari. Chiziqli implicent funktsiya. Chiziqli kon'yunktiv normal shakl (LCNF). Barcha chiziqli implicent funktsiyalarni topish. Imtihon
2-ma'ruza. Yaratuvchi funktsiyalar: kombinator yig'indilarni sanash va o'ziga xoslikni isbotlash, kombinator ob'ektlarni sanab o'tish. Inklyuziya-tashqariga qo'yish printsipi. Almashtirish-tartibsizliklar sonini hisoblash. O'qituvchi -
Ma’ruza 5. Grafiklar. Grafik bo'yash sahifalari. Grafikning xromatik raqami. Grafik uchun bixromatiklik mezoni. Grafikning xromatik sonining yuqori chegaralari. O'qituvchi Selezneva Svetlana Nikolaevna [elektron pochta himoyalangan] Ma'ruzalar
Ma'ruza: Chiqishsiz chekli avtomatlar (KA) (cheklangan avtomatlarni tan oluvchilar). O'tish diagrammasi. Avtomatik to'plamlar (tillar). Avtomatlar to'plamlarining xususiyatlariga oid lemma. Avtomatik bo'lmagan to'plamga misol. O'qituvchi
Ma’ruza 1. Cheklangan qiymatli funksiyalar. Elementar k qiymatli funksiyalar. k-qiymatli funksiyalarni ko'rsatish usullari: jadvallar, formulalar, 1 va 2-shakllar, ko'phadlar. To'liqlik. Post tizimining to'liqligi haqidagi teorema. Webb funktsiyasi.
Ma'ruza 7 Parvozlarni taqsimlash vazifasi uchun grafik model. Grafikning xromatik raqami. Grafikning ikki rangli bo'lish mezoni.
01.02.09.01 ixtisosligi talabalari uchun “Kibernetika asoslari” kursi (matematik va EHM uchun dasturiy ta’minot) 1. Umumiy ma’lumotlar (ish hajmi, nazorat shakllari va boshqalar). Kurs
Ma’ruza 6. Grafiklar. Grafiklarning irsiy xossalari. Grafiklarda irsiy xususiyatga ega qirralarning sonini hisoblash. Ekstremal grafiklar. Berilgani bilan tekis va uchburchaksiz grafiklardagi eng ko'p qirralar soni
Math-Net.Ru Butunrossiya matematik portali DS Romanov, doimiy uzunlikdagi birliklarni tekshirish testlarini qabul qiluvchi oson sinovdan o'tkaziladigan sxemalarni loyihalash usuli, Diskr. Mat., 2014 yil, 26-jild, 2-son,
Ma'ruza: Chiqishsiz, deterministik va deterministik bo'lmagan chekli avtomatlar. Cheklangan deterministik va deterministik bo'lmagan avtomatlar tomonidan ruxsat etilgan so'zlar to'plami sinflarining mos kelishi haqidagi teorema. Jarayon
2-amaliy ish Mantiqiy funktsiyaning normal shakllarini qurish Ishning maqsadi: Mantiqiy funktsiyaning kon'yunktiv, ayiruvchi, mukammal normal shakllarini qurishni o'rganish Ish mazmuni: Asosiy.
Mantiqiy funktsiyalarning murakkabligi bo'yicha seminar 1-ma'ruza: Kirish A. Kulikov POMIdagi kompyuter fanlari klubi http://compsciclub.ru 09/25/2011 09/25/2011 1 / 26 Ma'ruza rejasi 1 Mantiqiy funktsiyalar 2 Mantiqiy sxemalar 3 Deyarli
Amaliy ish 1 Mantiqiy va releli boshqaruv tizimlarini tahlili va sintezi
Ma'ruza: Muntazam iboralar va muntazam to'plamlar. Avtomat to'plamlari va muntazam to'plamlar sinflarining mos kelishi haqidagi Klin teoremasi. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva Diskret matematikadan ma'ruzalar.
3-ma’ruza Mantiqiy algebra va mantiqiy funksiyalar Mantiqiy algebra Algebraik tizimlar tushunchasi Algebraik tizim yoki algebraik tuzilma deganda ma’lum bir alifbo (tashuvchi) belgilari to‘plami tushuniladi.
Ma’ruza 5. Grafiklar. Grafiklardan foydalanishga misollar. transport vazifasi. Tarmoqdagi oqim, tarmoqdagi maksimal oqim qiymati bo'yicha Ford va Fulkerson teoremasi. Tarmoqdagi maksimal oqimni qurish algoritmi. O'qituvchi
Ma'ruza: Grafiklar. Grafiklardan foydalanishga misollar. transport vazifasi. Tarmoqdagi oqim, tarmoqdagi maksimal oqim qiymati bo'yicha Ford va Fulkerson teoremasi. Tarmoqdagi maksimal oqimni qurish algoritmi. O'qituvchi -
8-dars Esda tutingki, ixtiyoriy A va B to'plamlar uchun A B = (x x A va x B) to'plamlar mavjud; (A va B kesishuvi) A B = (x x A yoki x B); (A va B ning birlashishi) A \ B = (x x A va x / B) (A va B ning farqi).
Ma’ruza 7. Ramsi raqamlari. Ramsey raqami uchun yuqori chegara. Ramsey raqami uchun pastki chegara. O'qituvchi Selezneva Svetlana Nikolaevna [elektron pochta himoyalangan] M.V nomidagi Moskva davlat universiteti CMC fakulteti. Lomonosov ma'ruzalari http://mk.cs.msu.ru saytida
Ma'ruza: Grafiklar. Asosiy tushunchalar. Bog'langan grafikalar. Daraxtlar. Yadro daraxti. Yopiladigan daraxtdagi osilgan cho'qqilar soni. Ma'ruzachi - dotsent Svetlana N. Selezneva Diskret modellar bo'yicha ma'ruzalar. magistratura,
Ma’ruza 11. Mantiqiy sxemalar. Diskret matematika, HSE, Informatika fakulteti (2014 yil kuzi, 2015 yil bahori) x 1,..., x n o'zgaruvchilardagi mantiqiy sxema - g mantiqiy funktsiyalar ketma-ketligi
TASDIQLANGAN O'quv ishlari bo'yicha prorektor Yu.A.Samarskiy 2008 yil 10-iyun FIVT fakulteti 010600 yo'nalishi bo'yicha DISKRET TUZILMALAR kursi bo'yicha DASTUR VA VAZIFALAR FIVT kafedrasi ma'lumotlar tahlili kursi II semestr 4 Ikkita
Lomonosov nomidagi MDU Hisoblash matematikasi va kibernetika fakulteti S. A. Lojkin DISKRET BOSHQARUV TIZIMLARI SINTEZI NAZARIYASI ELEMENTLARI Moskva 2016 Mundarija.
Ma’ruza: Grafiklarning irsiy xossalari. Ekstremal grafiklar. Ramsey raqamlari. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva, M.V. nomidagi Moskva davlat universiteti CMC fakulteti. Lomonosov ma'ruzalari http://mk.cs.msu.su irsiy
Ma’ruza: Chekli avtomatlar to‘plamlari ustida amallar. Avtomat majmualarining komplementatsiyasi, birlashmasi, kesishishi, mahsuloti va iteratsiyasi, ularning avtomatizmi. Ma'ruzachi - dotsent Svetlana Nikolaevna Selezneva Ma'ruzalar
Rossiya Federatsiyasi Aloqa va axborotlashtirish vazirligi Volga viloyati davlat telekommunikatsiya va informatika akademiyasi Oliy matematika kafedrasi PGATI uslubiy kengashi tomonidan 2002 yil 29 martda tasdiqlangan.
5-ma'ruza. Grafiklarning qirralarini bo'yash. Grafikning xromatik indeksi. Ikki tomonlama grafiklarning xromatik indeksi. Grafikning xromatik indeksining yuqori va pastki chegaralari. O'qituvchi Selezneva Svetlana Nikolaevna [elektron pochta himoyalangan]
Math-Net.Ru Butunrossiya matematik portali NP Red'kin, Qisqa yagona diagnostika testlarini qabul qiladigan sxemalar bo'yicha, Diskr. Mat., 1989, 1-jild, 3-son, 71 76 Butunrossiyadan foydalanish
MATEMATIK MANTIQ(1) Amaliy mashg'ulotlar uchun topshiriqlar 1. Ko'rsatmalar algebrasi Bayonot ikki qiymat qabul qilishi mumkin bo'lgan qiymatdir: rost va yolg'on. Bayonotlar bosh harflar bilan belgilanadi
Boshqarish va hisoblash qurilmalarining zamonaviy texnologiyasida muhim o'rinni diskret konvertorlar, ya'ni ma'lum miqdordagi kirish va chiqishlarga ega bo'lgan qurilmalar egallaydi. Kirishlarga keladigan va chiqishlarda paydo bo'ladigan signallar to'plami ma'lum chekli to'plamlarga tegishli.
Ishlaringizni ijtimoiy tarmoqlarda baham ko'ring
Agar ushbu ish sizga mos kelmasa, sahifaning pastki qismida shunga o'xshash ishlar ro'yxati mavjud. Qidiruv tugmasidan ham foydalanishingiz mumkin
Aranov Viktor Pavlovich Diskret matematika. 5-bo'lim. DNF va FE dan sxemalar.
28-ma'ruza Analiz va sintez muammolari
28-ma'ruza FUNKSIONAL Elementlardan Sxemalar.
TAHLIL VA SINTEZ MAMULLARI
Dars rejasi:
1. Funktsional elementlar sxemasi haqida tushuncha(FE).
2. FE dan sxemalarni tahlil qilish va sintez qilish muammolari.
- FE dan sxema tushunchasi
Boshqarish va hisoblash qurilmalarining zamonaviy texnologiyasida muhim o'rin egallaydidiskret konvertorlar, ya'ni ma'lum miqdordagi kirish va chiqishlarga ega bo'lgan qurilmalar. Kirishlarga keladigan va chiqishlarda paydo bo'ladigan signallar to'plami ma'lum chekli to'plamlarga tegishli. Qurilmalar kirish signallari to'plamini chiqish signallariga aylantiradi. Bunday qurilmalarning matematik modeli deyiladifunktsional elementlardan sxemalar(SFE).
Misol sifatida, rasmda ko'rsatilgan uchta diodning elektr davri va qarshilikni ko'rib chiqing. bitta.
Guruch. 1. Elektr zanjiri va uning belgisi
Doira bilan tasvirlangan sxema nuqtalarida, turli vaqtlarda, taxminan 5 V ga teng yuqori daraja yoki taxminan nolga teng past daraja paydo bo'lishi mumkin. Chiziq bilan belgilangan sxema nuqtasida doimiy past kuchlanish darajasi saqlanadi.
Belgilangan nuqtalar kirish, nuqta esa chiqish sifatida talqin qilinadi. Sxemaning ishlashini quyidagicha ta'riflash mumkin: agar barcha kirishlar past kuchlanish darajasiga ega bo'lsa, unda chiqish ham past bo'ladi, agar kirishlardan kamida bittasi yuqori kuchlanish darajasiga ega bo'lsa, u holda chiqish yuqori bo'ladi. Agar biz yuqori kuchlanish darajasiga ega bo'lgan holatni bitta, past kuchlanish darajasi esa nol deb belgilasak, u holda chiqishning kirishlarga bog'liqligini mantiqiy funktsiya yordamida aniqlash mumkin.
Shunga asoslanib, yuqoridagi sxema “YOKI” mantiqiy elementi deb ataladi.
Shunga o'xshash sxemalar vakuum naychalari, elektromexanik kalitlar, pnevmatik elementlar va boshqalardan qurilishi mumkin. Chiqishning kirishlarga bog'liqligini nafaqat dis'yunksiya sifatida, balki kon'yunksiya, inkor va murakkabroq mantiqiy funktsiyalar yordamida ham tasvirlash mumkin.
Chiqishning kirishlarga har xil bog'liqligi bo'lgan mantiqiy elementlarni ko'rib chiqamiz. Ba'zi elementlarning chiqishlarini boshqalarning kirishlariga oziqlantirish orqali bu elementlar bir-biriga ulanishi mumkin. Natijada biz SFE ni olamiz.
SFE kontseptsiyasining ta'rifini ikki bosqichga bo'lish mumkin. Birinchi bosqichda ushbu kontseptsiyaning tarkibiy qismi, ikkinchisida - funktsional qismi ochiladi.
I bosqich. Keling, ushbu bosqichni bir necha bosqichlarga ajratamiz.
1 . Ob'ektlarning cheklangan to'plami () mavjudmantiqiy elementlar.Har bir element kirish va bitta chiqishga ega. Element rasmda ko'rsatilganidek, grafik tasvirlangan. 2.
2 . Induksiya orqali biz kontseptsiyani aniqlaymiz mantiqiy tarmoq ma'lum miqdordagi kirish va ma'lum miqdordagi chiqishga ega bo'lgan ob'ekt sifatida (3-rasm).
a) Induksiya asoslari. Izolyatsiya qilingan cho'qqi trivial mantiqiy tarmoq deb ataladi. Ta'rifiga ko'ra, u ham kirish, ham chiqishdir (4-rasm).
… …
…
Guruch. 2-rasm. 3-rasm. 4
b) induktiv o'tish. Ushbu qism uchta operatsiyadan foydalanishga asoslangan.
I . Ajratilgan tarmoqlarni birlashtirish operatsiyasi. Kelishmaydigan ikkita tarmoq (umumiy elementlar, kirish va chiqishlarsiz) mos ravishda kirish va chiqishga ega bo'lsin va bo'lsin. Tarmoqlarning to'plam-nazariy birlashmasi kirish va chiqishlarga ega bo'lgan mantiqiy tarmoqdir.
II . Elementni biriktirish operatsiyasi. Tarmoq va element shunday bo'lsinki va turli xil chiqishlarda raqamlar tanlanadi. Keyin rasm elementni tarmoqqa ulash natijasi bo'lgan mantiqiy tarmoq deb ataladi. Kirishlar - barcha kirishlar, chiqishlar - tarmoqning barcha chiqishlari, raqamlar bilan chiqishlar, shuningdek, elementning chiqishi bundan mustasno. Tarmoqning kirish va chiqishlari mavjud (5-rasm).
… …
Guruch. 6.
Guruch. 5
III . Chiqishni bo'lish operatsiyasi. Tarmoqdagi raqam bilan chiqish tanlansin. Keyin raqam chiqishni bo'lish orqali olingan mantiqiy tarmoq deb ataladi. Barcha kirishlar kirishlar, chiqishlar 1, ..., ... raqamlari bilan tarmoqning barcha chiqishlari va tarmoq raqami bilan chiqishdan kelib chiqadigan yana ikkita chiqishdir (6-rasm). Shuning uchun u kirish va chiqishlarga ega.
3 . Alfavit va berilsin.
Funktsional elementlar diagrammasialifbodan kirishlar va alifbodan chiqishlar bilan belgilanadigan mantiqiy tarmoq deb ataladi.
. (1)
Biz sxemalarga misollar keltiramiz.
1. To'plam uchta elementdan iborat bo'lsin VA (kon'yunktor), OR (dizyunktor) va EMAS (invertor).
Keyin rasm (6-rasm) diagramma bo'ladi, chunki uni operatsiyalar yordamida qurish mumkin I - III .
Guruch. 6-rasm. 7
2. Shaklda ko'rsatilgan rasm. 7, shuningdek, diagramma.
II bosqich. Sxemaning ishlashini aniqlash.
4 . SFE (1) ni mantiq algebrasining funksiyalar tizimi bilan solishtiramiz
(2)
ham chaqiriladiushbu konturning o'tkazuvchanligi.
Misol. a) Sxema uchun bizda bitta tenglamadan iborat tizim mavjud
Yoki.
b) Sxema uchun biz ham xuddi shunday olamiz
- FE sxemalari tomonidan mantiqiy funktsiyalarni amalga oshirish. Analiz va sintez muammolari
PV dan sxemalar
Tahlil vazifasi: berilgan SFE (1) uchun mantiqiy tenglamalar tizimini (2) olish.
Muammoni hal qilish algoritmi: tarmoqni qurish operatsiyalarini bajarish I-III , biz tarmoq elementlarining chiqishlarida funktsiyalarni ketma-ket hisoblaymiz.
Sintez vazifasi: funktsional elementlarning berilgan asosi va mantiqiy tenglamalarning ixtiyoriy tizimi (2) uchun ushbu tenglamalar tizimini amalga oshiruvchi berilgan FE lardan sxema (1) tuzing.
Sintez masalasi yechimining mavjudligi Post teoremasi bilan belgilanadi, unga ko'ra asosiy FE ni amalga oshiradigan funktsiyalar tizimi to'liq bo'lishi kerak. Funktsiyalar funksiyalarning superpozitsiyasi sifatida ifodalanishi mumkin va superpozitsiyaning har bir bosqichi elementlarning ma'lum bir birikmasiga mos keladi.
Misol. Funktsiya uchun
(3)
Formula (3) ning o'ng tomonidagi superpozitsiyaga mos keladigan sxema rasmda ko'rsatilgan. sakkiz.
Guruch. sakkiz
Sintez muammosi shundan iboratki, ma'lum mantiqiy tenglamalar tizimi uchun FE dan ushbu tizimni amalga oshiradigan ko'plab sxemalar qurish mumkin. Shu munosabat bilan optimal sintez muammosi paydo bo'ladi: berilgan funktsiyani amalga oshiradigan barcha mumkin bo'lgan sxemalardan u yoki bu xususiyat bo'yicha eng yaxshisini tanlang, masalan, elementlarning eng kichik soni. Bunday sxemalar chaqiriladi minimal.
Quyidagi tasdiq haqiqatdir.
Teorema. Mantiqiy funktsiyalarning har bir tizimi uchun minimal sxemani quradigan algoritm mavjud.
Minimal sxemalarni qurish uchun ushbu algoritm "qo'pol kuch" turidagi algoritmlar sinfiga kiradi, chunki u barcha sxemalarni ma'lum bir murakkablikgacha ko'rishga asoslangan. Qo'pol kuch algoritmlari, qoida tariqasida, juda mashaqqatli va amaliy maqsadlar uchun yaroqsiz. Shuning uchun biz yana oddiyroq masalani ko'rib chiqamiz, buning uchun dastlabki tenglamalar tizimi bitta tenglamani o'z ichiga oladi
va shuning uchun kerakli sxema bitta chiqishga ega.
Minimal sxemaning murakkabligini bilan belgilang. Sintez masalasini bitta funksiya uchun emas, balki o‘zgaruvchilar funksiyalarining butun sinfi uchun ko‘rib chiqamiz. Sintez algoritmlarining sifati Shannon funktsiyalari deb ataladigan narsalarni solishtirish orqali taqqoslanadi. Mayli
- algoritm yordamida olinadigan amalga oshiradigan sxemalarning minimal murakkabligi.
Funktsiyalar Shannon funktsiyalari deb ataladi va bu aniq
Sintez muammosi algoritmni iloji boricha yaqinroq topish va algoritmning murakkabligi to'liq qidiruv algoritmining murakkabligidan sezilarli darajada kamroq bo'lishi uchun algoritmni topishdir. Muammoning bunday formulasi bilan har bir funktsiya uchun algoritm minimal sxemani topishi shart emas, faqat yordami bilan olingan eng oddiy sxema unchalik oshmaydigan murakkablikka ega bo'lishi kerak.
Sizni qiziqtirishi mumkin bo'lgan boshqa tegishli ishlar.vshm> |
|||
| 9013. | FE dan Sxemalar SINTEZI USULLARI. DKODER VA BINAR QO'SHIMCHI Sxemasi | 153,07 Kb | |
| SFE sintezining umumiy nazariyasi katta qiymatlar uchun mantiqiy funktsiyalarning aksariyati murakkab minimal sxemalarga ega degan xulosaga olib keladi. Bu shuni anglatadiki, mantiqiy funktsiyalarning juda tor sinfi sintez nuqtai nazaridan amaliy ahamiyatga ega. | |||
| 5321. | Berilgan dizayn sxemasining turli elementlari uchun avtomatik himoya parametrlarining turlari va qiymatlari | 526,7 Kb | |
| Energetika tizimi va elektr energiyasi iste'molchilarining normal ishlashini ta'minlash uchun energiya tizimi va iste'molchilar uchun normal ish sharoitlarini tiklagan holda shikastlangan joyni imkon qadar tezroq aniqlash va buzilmagan tarmoqdan ajratish kerak. | |||
| 5384. | 4 ta kirish va 16 ta chiqish uchun soatli dekoderning ishlashini tahlil qilish uchun stendning elektr sxemasini ishlab chiqish. | 626,63 Kb | |
| ATP harakatlanuvchi tarkibining ishlashini yaxshilash uchun ATP harakatlanuvchi tarkibiga texnik xizmat ko'rsatish va ta'mirlash tizimining tashkiliy tuzilmasi ishlab chiqildi, diagnostika va texnik xizmat ko'rsatish uchun uskunalar majmuasi taklif qilindi. Korxonaning ta'mirlash inshootlari faoliyatining asosiy maqsadi jihozlarning uzluksiz ishlashini ta'minlashdir. U quyidagilarni o'z ichiga oladi: korxonaning ta'mirlash-tiklash bazasi, ta'mirlash ob'ektlarining omborlari, ustaxonalari va umumiy zavod bo'limlari, texnologik jihozlar, dispetcher. Tashkilot... | |||
| 1886. | Tizim tahlilining bosqichlari, ularning asosiy maqsadlari, vazifalari | 27,44 Kb | |
| Optimal tizimlar nazariyasi optimal tizimda erishish mumkin bo'lgan chegarani baholashga, uni mavjud nooptimal tizim ko'rsatkichlari bilan solishtirishga va ko'rib chiqilayotgan holatda optimal tizimni ishlab chiqish maqsadga muvofiqligini aniqlashga imkon beradi. Avtomatik boshqariladigan tizimning avtomatik boshqariladigan jarayoni uchun optimallashtirishning ikki bosqichi ajratiladi: statik va dinamik. Statik optimallashtirish optimal jarayon modelini yaratish va amalga oshirish masalalarini hal qiladi, dinamik esa... | |||
| 5123. | Funktsional strategiyalarni ishlab chiqish | 35,44 Kb | |
| Xodimlarni boshqarish strategiyasi. Boshqaruvning funktsiyalari va tuzilishi. Boshqaruv funktsiyalari va ularning boshqaruv tuzilmalarini shakllantirishdagi roli. Boshqarish strukturasining ierarxik turi. | |||
| 20368. | Retsept bo'yicha komponentlar va texnologiyalar tarkibining funktsional mahsulotlarning iste'mol xususiyatlariga ta'siri | 742,05 Kb | |
| Zamonaviy tibbiyot fani optimal ovqatlanish kontseptsiyasini qabul qildi. Bu shuni anglatadiki, makronutrientlar asosan tartibga solingan va me'yorlashtirilgan - yog 'manbalari, energiya manbalari, plastmassa materiallar (lipidlar, oqsillar, yog'lar) to'g'ri ovqatlanish kontseptsiyasidan optimal ovqatlanish kontseptsiyasiga o'tish amalga oshirilgan. organizmning hayoti uchun zarur bo'lgan, ilgari e'tibor berilmagan, oziq moddalar va boshqa oziq moddalar qatori sezilarli darajada kengaytirildi. | |||
| 4706. | Me karboksilatlarni sintez qilish usullari | 9,26 MB | |
| Usulning mohiyati metall oksidi, gidroksid yoki karbonatning tegishli kislotaning suvli eritmasida erishi hisoblanadi. Mahsulot kristallanish boshlanishidan oldin eritmaning bug'lanishi yoki karboksilat suvda erimaydigan yoki kam eriydigan cho'kmani filtrlash yo'li bilan ajratiladi. | |||
| 15923. | Pirazalodiazepinlarni sintez qilishning asosiy usullari | 263,39 KB | |
| Pirazolodiazepin hosilalarini sintez qilishning yangi usullari. Yangi sintez strategiyalarini ishlab chiqish katta qiziqish uyg'otadi. Pirazolodiazepin hosilalarining sintezi bo'yicha tizimli va umumlashtiruvchi tadqiqotlar o'tkazilmagan, ba'zi muammolar o'zgarmagan, munozarali yoki to'liq hal etilmagan. | |||
| 11978. | Elektr, issiqlik, vodorod va funktsional nanomateriallarni ishlab chiqarish uchun alyuminiyning gidrotermik oksidlanishiga asoslangan energiya texnologiyasi qurilmalari | 49,89 KB | |
| Rivojlanish alyuminiyning gidrotermik oksidlanish reaktsiyasiga asoslanadi, bunda katta miqdorda issiqlik energiyasi ajralib chiqadi va alyuminiy oksidlari va vodorod hosil bo'ladi: l2H2O→lOOH boehmite15H2415. Dastlabki reagentlar sifatida distillangan suv va mikron alyuminiy kukunlari ishlatiladi. KEU10 o'rnatilishi ETK100 o'rnatilishi ETK100 o'rnatilishining texnik xususiyatlari: Parametr qiymati Alyuminiy iste'moli kg h 101 Suv tozalash moslamasiga kirishda suv iste'moli kg h 484 Vodorod quvvati nm3 110 Issiqlik quvvati ... | |||
| 6605. | Ekspert tizimlari. TPni sintez usuli bilan loyihalash | 11,67 KB | |
| Bilimlar to‘planishini ifodalash va ularni dolzarbligini ta’minlash informatika fanining “Bilim muhandisligi” bo‘limida o‘rganiladigan murakkab vazifadir. Bilim muhandisi bilimlar bazasini - aqlli deb ataladigan tizimlarning yadrosini ishlab chiqishda ishtirok etadi. Ko'pincha aqlli tizimlar murakkab muammolarni hal qilish uchun ishlatiladi, bu erda yechimning asosiy murakkabligi ... | |||
31. Funktsional elementlar sxemalari, qurilish va ishlash qoidalari, sdnf va sknf asosida sfe sintez usuli.
Ta'rifTa'rif. Funktsional element - elementar diskret konvertorning matematik modeli bo'lib, u ma'lum bir qonunga muvofiq kirishda qabul qilingan signallarni konvertorning chiqishidagi signalga aylantiradi. Funktsional elementlardan ba'zi qoidalar yordamida tuzilishi va ishlashi jihatidan murakkabroq modellarni - funktsional elementlarning diagrammalarini qurish mumkin. Ushbu modellarda kirish va chiqish signallari 0 va 1 belgilari bilan kodlangan.
Qurilish qoidalari. Oddiylaridan murakkab SPElarni olish uchun sxemaning kirish yoki chiqishini bo'lish, kontaktlarning zanglashiga funktsional elementni ulash va funktsional elementni sxemaning kirish yoki chiqishiga ulash operatsiyalari ularga ketma-ket qo'llaniladi. Ushbu operatsiyalar superpozitsiyadan foydalangan holda oddiyroq formulalardan murakkab formulani olish qoidalariga o'xshaydi.
SFE sintezi. Dizyunksiya, konyunksiya va inkor sinfda yaxlit tizimni tashkil qilganligi sababli R 2, keyin har qanday mantiqiy funktsiyadan n Argumentlar funktsional elementlar sxemasi - disjunktorlar, kon'yunktorlar va invertorlar tomonidan amalga oshirilishi mumkin. n kirish va bitta chiqish. Buning uchun, masalan, berilgan mantiqiy funktsiyani SDNF yoki SKNF ko‘rinishida ifodalab, so‘ngra hosil bo‘lgan formulani ro‘yxatdagi bo‘lish, qo‘shish va ulash amallarini ketma-ket qo‘llagan holda funksional elementlar sxemasi ko‘rinishida “sintezlash” mumkin. yuqorida.
32. SPE sintez usuli universal multipole yordamida barcha birikmalarni ixcham amalga oshirishga asoslangan, natijada olingan sxemalarning murakkabligi.
Ta'rif. n ta argumentli funktsiya mantiqiy funktsiya (yoki mantiq algebrasining funktsiyasi) deb ataladi, agar u har bir to'plam bilan raqamni bog'lasa.
Mantiqiy funktsiyalarni o'rnatish uchun biz jadvallar, vektorlar, formulalar va grafiklardan foydalanamiz. Keling, quyidagi belgini olaylik: bu barcha to'plamlar to'plami, bu erda.
Ta'rif. Funktsional element - elementar diskret konvertorning matematik modeli bo'lib, u ma'lum bir qonunga muvofiq kirishda qabul qilingan signallarni konvertorning chiqishidagi signalga aylantiradi. Funktsional elementlardan ba'zi qoidalar yordamida tuzilishi va ishlashi jihatidan murakkabroq modellarni - funktsional elementlarning diagrammalarini qurish mumkin. Ushbu modellarda kirish va chiqish signallari 0 va 1 belgilari bilan kodlangan.
SPE sintez usuli universal multipole yordamida barcha birikmalarni ixcham amalga oshirishga asoslangan. Bu usul, shuningdek, funksiyani SDNF ko'rinishida ko'rsatishga asoslanadi, lekin birlashmalarning yanada ixcham amalga oshirilishi tufayli kamroq murakkab sxemalarni qurish imkonini beradi. SDNFda funktsiyaning parchalanishi umumiy omillarga ega bo'lgan birikmalarni o'z ichiga olishi mumkin. Agar ikkita bunday birikma bitta blokda bitta kichik sxema tomonidan amalga oshirilsa, buning uchun birinchi sintez usuli bilan barcha birikmalarni mustaqil ravishda amalga oshirish bilan oldingi talab qilinganidan kamida bitta kamroq konyunktor kerak bo'ladi. Uzunlikning barcha mumkin bo'lgan birikmalarining ixcham bajarilishi n induktiv tarzda qurilgan universal ko'p qutbli yordamida erishish mumkin n kirishlar va 2 n chiqishlar, qayerda n = 1,2,3,… Usulning afzalliklari, ayniqsa, bitta sxema yordamida bir nechta mantiqiy funktsiyalar tizimini amalga oshirish zarur bo'lganda sezilarli bo'ladi. Bunday holda, berilgan tizim funktsiyalarining SDNF tarkibiga kiritilgan birikmalarga mos keladigan universal ko'p qutbning chiqishlarini ajratish va keyin disyunktorlar orqali o'tkazish mumkin edi. Bu ma'lum bir tizimning har bir funktsiyasi o'z kichik sxemasi tomonidan mustaqil ravishda amalga oshirilgandan ko'ra, kamroq kon'yunktorlar bilan ishlashga imkon beradi.
Bunday multipolning murakkabligi tengdir L() =.
Funktsional elementlar sxemasi S aniq bo'lsa r funktsional elementlar, keyin biz uning murakkabligi borligini aytamiz r va uni tenglama sifatida yozing L(Σ) = r.
| " |
