|
f = x y.
Karnaugh xaritasida OR funksiyasi uchun allaqachon uchta 1 mavjud va ikkita yopishtirilgan juftlik yasalishi mumkin, xy atamasiga mos keladigan 1 ikki marta ishlatiladi. Minimal funksiya ifodasida yopishtiriladigan juftliklar uchun shartlarni yozish, ularda shu juftlik uchun o‘zgarmaydigan barcha o‘zgaruvchilarni qoldirib, qiymatini o‘zgartiruvchi o‘zgaruvchilarni olib tashlash kerak. Gorizontal yopishtirish uchun biz x, vertikal yopishtirish uchun esa y ni olamiz, natijada ifodani olamiz.
f = x + y.
Shaklda. 9 rasmda uchta o'zgaruvchining ikkita funktsiyasining haqiqat jadvallarini (a) va ularning Carnot xaritalarini (b va c) ko'rsatadi. f2 funktsiyasi birinchisidan farq qiladi, chunki u uchta o'zgaruvchilar to'plamida aniqlanmagan (bu jadvalda chiziqcha bilan ko'rsatilgan).
Funktsiyaning minimal DNF ni aniqlashda quyidagi qoidalar qo'llaniladi. 1 ni o'z ichiga olgan barcha hujayralar yopiq to'rtburchaklar maydonlarga birlashtiriladi, ular k-kublar deb ataladi, bu erda k = log2K, K - to'rtburchaklar maydonidagi 1lar soni. Bundan tashqari, har bir maydon 2k katakchali to'rtburchak bo'lishi kerak, bu erda k = 0, 1, 2, 3, … . k = 1 uchun to'rtburchak bir kub deb ataladi va 21 = 2 birlikni o'z ichiga oladi; k = 2 uchun to'rtburchak 22 = 4 birlikni o'z ichiga oladi va ikki kub deb ataladi; k = 3 uchun 23 = 8 birlik maydoni uch kub deb ataladi; va hokazo.Toʻgʻri toʻrtburchaklarga birlashtirib boʻlmaydigan birliklarni faqat bitta birlikdan (20=1) oʻz ichiga oluvchi nol kub deb atash mumkin. Ko'rib turganingizdek, hatto k uchun mintaqalar kvadrat shakliga ega bo'lishi mumkin (lekin shart emas), toq k uchun esa faqat to'rtburchaklar.
9-rasm. Uch o'zgaruvchining funksiyalari uchun Karno xaritalariga misol
Bu joylar bir-birining ustiga chiqishi mumkin, ya'ni bir xil hujayralar turli sohalarga kiritilishi mumkin. Keyin funksiyaning minimal DNF si k-kublarga mos keladigan barcha konyunktiv atamalarning diszyunksiyasi sifatida yoziladi. Karno xaritasidagi ko'rsatilgan maydonlarning har biri minimal DNFda konjunksiya bilan ifodalanadi, bunda argumentlar soni m funksiya argumentlarining umumiy sonidan k ga kam, ya'ni bu raqam m - k ga teng. Minimal DNF ning har bir birikmasi faqat xaritaning tegishli maydoni uchun inversiyasiz yoki faqat inversiya bilan qiymatlarga ega bo'lgan, ya'ni ularning qiymatini o'zgartirmaydigan argumentlardan iborat. Bu joylar bir-birining ustiga chiqishi mumkin, ya'ni bir xil hujayralar turli sohalarga kiritilishi mumkin. Keyin funksiyaning minimal DNF si k-kublarga mos keladigan barcha konyunktiv atamalarning diszyunksiyasi sifatida yoziladi.
Karno xaritasidagi ko'rsatilgan maydonlarning har biri minimal DNFda konjunksiya bilan ifodalanadi, bunda argumentlar soni m funksiya argumentlarining umumiy sonidan k ga kam, ya'ni bu raqam m - k ga teng. Minimal DNF ning har bir birikmasi faqat xaritaning tegishli maydoni uchun inversiyasiz yoki faqat inversiya bilan qiymatlarga ega bo'lgan, ya'ni ularning qiymatini o'zgartirmaydigan argumentlardan iborat. Shakldagi xaritada aniqlanmagan qiymatlar. 9, in nol yoki bitta bilan almashtirish orqali qayta belgilanishi mumkin. Ushbu funktsiya uchun ikkala noaniq qiymatni 1 bilan almashtirish foydaliroq ekanligi aniq. Bunday holda, har xil turdagi 2 kubiklar bo'lgan ikkita mintaqa hosil bo'ladi. Keyin minimal DNF funktsiyasining ifodasi quyidagicha bo'ladi:
Yopiq maydonlarni qurishda Karnaugh xaritasini gorizontal va vertikal o'qlar bo'ylab xaritaning qarama-qarshi tomonlarini birlashtirgan holda silindrga siqib chiqarishga ruxsat beriladi, ya'ni Karnaugh xaritasining chekkalari bo'ylab nosimmetrik joylashgan birliklar ham birlashtirilishi mumkin.
Karnot xaritalarini turli usullarda chizish mumkin (10-rasm).
Guruch. 10. 3 o'zgaruvchili funksiya uchun Karnaugh xaritalarini ko'rsatishning turli usullari Jadvalning 11-bandi, chunki ular har bir hujayra uchun barcha o'zgaruvchilarni to'g'ridan-to'g'ri yoki teskari shaklda ko'rsatadi.
11. 3 (a) va 4 (b) o‘zgaruvchili funksiyalar uchun Karno xaritalarining eng qulay tasviri.
Do'stlaringiz bilan baham: |
