Untuk rumus logika apa pun, dengan menggunakan transformasi identitas, seseorang dapat membuat banyak rumus yang setara dengannya. Dalam aljabar logika, salah satu tugas utamanya adalah mencari bentuk kanonik (yaitu rumus yang dibuat menurut satu aturan, kanon).

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

Di antara bentuk-bentuk normal, bentuk-bentuk normal sempurna dibedakan (bentuk-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 ditulis dalam bentuk berikut: F 1 ∨ F 2 ∨ ... ∨ F n , dimana F i adalah 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 di tempat ke-i konjungsi tersebut terdapat 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 (PCNF)

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 (CPNF) jika:
1) rumusnya adalah CNF, yang setiap disjungsi elementernya merupakan disjungsi k variabel x 1, x 2, ..., x k, dan pada tempat ke-i disjungsi tersebut terdapat 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 menggunakan 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 untuk membangun SCNF menggunakan tabel kebenaran

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

Analisis algoritma menunjukkan bahwa jika pada sebagian besar baris tabel kebenaran nilai fungsinya adalah 0, maka untuk mendapatkan rumus logikanya lebih baik membuat SDNF, jika tidak - SCNF.

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

Karena pada sebagian besar baris tabel kebenaran nilai fungsinya adalah 1, maka kita akan membuat SCNF. Hasilnya, kita memperoleh rumus logika berikut:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

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

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

Bentuk normal aljabar proposisional disjungtif dan konjungtif. Untuk setiap fungsi logika proposisional, tabel kebenaran dapat dibuat. 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 (disjungsi) disebut disjungsi variabel dengan atau tanpa negasi.

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

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

Algoritma untuk membuat DNF:

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

2. Gunakan 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. Ambil suku yang berulang satu per satu - hukum idempotensi.

5. Menerapkan hukum serapan dan setengah serapan.

Contoh 6. Temukan rumus DNF: .

Dalam aljabar Boolean hal ini benar 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 .

Di antara fungsi-fungsi dasar aljabar logika, 1 adalah ganda terhadap 0 dan sebaliknya, x adalah ganda terhadap x, ganda menjadi , ganda dan sebaliknya.

Jika pada rumus F 1 yang mewakili fungsi kita mengganti semua konjungsi

pada disjungsi, disjungsi pada konjungsi, 1 lawan 0, 0 lawan 1, maka diperoleh rumus F* yang mewakili fungsi * ganda ke .

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

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 SCNF.

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

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

Contoh 9. Temukan SDNF untuk DNF Contoh 6

Disjungsi dasar sempurna adalah jumlah logis dari semua variabel dengan atau tanpa negasi, dan setiap variabel dimasukkan ke dalam jumlah hanya satu kali.

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

Contoh 10. Bawa KNF ke SKNF:

Untuk membuat SCNF, Anda dapat menggunakan diagram

Contoh 11. Temukan SCNF untuk rumus contoh 6.

Setiap fungsi memiliki SDNF dan, terlebih lagi, memiliki fungsi yang unik. Setiap fungsi memiliki SCNF dan, terlebih lagi, fungsi yang unik.

Karena SDNF dan SKNF ditentukan secara unik oleh rumus; keduanya dapat dibuat menggunakan 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 suatu 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 membuat SCNF menggunakan tabel kebenaran, perlu untuk memilih baris-baris di dalamnya yang F = 0, dan menuliskan disjungsi dasar sempurna, kemudian menghubungkannya dengan tanda konjungsi. Jika pada baris tabel kebenaran yang disyaratkan (F=0) nilai variabel sama dengan nol, maka pada klausa sempurna diambil tanpa negasi, jika satu maka dengan negasi.

Contoh 12. Cari SDNF dan SCNF menggunakan tabel kebenaran rumus contoh 6.

Tabel 14 hanya menunjukkan nilai akhir F=10101101. Anda harus memverifikasi sendiri validitas pernyataan ini dengan membuat tabel kebenaran terperinci.

Tabel 14

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

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

Kuliah 1.xx

Bentuk normal dari fungsi logika

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

, (2.7)

ditelepon bentuk normal disjungtif(DNF) dari fungsi ini.

Jika semua suku penghubung di DNF adalah persyaratan , yaitu memuat tepat satu dari semua variabel logika, diambil dengan atau tanpa negasi, maka bentuk representasi fungsi ini disebutbentuk normal disjungtif sempurna(SDNF ) fungsi ini. Ini disebut SDNF 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.

Dengan memperhatikan hal di atas, teorema berikut mengikuti Teorema 2.1.

Teorema 2. Fungsi Boolean apa pun(tidak identik 0) dapat disajikan dalam SDNF, .

Contoh 3. Mari kita buat tabel dengan fungsi tertentu f (x 1 , x 2 , x 3 ) (Tabel 10).

Tabel 10

Berdasarkan rumus (2.6) kita memperoleh:

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

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

, (2.8)

ditelepon bentuk normal konjungtif(CNF) dari fungsi ini.

Jika semua suku CNF disjungtif adalah ketentuan maksimal , yaitu berisi tepat satu dari 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 dengan 1) dapat diserahkan ke SKNF, dan representasi seperti itu adalah satu-satunya.

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 seperti ini:

. (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 di CNF (kecuali untuk yang identik). ). Tergantung pada situasinya, representasi suatu 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 memiliki keinginan untuk membuka tanda kurung dan dengan demikian beralih ke DNF).

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

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

Perlu dicatat bahwa tidak mungkin untuk berpindah secara langsung dari SDNF suatu fungsi ke SCNF-nya atau sebaliknya. Saat mencoba transformasi tersebut, hasilnya adalah fungsi yang berlawanan dengan yang diinginkan. Ekspresi fungsi SDNF dan SCNF hanya dapat diperoleh langsung dari tabel kebenarannya.

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

Dengan menggunakan hasil contoh 2.3 kita mendapatkan:

Seperti yang Anda lihat, dengan inversi umum kami memperoleh SCNF dari fungsi logika, yang merupakan kebalikan dari fungsi yang diperoleh pada contoh 2.4:

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

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

2. Dengan menggunakan sifat negasi dan hukum De Morgan (lihat Tabel 9), kami memastikan bahwa operasi negasi hanya berlaku untuk variabel individual, dan tidak untuk seluruh 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 lanjutkan ke bentuk penyempurnaan (SDNF atau SKNF). Misalnya, untuk mendapatkan SCNF Anda sering kali perlu menggunakan properti: .

Contoh 6. Ubah fungsi logis menjadi SKNF

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

Dengan menggunakan sifat absorpsi, diperoleh:

Jadi, kita telah memperoleh fungsi CNF f (x 1 , x 2 , x 3 ). Untuk mendapatkan SCNF-nya, Anda perlu mengulangi setiap disjungsi yang tidak ada variabelnya, dua kali dengan variabel ini dan dengan negasinya:

2.2.6. Meminimalkan Fungsi Logis

Karena fungsi logis yang sama dapat direpresentasikan sebagai H rumus pribadi, lalu mencari bentuk yang paling sederhana R bagal yang mendefinisikan fungsi Boolean, menyederhanakan rangkaian logika yang mengimplementasikan fungsi Boolean untuk menyebutkan. Bentuk minimal l HAI fungsi logisdalam beberapa hal kita dapat mempertimbangkan salah satu yang mengandung jumlah minimum superposisi kesenangan Ke dasar, memungkinkan adanya tanda kurung. Namun, sulit untuk membangun sistem yang efektif aku algoritma untuk minimalisasi tersebut untuk mendapatkan tanda kurung minimum r kita.

Mari kita pertimbangkan masalah minimalisasi yang lebih sederhana dalam sintesis rangkaian kombinasional, di mana kita tidak mencari bentuk tanda kurung minimal dari suatu fungsi, tetapi DNF minimalnya. Ada algoritma yang sederhana dan 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 hingga tidak ada satu pun suku tersisa yang dapat diikat ke suku lain.

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

Metode ini buruk karena dengan minimalisasi langsung seperti itu, suku-suku penghubung akan hilang, meskipun masih ada kemungkinan penggunaannya untuk perekatan dan penyerapan dengan suku-suku yang tersisa.

Perlu dicatat bahwa metode Quine cukup padat karya, sehingga kemungkinan terjadinya kesalahan selama transformasi cukup tinggi. Namun keuntungannya adalah secara teoritis dapat digunakan untuk sejumlah argumen dan seiring bertambahnya jumlah variabel, transformasi menjadi lebih mudah.

Metode peta Karnaugh

Metode peta Carnot (tabel) merupakan cara yang lebih visual, tidak memakan banyak tenaga dan dapat diandalkan untuk meminimalkan fungsi logis, 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 memungkinkan Anda dengan mudah menemukan DNF minimum fungsi logis dalam bentuk visual grafis. Setiap sel tabel dikaitkan dengan minterm SDNF dari fungsi yang diminimalkan, dan sedemikian rupa sehingga setiap sumbu simetri tabel sesuai dengan zona yang saling berbanding terbalik terhadap beberapa variabel. Susunan sel dalam tabel ini memudahkan untuk menentukan suku-suku melekat SDNF (berbeda dalam tanda inversi hanya satu variabel): letaknya simetris dalam tabel.

Tabel kebenaran dan peta Carnaugh untuk fungsi AND dan OR dua jalur e Variabelnya disajikan pada Gambar. 8. Sebuah nilai ditulis di setiap sel kartu A Nilai suatu fungsi pada kumpulan nilai argumen yang sesuai dengan sel ini N Kamerad

A) DAN b) ATAU

Beras. 8. Contoh peta Karnaugh untuk fungsi dua variabel

Pada peta Karnaugh hanya terdapat satu angka 1 untuk fungsi And, sehingga tidak dapat dilekatkan pada apapun. Ekspresi untuk fungsi minimal hanya akan berisi suku yang bersesuaian dengan 1 ini:

f = x kamu .

Di peta Carnot untuk fungsi OR sudah ada tiga angka 1 dan Anda dapat membuat dua pasangan yang saling menempel, dengan angka 1 sesuai dengan istilah tersebut xy , digunakan dua kali. Dalam ekspresi fungsi minimal, Anda perlu menuliskan suku-suku pasangan yang direkatkan, menyisakan semua variabel yang tidak berubah untuk pasangan ini, dan menghilangkan variabel yang mengubah nilainya. Untuk perekatan horizontal yang 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 Carnotnya ( b dan c). Fungsi f 2 berbeda dari yang pertama karena tidak didefinisikan pada tiga set variabel (dalam tabel ini ditunjukkan dengan tanda hubung).

Saat menentukan fungsi DNF minimum, aturan berikut digunakan. Semua sel yang berisi 1 digabungkan menjadi area persegi panjang tertutup yang disebut k-kubus, dimana k = log 2 K, K besaran 1 pada luas 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 wilayah 2 3 = 8 satuan disebut 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 luasnya bisa berbentuk persegi (tetapi tidak harus), dan jika ganjil k hanya persegi panjang.

Beras. 9. Contoh peta Karnaugh untuk fungsi tiga variabel

Wilayah ini bisa tumpang tindih, artinya sel yang sama bisa masuk ke wilayah berbeda. Kemudian fungsi DNF minimal ditulis sebagai disjungsi semua suku penghubung yang bersesuaian k - kubus.

Masing-masing area yang ditunjukkan pada peta Karnaugh diwakili dalam DNF minimal dengan sebuah konjungsi, jumlah argumennya adalah k kurang dari jumlah total argumen fungsi M , yaitu angka ini sama 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 maknanya.

Jadi, ketika menutupi sel peta dengan area tertutup, kita harus berusaha untuk memastikan bahwa jumlah area minimal, dan setiap area 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 fungsi menurut peta Karnaugh 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 terdefinisi pada peta pada Gambar. 9, V dapat didefinisikan lebih lanjut dengan menggantinya dengan nol atau satu. Untuk fungsi ini, jelas lebih menguntungkan mengganti kedua nilai yang tidak terdefinisi dengan 1. Dalam hal ini, terbentuk dua area, yang merupakan tipe 2 kubus yang berbeda. Maka ekspresi fungsi DNF minimum adalah sebagai berikut:

Saat membangun area tertutup, peta Carnot boleh dilipat menjadi silinder baik secara horizontal maupun vertikal. R sumbu tikal dengan penyatuan sisi yang berlawanan R kamu, yaitu satuan yang terletak di sepanjang tepi peta simetri Carnot H tapi bisa juga digabungkan.

Peta Carnaugh dapat digambar dengan berbagai cara (Gbr. 10).

sebuah b

Beras. 10. Berbagai cara untuk menggambarkan peta Carnaugh
untuk fungsi 3 variabel

Namun pilihan yang paling tepat untuk peta Karnaugh untuk fungsi 2-4 variabel adalah yang ditunjukkan pada Gambar. 11 tabel, karena ditampilkan untuk setiap sel A Kami memiliki semua variabel dalam bentuk langsung atau terbalik.

sebuah b

Beras. sebelas. Gambar peta Carnaugh 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, padanan dan negasi terhadap rumus-rumus non-dasar.

Bentuk normal hadir 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 (PCNF) 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 yang termasuk dalam CNF tertentu.

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

Aturan pembuatan SKNF menggunakan tabel kebenaran

Untuk setiap kumpulan variabel yang mana fungsi sama dengan 0, jumlahnya dituliskan, 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 berisi setiap variabel yang termasuk dalam DNF tertentu, dan dalam urutan yang sama.

Rumus Boolean apa pun yang tidak sepenuhnya salah dapat direpresentasikan dalam SDNF, dan dengan cara yang unik.

Aturan untuk membangun SDNF menggunakan tabel kebenaran

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

Contoh pencarian SCNF dan SDNF

Contoh 1

Tulis fungsi logis menggunakan tabel kebenarannya:

Gambar 1.

Larutan:

Mari kita gunakan aturan untuk membuat SDNF:

Gambar 2.

Kami mendapatkan SDNF:

Mari kita gunakan aturan untuk membuat SCNF.