|
Ta’rif. Har qanday minimal DNSh eng qisqa DNSh bo‘ladi.
Ta’rif. Har qanday qisqa DNSh minimal DNSh bo‘lmaydi.
Ta’rif. E.k. da ishtirok etayotgan barcha belgilar soni K ning uzunligi deyiladi.
Masalan, ning uzunligi .
Ta’rif. Tupikli DNSh eng qisqa DNSh deyiladi, agarda undagi konyunsiyalari uzunliklarining yig‘indisi boshqa tupikli DNSh larga nisbatan eng kichik bo‘lsa.
Masalan,
Demak, mDNSh2 minimal DNSh bo‘ladi, chunki
Endi qisqatritirilgan DNSh larni hosil qilishining umumiy qonuniyatlarini ko‘rib chiqamiz:
- oddiy birlashtirish qonuni.
- yutilish qonuni.
-umumiy birlashtirish qonuni.
- to‘liq bo‘lmagan birlashtirish qonuni.
Minimal va eng qisqa DNSh qurishning sxemasini keltiramiz:
Endi yuqoridagi qonunlarga asoslangan minimal DNSh qurish usulini ko‘rib chiqamiz.
DNSh sifatida funksiyaning TDNSh ni olamiz.
Berilgan DNSh da kon’yunksiyalarni inkorlar sonining kamayish tartibida yozib chiqiladi, ya’ni avval hammasi inkor amali bilan qatnashgan o‘zgaruvchilardan tashkil topgan kon’yunksiya, undan keyin bitta o‘zgaruvchidan tashqari inkor belgisi bilan qatnashgan kon’yunksiya va h.k.
Barcha qo‘shni kon’yuksiyalar uchun oddiy birlashtirish qonuni qo‘llaniladi. Agar qo‘llash mumkin bo‘lmasa, u holda hosil bo‘lgan DNSh tupikli DNSh bo‘ladi.
Barcha qo‘shni konyuksiyalarga yutilish qonuni qo‘llaniladi.
1-misol. TDNSh berilgan.
Inkor bo‘yicha tartiblashtiramiz
.
x1x2
|
|
0 0
|
0
|
0 1
|
1
|
1 0
|
1
|
1 1
|
1
|
2. birlashtirish qonunga asosan
hosil qilinadi.
3. - minimal DNSh.
2-misol. funksiyaning qiymati jadval usulda berilgan.
-
|
|
0 0 0
|
1
|
0 0 1
|
1
|
0 1 0
|
0
|
0 1 1
|
0
|
1 0 0
|
0
|
1 0 1
|
1
|
1 1 0
|
0
|
1 1 1
|
1
|
1. Ushbu jadvaldan TDNSh ni xosil qilamiz.
TDNSh da elementar kon’yunksiyalar inkorlar sonining kamayishi bo‘yicha tartiblangan.
3. TDNSh dan ga asosan
,
, larni xosil qilamiz.
U holda qisqartirilgan DNSh
keladi.
Endi qisqartirilgan DNSh dan tupikli DNSh hosil qilish algoritmni ko‘rib o‘tamiz.
Qisqartirilgan DNSh dagi har bir e.k. funksiyaning qiymatlarini hisoblash uchun quyidagi jadval tuziladi.
|
|
|
. . .
|
|
K1
|
|
|
. . .
|
|
K2
|
|
|
. . .
|
|
:
|
:
|
:
|
. . .
|
:
|
Ks
|
|
|
. . .
|
|
2. Jadval katakchalari qoidaga asosan to‘ldiriladi.
|
|
|
. . .
|
|
K1
|
0
|
1
|
. . .
|
1
|
K2
|
1
|
0
|
. . .
|
1
|
:
|
:
|
:
|
. . .
|
:
|
Ks
|
1
|
0
|
. . .
|
0
|
3. Jadvaldagi har bir ustunda larning qiymati =1 bo‘lgan joylarda larni qo‘yib chiqamiz va har bir ustun uchun larning elementar diz’yunksiyasini tuzamiz. Har bir ustun uchun tuzilgan elementar diz’yunksiyalarning kon’yuksiyasini tuzsak, natijada KNSh hosil bo‘ladi.
4. Hosil bo‘lgan KNSh ni DNSh ga keltiramiz va soddalashtiramiz. Hosil bo‘lgan DNSh da har bir elementar kon’yunksiyani aloxida-aloxida qaraymiz. Ushbu kon’yunksiyalardagi kon’yunksiya belgisini diz’yunksiya belgisiga almashtirib chiqamiz hamda 3- qadamdagi almashtirishga teskari almashtirish bajaramiz. Ya’ni belgisini K1 kon’yunksiya bilan, ni K2 bilan, ni K3 va x.k ni Ks bilan almashtiramiz. Natijada 4- qadamda hosil bo‘lgan DNSh da nechta kon’yunksiyalar bo‘lsa, shuncha DNSh lar hosil bo’ladi. Bu DNSh larning har biri tupikli DNSh hisoblanadi.
Misol: Kisqartirilgan DNSh berilgan bo’lsin. DNSh = .
|
000
|
001
|
010
|
011
|
100
|
101
|
110
|
111
|
|
1(a1)
|
1(a1)
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
1(a2)
|
0
|
0
|
0
|
1(a2)
|
0
|
0
|
|
0
|
0
|
0
|
0
|
0
|
1(a3)
|
0
|
1(a3)
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1(a4)
|
1(a4)
|
|
0
|
0
|
1(a5)
|
0
|
0
|
0
|
1(a5)
|
0
|
|
1(a6)
|
0
|
1(a6)
|
0
|
0
|
0
|
0
|
0
|
KNSh=
Qavslarni ochamiz, ya’ni KNSh ni DNSh ga keltiramiz.
Demak DNSh=
Endi ga almashtiramiz.
U holda
Bulardan minimali 2) va 4) chilaridir.
Demak DNShm = yoki DNShm = .
Topshiriq variantlari.
Quyidagi qisqartirilgan DNSh lardan tupikli va minimal DNSh larni toping.
12-AMALIY MASHG’ULOT. Mukammal diz’yunktiv normal shakldagi bul funksiyalarini karno kartalari orqali soddalashtirish. Ikkilik mantiqiy amallariga mos sxemalar tuzish
Reja:
Ikkilik mantiqiy amallariga mos sxemalar tuzishga oid tushunchalar
Mustaqil bajarish uchun masala va topshiriqlar
RELE - KONTAKTLI SXEMALAR (RKS).
Muloxazalar algebrasining formulalarini RKS yordamida realizatsiya (ifodalash) qilish.
Aftomatik boshkarish kurilmalari va EXM larda yuzlab va minglab rele, elektron lampa, yarim o‘tkazgich va magnit elementlarini uz ichiga olgan rele – kontakti va elektron – lampa sxemalar uchraydi. Bu sxemalar avtomatik boshkarish kurilmalari va EXM tarkibida benixoya katta tezlikda juda murakkab operatsiyalar bajarishda bevosita ishtirok etadilar va avtomatlarning barcha ish faoliyatini boshkarib turadilar.
Biz kuyida Bul algebrasining yana bir modeli – rele kontakt sxemasi (RKS) bilan tanishamiz.
Xar bir kontakt fizik kurilma bulgan rele bilan birga boglangan bulib, rele kontaktni yopadi (ulaydi, yani kontakt orkali tok utadi) yoki ochadi (uzadi, yani kontakt orkali tok utmaydi). Biz rele – kontakt kurilmasini kontakt deb ataymiz.
Bundan buyon sxema yordamida kontaktning xam yopik, xam ochik xolatlarini belgilaymiz.
4.1 va 4.2 – shakldagi eng oddiy sxemalarni mos ravishda ochik va yopik kontakt deyiladi. Tabiiyki, xar bir kontakt
fakat ikkita xolatda bulishi mumkin : “ochik” va “yopik” yoki “tok o‘tkazmaydi” va “tok o‘tkazadi”.
4.1 – shakl. 4.2 – shakl.
Kontaktlarning bunday xolatlari muloxazalarning xam ikki xolatda yani 0 va 1 xolatdan bulishini eslatadi. Shunday kilib, kontaktning ochik xolatiga muloxazalarning “yolgon” – “0” qiymatini, yopik xolati esa muloxazaning “rost” – “1” qiymatini mos kuyish mumkin.
Demak, barcha kontaktlar bilan barcha elementar muloxazalar orasida uzaro bir qiymatli moslik mavjud ekan. Bundan buyon x muloxazaga mos keluvchi kontaktni xam shu xarf bilan belgilaymiz.
Kontaktlar ustida quyidagi operatsiyalarni kiritamiz:
Do'stlaringiz bilan baham: |
