Untuk rumus logika apa pun, dengan bantuan transformasi identik, dimungkinkan untuk membuat rumus yang setara dengannya dalam jumlah tak terbatas. Dalam aljabar logika, salah satu tugas utamanya adalah mencari bentuk kanonik (yaitu rumus yang dibangun menurut aturan tunggal, kanon).

Jika suatu fungsi logika dinyatakan melalui disjungsi, konjungsi, dan negasi variabel, maka bentuk representasi ini disebut normal.

Di antara bentuk normal, bentuk normal sempurna menonjol (bentuk yang fungsinya ditulis dengan cara yang unik).

Bentuk Normal Disjungtif Sempurna (PDNF)

Definisi. Suatu rumus disebut konjungsi elementer jika dibentuk oleh konjungsi sejumlah variabel tertentu atau negasinya.

Contoh: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definisi. Suatu rumus disebut bentuk normal disjungtif (DNF) jika merupakan disjungsi konjungsi elementer yang tidak berulang.

DNF dituliskan dalam bentuk berikut: F 1 ∨ F 2 ∨ ... ∨ F n , dimana F i merupakan konjungsi elementer

Contoh: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definisi. Rumus logika dalam k variabel disebut bentuk normal disjungtif sempurna (PDNF) jika:
1) rumusnya adalah DNF, yang setiap konjungsi elementernya merupakan konjungsi dari k variabel x 1 , x 2 , ..., x k , dan tempat ke-i dari konjungsi tersebut adalah variabel x i atau negasinya;
2) semua konjungsi dasar dalam DNF tersebut berbeda berpasangan.

Contoh: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Bentuk normal konjungtif sempurna (SKNF)

Definisi. Suatu rumus disebut disjungsi elementer jika dibentuk oleh disjungsi sejumlah variabel atau negasinya.

Contoh: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definisi. Suatu rumus disebut bentuk normal konjungtif (CNF) jika merupakan konjungsi disjungsi elementer yang tidak berulang.

CNF ditulis dalam bentuk berikut: F 1 ∧ F 2 ∧ ... ∧ F n , dimana F i adalah disjungsi elementer

Contoh: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definisi. Rumus logika dalam k variabel disebut bentuk normal konjungtif sempurna (KDNF) jika:
1) rumusnya adalah CNF, yang setiap disjungsi elementernya merupakan disjungsi k variabel x 1 , x 2 , …, x k , dan tempat ke-i disjungsi tersebut adalah variabel x i atau negasinya;
2) semua disjungsi dasar dalam CNF tersebut berbeda berpasangan.

Contoh: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

perhatikan itu fungsi logis apa pun yang tidak sama dengan 0 atau 1 dapat direpresentasikan sebagai SDNF atau SKNF.

Algoritma untuk membangun SDNF sesuai tabel kebenaran

1. Pilih semua baris tabel yang nilai fungsinya sama dengan satu.
2. Untuk setiap baris tersebut, tuliskan konjungsi semua variabel sebagai berikut: jika nilai suatu variabel dalam himpunan ini sama dengan 1, maka variabel itu sendiri dimasukkan ke dalam konjungsi, jika tidak, negasinya.
3. Kami menghubungkan semua konjungsi yang dihasilkan dengan operasi disjungsi.

Algoritma pembuatan SKNF sesuai tabel kebenaran

1. Pilih semua baris tabel yang nilai fungsinya sama dengan nol.
2. Untuk setiap baris tersebut, tuliskan disjungsi semua variabel sebagai berikut: jika nilai suatu variabel dalam himpunan ini adalah 0, maka variabel itu sendiri dimasukkan ke dalam konjungsi, jika tidak, negasinya.
3. Kami menghubungkan semua disjungsi yang diperoleh dengan operasi konjungsi.

Analisis algoritma menunjukkan bahwa jika nilai fungsi sama dengan 0 pada sebagian besar baris tabel kebenaran, maka untuk mendapatkan rumus logikanya, lebih baik membuat SDNF, jika tidak - SKNF.

Contoh: Diberikan tabel kebenaran fungsi logika tiga variabel. Buatlah rumus logis yang mengimplementasikan fungsi ini.

Karena pada sebagian besar baris tabel kebenaran, nilai fungsinya sama dengan 1, lalu kita buat SKNFnya. Hasilnya, kita mendapatkan rumus logika berikut:
F = (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Mari kita periksa rumus yang dihasilkan. Untuk melakukan ini, kami membuat tabel kebenaran dari fungsi tersebut.

Membandingkan tabel kebenaran asli dan tabel yang dibuat untuk rumus logika, kami mencatat bahwa kolom nilai fungsi adalah sama. Artinya fungsi logika dibangun dengan benar.

Bentuk normal disjungtif dan konjungtif dari aljabar proposisional. Untuk setiap fungsi logika proposisional, tabel kebenaran dapat disusun. Masalah sebaliknya juga selalu bisa dipecahkan. Mari kita perkenalkan beberapa definisi.

Konjungsi dasar (konjungsi) disebut konjungsi variabel atau negasinya, yang mana setiap variabel paling banyak muncul

sekali.

Bentuk normal disjungtif(DNF) adalah rumus yang berbentuk disjungsi konjungsi dasar.

Disjungsi dasar (menurut klausa) disebut disjungsi variabel dengan atau tanpa negasi.

Bentuk normal konjungtif(CNF) merupakan rumus yang berbentuk konjungsi disjungsi elementer.

Untuk setiap fungsi aljabar proposisional, seseorang dapat menemukan himpunan bentuk normal disjungtif dan konjungtif.

Algoritma konstruksi DNF:

1. Lanjutkan ke operasi Boolean menggunakan rumus transformasi yang setara.

2. Pergi ke rumus dengan negasi dekat, yaitu rumus yang letak negasinya tidak lebih tinggi dari di atas variabel - terapkan hukum de Morgan.

3. Buka tanda kurung - terapkan hukum distribusi.

4. Pengulangan suku memakan waktu satu kali – hukum idempotensi.

5. Menerapkan hukum serapan dan semi serapan.

Contoh 6 Temukan rumus DNF: .

Dalam aljabar Boole, prinsip dualitas. Ini adalah sebagai berikut.

Fungsinya disebut ganda ke fungsi jika . Itu. untuk menemukan suatu fungsi ganda dari suatu fungsi tertentu, perlu untuk membangun negasi fungsi tersebut dari negasi argumennya.

Contoh 7 Temukan fungsi ganda ke .

Diantara fungsi dasar aljabar logika 1 adalah ganda ke 0 dan sebaliknya, x ganda ke x, ganda ke , ganda ke dan sebaliknya.

Jika pada rumus F 1 yang mewakili fungsi semua konjungsi diganti

pada disjungsi, disjungsi pada konjungsi, 1 pada 0, 0 pada 1, maka kita mendapatkan rumus F * , mewakili fungsi * , ganda .

Bentuk normal konjungtif (CNF) merupakan konsep ganda untuk DNF, sehingga dapat dengan mudah disusun sesuai skema:

Contoh 8 Temukan rumus CNF: .

Dengan menggunakan hasil Contoh 6, kita punya

Bentuk normal disjungtif sempurna dan konjungtif sempurna. Pada masing-masing jenis bentuk normal (disjungtif dan konjungtif) dapat dibedakan kelas bentuk sempurna SDNF dan SKNF.

Konjungsi elementer sempurna adalah perkalian logika semua variabel dengan atau tanpa negasi, dan setiap variabel dimasukkan ke dalam perkalian hanya satu kali.

DNF apa pun dapat direduksi menjadi SDNF dengan memisahkan konjungsi yang tidak memuat semua variabel, mis. penjumlahan variabel x i yang hilang dikalikan menggunakan hukum distributivitas

Contoh 9 Temukan SDNF untuk contoh DNF 6

Disjungsi dasar sempurna disebut penjumlahan logis semua variabel dengan atau tanpa negasi, apalagi setiap variabel dimasukkan ke dalam penjumlahan hanya satu kali.

Setiap CNF dapat direduksi menjadi SKNF dengan menambahkan suku konjungsi yang tidak mengandung variabel apa pun X i dengan menggunakan konjungsi dan menerapkan hukum distributif

Contoh 10 . Mengonversi CNF ke SKNF:

Untuk membangun SKNF, Anda dapat menggunakan skema

Contoh 11. Cari SKNF untuk rumus contoh 6.

Setiap fungsi memiliki SDNF dan, terlebih lagi, satu-satunya fungsi . Setiap fungsi memiliki SKNF dan, terlebih lagi, satu .

Karena SDNF dan SKNF ditentukan secara unik oleh rumus, dapat dibangun berdasarkan tabel kebenaran rumus tersebut.

Untuk membuat SDNF, perlu untuk memilih baris di mana F mengambil nilai 1 dan menuliskan konjungsi dasar yang sempurna untuk baris tersebut. Jika nilai variabel pada baris tabel kebenaran yang diinginkan sama dengan satu, maka dalam konjungsi sempurna diambil tanpa negasi, jika nol maka dengan negasi. Kemudian konjungsi sempurna (jumlahnya sama dengan jumlah satuan dalam tabel) dihubungkan dengan tanda disjungsi.

Untuk membangun SKNF berdasarkan tabel kebenaran, perlu dilakukan pemilihan baris-baris di dalamnya, dimana F=0, dan menuliskan disjungsi dasar sempurna, kemudian menghubungkannya dengan tanda konjungsi. Jika pada baris tabel kebenaran yang diperlukan (F=0) nilai variabel sama dengan nol, maka pada disjung sempurna diambil tanpa negasi, jika sama dengan satu maka dengan negasi.

Contoh 12. Cari SDNF dan SKNF sesuai tabel kebenaran rumus contoh 6.

Tabel 14 hanya menunjukkan nilai akhir F=10101101. Validitas pernyataan ini harus diverifikasi secara independen dengan menyusun tabel kebenaran yang diperluas.

Tabel 14

Bentuk Normal Fungsi Boolean Representasi fungsi Boolean dalam bentuk disjungsi suku-suku penghubung penyusun satuan Ki 2.7 disebut bentuk normal disjungtif DNF fungsi tersebut. memuat tepat satu per satu semua variabel logika yang diambil dengan atau tanpa negasi, maka bentuk representasi fungsi ini disebut bentuk normal disjungtif sempurna dari SDNF fungsi tersebut. Seperti yang Anda lihat, saat mengkompilasi fungsi SDNF, Anda perlu membuat disjungsi semua minterm yang fungsinya bernilai 1.

Jika karya ini tidak cocok untuk Anda, ada daftar karya serupa di bagian bawah halaman. Anda juga dapat menggunakan tombol pencarian

Kuliah 1.xx

Bentuk Normal Fungsi Boolean

Representasi fungsi Boolean dalam bentuk disjungsi suku-suku penghubung (satuan penyusun) K saya

, (2.7)

ditelepon bentuk normal disjungtif(DNF) dari fungsi ini.

Jika semua suku penghubung di DNF adalah persyaratan , yaitu memuat tepat satu per satu semua variabel logika, diambil dengan atau tanpa negasi, maka bentuk representasi fungsi ini disebutbentuk normal disjungtif sempurna(SDNF ) dari fungsi ini. SDNF dipanggil sempurna , karena setiap suku dalam disjungsi mencakup semua variabel; yg memisahkan , karena operasi utama dalam rumus tersebut adalah disjungsi. Konsep "bentuk biasa” berarti cara penulisan rumus yang jelas yang mengimplementasikan fungsi tertentu.

Mengingat hal di atas, Teorema 2.1 menyiratkan teorema berikut.

Teorema 2. Fungsi boolean apa pun(tidak identik sama dengan 0) dapat direpresentasikan dalam SDNF, .

Contoh 3 Biarkan kita memiliki fungsi tabel f (x 1, x 2, x 3) (Tabel 10).

Tabel 10

Berdasarkan rumus (2.6), kita memperoleh:

Seperti yang Anda lihat, saat mengkompilasi fungsi SDNF, Anda perlu membuat disjungsi semua minterm yang fungsinya bernilai 1.

Representasi fungsi Boolean dalam bentuk konjungsi suku-suku disjungtif (konstituen nol) D saya

, (2.8)

ditelepon bentuk normal konjungtif(CNF ) dari fungsi ini.

Jika semua suku disjungtif CNF adalah ketentuan maksimal , yaitu memuat tepat satu per satu semua variabel logis dari fungsi tersebut, diambil dengan atau tanpa negasi, maka CNF seperti itu disebutbentuk normal konjungtif sempurna(SKNF) dari fungsi ini.

Teorema 3. Fungsi boolean apa pun(tidak identik sama dengan 1) dapat diserahkan ke SKNF, dan representasi ini unik.

Pembuktian teorema dapat dilakukan serupa dengan pembuktian Teorema 2.1 berdasarkan lemma Shannon berikut tentang dekomposisi konjungtif.

Lemma Shannon . Fungsi boolean apa pun f (x 1 , x 2 , …, x m ) dari m variabel dapat direpresentasikan sebagai:

. (2.9)

Perlu dicatat bahwa kedua bentuk representasi fungsi logis (DNF dan CNF) secara teoritis memiliki kemampuan yang sama: rumus logika apa pun dapat direpresentasikan baik dalam DNF (kecuali untuk nol yang identik) dan dalam CNF (kecuali untuk unit yang identik) . Tergantung pada situasinya, representasi fungsi dalam satu bentuk atau lainnya mungkin lebih pendek.

Dalam praktiknya, DNF paling sering digunakan., karena bentuk ini lebih familiar bagi seseorang: sejak kecil, dia lebih terbiasa menjumlahkan produk daripada mengalikan jumlah (dalam kasus terakhir, dia secara intuitif ingin membuka tanda kurung dan dengan demikian menuju ke DNF).

Contoh 4. Untuk fungsi f (x 1, x 2, x 3 ), diberikan dalam Tabel. 10, tulis ke SKNF.

Berbeda dengan SDNF, saat menyusun SKNF, dalam tabel kebenaran suatu fungsi logis, Anda perlu melihat kombinasi variabel yang fungsinya bernilai 0, dan membuat konjungsi dari maxterms yang sesuai,tetapi variabelnya harus diambil dengan inversi terbalik:

Perlu dicatat bahwa tidak mungkin untuk berpindah langsung dari SDNF suatu fungsi ke SKNF-nya atau sebaliknya. Saat mencoba transformasi seperti itu, diperoleh fungsi yang berbanding terbalik dengan yang diinginkan. Ekspresi fungsi SDNF dan SKNF hanya dapat diperoleh langsung dari tabel kebenarannya.

Contoh 5. Untuk fungsi f (x 1, x 2, x 3 ), diberikan dalam Tabel. 10, coba alihkan dari SDNF ke SKNF.

Dengan menggunakan hasil contoh 2.3 kita mendapatkan:

Seperti yang Anda lihat, dengan inversi umum, kita mendapatkan SKNF dari fungsi logika, yang merupakan kebalikan dari fungsi yang diperoleh pada contoh 2.4:

karena berisi semua maxterms yang tidak ada dalam ekspresi SKNF dari fungsi yang sedang dipertimbangkan.

1. Dengan menggunakan properti operasi (lihat Tabel 9) identitas (), jumlah modulo 2 (), implikasi (), kita meneruskan ke operasi AND, OR, NOT (ke basis Boole).

2. Dengan menggunakan sifat negasi dan hukum de Morgan (lihat Tabel 9), kita mencapai bahwa operasi negasi hanya berlaku untuk variabel individual, dan tidak untuk keseluruhan ekspresi.

3. Dengan menggunakan sifat-sifat operasi logika AND dan OR (lihat Tabel 9), kita memperoleh bentuk normal (DNF atau CNF).

4. Bila perlu kita lolos ke formulir sempurna (SDNF atau SKNF). Misalnya, untuk mendapatkan SKNF, Anda sering kali perlu menggunakan properti: .

Contoh 6 Konversikan ke Fungsi Boolean SKNF

Dengan melakukan langkah-langkah algoritma di atas secara berurutan, kita mendapatkan:

Dengan menggunakan sifat absorpsi, diperoleh:

Jadi, kami telah memperoleh fungsi CNF f (x 1 , x 2 , x 3 ). Untuk mendapatkan SKNF-nya, Anda perlu mengulangi setiap disjungsi yang tidak memiliki variabel apa pun, dua kali dengan variabel ini dan dengan negasinya:

2.2.6. Minimalkan Fungsi Boolean

Karena fungsi logika yang sama dapat diwakili oleh H rumus pribadi, lalu temukan pho paling sederhana R bagal yang mendefinisikan fungsi Boolean menyederhanakan rangkaian logika yang mengimplementasikan fungsi Boolean ke tsyu. Bentuk minimal l HAI fungsi logisdalam beberapa basis, kita dapat mempertimbangkan basis yang mengandung jumlah minimum superposisi fungsi Ke dasar, izin dan tanda kurung. Namun, sulit untuk membangun yang efisien aku algoritma minimalisasi tersebut dengan mendapatkan fo dalam tanda kurung minimum r kita.

Pertimbangkan masalah minimalisasi yang lebih sederhana dalam sintesis rangkaian kombinasional, yang tidak mencari bentuk fungsi dalam tanda kurung minimal, tetapi DNF minimalnya. Ada algoritma sederhana yang efisien untuk tugas ini.

Metode Quine

Fungsi yang akan diminimalkan direpresentasikan dalam SDNF, dan semua kemungkinan operasi pengeleman yang tidak lengkap diterapkan padanya

, (2.10)

dan kemudian penyerapan

, (2.11)

dan pasangan langkah ini diterapkan berulang kali. Dengan demikian, dimungkinkan untuk menurunkan peringkat istilah. Prosedur ini diulangi sampai tidak ada lagi istilah yang tersisa yang dapat dilekatkan dengan istilah lainnya.

Perhatikan bahwa ruas kiri persamaan (2.10) dapat segera diminimalkan dengan cara yang lebih sederhana dan jelas:

Cara ini buruk karena dengan minimalisasi langsung seperti itu, suku-suku penghubungnya akan hilang, meskipun masih ada kasus penggunaannya untuk merekatkan dan menyerap suku-suku lainnya.

Perlu diperhatikan bahwa metode Quine cukup memakan waktu, sehingga kemungkinan terjadinya kesalahan pada saat transformasi cukup tinggi. Namun keuntungannya adalah secara teoritis dapat digunakan untuk sejumlah argumen, dan seiring bertambahnya jumlah variabel, transformasi menjadi lebih mudah.

Metode peta Carnot

Metode peta Carnot (tabel) adalah cara yang lebih visual, memakan waktu lebih sedikit dan dapat diandalkan untuk meminimalkan fungsi logika, namun penggunaannya secara praktis terbatas pada fungsi 3-4 variabel, maksimal 5-6 variabel.

Peta Carnot ini adalah bentuk tabel dua dimensi yang mewakili tabel kebenaran fungsi Boolean, yang memudahkan untuk menemukan DNF minimum fungsi logika dalam bentuk visual grafis. Setiap sel tabel dikaitkan dengan minterm SDNF dari fungsi yang diminimalkan, terlebih lagi, sedemikian rupa sehingga setiap sumbu simetri tabel sesuai dengan zona yang saling berbanding terbalik dalam beberapa variabel. Susunan sel dalam tabel seperti itu memudahkan untuk menentukan suku-suku SDNF yang melekat (yang berbeda dalam tanda inversi hanya satu variabel): sel-sel tersebut disusun secara simetris dalam tabel.

Tabel kebenaran dan peta Karnaugh untuk fungsi AND dan OR dua jalur e Variabelnya disajikan pada gambar. 8. Sebuah nilai ditulis di setiap sel peta. A nilai fungsi pada himpunan nilai argumen yang sesuai dengan sel ini dan tov.

A ) DAN b ) ATAU

Beras. 8. Contoh peta Karnaugh untuk fungsi dua variabel

Hanya ada satu angka 1 di peta Karnaugh untuk fungsi And, sehingga tidak dapat direkatkan dengan apa pun. Dalam ekspresi fungsi minimum, hanya akan ada suku yang sesuai dengan 1 ini:

f = x kamu .

Sudah ada tiga angka 1 di peta Karnaugh untuk fungsi OR, dan dua pasang perekatan dapat dibuat, dengan 1 sesuai dengan istilah tersebut xy , digunakan dua kali. Dalam ekspresi fungsi minimum, Anda perlu menulis suku-suku untuk pasangan yang akan direkatkan, menyisakan semua variabel yang tidak berubah untuk pasangan ini, dan menghapus variabel yang mengubah nilainya. Untuk perekatan horizontal, kita dapatkan X , dan untuk vertikal kamu , sebagai hasilnya kita mendapatkan ekspresi

f = x + kamu .

Pada gambar. 9 menunjukkan tabel kebenaran dua fungsi tiga variabel ( A ) dan peta Karnotnya ( b dan c). Fungsi f 2 berbeda dari yang pertama karena tidak ditentukan pada tiga kumpulan variabel (ini ditunjukkan dengan tanda hubung pada tabel).

Saat menentukan DNF minimum suatu fungsi, aturan berikut digunakan. Semua sel yang berisi 1 digabungkan menjadi area persegi panjang tertutup yang disebut k-kubus, dimana k = log 2 K, K nomor 1 pada suatu bidang persegi panjang. Dalam hal ini, setiap area harus berbentuk persegi panjang dengan jumlah sel 2 k , dimana k = 0, 1, 2, 3, … . Untuk k = 1 persegi panjang disebut satu berbentuk kubus dan berisi 2 1 = 2 satuan; untuk k = 2 persegi panjang berisi 2 2 = 4 satuan dan disebut dua kubus; untuk k = 3 luas 2 3 = 8 unit dipanggil tiga kubus ; dll. Satuan yang tidak dapat digabungkan menjadi persegi panjang dapat dipanggil nol kubus , yang hanya berisi satu unit (2 0 = 1). Seperti yang bisa dilihat, bahkan k wilayahnya mungkin persegi (tetapi tidak harus), dan jika ganjil k hanya persegi panjang.

Beras. 9. Contoh peta Karnaugh untuk fungsi tiga variabel

Area-area ini dapat tumpang tindih, yaitu sel-sel yang sama dapat dimasukkan ke dalam area yang berbeda. Kemudian DNF minimal dari fungsi tersebut ditulis sebagai disjungsi dari semua suku penghubung yang bersesuaian k - kubus.

Masing-masing area pada peta Karnaugh diwakili dalam DNF minimum dengan sebuah konjungsi, jumlah argumennya adalah k kurang dari jumlah total argumen fungsi M , yaitu nomor ini adalah mk . Setiap konjungsi DNF minimal hanya terdiri dari argumen-argumen yang memiliki nilai untuk area peta yang bersangkutan tanpa inversi atau hanya dengan inversi, yaitu tidak mengubah nilainya.

Jadi, ketika menutupi sel peta dengan wilayah tertutup, kita harus berusaha untuk memastikan bahwa jumlah wilayah minimal, dan setiap wilayah berisi sel sebanyak mungkin, karena dalam hal ini jumlah suku dalam DNF minimal akan minimal dan jumlah suku dalam DNF minimal akan minimal. jumlah argumen dalam konjungsi terkait akan minimal.

Untuk fungsinya sesuai peta Karnot pada Gambar. 9, b kita temukan

karena untuk wilayah tertutup atas variabelnya x 1 dan x 2 memiliki nilai tanpa inversi, untuk yang lebih rendah x 1 penting dengan inversi, dan x 3 tanpa inversi.

Nilai yang tidak ditentukan pada peta pada gambar. 9, V dapat didefinisikan ulang dengan menggantinya dengan nol atau satu. Untuk fungsi ini, jelas lebih menguntungkan jika kedua nilai tak tentu tersebut diganti dengan 1. Dalam hal ini, terbentuk dua daerah yang merupakan tipe 2 kubus yang berbeda. Maka ekspresi fungsi DNF minimum adalah sebagai berikut:

Saat membangun area tertutup, peta Karnot diperbolehkan diciutkan menjadi silinder baik secara horizontal maupun vertikal. R ke sumbu vertikal dengan penyatuan permukaan yang berlawanan ka R Anda, yaitu unit-unit yang terletak di sepanjang tepi peta Carnot secara simetris H tapi, bisa juga digabungkan.

Peta Karnot dapat digambar dengan berbagai cara (Gambar 10).

sebuah b

Beras. 10. Berbagai Cara Menggambarkan Peta Carnot
untuk fungsi 3 variabel

Namun versi peta Karnaugh yang paling mudah digunakan untuk fungsi 2-4 variabel adalah yang ditunjukkan pada Gambar. 11 tabel, karena ditampilkan untuk setiap sel A semua variabel berbentuk langsung atau terbalik.

sebuah b

Beras. sebelas. Gambar peta Carnot yang paling nyaman
untuk fungsi 3 ( a) dan 4 (b) variabel

Untuk fungsi 5 dan 6 variabel, metode yang ditunjukkan pada gambar. 10, V .

Beras. 12. Gambar peta Karnaugh untuk fungsi 5 variabel

Beras. 13. Gambar peta Karnaugh untuk fungsi 6 variabel

bentuk biasa rumus logika tidak mengandung tanda-tanda implikasi, kesetaraan dan negasi dari rumus-rumus non-dasar.

Bentuk normal ada dalam dua bentuk:

bentuk normal konjungtif (CNF)-- konjungsi beberapa disjungsi, misalnya, $\left(A\vee \overline(B)\vee C\right)\wedge \left(A\vee C\right)$;

bentuk normal disjungtif (DNF)-- disjungsi beberapa konjungsi, misalnya $\left(A\wedge \overline(B)\wedge C\right)\vee \left(B\wedge C\right)$.

SKNF

Bentuk normal konjungtif sempurna (SKNF) adalah CNF yang memenuhi tiga kondisi:

tidak mengandung disjungsi dasar yang identik;

tidak ada disjungsi yang mengandung variabel yang sama;

setiap disjungsi dasar berisi setiap variabel dalam CNF yang diberikan.

Rumus Boolean apa pun yang kebenarannya tidak identik dapat direpresentasikan dalam SKNF.

Aturan pembuatan SKNF menurut tabel kebenaran

Untuk setiap kumpulan variabel yang mana fungsi sama dengan 0, dituliskan penjumlahannya, dan variabel yang bernilai 1 diambil dengan negasi.

SDNF

Bentuk Normal Disjungtif Sempurna (PDNF) adalah DNF yang memenuhi tiga kondisi:

tidak mengandung konjungsi dasar yang identik;

tidak ada satupun konjungsi yang mengandung variabel yang sama;

setiap konjungsi dasar memuat setiap variabel dari DNF yang diberikan, terlebih lagi, dalam urutan yang sama.

Terlebih lagi, rumus Boolean apa pun yang tidak sepenuhnya salah dapat direpresentasikan dalam SDNF dengan cara yang unik.

Aturan pembuatan SDNF sesuai tabel kebenaran

Untuk setiap himpunan variabel yang fungsinya sama dengan 1, produknya ditulis, dan variabel yang bernilai 0 diambil dengan negasi.

Contoh pencarian SKNF dan SDNF

Contoh 1

Tuliskan fungsi logika sesuai tabel kebenarannya:

Gambar 1.

Larutan:

Mari kita gunakan aturan untuk membuat SDNF:

Gambar 2.

Kami mendapatkan SDNF:

Mari kita gunakan aturan konstruksi SKNF.