Analisis dan sintesis peranti logik. Kaedah untuk meminimumkan fungsi logik dan litar. Pemodelan matematik ubah bentuk plastik kristal

Apabila mereka bentuk automata digital, kaedah untuk meminimumkan fungsi Boolean digunakan secara meluas untuk mendapatkan litar kos efektif. Tugas am pengecilan fungsi Boolean boleh dirumuskan seperti berikut: cari ungkapan analitikal untuk fungsi Boolean yang diberikan dalam bentuk yang mengandungi bilangan huruf minimum yang mungkin.

Kaedah pengecilan adalah berdasarkan operasi pelekatan (algoritma untuk menggabungkan jiran nombor binari):

di mana A ialah kata sendi asas.

Dalam ungkapan, istilah adalah nombor binari bersebelahan yang berbeza antara satu sama lain dengan hanya satu digit. Apabila melakukan operasi pelekatan pada dua nombor bersebelahan, satu pembolehubah dikecualikan daripada set, yang membezakan satu nombor dari yang lain, pada empat nombor bersebelahan berpasangan - dua pembolehubah, pada lapan - tiga pembolehubah, dll.

Bentuk normal disjungtif minimum (MDNF) bagi fungsi Boolean ialah DNF yang mengandungi bilangan huruf terkecil (berbanding dengan semua DNF lain yang mewakili fungsi Boolean tertentu).

Minimumkan fungsi, iaitu, cari ungkapan paling mudah untuk fungsi asal boleh pelbagai kaedah. Kesemua mereka secara praktikal berbeza hanya pada peringkat pertama - peringkat mendapatkan DNF yang disingkat. Perlu diingatkan bahawa, malangnya, carian untuk MDNF sentiasa dikaitkan dengan beberapa carian untuk penyelesaian. Mari lihat sebahagian daripada mereka.

Meminimumkan Ungkapan Boolean Kompleks Menggunakan Matriks Carnot

Untuk melaksanakan algoritma penggabungan, adalah perlu untuk mencari yang jiran daripada keseluruhan set juzuk wajib dalam bentuk normal disjungtif yang sempurna bagi fungsi algebra logik. Untuk mencari juzuk jiran, matriks Carnot, kekisi nombor jiran, dan jadual juzuk jiran digunakan.

Adalah dinasihatkan untuk menggunakan matriks Carnot untuk meminimumkan FAL pada set 2,3,4,5 dan 6 pembolehubah. Nombor lajur dalam matriks Carnot membentuk digit paling tidak bererti, dan nombor baris membentuk digit paling bererti bagi set. Nombor sel terdiri daripada nombor baris dan lajur dan sepadan dengan set pembolehubah.

Mari kita pertimbangkan matriks Carnot untuk fungsi algebra logik pada set 4 pembolehubah (Jadual 1).

Jadual 1. Matriks Carnot

Lajur dan baris dalam matriks ini ditetapkan oleh nombor bersebelahan binari: 00-0I-II-I0. Oleh itu, bilangan sel bersebelahan mendatar dan menegak, serta sel paling luar dalam baris dan lajur, ialah nombor bersebelahan, contohnya:

sel dengan nombor dan;

sel dengan nombor;

sel dengan nombor.

Untuk meminimumkan fungsi algebra logik yang dinyatakan dalam bentuk normal disjungtif sempurna menggunakan matriks Carnot, adalah perlu untuk: menyediakan matriks Carnot dengan menulis unit dalam sel yang sepadan dengan juzuk wajib, menggabungkan sel dengan unit ke dalam "subkubus", menulis diminimumkan. fungsi algebra logik dalam bentuk normal disjungtif.

"subkubus" bergabung:

- dua sel dengan nombor yang merupakan nombor bersebelahan, manakala satu pembolehubah dikecualikan;
- empat sel (baris, lajur, segi empat sama, sel penjuru), manakala dua pembolehubah dikecualikan;
- lapan sel (dua baris bersebelahan atau melampau (lajur)), dengan tiga pembolehubah dikecualikan.

Untuk memberikan pengecualian adalah mungkin lebih pembolehubah, saiz "subkubus" hendaklah sebesar mungkin, dan bilangannya serendah mungkin. Untuk tujuan ini, anda boleh menggunakan sel yang sama dengan unit beberapa kali, termasuk dalam "subkubus" yang berbeza. Bilangan sebutan dalam fungsi algebra logik yang diminimumkan adalah sama dengan bilangan subkubus dan sel dengan unit yang tidak digabungkan menjadi subkubus.

Biarkan ia perlu untuk meminimumkan fungsi algebra logik berikut:

Matriks Carnot, diisi mengikut formula ini, boleh dibentangkan dalam bentuk Jadual 2:

Jadual 2. Matriks Carnot

Dalam matriks ini, dua subkubus dua sel boleh dibezakan. Hasil daripada pengurangan yang kita akan perolehi fungsi seterusnya algebra logik:

Kaedah Quine

Untuk mendapatkan bentuk fungsi logik yang minimum, adalah perlu untuk melakukan semua pelekatan dan penyerapan yang mungkin dalam bentuk normal disjungtif sempurna bagi fungsi (PDNF) supaya hasilnya adalah bentuk normal disjungtif terkurang bagi fungsi tersebut. (DNF). DNF yang dikurangkan dalam kes umum mungkin mengandungi implikasi utama tambahan, yang mesti dikenal pasti pada peringkat pengecilan kedua.

Pada peringkat pertama, peralihan dibuat daripada fungsi yang dinyatakan dalam bentuk DNF kepada DNF yang dikurangkan. Intipati kaedah ini adalah untuk melakukan secara berurutan semua gluing yang mungkin dan kemudian semua penyerapan, yang membawa kepada pengurangan DNF. Kaedah ini boleh digunakan untuk DNF yang sempurna. Daripada hubungan serapan ia mengikuti bahawa produk asas sewenang-wenangnya diserap oleh mana-mana bahagian daripadanya. Untuk membuktikannya, sudah cukup untuk menunjukkan bahawa implikan perdana arbitrari p = x i1 x i2... x dalam boleh diterima. Malah, menggunakan operasi terbentang pada p (sebalikan operasi gam):

untuk semua pembolehubah yang tiada x ik , ..., x im fungsi asal f, kita memperoleh set S juzuk perpaduan. Dengan melekatkan semua juzuk daripada S kita memperoleh p tersirat. Yang terakhir adalah jelas, kerana operasi pelekatan adalah songsang daripada operasi terungkap. Set S juzuk semestinya hadir dalam DNF sempurna bagi fungsi f kerana p ialah implikannya.

Hasil daripada pelekatan, kata hubung pangkat n-1 diperoleh, dan kata hubung kekal dalam ungkapan asal dan mengambil bahagian berbanding dengan ahli SDNF yang lain. Oleh itu, adalah mungkin untuk mengurangkan pangkat istilah.

Gam dan penyerapan dilakukan selagi ada ahli yang tidak mengambil bahagian dalam perbandingan berpasangan. Istilah-istilah yang telah menjalani operasi pelekatan ditandakan. Istilah yang tidak bertanda adalah implikasi utama dan termasuk dalam DNF yang disingkatkan. Semua kata sendi bertanda pangkat n-1 sekali lagi tertakluk kepada operasi pelekatan sehingga terma pangkat n-2 diperoleh, dan seterusnya sehingga bilangan kata sendi tidak bertanda lebih besar daripada 2. Hasil daripada peringkat pertama, DNF berkurangan diperolehi.

Ungkapan logik yang terhasil tidak selalunya minimum. Pada peringkat kedua, mereka beralih daripada DNF terkurang kepada DNF buntu dan memilih MDNF antaranya.

Untuk membentuk DNF buntu, jadual (matriks) tersirat dibina, baris yang ditandakan dengan implikasi mudah DNF yang disingkatkan, dan lajur dengan konstituen unit SDNF asal. Dalam baris bertentangan dengan setiap implikan ringkas, satu tanda diletakkan di bawah set tersebut (konstituen unit) di mana ia mengambil nilai 1. Konstituen yang sepadan diserap (dilindungi) oleh implikan ringkas ini.

Daripada jumlah bilangan implikasi utama, adalah perlu untuk memilih nombor minimum mereka, menghapuskan yang tidak perlu. Pembentukan bentuk buntu dan pemilihan liputan minimum bermula dengan pengenalpastian implikasi utama wajib, iaitu, yang (dan hanya mereka) meliputi beberapa set awal. Mari kita lihat contoh meminimumkan fungsi logik:

f SDNF = V (1,2,5,6,7)=x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3 + x 1 x 2 x 3

1 2 3 4 5

Mari lakukan operasi pelekatan:

1 - 3 (x 1 )x 2 x 3 1
2 - 4 (x 1 )x 2 x 3 2
3 - 5 (x 2 )x 1 x 3 3
4 - 5 (x 3 )x 1 x 2 4

Hasil daripada langkah pelekatan pertama, kami memperoleh empat kata hubung baharu; tiada implikasi mudah telah dikenal pasti. Kata hubung yang terhasil tidak lagi melekat dan membentuk DNF yang dipendekkan.

f abbr SDNF =x 2 x 3 + x 2 x 3 + x 1 x 3 + x 1 x 2

Untuk mengenal pasti implikasi mudah mandatori dan merumuskan liputan minimum berdasarkannya, jadual implikan dibina (Jadual 3). Implikasi mudah ditulis dalam baris jadual implikan, dan konstituen kesatuan ditulis dalam lajur. Asterisk diberikan jika implikan utama meliputi konstituen.

Jadual 3. Jadual tersirat

x 1 x 2 x3	X 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3	x 1 x 2 x3

Implikasi utama adalah wajib kerana ia hanya meliputi konstituen dan termasuk dalam perlindungan minimum. Masih terdapat satu juzuk yang tidak bertutup x 1 x 2 x 3 yang boleh dilindungi oleh salah satu daripada dua implikasi utama yang tinggal. Ini menghasilkan dua bentuk buntu.

Kaedah Blake-Poretsky

Kaedah ini membolehkan seseorang memperoleh DNF terkurang bagi fungsi Boolean f daripada DNF arbitrarinya. Berdasarkan penggunaan formula pelekatan umum:

kesahihannya mudah dibuktikan. sungguh,

Oleh itu,

Kaedah ini adalah berdasarkan pernyataan berikut: jika dalam DNF arbitrari bagi fungsi Boolean f kita melakukan semua gluing umum yang mungkin dan kemudian melakukan semua penyerapan, maka hasilnya adalah pengurangan DNF bagi fungsi f.

Mari kita lihat satu contoh. Biarkan fungsi Boolean f diberikan oleh DNF sewenang-wenangnya.

Ia adalah perlu untuk mendapatkan DNF yang dipendekkan bagi fungsi f menggunakan kaedah Blake-Poretsky. Kami menjalankan pelekat umum. Adalah mudah untuk melihat bahawa unsur pertama dan kedua DNF asal menerima pelekatan umum berkenaan dengan pembolehubah x 1 . Hasil daripada melekatkan kami mendapat:

Unsur pertama dan ketiga DNF asal mengakui pelekatan umum berkenaan dengan kedua-dua pembolehubah x 1 dan x 2 . Selepas melekat bersama x 1 kami ada:

Selepas melekat bersama x 2 kita ada:

Unsur kedua dan ketiga DNF mengakui pelekatan umum berkenaan dengan pembolehubah x 2 . Selepas melekat kami mendapat:

Setelah melakukan pelekatan umum terakhir, kami tiba di DNF:

Selepas melakukan penyerapan kami mendapat:

Percubaan untuk terus menggunakan operasi pelekatan umum dan penyerapan tidak membuahkan hasil. Akibatnya, pengurangan DNF bagi fungsi f diperolehi. Seterusnya, masalah mencari DNF minimum diselesaikan menggunakan matriks implikan dengan cara yang sama seperti dalam kaedah Quine.

Meminimumkan FAL yang tidak ditakrifkan sepenuhnya

Jika, apabila mensintesis litar logik yang melaksanakan beberapa FAL daripada n pembolehubah, ternyata beberapa set daripada jumlah nombor 2 n tidak boleh muncul pada input litar, maka fungsi logik ini tidak ditakrifkan pada set ini. Kemudian 2 n set pembolehubah boleh dibahagikan kepada tiga kumpulan: set di mana fungsi mengambil nilai unit L, nilai sifar D dan kumpulan set yang fungsinya tidak ditakrifkan N (set tidak ditentukan). FAL yang mengandungi set tidak ditentukan dipanggil tidak lengkap atau separa ditakrifkan. Set yang tidak ditentukan boleh digunakan untuk meningkatkan kualiti pengecilan. Dalam kes ini, set tidak pasti (apabila diminimumkan, contohnya, oleh Veitch, peta Carnaugh) boleh mengambil bahagian dalam pembentukan kontur dengan set unit dan sifar. Ini menghasilkan pembentukan fungsi logik terminimum yang lebih mudah.

Kaedah pengecilan sejagat ialah penggunaan undang-undang dan hubungan algebra logik, yang membolehkan meminimumkan FAL untuk sebarang bilangan pembolehubah.

Pelajar mesti:

ketahui:

· Kaedah untuk meminimumkan fungsi logik.

Mampu untuk:

· Lakukan pengecilan fungsi menggunakan kaedah transformasi langsung; Lakukan pengecilan fungsi menggunakan kaedah transformasi langsung;

· Lakukan pengecilan fungsi menggunakan peta Karnaugh.

Kaedah transformasi langsung

Fungsi logik yang menentukan prinsip membina litar peranti digital, boleh, seperti yang ditunjukkan di atas, dibentangkan dalam bentuk jadual kebenaran atau dalam bentuk SDNF atau SKNF dan boleh digunakan untuk mendapatkan litar logik peranti. Walau bagaimanapun, litar logik yang terhasil secara amnya tidak akan optimum. sebab tu peringkat penting sintesis litar logik ialah meminimumkan fungsi logik.

Minimumkan(pemudahan bentuk tatatanda) fungsi ialah operasi penting apabila mensintesis litar logik, kerana terima kasih kepada pengecilan awal, litar dilaksanakan dengan bilangan elemen terkecil.

Beberapa kaedah telah dibangunkan untuk meminimumkan. Satu daripada kaedah mudah pengecilan adalah kaedah transformasi langsung, yang dijalankan menggunakan teorem asas algebra logik.

Sebagai contoh, fungsi logik

dalam bentuk SDNF, boleh diminimumkan seperti berikut:

1. Tambahkan pada fungsi ini istilah yang sudah ada dalam fungsi ini, menggunakan peraturan x+x=x

2. Mari kita gunakan kaedah melekatkan kata hubung asas yang sama bergaris bawah

3. Mari kita gunakan kaedah pelekatan untuk dua kata hubung asas yang terakhir

Fungsi logik yang diperoleh hasil daripada pengecilan dipanggil fungsi buntu. Fungsi logik boleh mempunyai beberapa bentuk buntu.

Mengenal pasti dan menghapuskan lebihan dalam rakaman fungsi dengan mengubahnya menggunakan aksiom, hukum, identiti dan teorem algebra logik memerlukan pengiraan yang rumit dan dikaitkan dengan banyak masa.

Peta Carnot

Kaedah transformasi langsung paling sesuai untuk formula mudah, apabila urutan transformasi jelas kepada pelaku. Selalunya, kaedah ini digunakan untuk meminimumkan akhir ungkapan yang diperoleh selepas meminimumkannya dengan kaedah lain.

Keinginan untuk membuat algoritma pencarian produk asas jiran membawa kepada pembangunan kaedah jadual meminimumkan fungsi logik. Salah satunya ialah kaedah berdasarkan penggunaan peta Karnaugh.

Peta Carnot telah dicipta pada tahun 1952 oleh Edward W. Veitch dan diperbaiki pada tahun 1953 oleh Maurice Carnot, seorang ahli fizik di Bell Labs, dan bertujuan untuk membantu memudahkan litar elektronik digital.

Peta Karnaugh ialah perwakilan grafik bagi jadual kebenaran fungsi logik. Ia ialah jadual yang mengandungi 2 n sel segi empat tepat, dengan n ialah bilangan pembolehubah logik.

Sebagai contoh, peta Karnaugh untuk fungsi empat pembolehubah mempunyai 2 4 = 16 sel.

Struktur peta Karnaugh untuk fungsi dua pembolehubah ditunjukkan dalam Rajah 2.2. 2

Rajah 2.2

Rajah 2.3 menunjukkan struktur peta Karnaugh bagi fungsi tiga pembolehubah.

a) jadual kebenaran; b) struktur peta Karnaugh

Rajah 2.3

Peta ditandakan dengan sistem koordinat yang sepadan dengan nilai pembolehubah input. Sebagai contoh, baris atas peta untuk fungsi tiga pembolehubah (Rajah 2.3) sepadan dengan nilai sifar pembolehubah x1, dan yang lebih rendah - nilai unitnya.

Setiap lajur peta ini dicirikan oleh nilai dua pembolehubah: x2 dan x3. Gabungan nombor yang menandakan setiap lajur menunjukkan nilai pembolehubah x2 dan x3 fungsi yang diletakkan dalam sel lajur ini dikira.

Jika pada set yang ditetapkan fungsi berubah-ubah adalah sama dengan satu, maka SDNFnya semestinya mengandungi produk asas yang mengambil nilai unit pada set ini. Oleh itu, sel-sel peta Carnot yang mewakili fungsi mengandungi seberapa banyak unit kerana terdapat produk asas yang terkandung dalam SDNFnya, dan setiap unit sepadan dengan salah satu produk asas.

Marilah kita memberi perhatian kepada fakta bahawa koordinat baris dan lajur dalam peta Carnaugh tidak mengikut susunan semula jadi untuk meningkatkan kod binari, tetapi dalam susunan 00, 01, 11, 10. Perubahan dalam susunan set adalah dilakukan supaya set jiran bersebelahan, iaitu. berbeza dalam nilai hanya satu pembolehubah.

Sel di mana fungsi mengambil nilai yang sama dengan satu diisi dengan satu. Sel yang tinggal diisi dengan sifar.

Mari kita pertimbangkan proses pengecilan menggunakan contoh yang dibentangkan dalam Rajah 2.4.

a) jadual kebenaran; b) Peta Carnaugh

Rajah 2.4

Pertama, kita membentuk segi empat tepat yang mengandungi 2k sel, dengan k ialah integer.

Sel jiran yang sepadan dengan produk asas bersebelahan digabungkan menjadi segi empat tepat.

Sebagai contoh, dalam Rajah 2.4b, sel-sel dengan koordinat 001 dan 101 digabungkan. Apabila sel-sel ini digabungkan, segi empat tepat terbentuk di mana pembolehubah x1 menukar nilainya. Akibatnya, ia akan hilang apabila melekatkan produk asas yang sepadan dan hanya x2 dan x3 akan kekal, dan kami mengambil pembolehubah x2 dalam bentuk songsang, kerana ia sama dengan 0.

Sel yang terletak di baris pertama (Rajah 2.4 b) mengandungi unit dan bersebelahan. Oleh itu, kesemuanya digabungkan menjadi segi empat tepat yang mengandungi 2 2 = 4 sel.

Pembolehubah x2 dan x3 dalam segi empat tepat menukar nilainya; oleh itu, mereka akan hilang daripada produk asas yang terhasil. Pembolehubah x1 kekal tidak berubah dan sama dengan sifar. Oleh itu, produk asas yang diperoleh dengan menggabungkan sel-sel baris pertama Rajah 2.4 b mengandungi hanya satu x1, yang kita ambil dalam bentuk songsang, kerana ia sama dengan 0.

Ini, khususnya, berikutan daripada fakta bahawa empat sel baris pertama sepadan dengan jumlah empat produk asas:

Dua sel lajur kedua sepadan dengan jumlah dua produk

Fungsi yang sepadan dengan Rajah 2.4 mempunyai bentuk:

Koleksi segi empat tepat yang meliputi semua unit dipanggil penutup. Ambil perhatian bahawa sel yang sama (contohnya, sel dengan koordinat 001) boleh diliputi dua kali atau lebih.

Jadi, anda boleh lakukan kesimpulan berikut:

1. Formula yang terhasil daripada meminimumkan fungsi logik menggunakan peta Carnaugh mengandungi jumlah produk asas sebanyak mana terdapat segi empat tepat dalam liputan.

2. Lebih banyak sel terdapat dalam segi empat tepat, semakin sedikit pembolehubah terkandung dalam hasil asas yang sepadan.

Sebagai contoh, untuk peta Carnot yang ditunjukkan dalam Rajah 2.5 a, segi empat tepat yang mengandungi empat sel sepadan dengan hasil darab asas dua pembolehubah, dan segi empat sama yang terdiri daripada hanya satu sel sepadan dengan hasil darab asas. termasuk keempat-empat pembolehubah.

a B C)

Rajah 2.5

Fungsi yang sepadan dengan liputan yang ditunjukkan dalam Rajah 2.5 a mempunyai bentuk:

Walaupun pada hakikatnya peta Carnot digambarkan di atas kapal terbang, kejiranan dataran didirikan di permukaan torus. Atas dan had bawah Peta Carnot nampaknya "melekat bersama", membentuk permukaan silinder. Apabila melekatkan sempadan sisi, permukaan toroidal diperolehi. Berikutan alasan di atas, kami menetapkan bahawa sel dengan koordinat 1011 dan 0011, ditunjukkan dalam Rajah 2.5 b, adalah bersebelahan dan digabungkan menjadi segi empat tepat. Sesungguhnya, sel yang ditunjukkan sepadan dengan jumlah produk asas

Baki empat sel unit digabungkan dengan cara yang sama. Hasil daripada gabungan mereka, kami memperoleh produk asas.

Akhirnya, fungsi yang sepadan dengan liputan yang ditunjukkan dalam Rajah 2.5 b mempunyai bentuk

Peta Carnaugh yang ditunjukkan dalam Rajah 2.5c mengandungi sel tunggal yang terletak di sudut. Keempat-empat sel bersebelahan, dan selepas menggabungkan mereka akan memberikan produk asas

Contoh-contoh yang dibincangkan di atas membolehkan kita merumuskan urutan meminimumkan fungsi logik menggunakan peta Karnaugh:

1. Jadual untuk n pembolehubah dipaparkan dan sisinya ditanda.

2. Sel jadual yang sepadan dengan set pembolehubah yang menukar fungsi kepada satu diisi dengan satu, sel yang tinggal diisi dengan sifar.

3. Liputan terbaik jadual dipilih dengan segi empat tepat biasa, yang kami gariskan. Setiap segi empat tepat mesti mempunyai 2 n sel.

4. Sel yang sama dengan unit boleh dimasukkan dalam kontur yang berbeza.

5. Bilangan segi empat tepat hendaklah minimum, dan luas segi empat tepat hendaklah maksimum.

6. Bagi setiap segi empat tepat, kami menulis hasil darab hanya pembolehubah yang tidak mengubah nilainya. Jika pembolehubah ini sama dengan sifar, maka ia ditulis dalam bentuk songsang.

7. Kami menyambungkan produk yang terhasil dengan tanda tambahan logik.

Soalan kawalan:

1. Apakah yang dipanggil minterms dan minterms?

2.Tulis fungsi yang dinyatakan oleh jadual 2.9 dan 2.10 dalam SDNF dan SKNF.

Jadual 2.9

3. Permudahkan fungsi logik menggunakan aksiom identiti dan hukum algebra logik:

Unsur logik

Pelajar mesti

ketahui:

· Jadual keadaan logik untuk litar logik berfungsi asas;

· Prinsip asas membina litar logik.

Mampu untuk:

· Tentukan keadaan logik pada output litar digital oleh keadaan yang diketahui pada input;

· Penuhi reka bentuk logik dalam pangkalan litar mikro;

· Pilih litar mikro daripada buku rujukan, berdasarkan parameter yang diberikan dan syarat penggunaan.

Prinsip peranti logik adalah berdasarkan IC di tempat kerja transistor bipolar dalam mod kunci (sama ada tertutup atau terbuka).

Tindakan logik dijalankan seperti dengan satu (single-input unsur logik) dan dengan set (elemen logik berbilang input) pembolehubah input.

Apabila bekerja peranti logik Tiga operasi asas digunakan mengikut algebra Boolean - "DAN", "ATAU", "TIDAK".

Fungsi logik boleh dinyatakan secara lisan, dalam bentuk algebra, dengan jadual kebenaran yang dipanggil jadual suis, menggunakan gambar rajah pemasaan. Mari kita pertimbangkan semua pilihan untuk mewakili fungsi logik.

untuk yang pertama – X 3 X 4;

untuk yang kedua – X 1 X 3;

untuk yang ketiga – X 2 X 3;

untuk keempat – X 1 X 2 X 4;

untuk yang kelima – X 1 X 2 X 4;

DNF minimum akan kelihatan seperti ini:

Membandingkan kaedah peta Karnaugh dengan kaedah pengecilan fungsi lain, kita boleh membuat kesimpulan bahawa yang pertama adalah paling sesuai untuk pelaksanaan manual. Masa buatan sendiri dikurangkan dengan ketara (disebabkan oleh perwakilan visual implikasi pelekat). Pelaksanaan perisian Kaedah ini mempunyai kesukaran tersendiri. Jadi, ia akan menjadi sangat sukar untuk dilaksanakan pilihan yang optimum segi empat tepat biasa, terutamanya untuk nombor besar hujah.

1.3.5 Kaedah pekali tidak pasti

Kaedah ini boleh digunakan untuk sebarang bilangan hujah. Tetapi kerana kaedah ini agak rumit, ia hanya digunakan dalam kes di mana bilangan hujah tidak lebih daripada 5-6.

Kaedah pekali tak tentu menggunakan undang-undang set universal dan nol dan undang-undang pengulangan. Pada mulanya, semua pekali tidak pasti (oleh itu nama kaedah).

Mari kita bina matriks pekali tidak pasti untuk empat hujah. Dalam kes ini, kita akan mempunyai sistem 16 persamaan.

Sistem ditunjukkan pada halaman seterusnya.

Mari kita samakan semua pekali kepada 0 dalam baris yang sepadan dengan 0 dalam lajur vektor. Kemudian kita samakan pekali yang sepadan dalam baris lain kepada 0. Selepas transformasi ini, sistem akan mengambil bentuk berikut:

V = 1 VVVVVV = 1 VVV V VV = 1 V = 1 VVV = 1 VVVVVV = 1 VVV = 1 VVVVV = 1 VVV = 1

Sekarang dalam setiap baris anda perlu memilih pekali pangkat minimum dan tetapkannya sama dengan satu, dan pekali yang tinggal kepada 0. Selepas ini, potong garisan yang sama, tinggalkan salah satu daripadanya (garisan dengan semua pekali sama dengan 0 juga disilang keluar).

= 1 = 1 = 1 = 1 = 1

Mari kita sekarang menulis kata hubung yang sepadan dengan pekali sama dengan perpaduan. Kami akan mendapat DNF minimum.

F(X 1 X 2 X 3 X 4) = X 1 X 3 V X 2 X 3 V X 3 X 4 V X 1 X 2 X 4 V X 1 X 2 X 4 .

Jadi, kami memperoleh DNF minimum dalam beberapa cara. Dalam semua kes, ia ternyata sama, iaitu, mana-mana kaedah yang diterangkan boleh digunakan untuk meminimumkan fungsi. Walau bagaimanapun, kaedah ini berbeza dengan ketara antara satu sama lain dalam prinsip mencari MDNF dan dalam masa pelaksanaan. Kaedah peta Karnaugh sangat mudah untuk pengiraan manual. Ia adalah visual dan tidak memerlukan operasi rutin, dan memilih lokasi optimum bagi segi empat tepat yang betul tidaklah sukar. Manakala pelaksanaan mesin kaedah ini adalah rumit oleh keperluan untuk mencari susunan optimum segi empat tepat. Sememangnya, penggunaan kaedah lain (kaedah Quine, kaedah Quine-McCluskey, kaedah pekali tak tentu) untuk pengiraan manual adalah tidak sesuai. Ia lebih sesuai untuk pelaksanaan mesin, kerana ia mengandungi sejumlah besar operasi mudah berulang.

Tugasan 2.

2.1 Gambar rajah algoritma untuk kaedah Quine

1. Permulaan.

2. Masukkan matriks DSNF bagi fungsi asal.

3. Periksa garis i-th (i=1,m-1: dengan m ialah bilangan garisan dalam DSNF) dan garisan j-th (j=i+1, m) untuk pelekatan. Jika garisan melekat bersama, kemudian pergi ke langkah 6, jika tidak pergi ke langkah 5.

4. Bentukkan susunan implikasi mudah, setelah sebelumnya ditanda dengan simbol ‘*’ pembolehubah yang mana rentetan ini dilekatkan bersama.

5. Pergi ke langkah 2.

6. Tulis baris yang tidak digabungkan dengan mana-mana baris lain ke dalam tatasusunan akhir.

7. Pergi ke langkah 2.

8. Output matriks yang terhasil.

Gambar rajah logik algoritma dalam tatatanda Lyapunov

V H V 1 Z 1 V 2 ¯ V 3 V 4 V K

V H – permulaan.

V 1 – masukkan matriks DSNF bagi fungsi asal.

V 2 – membentuk tatasusunan implikasi mudah, setelah sebelumnya ditanda dengan simbol ‘*’ pembolehubah yang mana rentetan ini dilekatkan bersama.

V 3 – rentetan yang tidak digabungkan dengan mana-mana rentetan lain ditulis ke dalam tatasusunan akhir.

V 4 – keluaran matriks yang terhasil.

Z 1 – jika garisan dilekatkan bersama, kemudian pergi ke langkah 3, jika tidak pergi ke langkah 5.

V K – akhir.

Gambar rajah graf algoritma.

Penerangan mesin prosedur

Prosedur Tersekat(S1, S2: Diz; IndexS1, IndexS2: bait);

Prosedur ini melekatkan kedua-dua belah yang dilalui padanya. Klausa dinyatakan dalam parameter S1, S2. Indeks IndeksS1, IndeksS2 menentukan indeks klausa ini dalam tatasusunan kerja utama. Algoritma prosedur adalah seperti berikut: pertama, bilangan aksara yang dilekatkan bersama dicari. Jika terdapat 0 daripadanya, maka ia adalah sama, dan hanya satu daripadanya ditulis ke tatasusunan akhir. Jika 1, maka lokasi simbol ditentukan di mana kedua-dua belah ini dilekatkan bersama, dan kami menggantikan simbol ini dengan ‘*’. Semua keputusan yang diperoleh dimasukkan ke dalam tatasusunan REZ.

Semua fungsi dan prosedur program lain berkaitan dengan tindakan pada tatasusunan, iaitu, ia tidak berkaitan secara langsung dengan kaedah ini mencari MDNF. Oleh itu tidak ada gunanya menggambarkan mereka.

2.2 Gambar rajah algoritma bagi kaedah Petrik

1. Permulaan.

2. Masukkan matriks DSNF bagi fungsi asal dan implikasi mudah yang diperoleh dalam kaedah Quine.

3. Buat jadual label.

4. Dengan menggunakan jadual label, bina kata hubung bagi disjungsi, setiap satunya ialah satu set implikasi yang terdapat dalam lajur ini mempunyai markah.

Algebra logik

3.3.1. Meminimumkan FAL menggunakan matriks Carnot

Matriks Carnot ialah sejenis jadual kebenaran FAL, yang dibahagikan kepada sel. Bilangan sel matriks ialah 2 n, Di mana n– bilangan hujah FAL. Lajur dan baris matriks ditetapkan oleh set argumen. Setiap sel matriks sepadan dengan juzuk unit FAL (nombor binari). Nombor binari sel terdiri daripada satu set argumen baris dan lajur. Matriks Carnot untuk FAL, bergantung pada dua argumen, dibentangkan dalam bentuk jadual 3.3., daripada tiga argumen dalam jadual 3.4. dan daripada empat argumen jadual 3.5.

Jadual 3.3.

Jadual 3.5.

X 3 X 4 X 1 X 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Sel-sel matriks (Jadual 3.3., 3.4. dan 3.5.) dinomborkan dengan persamaan perpuluhan bagi nombor perduaan sel. Sel matriks bersebelahan, secara mendatar dan menegak, mengandungi nombor binari bersebelahan. Di samping itu, nombor binari bersebelahan ditemui dalam semua lajur baris atas dan bawah, serta dalam semua baris lajur paling luar.

Proses meminimumkan FAL menggunakan matriks Carnot adalah berdasarkan hukum melekatkan nombor binari bersebelahan. Anda boleh melekatkan nombor perduaan sel bersebelahan, tetapi disyorkan untuk melekatkan set hujah yang menunjukkan baris dan lajur matriks. Mari kita pertimbangkan untuk melekatkan nombor binari sel-sel lajur pertama matriks (Jadual 3.5.).

Sel 0 dan 4, nombor binari 0000 dan 0100, masing-masing, hasil pelekatan ialah 0-00.

Sel 8 dan 12, nombor binari 1000 dan 1100, keputusan 1-00. Implikasi yang terhasil dilekatkan bersama, kerana Tanda sempang berada di tempat yang sama dan nombor perduaan tersirat adalah bersebelahan, keputusan akhir ialah - 00.

Sel 8 dan 12

Oleh itu, jika semua nombor perduaan satu lajur dilekatkan bersama, maka bit yang menunjukkan baris itu hilang. Begitu juga, jika semua nombor perduaan satu baris dilekatkan bersama, contohnya 4, 5, 7, 6, maka semua digit yang menunjukkan lajur hilang, i.e. keputusan akan menjadi berikut 01- -.

Jika nombor perduaan bagi mana-mana dua sel sahaja dilekatkan bersama, maka sengkang diletakkan dan bukannya digit nombor perduaan baris atau lajur yang akan berubah apabila sel bergerak dari satu baris ke baris yang lain (atau dari satu lajur ke lajur yang lain) . Sebagai contoh, nombor sel 5 dan 13 dilekatkan bersama, kita mendapat keputusan -101, atau sel 7 dan 6 hasilnya ialah 011-.

Apabila melekatkan nombor binari lapan sel bersebelahan, tiga pembolehubah hilang, contohnya, untuk sel 3, 7, 15, 11, 2, 6, 14, 10, pembolehubah hilang X 1 , X 2 , X 3. Pembolehubah X 1 , X 2 hilang kerana semua sel lajur dilekatkan bersama, dan X 3 kerana dua lajur terakhir dilekatkan bersama.

Sebelum mempertimbangkan contoh meminimumkan FAL menggunakan matriks Carnot, adalah perlu untuk mengklasifikasikan set hujah dengan bantuan yang mana fungsi algebra logik ditentukan.

Adalah diketahui bahawa untuk setiap FAL terdapat 2 set hujah n, Di mana n– bilangan hujah yang bergantung kepada fungsi atau ungkapan logik.

Set hujah terbahagi kepada tiga jenis

1. Set hujah yang fungsinya sama dengan satu dipanggil bekerja.

2. Set hujah yang fungsinya sama dengan sifar dipanggil dilarang.

3. Set hujah yang fungsinya boleh sama dengan satu atau sifar dipanggil acuh tak acuh.

Jika FAL tertentu tidak mempunyai set acuh tak acuh, maka ia boleh diwakili dalam ungkapan literal dalam bentuk SDNF. Jika terdapat set acuh tak acuh dalam FAL tertentu, perwakilannya boleh mempunyai bentuk berikut.

di mana persamaan perpuluhan set kerja,

– persamaan perpuluhan bagi set terlarang.

Himpunan hujah yang bukan di antara yang bekerja dan yang dilarang akan menjadi acuh tak acuh.

Contoh 3.3. Minimumkan FAL yang diberikan dalam bentuk SDNF menggunakan matriks Carnot.

Oleh itu, fungsi ditentukan oleh set kerja sahaja. Selebihnya akan dilarang. Fungsi bergantung pada tiga argumen sahaja. Kami membina matriks Carnot dan memasukkannya ke dalam selnya yang sepadan dengan set kerja, dan meletakkan sifar dalam sel yang tinggal.

Jadual 3.5.

X 2 X 3 X 1
	0

Untuk meminimumkan, sel matriks yang mengandungi sel digabungkan menjadi kontur. Litar boleh merangkumi dua sel, empat atau kesemua lapan. DALAM dalam contoh ini garis besar termasuk empat sel bersebelahan baris yang sama. Implikan bagi kontur yang diberikan ialah 1 - -. Hasil pengecilan adalah seperti berikut, i.e. terdapat pengurangan fungsi yang diberikan dalam SDNF dengan 11 huruf.

Contoh 3.4. Minimumkan ungkapan Boolean yang diberikan oleh set berfungsi dan terlarang menggunakan matriks Carnot.

Kami membina matriks Carnot untuk empat pembolehubah dan mengisi sel dengan satu dan sifar, masing-masing, untuk set berfungsi dan terlarang.

Jadual 3.6.

X 3 X 4 X 1 X 2	00
		(1)

	(1)	(1)

Apabila menggabungkan sel dengan unit ke dalam kontur, adalah wajar setiap kontur termasuk bilangan sel yang mungkin paling banyak. Untuk melakukan ini, kami menggunakan sel beberapa set acuh tak acuh sebagai sel set kerja, menggantikan sel dalam kurungan ke dalamnya. Hasilnya, kami mendapat tiga kontur yang mengandungi 4 sel setiap satu. Dalam kod litar umum, yang merangkumi semua sel satu baris, pembolehubah hilang X 2 X 3 (10 - -). Dalam kod litar umum, yang merangkumi semua sel satu lajur, pembolehubah hilang X 1 X 2 (- - 11) dan untuk kontur yang mengandungi dua sel dua garis, pembolehubah hilang X 2 (apabila bergerak dari satu baris ke satu baris yang lain dalam kontur) dan X 3 (apabila bergerak dari satu lajur ke lajur yang lain). Akibatnya, kami memperoleh DNF minimum dalam borang berikut

Pilihan yang mungkin gabungan sel matriks Carnot ke dalam kontur ditunjukkan dalam Rajah 3.4.

X 3 X 4 X 1 X 2

A = 0 - 0 -

Z = - 0 - 0

B = 1 - 1 -

K = - - - 1

B = - - 0 0

L = - 1 - -

Г = 1 0 - -

M = - - - 0

D = - 0 0 1

H = - 0 - -

E = - 0 1 -

F = - 1 - 1

nasi. 3.1. Pilihan yang mungkin untuk menggabungkan sel matriks Carnot ke dalam kontur

3.3.2. Meminimumkan fungsi algebra logik menggunakan matriks lima pembolehubah

Matriks pengecilan untuk lima pembolehubah dibina sama dengan matriks Carnot, i.e. dalam matriks ini, lajur dan baris bersebelahan mesti ditetapkan oleh nombor binari bersebelahan set pembolehubah

Dalam matriks lima pembolehubah (Jadual 3.7.), baris sepadan dengan set pembolehubah X 1 X 2 X 3, dan lajur ialah set pembolehubah X 4 X 5 . Setiap sel matriks sepadan dengan nombor perduaan lima bit. Sel-sel matriks (Jadual 3.7.) mengandungi persamaan perpuluhan bagi nombor binari yang sepadan.

Jadual 3.7.

X 4 X 5 X 1 X 2 X 3

Meminimumkan FAL menggunakan matriks lima pembolehubah terdiri daripada menggabungkan sel dengan set kerja (termasuk, jika perlu, sel dengan set acuh tak acuh) ke dalam kontur dan mendapatkan kod umum yang sepadan dengan kontur ini.

Keanehan di sini ialah dalam lajur matriks lima pembolehubah, anda boleh menggabungkan empat sel menjadi kontur sahaja, atau empat sel di bahagian atas, atau empat sel di bahagian bawah, atau empat sel di tengah. Contohnya, untuk lajur terakhir matriks, kontur mungkin terdiri daripada sel 2, 6, 14, 10, atau 26, 30, 22, 18 atau 14, 10, 26, 30.

Contoh 3.6. Gunakan matriks lima pembolehubah untuk meminimumkan ungkapan logik berikut

Kami membina matriks lima pembolehubah dan mengisi sel set kerja dengan satu, dan sel set terlarang dengan sifar.

Kami menggabungkan sel dengan set kerja ke dalam kontur, termasuk sel yang diperlukan bagi set acuh tak acuh. Untuk setiap litar kami mentakrifkan kod umum.

Jadual 3.8.

X 4 X 5 X 1 X 2 X 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Kami mendapat DNF minimum

Soalan kawalan

1. Takrifkan DNF yang disingkatkan.

2. Apakah itu DNF buntu?

3. Bagaimanakah DNF minimum dipilih daripada DNF buntu?

4. Apakah kegunaan jadual implikan dan bagaimanakah ia dibina?

5. Terangkan kaedah analisis untuk meminimumkan Quine-McClassky FAL.

6. Bagaimanakah matriks Carnot dibina untuk tiga dan empat pembolehubah?

7. Minimumkan yang berikut secara analitik ungkapan logik, ditakrifkan hanya oleh set kerja

8. Menggunakan matriks Carnaugh, minimumkan ungkapan logik yang ditentukan oleh set kerja dan terlarang

Maklumat berkaitan.

Meminimumkan fungsi logik adalah salah satu daripada tugas biasa dalam proses pembelajaran reka bentuk litar. Oleh itu, saya berpendapat bahawa artikel sedemikian mempunyai tempat, saya harap anda menyukainya.

Mengapa ini perlu?

Kerumitan fungsi logik, dan oleh itu kerumitan dan kos litar yang melaksanakannya, adalah berkadar dengan bilangan operasi logik dan bilangan kejadian pembolehubah atau penolakannya. Pada dasarnya, sebarang fungsi logik boleh dipermudahkan secara langsung menggunakan aksiom dan teorem logik, tetapi, sebagai peraturan, transformasi sedemikian memerlukan pengiraan yang rumit.

Di samping itu, proses memudahkan ungkapan Boolean bukan algoritma. Oleh itu, lebih dinasihatkan untuk menggunakan khas kaedah algoritma pengecilan yang membolehkan penyederhanaan fungsi dijalankan dengan lebih ringkas, cepat dan bebas ralat. Kaedah tersebut termasuk, sebagai contoh, kaedah Quine, kaedah peta Karnaugh, kaedah ujian implikan, kaedah matriks implikan, kaedah Quine-McCluskey, dsb. Kaedah ini paling sesuai untuk amalan biasa, terutamanya meminimumkan fungsi logik menggunakan peta Karnaugh. Kaedah peta Karnaugh mengekalkan kejelasan apabila bilangan pembolehubah tidak lebih daripada enam. Dalam kes di mana bilangan hujah lebih daripada enam, kaedah Quine-McCluskey biasanya digunakan.

Dalam proses meminimumkan fungsi logik tertentu, ia biasanya diambil kira dalam asas apakah ia akan menjadi lebih cekap untuk melaksanakan bentuk minimumnya menggunakan litar elektronik.

Meminimumkan Fungsi Logik Menggunakan Peta Karnaugh

Peta Carnot - kaedah grafik meminimumkan fungsi pensuisan (Boolean), memberikan kemudahan relatif untuk bekerja dengan ekspresi besar dan menghapuskan perlumbaan yang berpotensi. Mewakili operasi gam tidak lengkap berpasangan dan penyerapan asas. Peta Karnaugh dianggap sebagai jadual kebenaran bagi fungsi yang disusun semula dengan sewajarnya. Peta Carnaugh boleh dianggap sebagai pembangunan rata khusus bagi kubus Boolean n-dimensi.

Dalam peta Carnaugh, pembolehubah Boolean dipindahkan daripada jadual kebenaran dan dipesan menggunakan kod Kelabu, di mana setiap nombor seterusnya berbeza daripada yang sebelumnya dengan hanya satu digit.

Kaedah utama untuk meminimumkan fungsi logik yang dibentangkan dalam bentuk SDNF atau SCNF ialah operasi pelekatan tidak lengkap berpasangan dan penyerapan asas. Operasi pelekatan berpasangan dijalankan antara dua istilah (ahli) yang mengandungi pembolehubah yang sama, kejadiannya (langsung dan songsang) bertepatan untuk semua pembolehubah kecuali satu. Dalam kes ini, semua pembolehubah kecuali satu boleh dikeluarkan daripada kurungan, dan kejadian langsung dan songsang bagi satu pembolehubah yang tinggal dalam kurungan boleh dilekatkan bersama. Sebagai contoh:

Kemungkinan penyerapan berikutan daripada persamaan yang jelas

Oleh itu, tugas utama Apabila meminimumkan SDNF dan SCNF, adalah perlu untuk mencari istilah yang sesuai untuk melekat dengan penyerapan berikutnya, yang untuk bentuk besar boleh menjadi tugas yang agak sukar. Peta Carnaugh menyediakan cara visual untuk mencari istilah sedemikian.

Seperti yang diketahui, fungsi Boolean pembolehubah N, yang dibentangkan dalam bentuk SDNF atau SCNF, boleh mengandungi 2N istilah yang berbeza. Kesemua istilah ini membentuk struktur tertentu, secara topologi bersamaan dengan kubus N-dimensi, dan mana-mana dua sebutan yang disambungkan oleh tepi adalah sesuai untuk pelekatan dan penyerapan.

Gambar menunjukkan meja ringkas nilai kebenaran untuk fungsi dua pembolehubah, kubus 2 dimensi (persegi) sepadan dengan jadual ini, serta kubus 2 dimensi dengan sebutan sebutan SDNF dan jadual setara untuk mengelompokkan istilah:

Dalam kes fungsi tiga pembolehubah, anda perlu berurusan dengan kubus tiga dimensi. Ini lebih rumit dan kurang visual, tetapi secara teknikal mungkin. Rajah menunjukkan, sebagai contoh, jadual kebenaran untuk fungsi Boolean bagi tiga pembolehubah dan kubus sepadannya.

Seperti yang dapat dilihat dari rajah, untuk kes tiga dimensi, konfigurasi istilah yang lebih kompleks adalah mungkin. Sebagai contoh, empat sebutan kepunyaan satu muka kubus digabungkan menjadi satu sebutan dengan dua pembolehubah diserap:

Secara umum, kita boleh mengatakan bahawa sebutan 2K kepunyaan satu muka dimensi K hiperkubus dilekatkan bersama menjadi satu sebutan, dan pembolehubah K diserap.

Untuk memudahkan kerja dengan fungsi Boolean bagi sejumlah besar pembolehubah, perkara berikut telah dicadangkan penerimaan yang selesa. Kubus, yang mewakili struktur sebutan, dibentangkan pada satah seperti yang ditunjukkan dalam rajah. Ini memungkinkan untuk mewakili fungsi Boolean dengan lebih daripada dua pembolehubah dalam bentuk jadual rata. Perlu diingat bahawa susunan kod istilah dalam jadual (00 01 11 10) tidak sepadan dengan susunan nombor binari, dan sel yang terletak di lajur luar jadual bersebelahan antara satu sama lain.

Dengan cara yang sama, anda boleh bekerja dengan fungsi empat, lima atau lebih pembolehubah. Contoh jadual untuk N=4 dan N=5 ditunjukkan dalam rajah. Untuk jadual ini, harus diingat bahawa sel jiran adalah sel yang terletak di dalam sel yang sepadan pada lajur paling luar dan sel yang sepadan di atas dan pokoknya. Untuk jadual 5 atau lebih pembolehubah, anda juga mesti mengambil kira bahawa petak 4x4 hampir terletak di atas satu sama lain dalam dimensi ketiga, oleh itu sel yang sepadan bagi dua petak 4x4 bersebelahan adalah bersebelahan, dan istilah yang sepadan dengannya boleh dilekatkan bersama.

Peta Karnaugh boleh disusun untuk sebarang bilangan pembolehubah, tetapi ia adalah mudah untuk berfungsi dengan tidak lebih daripada lima pembolehubah. Pada asasnya, Peta Karnaugh ialah jadual kebenaran yang disusun dalam bentuk 2 dimensi. Terima kasih kepada penggunaan kod Kelabu, baris atas bersebelahan dengan bahagian bawah, dan lajur kanan bersebelahan dengan kiri, i.e. keseluruhan Peta Carnot diruntuhkan menjadi bentuk torus (donut). Di persimpangan baris dan lajur, nilai yang sepadan daripada jadual kebenaran dimasukkan. Setelah Kad diisi, anda boleh mula meminimumkan.

Jika perlu untuk mendapatkan DNF minimum, maka dalam Peta kita hanya mempertimbangkan sel yang mengandunginya; jika CNF diperlukan, maka kita menganggap sel yang mengandungi sifar. Pengurangan itu sendiri dilakukan mengikut peraturan berikut (menggunakan contoh DNF):

Seterusnya, kami mengambil kawasan pertama dan melihat pembolehubah mana yang tidak berubah dalam kawasan ini, tuliskan gabungan pembolehubah ini, jika pembolehubah tidak berubah adalah sifar, kami meletakkan penyongsangan di atasnya. Ambil kawasan seterusnya, lakukan perkara yang sama seperti yang pertama, dan seterusnya untuk semua kawasan. Kami menggabungkan kata hubung kawasan dengan percanggahan.
Contohnya (untuk Peta dengan 2 pembolehubah):

Untuk CNF, segala-galanya adalah sama, hanya kami menganggap sel dengan sifar, pembolehubah tidak berubah dalam satu rantau digabungkan menjadi percanggahan (kami meletakkan penyongsangan ke atas pembolehubah unit), dan pencacah kawasan digabungkan menjadi konjungsi. Pada ketika ini, pengecilan dianggap selesai. Jadi untuk Peta Karnaugh dalam Rajah 1, ungkapan dalam format DNF akan kelihatan seperti:

Dalam format CNF: