O`zbekiston Respublikasi Axborot Texnologiyalari va Kommunikatsiyalarini Rivojlantirish Vazirligi
Download 330.93 Kb. Pdf ko'rish
|
evas
- Bu sahifa navigatsiya:
- Karno kartalari bilan mantiqiy funktsiyalarni minimallashtirish
- Karno kartasi yordamida funktsiyalarni minimallashtirish
- Mantiqiy funktsiyani kiritish qoidalari
- Operatsiya EMAS - mantiqiy rad etish (inversiya)
- Operatsiya OR - mantiqiy qoshimcha (ajralish, ittifoq)
- Operatsiya AND - mantiqiy kopaytirish (birikma)
- "IF-TO" operatsiyasi - mantiqiy kuzatuv (malumot)
- Operatsiya "Va agar va faqat B" bolsa (ekvivalentlik, ekvivalentlik)
- "Modulo 2 Addition" operatsiyasi (XOR, qatiy ravishda uzilishlarsiz)
- Mantiqiy operatsiyalarning ustuvorligi
- Zor disjunktiv normal shakl
- Mukammal konyunktiv normal shakl
|
O`zbekiston Respublikasi Axborot Texnologiyalari va Kommunikatsiyalarini Rivojlantirish Vazirligi Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti Kompyuter injiniring fakulteti 2- bosqich 214-19-guruh talabasi Jamoliddinov Ibrohimning Elektronika va sxema texnikasi fanidan bajargan
O`qituvchi: Hasan Narkulov
Mavzu: Karno kartasi, to`ldirilish usullari va qo`llanilishi
Reja: 1. Karno kartasi nima? 2. Karno kartalari bilan mantiqiy funktsiyalarni minimallashtirish. 3. Karno kartasi bilan funksiyalarni minimallashtirish 4. Mantiqiy funksiyalarni kiritish qoidalari. 5. Xulosa.
Karno kartalarini onlayn echimidan foydalanishni minimallashtiring. Karno kartasi bilan ishlash tartibi
Mantiqiy funktsiyalarni minimallashtirish - bu elektronni o'rganish jarayonida odatiy vazifalardan biridir. Shuning uchun, men bunday maqolaning joyi borligiga ishonaman, umid qilamanki sizga yoqadi. Nima uchun bu kerak? Mantiqiy funktsiyaning murakkabligi va shuning uchun uni amalga oshiradigan kontaktlarning zanjiri (davri) ning qiymati va qiymati mantiqiy operatsiyalar soni va o'zgaruvchilar yoki ularning rad etilishlarining soni bilan mutanosibdir. Aslida, har qanday mantiqiy funktsiyani to'g'ridan-to'g'ri aksioma va mantiq teoremalari yordamida soddalashtirish mumkin, ammo, qoida tariqasida, bunday o'zgartirishlar juda katta hisob-kitoblarni talab qiladi. Bundan tashqari, Boolean iboralarini soddalashtirish jarayoni algoritmik emas. Shuning uchun funktsiyani sodda, tez va aniqroq soddalashtirishga imkon beradigan maxsus algoritmik minimallashtirish usullaridan foydalanish tavsiya etiladi. Bunday usullarga, masalan, Quine usuli, Karno xaritasi usuli, implikatsion test usuli, implikatsion matritsa usuli, Quine-McCluskey usuli va boshqalar kiradi. Ushbu usullar odatiy amaliyot uchun eng mos keladi, ayniqsa Carno kartalari yordamida mantiqiy funktsiyani minimallashtirish. Carno xaritasi usuli, agar o'zgaruvchilar soni oltitadan oshmasa, aniqlikni saqlab qoladi. Argumentlar soni oltidan ortiq bo'lgan holatlarda, odatda Quine- McCluskey usuli qo'llaniladi. Bir yoki boshqa mantiqiy funktsiyani minimallashtirish jarayonida, odatda, elektron aylanishlar yordamida minimal shaklini amalga oshirish samaraliroq bo'lishi hisobga olinadi. Karno kartalari bilan mantiqiy funktsiyalarni minimallashtirish Karno xaritasi katta ifodalar bilan ishlashning nisbiy soddaligini ta'minlaydigan va potentsial irqlarni yo'q qiladigan kommutatsion (Boolean) funktsiyalarni minimallashtirishning grafik usulidir. Ikkilamchi to'liqsiz bog'lanish va elementar assimilyatsiya operatsiyalarini aks ettiradi. Carno xaritalari funktsiyaning mos ravishda qayta tuzilgan haqiqat jadvali sifatida ko'rib chiqiladi. Karno kartalari n- o'lchovli Boolean kubining ma'lum bir tekis skaneri sifatida ko'rib chiqilishi mumkin. Karno xaritalari 1952 yilda Edvard Veyt tomonidan ixtiro qilingan va 1953 yilda Bell Labs fizigi Maurice Carno tomonidan takomillashtirilgan va raqamli elektron aylanishlarni soddalashtirishga yordam berish uchun yaratilgan. Karno xaritasida Boolean o'zgaruvchilari haqiqat jadvalidan uzatiladi va Gray kodidan foydalanib buyurtma qilinadi, unda har bir keyingi raqam avvalgisidan faqat bitta raqam bilan farqlanadi. SDNF yoki SKNF shaklida taqdim etilgan mantiqiy funktsiyalarni minimallashtirishning asosiy usuli - bu juftlik bilan to'liq bo'lmagan bog'lanish va elementar assimilyatsiya qilish. Juftlik bilan yopishtirish jarayoni bir xil parametrlarga ega bo'lgan ikkita atama (a'zolar) o'rtasida amalga oshiriladi, ularning yuzaga kelishi (to'g'ridan-to'g'ri va teskari) bitta o'zgaruvchidan tashqari barcha o'zgaruvchilar uchun to'g'ri keladi. Bunday holda, bitta o'zgaruvchidan tashqari barcha o'zgaruvchilar qavslardan chiqarilishi mumkin va qavs ichida qolgan bitta o'zgaruvchining to'g'ridan-to'g'ri va teskari holatlari bir-biriga yopishtirilgan bo'lishi mumkin. Masalan: Yutilish ehtimoli aniq tengliklardan kelib chiqadi Shunday qilib, SDNF va SKNF-ni minimallashtirishning asosiy vazifasi keyinchalik katta yutuq bilan yopishtirish uchun mos keladigan shartlarni izlash bo'lib, katta shakllar uchun bu juda qiyin vazifa bo'lishi mumkin. Karno kartalari bunday atamalarni topishning ingl. Ma'lumki, SDNF yoki SKNF shaklida berilgan N o'zgaruvchisining funktsiyalari 2N har xil atamalarni o'z ichiga olishi mumkin. Bu
atamalarning barchasi N o'lchovli kubga topologik jihatdan teng keladigan ba'zi bir tuzilishni tashkil etadi va chetiga bog'langan har qanday ikkita atama yopishtirish va yutish uchun javob beradi. Rasmda ikkita o'zgaruvchining funktsiyasi uchun sodda haqiqat jadvali, ushbu jadvalga mos keladigan 2 o'lchovli kub (kvadrat), shuningdek, SDNF a'zolarining belgilanishi bilan 2 o'lchovli kub va guruhlash shartlari uchun ekvivalent jadval ko'rsatilgan: Uchta o'zgaruvchining funktsiyasi bo'lsa, siz uch o'lchovli kub bilan shug'ullanishingiz kerak. Bu yanada murakkab va kamroq aniq, ammo texnik jihatdan mumkin. Misol tariqasida, rasm uchta o'zgaruvchining va tegishli kubning Boolean funktsiyasi uchun haqiqat jadvalini ko'rsatadi. Rasmdan ko'rinib turibdiki, uch o'lchovli holat uchun atamalarning murakkabroq konfiguratsiyasi mumkin. Masalan, kubning bir yuziga tegishli to'rtta atama ikkita o'zgaruvchining yutilishi bilan bir atamaga birlashtirilgan:
Umumiy holda, giperkubkaning bitta K o'lchovli yuziga tegishli 2K atamalar bitta atama ichiga yopishtirilgan va K o'zgaruvchilar so'riladi deyish mumkin. Ko'p sonli o'zgaruvchilarning boolean funktsiyalari bilan ishlashni soddalashtirish uchun quyidagi qulay usul taklif qilindi. Atamalarning tuzilishi bo'lgan kub rasmda ko'rsatilgandek tekislikda joylashtirilgan. Shunday qilib, tekis jadvalda ikkitadan ortiq o'zgaruvchilar bilan Boolean funktsiyalarini namoyish etish mumkin bo'ladi. Shuni esda tutish kerakki, jadvaldagi muddatli kodlarning tartibi (00 01 11 10) ikkilik raqamlar tartibiga to'g'ri kelmaydi va jadvalning haddan Xuddi shunday, siz to'rt, besh yoki undan ko'p o'zgaruvchilarning funktsiyalari bilan ishlashingiz mumkin. N \u003d 4 va N \u003d 5 jadvallari misollari rasmda keltirilgan. Ushbu jadvallar uchun qo'shni hujayralar ekstremal ustunlarning mos keladigan hujayralarida va yuqori va pastki qatorlarning tegishli hujayralarida joylashganligini eslash kerak. 5 yoki undan ko'p o'zgaruvchilar jadvallari uchun, shuningdek, 3x o'lchamda 4x4 kvadrat deyarli bir-birining ustiga joylashganligini hisobga olish kerak, shuning uchun ikkita qo'shni 4x4 kvadratlarning tegishli hujayralari ulashgan va tegishli atamalarni bir-biriga yopishtirish mumkin.
Carnot xaritasi har qanday o'zgaruvchilar uchun tuzilishi mumkin, ammo beshdan ko'p bo'lmagan o'zgaruvchilar bilan ishlash qulay. Aslida, Karno xaritasi 2 o'lchovli shaklda tuzilgan haqiqat jadvali. Undagi kulrang koddan foydalanilganligi sababli yuqori qator pastki qismga, o'ng ustun chapga ulashgan. butun Karno Card torus shakliga tushib qolgan. Qator va ustunning kesishmasida haqiqat jadvalidan mos keladigan qiymat beriladi. Karta to'lgandan so'ng, siz minimallashtirishni boshlashingiz mumkin. Agar minimal DNF olish zarur bo'lsa, unda biz xaritada faqat birliklari bo'lgan hujayralarni ko'rib chiqamiz, agar CNF kerak bo'lsa, unda nolga ega bo'lgan hujayralarni ko'rib chiqamiz. Minimallashtirishning o'zi quyidagi qoidalarga muvofiq amalga oshiriladi (masalan, DNF): Keyinchalik, birinchi mintaqani olamiz va ushbu mintaqada qanday o'zgaruvchilar o'zgarmasligini ko'rib chiqamiz, agar ushbu o'zgaruvchilarning konyunkturasini yozamiz, agar o'zgarmas o'zgaruvchi nol bo'lsa, uning ustiga inversiya qo'ying. Keyingi maydonni olamiz, birinchi va boshqalarni bajaramiz va hokazo. Viloyatlarning konjunktlari bir-biriga mos kelmaydigan qo'shilish bilan bog'langan. Masalan (2 o'zgaruvchiga ega xaritalar uchun):
CNF uchun hamma narsa bir xil, biz shunchaki nol bilan hujayralarni ko'rib chiqamiz, bir mintaqadagi o'zgarmas o'zgaruvchilarni ajratishlarga birlashtiramiz (bitta o'zgaruvchiga inversiya qo'yamiz) va mintaqalarning bo'linishlarini birlashtiramiz. Ushbu minimallashtirish to'liq deb hisoblanadi. 1-rasmdagi Karnot xaritasi uchun DNF formatidagi ifoda quyidagicha bo'ladi:
F 1 va f 2 funktsiyalarini jadvaldan minimallashtirishda. 3.2. Biz original iboralarni o'zgartirishning eng faol usullarini izlashimiz kerak edi. Masalan, f 2 funktsiyasini minimallashtirishning birinchi bosqichida ushbu atamani takrorlash to'g'risida qaror aniq emas edi - Bir nechta o'zgaruvchilarning mantiqiy funktsiyasini ifodalovchi minimal ifodani imkon qadar tezroq olish uchun siz Karno xaritasi deb nomlangan haqiqat jadvalining grafik tasvirini ishlatishingiz mumkin. Uchta o'zgaruvchini ishlashi uchun Karnot xaritasi sakkiz kvadratdan iborat bo'lib, har birida to'rtta to'rt qatordan iborat to'rtburchaklardir (3.14- rasm, a). Har bir kvadrat kirish parametrlarining ma'lum qiymatlari to'plamiga mos keladi. Masalan, ustki qatordagi uchinchi kvadrat (x 1 x 2, x 3) \u003d (1, 1, 0) qiymatlarni bildiradi. Uchta o'zgaruvchining funktsiyalari to'g'risidagi jadval sakkiz qatorni o'z ichiga olganligi sababli, xarita sakkiz kvadratdan iborat bo'lishi kerak.
Kvadratlar ichidagi qiymatlar o'zgaruvchining mos keladigan qiymatlari uchun funktsiyaning qiymatlari. Karno xaritasining asosiy g'oyasi shundaki, gorizontal va vertikal ravishda bir-birining yonida joylashgan kvadratchalar faqat bitta o'zgaruvchining qiymatlarida farq qiladi. Agar ikkita qo'shni kvadratlar birliklardan iborat bo'lsa, bu tegishli atamalar juftligini algebraik soddalashtirish imkoniyatini anglatadi. Masalan, f 2 funktsiyasining xaritasida (3.14-rasm, a) yuqori satrning chap va eng chap ikki kvadratchasidagi birliklar shartlarga va x 2 ga to'g'ri keladi. Ushbu juft atamalar quyidagicha soddalashtirilgan: f 2 funktsiyasi uchun algebraik ifodani minimallashtirish bilan oldingi bo'limda qilganmiz. Kvadratlar guruhiga mos keladigan minimallashtirilgan qiymat bu parametrlarning qiymatlari ushbu guruhning barcha kvadratlari uchun bir xil bo'lgan kirish o'zgaruvchilarining mahsulidir. Agar x o'zgaruvchisining qiymati guruhning barcha kvadratlari uchun nolga teng bo'lsa, x i o'zgaruvchisi hosil bo'lgan mahsulotga kiritiladi. Xaritaning chap chetidagi kvadratlar uning o'ng qirrasidagi kvadratlarga ulashgan deb hisoblanadi. Shunday qilib, f 2 funktsiyasining xaritasida xaritaning chap va o'ng tomonidagi ustunlaridan tashkil topgan to'rt birlikdan iborat guruh mavjud. Tegishli atamalar guruhi bitta o'zgaruvchini o'z ichiga olgan bitta atama uchun soddalashtirilgan, chunki x 2 o'zgaruvchisi guruhning barcha kvadratlarida bir xil qiymatlarga ega. Anjir. 3.14. Karno xaritalari yordamida funktsiyalarni minimallashtirish: uchta o'zgaruvchilar uchun xarita (a); to'rtta o'zgaruvchilar xaritasi (b);
Karno xaritalari uchdan ortiq o'zgaruvchini funktsiyalarini minimallashtirish uchun ham ishlatilishi mumkin. To'rtta o'zgaruvchilar uchun xarita uchta o'zgaruvchiga mo'ljallangan ikkita xaritadan iborat bo'lishi mumkin. Bunday kartalarning ikkita misoli sek. 3.14, b va ularning har biri ostida u ko'rsatadigan funktsiya uchun minimal ifoda mavjud. Agar ikkita kvadrat va to'rtta kvadratni xaritadagi uchta turli o'zgaruvchiga guruhlash mumkin bo'lsa, sakkiztasini xaritadagi to'rt xil o'zgaruvchiga guruhlash mumkin. Bunday guruhlashning misoli g funktsiyasi xaritasida ko'rsatilgan. To'rt burchak kvadratchalari bitta guruhga birlashtirilishi mumkin, g 2 funktsiyasi xaritasida bo'lgani kabi, atama ularga asoslangan. Uchta o'zgaruvchini xaritasida bo'lganidek, kvadratlar guruhiga mos keladigan atama bu guruhning barcha kvadratlari uchun bir xil bo'lgan o'zgaruvchilar mahsuloti. Shunday qilib, xaritaning yuqori o'ng burchagidagi to'rtta to'rtburchaklar guruhida g 2 funktsiyalari barcha maydonlarda x 1 \u003d 1 va x 3 \u003d 0, shuning uchun x1 atamasi ushbu guruhni anglatadi. Qolgan ikkita o'zgaruvchi, x 2 va x 4, ushbu guruhning kvadratlarida turli qiymatlarga ega. Karno xaritalaridan beshta o'zgaruvchini funktsiyalari uchun ham foydalanish mumkin. Bunday holda, ikkita xaritadan to'rtta o'zgaruvchiga funktsiyani namoyish qilish uchun foydalaniladi: ulardan biri beshinchi o'zgaruvchining 0 qiymatiga, ikkinchisi esa uning 1 qiymatiga to'g'ri keladi. Karno xaritasida ikki, to'rt, sakkiz va hokazo guruhlarni shakllantirishning umumiy tartibi juda oddiy. Birlikni o'z ichiga olgan ikkita qo'shni juftliklar to'rtta kvadratdan iborat guruhga birlashtirilishi mumkin. To'rt kvadratdan iborat ikkita qo'shni guruh sakkiz kvadratchadan iborat guruhga birlashtirilishi mumkin. Umuman olganda, guruhdagi kvadratchalar soni 2 k bo'lishi kerak, bu erda k butun son. Keling, Karno kartasidan foydalanish uchun minimal miqdordagi ishlarni olish tartibini ko'rib chiqaylik. Shakldan ko'rinib turibdiki. 3.14, kattaroq kvadratchalar guruhi kamroq sonli o'zgaruvchilarning mahsulotiga mos keladi. Shuning uchun, minimal ifodani olish uchun xaritadagi barcha kvadratlarning tarkibiy qismlarini eng kichik guruhlarga birlashtirib, eng kattasini tanlab, barcha birliklarni qamrab olish kerak. Misol sifatida, rasmda ko'rsatilgan g2 funktsiyasining xaritasini ko'rib chiqing. 3.14, b.) Karno kartalari deb nomlanadigan kartalarda. Karno xaritalari haqiqat jadvallarining yana bir grafik tasviridir. Ikki, uch va to'rtta o'zgaruvchilar funktsiyasi uchun bunday xaritalarning tuzilishi quyidagi shaklga ega: Bunday jadvalning har bir katakchasi x 3, a 2, a 1, a 0 va boshqa argumentlarining sobit qiymati uchun x mantiqiy funktsiyaning qiymatini o'z ichiga oladi. U haqiqat jadvalining satrlaridan birini tasvirlaydi. Agar ushbu katak ushbu argumentning belgisi bilan yon yoki pastki qismda ko'rsatilgan satrlar yoki ustunlarga kiritilgan bo'lsa, tegishli dalil berilgan katak uchun to'g'ri deb hisoblanadi, aks holda bu katakning argumenti noto'g'ri deb hisoblanadi. Qisqartirilgan DNF xaritaning qo'shni hujayralarining to'rtburchaklar guruhlari tomonidan qayd etiladi. Guruhdagi hujayralarning ruxsat etilgan soni 2 n, n \u003d 1,2,3, ...
1. V belgisi o'rniga + belgisini ishlating (gap, OR). 2. Mantiqiy funktsiyadan oldin, siz funktsiyaning belgilanishini ko'rsatishingiz shart emas. Masalan, F (x, y) \u003d (x | y) \u003d (x ^ y) o'rniga oddiygina (x | y) \u003d (x ^ y) kiritasiz. 3. O'zgaruvchilarning maksimal soni 10 ga teng. Kompyuterning mantiqiy zanjirlarini loyihalash va tahlil qilish matematikaning maxsus bo'limi - mantiq algebrasi yordamida amalga oshiriladi. Mantiq algebrasida uchta asosiy mantiqiy funktsiyani ajratish mumkin: "YO'Q" (inkor qilish), "VA" (uyg'unlik), "OR" (ajralish). Har qanday mantiqiy qurilmani yaratish uchun har bir chiqish o'zgaruvchisining haqiqiy kiritish parametrlariga bog'liqligini aniqlash kerak. Bu bog'liqlik kommutatsiya funktsiyasi yoki mantiq algebrasining funktsiyasi deb ataladi. Mantiqiy algebraning funktsiyasi, agar uning barcha n n qiymatlari berilgan bo'lsa, to'liq aniqlangan deb nomlanadi, bu erda n - chiqish o'zgaruvchilarining soni. Agar barcha qiymatlar aniqlanmasa, funktsiya qisman aniqlangan deb nomlanadi. Agar uning holati mantiq algebrasi funktsiyasidan foydalanilgan holda tasvirlangan bo'lsa, qurilma mantiqiy deb nomlanadi. Mantiq algebrasining funktsiyalarini ifodalash uchun quyidagi usullardan foydalaniladi: Algebraik shaklga ko'ra, mantiqiy elementlardan foydalanib, mantiqiy qurilma diagrammasini tuzishingiz mumkin.
Mantiq algebrasining barcha operatsiyalari aniqlangan haqiqat jadvallari qiymatlar. Haqiqat jadvali operatsiya natijasini belgilaydi hammasi mumkinx boshlang'ich gaplarning mantiqiy qiymatlari. Amallarni qo'llash natijasini aks ettiradigan variantlar soni mantiqiy ifoda tarkibidagi gaplar soniga bog'liq bo'ladi. Agar mantiqiy ifoda tarkibidagi iboralar soni N bo'lsa, unda haqiqat jadvalida 2 N satr mavjud, chunki argumentlarning mumkin bo'lgan qiymatlarining 2 N har xil kombinatsiyasi mavjud.
Mantiqiy operatsiya oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin bo'lgan bitta argumentga taalluqli emas. Operatsiya natijasi quyidagicha EMAS: • agar asl ifoda to'g'ri bo'lsa, uni rad etish natijasi noto'g'ri bo'ladi; • agar asl ifoda noto'g'ri bo'lsa, uni rad etishning natijasi to'g'ri bo'ladi. Rad etish amaliyoti uchun quyidagi konventsiyalar qabul qilinmaydi: emas A, Ā, emas A, âA,! A Rad etish operatsiyasining natijasi quyidagi haqiqat jadvali bilan belgilanmaydi: A emas 0 1 1 0
Rad etish operatsiyasining natijasi asl bayon noto'g'ri bo'lsa va aksincha haqiqiy bo'lsa. Operatsiya OR - mantiqiy qo'shimcha (ajralish, ittifoq) OR mantiqiy operatsiyasi oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin bo'lgan ikkita iborani birlashtirish funktsiyasini bajaradi. Mantiqiy operatsiya manbai bo'lgan ko'rsatmalar dalillar deb ataladi. OR operatsiyasining natijasi agar haqiqiy ifoda kamida bittasi to'g'ri bo'lsa, haqiqiy bo'ladi. Amaldagi belgi: A yoki B, A V B, A yoki B, A || B. OR operatsiyasining natijasi quyidagi haqiqat jadvali bilan belgilanadi: OR operatsiyasining natijasi A, B to'g'ri bo'lsa yoki A va B bir vaqtning o'zida haqiqiy bo'lsa, A va B argumentlari noto'g'ri bo'lsa, haqiqiydir. Operatsiya AND - mantiqiy ko'paytirish (birikma) Mantiqiy operatsiya AND oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin bo'lgan ikkita ibora (dalillar) kesishish funktsiyasini bajaradi. AND operatsiyasining natijasi, agar ikkala manba ifodalari ham to'g'ri bo'lsa, haqiqiy bo'ladi. Ishlatiladigan belgi: A va B, A Λ B, A & B, A va B AND operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanadi: A B
0 0 0 0 1 0 1 0 0 1 1 1 Amaliyot natijasi Va agar A va B so'zlar bir vaqtning o'zida to'g'ri bo'lsa va boshqa barcha holatlarda yolg'on bo'lsa to'g'ri bo'ladi.
Ushbu operatsiya ikkita oddiy mantiqiy iboralarni bog'laydi, ulardan birinchisi shart, ikkinchisi esa bu shartning natijasidir. Qo'llaniladigan belgi: agar A, keyin B; A; agar A bo' lsa B; A → B Haqiqat jadvali: A B A → B 0 0 1 0 1 1 1 0 0 1 1 1
Kuzatuv operatsiyasining natijasi faqat A asos to'g'ri va B xulosa (natija) noto'g'ri bo'lsa, soxta bo'ladi. Operatsiya "Va agar va faqat B" bo'lsa (ekvivalentlik, ekvivalentlik) Qo'llaniladigan belgi: A ↔ B, A ~ B Haqiqat jadvali: A B ABB 0 0 1 0 1 0 1 0 0 1 1 1
uzilishlarsiz) Qo'llaniladigan belgi: A XOR B, A ⊕ B Haqiqat jadvali: A B ABB 0 0 0 0 1 1 1 0 1 1 1 0 Amaliyot natijasi shundan iboratki, agar A va B bir vaqtning o'zida haqiqiy bo'lsa yoki bir vaqtning o'zida noto'g'ri bo'lsa, ekvivalentlik haqiqiydir. Mantiqiy operatsiyalarning ustuvorligi • Qavslar ichidagi harakatlar • Inversiya • Birlashma (&) • Ishdan chiqish (V), eksklyuziv OR (XOR), modul 2 so'm • Tasdiq (→) • Ekvivalentlik (↔) Zo'r disjunktiv normal shakl Zo'r disjunktiv normal formulalar (SDNF) - bu unga teng keladigan formula bo'lib, u quyidagi xususiyatlarga ega bo'lgan elementar konyunkturalarning uzilishidir. 1. Formulaning har bir mantiqiy atamasi F (x 1, x 2, ... x n) funktsiyasiga kiritilgan barcha o'zgaruvchilarni o'z ichiga oladi. 2. Formulaning barcha mantiqiy shartlari boshqacha. 3. Birorta ham mantiqiy atama o'zgaruvchini va rad etilishini o'z ichiga olmaydi. 4. Formulaning bitta mantiqiy atamasi ikki marta bir xil o'zgaruvchini o'z ichiga olmaydi. SDNF-ni haqiqat jadvallaridan yoki ekvivalent o'zgarishlardan foydalanib olish mumkin. Har bir funktsiya uchun SDNF va SKNF permutatsiyaga qadar aniq belgilanadi.
Mukammal kon'yunktiv formulalar (SKNF)bu unga teng keladigan formula, bu xususiyatlarni qondiradigan elementar uzilishlar yig'indisi. 1. Barcha elementar gaplarda F (x 1, x 2, ... x n) funktsiyalariga kiritilgan barcha o'zgaruvchilar mavjud. 2. Barcha elementar gaplar boshqacha. 3. Har bir elementar gap bitta marta o'zgaruvchini o'z ichiga oladi. 4. Birorta ham elementar disjunktsiya o'zgarmaydigan va uning inkorini o'z ichiga olmaydi.
Xulosa: men bu mastaqil ishda yetarlicha bilim va kunikmalarni oldim va yaxshi tushunib oldim. Yana karno kartasi uzi nimaligi va qanday ishlatilishini bilib oldim Document Outline
Download 330.93 Kb. Do'stlaringiz bilan baham: 
|