Mantiqiy funksiyalarni minimallashtirish. Minimallashtirish deb mantiqiy funksiyani soddalashtirish muolajasiga aytilib, minimal o’zgaruvchilar soni bilan minimal miqdordagi hadlar sonlaridan iborat bo’lishini ta’minlab beradi.
Ba’zi oddiyroq hollarda minimallashtirishni to’g’ridan-to’g’ri Bul algebrasining asosiy qonunlarini qo’llab amalga oshirish mumkin. Misol uchun biriktirishish qonunini qo’llagan holda, (1.3.) ifodani soddalashtiramiz:
.
Hosil qilingan ifoda, uning boshlangish ko’rinishi bilan teng kuchlidir, biroq ahamiyatli darajada soddalashtirilgan ko’rinishidir.
Mantiqiy funksiya mavjud deb olinadigan bo’lsa:
.
Ikki marotaba unung o’ng qismida mavjud bo’lgan hadni x3x2x1 ni qo’shamiz (bundan funksiya deyarli o’zgarmaydi). Shunda:
= .
Bu ifoda boshlangish ko’rinishiga nisbatan ancha soddalashtirilgan hisoblanadi. Shuni ta’kidlash kerakki, minimallashtirishning bunday elementlar usullaridan foydalanish imkoniyati faqatgina funksiya hadlarining va o’zgaruvchilarining soni kam bo’lgan hollardagina qo’llash mumkin bo’ladi. Boshqa hollarda minimallashtirishning maxsus usullaridan foydalaniladi, bu usullar birikib ketayotgan hadlarini topishni osonlashtiradi. Bularga Karno xaritasi yordamida minimizatsiya usuli ham kiradi.
Karno xaritasi shunday tuzulganki, uning qo’shni katakchalariga funksiyaning o’xshash a’zolari joylashadi, ya’ni bu shunday turdagi hadlarki, bir-biridan birgina o’zgaruvchi bilan farq qiladi. Qachonki agarda bir hadning ichiga bu o’zgaruvchi to’g’ri ko’rinishda kirsa, boshqasiga – invers ko’rinishda kiradi. Buning evaziga o’xshash hadlarni biriktirilishining turli variantlari haqidagi yaqqol ko’rsatuvchi tasavvur hosil bo’ladi. Karno xaritasining kataklar soni, o’zgaruvchilarning to’g’ri va invers qiymatlaridan, har birida n hadli, qancha kombinatsiyalar tuzish mumkin bo’lsa (to’plamlar) shunga teng bo’ladi. Shunday qilib, n = 2 bo’lganda, xarita to’rtta katakdan iborat bo’ladi (1.4, a, rasm), n = 3 bo’lganida esa sakkizta katakdan iborat bo’ladi (1.4, b, rasm), n = 4 bo’lganida esa, xarita o’n olti katakdan iborat bo’ladi (1.4, c, rasm).
Har-bir katak o’zgaruvchilarning ma’lum bir kombinatsiyasiga to’gri keladi. Shu tariqa, xaritaning chap yuqori katagi (1.4,a-rasm) x1x2 kombinatsiyasiga mos kelib, ustunining chap katagida x1 to’g’ri shaklda keltirilgan bo’lib, yuqori qatorning ro’parasida to’g’ri shaklda x2 yozilgan.
Shu xaritaning pastki chap katagiga kombinatsiyasi mos keladi, pastki qator kataklari esa mavjud bo’lgan kombinatsiyalarga mos keladi. Chapdan uchinchi ustunning, pastki qatorining kattagiga (1.4,b-rasmga qarang) x3 kombinatsiyasi mos keladi, chapdan ikkinchi ustunning, yuqoridan uchinchi qatorining katagiga (1.4,c-rasmga qarang) x4x3 kombinatsiyasi mos keladi va h.k..
1.4-rasm. Karno xaritasi:
a – ikki o’zgaruvchi uchun; b– uch o’zgaruvchi uchun; c– to’rtta o’zgaruvchi uchun
Qachonki y=1 bo’lganidagi o’zgaruvchilarning to’plami, ya’ni funksiyalarni mintermalari, xaritaning mos katagiga 1 soni bilan belgilanadi, qolgan kataklarga esa 0 soni yoziladi yoki bo’sh qoldiriladi. Ikkita qo’shni kataklarda joylashgan 1 sonlari, T.D.N.SH tarkibida bir o’zgaruvchi qiymatiga farq qiluvchi hadlar borligidan dalolat beradi. Odatda bunday hadlar birlashtiriladilar. Har bir mintermalar juftining birikishi, ularning tarkibiga kiruvchi o’zgaruvchilarning sonini bittaga qisqarishiga olib keladi.
Karno xaritasiga kiritilgan hadlarni biriktirilishini umumiy qoidalari quyidagilar hisoblanadi:
- 2,4,8 va h.k. hadlar birikishi mumkin bo’lib, bunda mos keladigan kataklardagi 1 sonlari ko’rinish uchun kontur bilan aylantirib chiqiladi va har bir kontur to’g’ri to’rtburchak shaklga ega bo’lishi kerak bo’ladi;
- bitta kontur bilan maksimal miqdordagi katakchalarni birlashtirish kerak;
- bitta katakdagi 1 soni, har xil konturlar tomonidan qamrab olinishi mumkin, ya’ni bitta mintermani o’zi bir necha qo’shni mintermalar bilan biriktirilishi mumkin va bu holat mavjud bo’lgan hadlarning qo’shilishi funksiya qiymatini o’zgartirmasligi bilan tushuntiriladi;
- Karno xaritasining chekka qatorlari, shuningdek chekka ustunlari bir biriga teng deb hisoblanadi va bu holatni tasdig’ini topish uchun, xaritani tasavvurimizda gorizontal yoki vertikal silindr shakliga aylantirish darkor.
Karno xaritasi yordamida minimallashtirilgan funksiya, oddiy konyuksiyalar yig’indisidan iborat bo’ladi. Ularning har biri, hadlarni birikishi natijasida hosil bo’ladi va ularga kontur qamrab olgan birliklar to’gri keladi. Bunday konyuksiyalarga faqatgina, kontur chegarasida qiymatlari o’zgarishsiz qoladigan o’zgaruvchilar kiradi.
Aytaylik mantiqiy funksiya haqiqat jadvali bilan berilib, 1.5.-jadvalda aks ettirilgan bo’lsin. Undan T.D.N.SH. funksiyasi hosil qilinadi:
(1.5.)
1.5-jadval
|
