Bentuk normal konjungtif dari fungsi logika. Bentuk normal konjungtif

Definisi 1.Monomial konjungtif (konjungsi dasar) dari variabel disebut konjungsi variabel ini atau negasinya.

misalnya, Merupakan konjungsi dasar.

Definisi 2.Monomial disjungtif (disjungsi dasar) dari variabel disebut disjungsi variabel ini atau negasinya.

misalnya, - disjungsi dasar.

Definisi 3. Rumus yang ekuivalen dengan rumus aljabar proposisi tertentu dan merupakan disjungsi dari monomial konjungtiva elementer disebut bentuk normal disjungtif(DNF) dari rumus ini.

Misalnya,- DNF.

Definisi 4. Rumus yang ekuivalen dengan rumus aljabar proposisi tertentu dan merupakan konjungsi dari monomial disjungtif elementer disebut bentuk normal penghubung(CNF) dari rumus ini.

misalnya, -CNF.

Untuk setiap rumus aljabar proposisional, seseorang dapat menemukan satu set bentuk normal disjungtif dan konjungtif.

Algoritma untuk membangun bentuk normal

Menggunakan kesetaraan aljabar logika, ganti semua operasi dalam rumus dengan yang dasar: konjungsi, disjungsi, negasi:

Singkirkan tanda-tanda negasi ganda.

Terapkan, jika perlu, pada operasi konjungsi dan disjungsi sifat-sifat distribusi dan rumus penyerapan.

2.6. Bentuk normal disjungtif sempurna dan konjungtiva sempurna

Setiap fungsi Boolean dapat memiliki banyak representasi dalam bentuk DNF dan CNF. Tempat khusus di antara representasi ini ditempati oleh DNF sempurna (SDNF) dan CNF sempurna (SKNF).

Definisi 1. Bentuk normal disjungtif sempurna(SDNF) adalah DNF di mana di setiap monomial konjungtif, setiap variabel dari himpunan muncul tepat satu kali, dan muncul sendiri atau negasinya.

Secara konstruktif, SDNF untuk setiap rumus aljabar proposisional yang direduksi menjadi DNF dapat didefinisikan sebagai berikut:

Definisi 2. Bentuk normal disjungtif sempurna(SDNF) dari rumus aljabar proposisi disebut DNF-nya, yang memiliki sifat-sifat berikut:

Definisi 3. Bentuk normal konjungtiva sempurna(SKNF) adalah CNF di mana di setiap monomial disjungtif, setiap variabel dari himpunan muncul tepat satu kali, dan muncul sendiri atau negasinya.

Secara struktural, SKNF untuk setiap rumus aljabar proposisional yang direduksi menjadi CNF dapat didefinisikan sebagai berikut.

Definisi 4. Bentuk normal konjungtiva sempurna(SKNF) dari rumus aljabar proposisi tertentu disebut CNF-nya yang memenuhi sifat-sifat berikut.

Teorema 1. Setiap fungsi Boolean dari variabel yang tidak identik salah dapat direpresentasikan dalam SDNF, dan, terlebih lagi, dengan cara yang unik.

Cara menemukan SDNF

cara pertama

cara ke-2

pilih garis di mana rumus mengambil nilai 1;

kita buat disjungsi konjungsi, dengan syarat jika suatu variabel termasuk dalam konjungsi bernilai 1, maka variabel ini kita tulis, jika dengan nilai 0, maka negasinya. Kami mendapatkan SDNF.

Teorema 2. Setiap fungsi Boolean dari variabel yang tidak identik benar dapat direpresentasikan dalam SKNF dan, terlebih lagi, dengan cara yang unik.

Cara menemukan SKNF

cara pertama- menggunakan transformasi yang setara:

cara ke-2- menggunakan tabel kebenaran:

pilih garis di mana rumus mengambil nilai 0;

kita buat konjungsi disjungsi, asalkan jika suatu variabel termasuk dalam disjungsi dengan nilai 0, maka kita tulis variabel ini, jika dengan nilai 1, maka negasinya. Kami mendapatkan SKNF.

Contoh 1. Plot fungsi CNF.

Larutan

Mari kita kecualikan bundel "" menggunakan hukum transformasi variabel:

= / de Morgan dan hukum negasi ganda / =

/ hukum distributif / =

Contoh 2. Bawa rumus ke DNF.

Larutan

Mari kita nyatakan operasi logis dalam hal, dan:

= / kita akan merujuk negasi ke variabel dan mengurangi negatif ganda / =

= / hukum distribusi /.

Contoh 3. Tuliskan rumus dalam DNF dan SDNF.

Larutan

Dengan menggunakan hukum logika, kita akan membawa rumus ini ke bentuk yang hanya berisi disjungsi dari konjungsi elementer. Rumus yang dihasilkan akan menjadi DNF yang diinginkan:

Untuk membangun SDNF, kita akan membuat tabel kebenaran untuk rumus ini:

Kami menandai baris tabel di mana rumus (kolom terakhir) mengambil nilai 1. Untuk setiap baris tersebut, kami menulis rumus yang benar pada himpunan variabel, dari baris yang diberikan:

baris 1;

baris 3;

baris 5:.

Disjungsi ketiga rumus ini akan mengambil nilai 1 hanya pada himpunan variabel pada baris 1, 3, 5, dan oleh karena itu akan menjadi bentuk normal disjungtif sempurna (SDNF):

Contoh 4. Bawa rumus ke SKNF dengan dua cara:

a) menggunakan transformasi ekuivalen;

b.menggunakan tabel kebenaran.

Larutan:

Kami mengubah disjungsi dasar kedua:

Rumusnya adalah:

b) menyusun tabel kebenaran untuk rumus ini:

Kami menandai baris tabel di mana rumus (kolom terakhir) mengambil nilai 0. Untuk setiap baris tersebut, kami menulis rumus yang benar pada himpunan variabel, dari baris yang diberikan:

baris 2;

baris 6:.

Konjungsi kedua rumus ini akan mengambil nilai 0 hanya pada himpunan variabel pada baris 2 dan 6, dan oleh karena itu akan menjadi bentuk normal konjungtif sempurna (SCNF):

Pertanyaan dan tugas untuk solusi independen

1.Menggunakan transformasi yang setara, bawa rumus ke DNF:

2.Menggunakan transformasi yang setara, bawa rumus ke CNF:

3.Gunakan hukum distributif kedua untuk mengubah DNF ke CNF:

sebuah) ;

4. Ubah DNF yang diberikan ke SDNF:

5. Ubah CNF yang diberikan ke SKNF:

6. Untuk rumus logika yang diberikan, buatlah SDNF dan SKNF dengan dua cara: menggunakan transformasi ekuivalen dan menggunakan tabel kebenaran.

B) ;

Bentuk normal konjungtif cocok untuk pembuktian teorema otomatis. Rumus Boolean apa pun dapat dikonversi ke CNF. Untuk melakukan ini, Anda dapat menggunakan: hukum negasi ganda, hukum de Morgan, distributivitas.

YouTube perguruan tinggi

• 1 / 5

  Rumus di KNF:

  A (B C), (\ displaystyle \ neg A \ wedge (B \ vee C),) (A B) (¬ B ∨ C ∨ ¬ D) (D ∨ ¬ E), (\ displaystyle (A \ vee B) \ wedge (\ neg B \ vee C \ vee \ neg D) \ wedge ( D \ vee \ neg E),) A B. (\ gaya tampilan A \ baji B.)

  Rumus tidak di KNF:

  (B C), (\ displaystyle \ neg (B \ vee C),) (A B) C, (\ displaystyle (A \ wedge B) \ vee C,) A (B (D E)). (\ tampilan gaya A \ baji (B \ vee (D \ baji E)).)

  Tetapi 3 rumus yang tidak ada di CNF ini setara dengan rumus di CNF berikut:

  B ¬ C, (\ displaystyle \ neg B \ wedge \ neg C,) (A C) (B C), (\ gaya tampilan (A \ vee C) \ baji (B \ vee C),) A (B D) (B E). (\ displaystyle A \ wedge (B \ vee D) \ wedge (B \ vee E).)

  Membangun CNF

  Algoritma untuk membangun CNF

  1) Singkirkan semua operasi logis yang terkandung dalam rumus, ganti dengan yang utama: konjungsi, disjungsi, negasi. Ini dapat dilakukan dengan menggunakan rumus yang setara:

  A → B = A B, (\ gaya tampilan A \ panah kanan B = \ neg A \ vee B,) A B = (¬ A B) (A ¬ B). (\ displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ wedge (A \ vee \ neg B).)

  2) Ganti tanda negasi, mengacu pada seluruh ekspresi, dengan tanda negasi, mengacu pada pernyataan variabel individu berdasarkan rumus:

  (A B) = ¬ A ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B,) (A B) = A B. (\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)

  3) Singkirkan tanda negasi ganda.

  4) Terapkan, jika perlu, pada operasi konjungsi dan disjungsi sifat-sifat distribusi dan rumus penyerapan.

  Contoh pembuatan CNF

  Mari kita bawa ke CNF rumusnya

  F = (X → Y) ((¬ Y → Z) → X). (\ gaya tampilan F = (X \ panah kanan Y) \ baji ((\ neg Y \ panah kanan Z) \ panah kanan \ neg X).)

  Mari kita ubah rumusnya F (\ gaya tampilan F) ke formula yang tidak mengandung → (\ gaya tampilan \ panah kanan):

  F = (¬ X Y) (¬ (¬ Y → Z) ¬ X) = (¬ X Y) (¬ (¬ ¬ Y ∨ Z) ​​X). (\ displaystyle F = (\ neg X \ vee Y) \ baji (\ neg (\ neg Y \ panah kanan Z) \ vee \ neg X) = (\ neg X \ vee Y) \ wedge (\ neg (\ neg \ neg Y \ vee Z) \ vee \ neg X).)

  Dalam rumus yang dihasilkan, kami mentransfer negasi ke variabel dan mengurangi negatif ganda:

  F = (¬ X Y) ((¬ Y ¬ Z) X). (\ displaystyle F = (\ neg X \ vee Y) \ wedge ((\ neg Y \ wedge \ neg Z) \ vee \ neg X).)

  Misalnya, rumus berikut ditulis dalam 2-CNF:

  (A B) (¬ B C) (B C). (\ displaystyle (A \ lor B) \ land (\ neg B \ lor C) \ land (B \ lor \ neg C).)

  Disjungsi sederhana(disjungsi inklusif) atau terpisah(English disjunct) adalah disjungsi dari satu atau lebih variabel atau negasinya, dan setiap variabel muncul tidak lebih dari satu kali.

  Disjungsi sederhana

  • menyelesaikan jika setiap variabel (atau negasinya) muncul tepat satu kali di dalamnya;
  • membosankan jika tidak mengandung variabel negatif.

  Bentuk normal konjungtif, CNF(eng. conjunctive normal form, CNF) normal form, di mana fungsi Boolean memiliki bentuk konjungsi dari beberapa klausa sederhana.

  Contoh CNF:$ f (x, y) = (x \ lor y) \ tanah (y \ lor \ neg (z)) $

  SKNF

  Bentuk normal konjungtiva sempurna, SKNF(bentuk normal penghubung sempurna, PCNF) adalah CNF yang memenuhi kondisi berikut:

  • itu tidak memiliki disjungsi sederhana yang sama
  • setiap disjungsi sederhana selesai

  Contoh SKNF:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ tanah (x \ lor y \ lor \ neg (z)) $

  Dalil: Untuk setiap fungsi Boolean $ f (\ vec (x)) $ yang tidak sama dengan identitas, ada SKNF yang mendefinisikannya.

  Bukti: Karena invers dari fungsi $ \ neg (f) (\ vec x) $ sama dengan satu pada tupel di mana $ f (\ vec x) $ sama dengan nol, maka SDNF untuk $ \ neg (f) (\ vec x) $ dapat ditulis sebagai berikut:

  $ \ neg (f) (\ vec x) = \ bigvee \ batas_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ baji x_ (2) ^ (\ sigma_ (2)) \ baji ... \ baji x_ (n) ^ (\ sigma_ (n ))) $, di mana $ \ sigma_ (i) $ menunjukkan ada tidaknya negasi untuk $ x_ (i) $

  Temukan invers dari sisi kiri dan kanan dari ekspresi:

  $ f (\ vec x) = \ neg ((\ bigvee \ batas_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ baji x_ (2) ^ (\ sigma_ (2)) \ baji ... \ baji x_ (n) ^ (\ sigma_ (n ))))) $

  Menerapkan aturan de Morgan dua kali ke ekspresi yang diperoleh di sisi kanan, kita mendapatkan: $ f (\ vec x) = \ bigwedge \ limit_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2), \ dots , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ dots \ vee \ neg (x_n ^ (\ sigma_n ))) $

  Ekspresi terakhir adalah SKNF. Karena SKNF diperoleh dari SDNF, yang dapat dibangun untuk setiap fungsi yang tidak identik dengan nol, teorema terbukti.

  Algoritma untuk membangun SKNF menurut tabel kebenaran

  • Dalam tabel kebenaran kita menandai himpunan variabel yang nilai fungsinya sama dengan $ 0 $.
  • Untuk setiap himpunan yang ditandai, kami menulis disjungsi semua variabel menurut aturan berikut: jika nilai beberapa variabel adalah $ 0 $, maka variabel itu sendiri termasuk dalam disjungsi, jika tidak maka negasinya.
  • Kami menghubungkan semua disjungsi yang dihasilkan dengan operasi konjungsi.

  Contoh pembuatan SKNF untuk median

  satu). Dalam tabel kebenaran kita menandai himpunan variabel yang nilai fungsinya sama dengan $ 0 $.

  x	kamu	z	$ \ langle x, y, z \ rangle $
  0	0	0	0
  0	0	1	0
  0	1	0	0
  0	1	1	1
  1	0	0	0
  1	0	1	1
  1	1	0	1
  1	1	1	1

  2). Untuk setiap himpunan yang ditandai, kami menulis konjungsi semua variabel sesuai dengan aturan berikut: jika nilai beberapa variabel adalah $ 0 $, maka kami memasukkan variabel itu sendiri ke dalam disjungsi, jika tidak, negasinya.

  x	kamu	z	$ \ langle x, y, z \ rangle $
  0	0	0	0	$ (x \ lor y \ lor z) $
  0	0	1	0	$ (x \ lor y \ lor \ neg (z)) $
  0	1	0	0	$ (x \ lor \ neg (y) \ lor z) $
  0	1	1	1
  1	0	0	0	$ (\ neg (x) \ lor y \ lor z) $
  1	0	1	1
  1	1	0	1
  1	1	1	1

  3). Kami menghubungkan semua disjungsi yang dihasilkan dengan operasi konjungsi.

  $ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ land (\ neg (x) \ lor y \ lor z) \ land (x \ lor \ neg (y) \ lor z) \ tanah (x \ lor y \ lor \ neg (z)) $

  Contoh SKNF untuk beberapa fungsi

  Pierce's Arrow: $ x \ downarrow y = (\ neg (x) \ lor (y)) \ land ((x) \ lor \ neg (y)) \ land (\ neg (x) \ lor \ neg (y) ) $

  Eksklusif atau: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ land (\ neg (x) \ lor y \ lor \ neg (z)) \ land (x \ lor \ neg (y) \ lor \ neg (z)) \ land (x \ lor y \ lor z) $

  
  

  Contoh. Temukan rumus CNF

  ~ ~

  

  Bentuk normal disjungtif sempurna SDNF dapat dibangun menggunakan algoritma berikut:

  1. = 1. dari algoritma DNF

  2. = 2. dari algoritma DNF

  3. = algoritma 3.DNF

  4. = 4. dari algoritma DNF

  5. Buang suku-suku yang identik salah, yaitu, suku-suku bentuknya

  6. Isi kembali suku yang tersisa dengan variabel yang hilang

  7. Ulangi langkah 4.

  Contoh. Temukan rumus SDNF.

  ~

  

  

  

  

  Untuk membangun SKNF, Anda dapat menggunakan skema berikut:

  Contoh. Temukan rumus SDNF.

  
  

  ~

  

  Diketahui (Teorema 2.11, 2.12) bahwa SDNF dan SKNF ditentukan secara unik oleh rumus dan, oleh karena itu, dapat dibangun dari tabel kebenaran rumus.

  Skema untuk membangun SDNF dan SKNF menurut tabel kebenaran diberikan di bawah ini, untuk rumus ~ :

  			~
  			1 0 1 0 1 1 0 1	SDNF; SKNF.

  2.2. Olahraga.

  2.2.1 Di bawah ini adalah ekspresi logis. Sederhanakan ekspresi varian Anda sebanyak mungkin menggunakan hukum logika Boole. Kemudian gunakan tabel kebenaran untuk membandingkan ekspresi sederhana Anda dengan aslinya.

  
  
  

  

  

  

  

  

  

  2.2.2. Temukan pertanyaan tentang kesetaraan f 1 dan f 2 dengan mereduksinya menjadi SDNF (Tabel 1).

  2.2.3. Temukan fungsi ganda untuk f 3 menurut prinsip umum dan Boolean (Tabel 1). Bandingkan hasilnya.

  №	f 1	f 2	f 3

  2.3. pertanyaan kontrol.

  2.3.1. Berikan definisi dari pernyataan tersebut.

  2.3.2. Sebutkan operasi-operasi dasar pada ujaran tersebut.

  2.3.3. Apa itu tabel kebenaran?

  2.3.4. Buat tabel kebenaran untuk rumus berikut:

  ~ ~ ~ ;

  2.3.5. Dengan mempertimbangkan konvensi tentang urutan pelaksanaan operasi, hilangkan tanda kurung "ekstra" dan tanda "" dalam rumus:

  ;

  2.3.6. Dengan menggunakan transformasi ekuivalen, buktikan kebenaran rumus yang identik:

  2.3.7. Temukan rumus ganda:

  

  

  )

  2.3.8. Bawa rumus berikut ke bentuk DNF (SDNF) sempurna:

  ~

  2.3.9. Bawa rumus berikut ke bentuk CNF (SKNF) sempurna:

  

  ~

  

  

  Pekerjaan laboratorium No.3

  Tema:“Minimisasi Fungsi Boolean. Logika"

  Target: Akuisisi keterampilan praktis dalam bekerja dengan metode meminimalkan fungsi Boolean.

  3.1. Informasi teoritis.

  Bentuk minimal

  Seperti yang ditunjukkan pada, setiap fungsi Boolean dapat direpresentasikan dalam bentuk normal sempurna (disjungtif atau konjungtif). Selain itu, presentasi seperti itu adalah langkah pertama dalam transisi dari definisi tabel fungsi ke ekspresi analitisnya. Berikut ini, kita akan melanjutkan dari bentuk disjungtif, dan hasil yang sesuai untuk bentuk konjungtif diperoleh berdasarkan prinsip dualitas.

  Masalah kanonik mensintesis rangkaian logika dalam basis Boolean direduksi untuk meminimalkan fungsi Boolean, yaitu. untuk mewakilinya dalam bentuk normal disjungtif, yang berisi jumlah huruf terkecil (variabel dan negasinya). Bentuk seperti itu disebut minimal. Dalam sintesis kanonik, diasumsikan bahwa kedua sinyal dan inversinya diumpankan ke input rangkaian.

  Rumus, disajikan dalam bentuk normal disjungtif, disederhanakan dengan beberapa aplikasi dari operasi perekatan dan operasi penyerapan dan (identitas ganda untuk bentuk normal konjungtif memiliki bentuk: dan). Di sini, dan dapat dipahami sebagai rumus apa pun dari aljabar Boolean. Akibatnya, kita sampai pada ekspresi analitik ketika transformasi lebih lanjut sudah tidak mungkin, mis. kita mendapatkan bentuk buntu.

  Di antara bentuk buntu adalah bentuk disjungtif minimal, dan mungkin tidak unik. Untuk memastikan bahwa formulir buntu yang diberikan minimal, perlu untuk menemukan semua formulir buntu dan membandingkannya dengan jumlah huruf yang dikandungnya.

  Sebagai contoh, biarkan fungsi diberikan dalam bentuk disjungtif normal sempurna:

  Mengelompokkan anggota dan menerapkan operasi perekatan, kita miliki.

  Dengan metode pengelompokan lain, kita mendapatkan:

  Kedua bentuk buntu tidak minimal. Untuk mendapatkan bentuk minimum, Anda perlu menebak untuk mengulang satu istilah dalam rumus aslinya (ini selalu bisa dilakukan, karena). Dalam kasus pertama, anggota seperti itu bisa. Kemudian . Dengan menambahkan anggota, kita mendapatkan:. Setelah melalui semua opsi yang memungkinkan, Anda dapat memastikan bahwa dua formulir terakhir minimal.

  Bekerja dengan formula pada level ini seperti berkeliaran di kegelapan. Proses menemukan bentuk minimal menjadi lebih visual dan terarah jika Anda menggunakan beberapa representasi grafis dan analitis dan simbol yang dirancang khusus untuk tujuan ini.

  kubus multidimensi

  Setiap simpul kubus -dimensi dapat dikaitkan dengan konstituen unit. Oleh karena itu, himpunan bagian dari simpul bertanda adalah pemetaan pada kubus -dimensi dari fungsi Boolean dari variabel dalam bentuk normal disjungtif sempurna. dalam gambar. 3.1 menunjukkan pemetaan seperti itu untuk fungsi dari Bagian 3.7.

  

  Gambar 3.1 Tampilan pada kubus tiga dimensi dari fungsi yang disajikan dalam SDNF

  Untuk menampilkan fungsi variabel yang disajikan dalam bentuk normal disjungtif apa pun, perlu untuk membuat korespondensi antara minitermnya dan elemen kubus berdimensi.

  Miniterm dari (-1) -th rank dapat dianggap sebagai hasil dari menempelkan dua miniterm dari -th rank (konstituen dari unit), yaitu. Pada kubus -dimensi, ini sesuai dengan mengganti dua simpul yang berbeda hanya dalam nilai koordinat yang menghubungkan simpul-simpul ini dengan tepi (sisi dikatakan menutupi simpul datang). Jadi, suku-suku dari orde (-1) bersesuaian dengan rusuk-rusuk kubus -dimensi. Demikian pula, korespondensi miniterms dari urutan (-2) ditetapkan ke wajah kubus -dimensi, yang masing-masing mencakup empat simpul (dan empat tepi).

  Elemen kubus -dimensi, ditandai dengan dimensi, disebut -kubus. Jadi, simpul adalah 0-kubus, tepi adalah 1-kubus, wajah adalah 2-kubus, dll. Meringkas alasan di atas, kita dapat mengasumsikan bahwa miniterm dari () -th rank dalam bentuk normal disjungtif untuk fungsi variabel ditampilkan oleh -kubus, dan masing-masing -kubus mencakup semua -kubus dari dimensi terendah yang terkait dengan simpulnya. Sebagai contoh, Gambar. 3.2 diberikan pemetaan fungsi tiga variabel. Di sini miniterm dan sesuai dengan 1 kubus (), dan miniterm ditampilkan sebagai 2 kubus ().

  

  Gambar 3.2 Cakupan fungsi

  Jadi, setiap bentuk normal disjungtif ditampilkan pada kubus -dimensi oleh kumpulan -kubus yang mencakup semua simpul yang sesuai dengan konstituen unit (0-kubus). Kebalikannya juga benar: jika beberapa kumpulan -kubus mencakup himpunan semua simpul yang sesuai dengan nilai satuan fungsi, maka disjungsi dari miniterm yang sesuai dengan -kubus ini adalah ekspresi dari fungsi ini dalam bentuk normal disjungtif . Dikatakan bahwa himpunan -kubus (atau miniterm yang sesuai) seperti itu membentuk cakupan suatu fungsi.

  Perjuangan untuk bentuk minimal secara intuitif dipahami sebagai pencarian cakupan seperti itu, yang jumlah kubusnya akan lebih kecil, dan dimensinya akan lebih besar. Cakupan yang sesuai dengan bentuk minimum disebut cakupan minimum. Misalnya, untuk cakupan fungsi pada Gambar. 3.3 cocok dengan bentuk minimal dan .

  

  Beras. 3.3 Fungsi Penutup.

  kiri – ; di sebelah kanan –

  Menampilkan fungsi pada kubus -dimensi jelas dan sederhana untuk. Sebuah kubus empat dimensi dapat dibuat seperti yang ditunjukkan pada gambar. 3.4, di mana fungsi empat variabel dan cakupan minimumnya sesuai dengan ekspresi ... Penggunaan metode ini membutuhkan konstruksi yang sedemikian kompleks sehingga semua kelebihannya hilang.

  Beras. 3.4 Tampilan fungsi pada kubus empat dimensi

  Peta Karnaugh

  Metode lain dari grafik fungsi boolean menggunakan peta karnot, yang merupakan tabel pencarian yang diatur secara khusus. Kolom dan baris tabel sesuai dengan semua kemungkinan set nilai yang tidak lebih dari dua variabel, dan set ini diatur sedemikian rupa sehingga setiap set berikutnya berbeda dari yang sebelumnya dengan nilai hanya satu variabel . Karena ini, sel tabel yang berdekatan secara horizontal dan vertikal berbeda dalam nilai hanya satu variabel. Sel yang terletak di tepi tabel juga dianggap berdekatan dan memiliki properti ini. dalam gambar. 3.5 menunjukkan grafik Karnaugh untuk dua, tiga, empat variabel.

  
  

  Beras. 3.5 Peta Karnot untuk dua, tiga dan empat variabel

  Seperti dalam tabel kebenaran biasa, sel-sel dari himpunan di mana fungsi mengambil nilai 1 diisi dengan satu (nol biasanya tidak cocok, mereka sesuai dengan sel kosong). Misalnya, pada Gambar. 3.6, sebuah menunjukkan peta Karnot untuk fungsi tersebut, yang pemetaannya pada kubus empat dimensi diberikan pada Gambar. 3.4. Untuk mempermudah, baris dan kolom yang sesuai dengan nilai 1 untuk beberapa variabel diapit oleh kurung kurawal dengan penunjukan variabel tersebut.

  
  

  Beras. 3.6 Menampilkan fungsi dari empat variabel pada grafik Karnot

  (a) dan cakupan minimumnya (b)

  Antara pemetaan fungsi pada n kubus -dimensi dan pada peta Karnot terdapat korespondensi satu-satu. Di peta Karnot S-cube sesuai dengan kumpulan 2 sel tetangga yang terletak di baris, kolom, persegi atau persegi panjang (dengan mempertimbangkan kedekatan tepi berlawanan dari peta). Oleh karena itu, semua ketentuan yang diatur di atas (lihat hal. kubus multidimensi) berlaku untuk peta Karnot. Jadi, dalam gambar. 3.6, B cakupan unit peta yang sesuai dengan bentuk disjungtif minimal ditampilkan fungsi yang sedang dipertimbangkan.

  Pembacaan miniterm dari kartu Karnot dilakukan dengan aturan sederhana. Sel yang terbentuk S-kubus, beri minit (n – s)-peringkat, yang termasuk itu (n – s) variabel yang menyimpan nilai yang sama pada ini S-cube, di mana nilai 1 sesuai dengan variabel itu sendiri, dan nilai 0 sesuai dengan negasinya. Variabel yang tidak menyimpan nilainya untuk S-kubus, dalam miniterm tidak ada. Cara membaca yang berbeda menghasilkan representasi fungsi yang berbeda dalam bentuk normal disjungtif (yang paling kanan minimal) (Gbr. 3.7).

  
  

  Penggunaan peta Karnaugh membutuhkan konstruksi yang lebih sederhana daripada pemetaan pada n kubus -dimensi, terutama dalam kasus empat variabel. Untuk menampilkan fungsi lima variabel, dua peta Karnot untuk empat variabel digunakan, dan untuk fungsi enam variabel, empat peta tersebut digunakan. Dengan peningkatan lebih lanjut dalam jumlah variabel, peta Karnot menjadi praktis tidak dapat digunakan.

  Dikenal dalam sastra Peta Weich hanya berbeda dalam urutan himpunan nilai variabel yang berbeda dan memiliki sifat yang sama dengan peta Karnot.

  Kompleks kubus

  Inkonsistensi metode grafis dengan sejumlah besar variabel dikompensasi oleh berbagai metode analisis untuk mewakili fungsi Boolean. Salah satu representasi tersebut adalah kompleks kubus menggunakan terminologi ruang logis multidimensi dalam kombinasi dengan simbologi yang dirancang khusus.

  ). 0-kubus yang sesuai dengan konstituen satu diwakili oleh set nilai variabel di mana fungsinya sama dengan satu. Jelas dalam catatan

  

  Beras. 3.8 Kompleks kubus dari fungsi tiga variabel ( sebuah) dan representasi simbolisnya ( B)

  Bentuk kompleks kubus cakupan fungsi maksimum... Tidak termasuk dari itu semua itu S-kubus, yang ditutupi oleh kubus dengan dimensi tertinggi, kami memperoleh penutup yang sesuai dengan bentuk buntu. Jadi, untuk contoh yang sedang dipertimbangkan (Gbr. 3.8) kami memiliki penutup buntu

  ,

  yang sesuai dengan fungsi ... Dalam hal ini, cakupan ini juga minim.

  Untuk dua fungsi Boolean, operasi disjungsi sesuai dengan penyatuan kompleks kubusnya, dan operasi konjungsi sesuai dengan perpotongan kompleks kubus. Negasi suatu fungsi sesuai dengan komplemen suatu kompleks kubus, yaitu ditentukan oleh semua simpul di mana fungsi tersebut bernilai 0. Dengan demikian, ada korespondensi satu-satu (isomorfisme) antara aljabar dari Fungsi Boolean dan himpunan Boolean mewakili kompleks kubus.

  Representasi fungsi dalam bentuk kompleks kubus kurang jelas, tetapi keuntungan yang paling penting adalah bahwa pembatasan jumlah variabel dihilangkan dan pengkodean informasi difasilitasi saat menggunakan komputer.

  Meminimalkan Fungsi Boolean

  Perumusan masalah. Meminimalkan sirkuit dalam basis Boolean dikurangi untuk menemukan bentuk disjungtif minimum, yang sesuai dengan cakupan minimum. Jumlah total huruf dalam bentuk normal dinyatakan dengan harga sampul , di mana adalah jumlah - kubus yang membentuk penutup dari fungsi yang diberikan dalam n variabel. Cakupan minimum ditandai dengan nilai terendah dari harganya.

  Biasanya masalah minimisasi diselesaikan dalam dua langkah. Pertama, cari cakupan singkat yang mencakup semua -kubus dengan dimensi maksimum, tetapi tidak berisi kubus apa pun yang tercakup oleh kubus apa pun dari cakupan ini. Bentuk normal disjungtif yang sesuai disebut disingkat, dan minitermsnya disebut implikan sederhana. Untuk fungsi ini, cakupan potong adalah satu-satunya, tetapi mungkin berlebihan karena fakta bahwa beberapa kubus ditutupi oleh koleksi kubus lainnya.

  Pada langkah kedua, transisi dari bentuk normal disjungtif tereduksi ke jalan buntu dilakukan, dari mana bentuk minimal dipilih. Bentuk buntu dibentuk dengan mengecualikan dari cakupan singkat semua kubus yang berlebihan, yang tanpanya himpunan kubus yang tersisa masih membentuk cakupan fungsi yang diberikan, tetapi setelah pengecualian lebih lanjut dari salah satu kubus, itu tidak lagi mencakup himpunan semua simpul yang sesuai dengan nilai satuan fungsi, yaitu, tidak lagi menjadi cakupan ...

  Kubus cakupan tereduksi yang menutupi simpul dari fungsi tertentu yang tidak tercakup oleh kubus lain tidak dapat menjadi redundan dan akan selalu disertakan dalam cakupan minimum. Kubus seperti itu, seperti implikan yang sesuai, disebut ekstrem (implikan esensial), dan simpul yang dicakupnya disebut simpul dibatalkan. Himpunan ekstrem membentuk inti dari cakupan; jelas bahwa ketika beralih dari cakupan yang dikurangi ke yang minimum, pertama-tama, semua ekstrem harus dipilih. Jika himpunan ekstrem tidak membentuk penutup, maka itu dilengkapi dengan kubus dari penutup yang dikurangi.

  Definisi ini diilustrasikan pada Gambar. 3.9, di mana cakupan yang berkurang (lihat gambar 3.9a, ) dan cakupan minimum (Gbr. 3.9b) dan (lihat Gbr. 3.9, b) dinyatakan sebagai berikut.

  Bentuk normal disjungtif dan konjungtif dari aljabar proposisional. Untuk setiap fungsi logika pernyataan, Anda dapat membuat tabel kebenaran. Masalah invers juga selalu dapat dipecahkan. Mari kita perkenalkan beberapa definisi.

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

  sekali.

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

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

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

  Untuk setiap fungsi aljabar proposisi, satu set bentuk normal disjungtif dan konjungtif dapat ditemukan.

  Algoritma untuk membangun DNF:

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

  2. Pergi ke rumus dengan negasi dekat, yaitu, ke rumus di mana negasi terletak tidak lebih tinggi dari di atas variabel - untuk menerapkan hukum de Morgan.

  3. Perluas tanda kurung - terapkan hukum distribusi.

  4. Ambil istilah yang diulang satu kali - hukum idempotensi.

  5. Terapkan hukum penyerapan dan semi-penyerapan.

  Contoh 6. Temukan rumus DNF:.

  Aljabar Boolean berlaku prinsip dualitas... Ini adalah sebagai berikut.

  Fungsi tersebut disebut ganda ke fungsi jika. Itu. untuk menemukan fungsi yang ganda dengan yang diberikan, perlu untuk membangun negasi fungsi dari negasi argumen.

  Contoh 7. Temukan fungsi ganda ke.

  Di antara fungsi dasar aljabar Boolean, 1 adalah ganda ke 0 dan sebaliknya, x adalah ganda ke x, ganda, ganda dan sebaliknya.

  Jika dalam rumus F 1 mewakili fungsi semua konjungsi diganti

  pada disjungsi, disjungsi pada konjungsi, 1 hingga 0, 0 hingga 1, maka kita peroleh rumus F * yang mewakili fungsi * ganda.

  Bentuk normal konjungtif (CNF) adalah konsep ganda untuk DNF, oleh karena itu mudah untuk membangunnya sesuai dengan skema:

  Contoh 8. Tentukan CNF dari rumus :.

  Dengan menggunakan hasil dari Contoh 6, kita memperoleh

  Bentuk normal disjungtif sempurna dan konjungsi sempurna. Pada masing-masing jenis bentuk normal (disjunctive dan conjunctive), kelas bentuk sempurna SDNF dan SKNF dapat dibedakan.

  Konjungsi elementer sempurna adalah produk logis dari semua variabel dengan atau tanpa negasi, dan setiap variabel hanya muncul satu kali dalam produk.

  Setiap DNF dapat direduksi menjadi SDNF dengan memisahkan konjungsi yang tidak mengandung semua variabel, mis. penambahan untuk variabel yang hilang x i dikalikan menggunakan hukum distribusi

  Contoh 9. Temukan SDNF untuk contoh DNF 6

  Disjungsi dasar sempurna adalah jumlah logis dari semua variabel dengan atau tanpa negasi, dan setiap variabel termasuk dalam jumlah hanya sekali.

  Setiap CNF dapat direduksi menjadi SKNF dengan menambahkan istilah konjungsi yang tidak mengandung konjungsi variabel X i dan menerapkan hukum distributif

  Contoh 10. Bawa CNF ke SKNF:

  Untuk membangun SKNF, Anda dapat menggunakan skema

  Contoh 11. Temukan SKNF untuk rumus pada Contoh 6.

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

  Karena SDNF dan SKNF didefinisikan secara unik oleh rumus, mereka dapat dibangun sesuai dengan tabel kebenaran rumus.

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

  Untuk menyusun SKNF menurut tabel kebenaran, perlu untuk memilih garis di dalamnya, di mana F = 0, dan menuliskan disjungsi dasar yang sempurna, dan kemudian menghubungkannya dengan tanda konjungsi. Jika di baris yang diperlukan dari tabel kebenaran (F = 0) nilai variabel sesuai dengan nol, maka dalam klausa sempurna diambil tanpa negasi, jika satu - maka dengan negasi.

  Contoh 12. Temukan SDNF dan SKNF menggunakan tabel kebenaran untuk rumus contoh 6.

  Tabel 14 hanya menunjukkan nilai akhir F = 10101101. Anda sendiri harus yakin akan validitas pernyataan ini dengan membangun tabel kebenaran yang diperluas.

  Tabel 14

  x	kamu	z