Aljabar Boolean Dan Peta Karnaugh

Bagi yang sedang belajar silahkan buka:http://karnaugh.shuriksoft.com/ 

Karnaugh Minimizer Standart

    

  

Karnaugh Minimizer Profesional

  

  

Silahkan mencoba....

PETA KARNAUGH

Telah ditunjukkan di bab sebelumnya bahwa penyederhanaan fungsi Boole

secara aljabar cukup membosankan dan hasilnya dapat berbeda dari satu orang

ke orang lain, tergantung dari kelincahan seseorang itu mempermainkan rumusrumus

logika Boole. Hasil penyederhanaan juga tidak segera dapat dipastikan

sebagai fungsi yang minimum. Cara lain untuk mempermudah proses

penyederhanaan dan mencegah kemungkinan memperoleh hasil yang dianggap

sudah minimum, padahal masih dapat lagi disederhanakan, adalah cara

pemetaan dan cara tabulasi. Cara tabulasi akan diuraikan dalam bab selanjutnya,

cara pemetaan yang dikenal sebagai pemetaan Karnaugh akan diuraikan dalam

bab ini. Cara ini jauh lebih mudah daripada cara penyederhanaan aljabar

terutama untuk fungsi-fungsi dengan 3 atau 4 variabel (peubah). Untuk peubah

yang lebih banyak, sudah lebih sulit dan secara umum dapat dikatakan bahwa

cara ini hanya mudah untuk fungsi sampai dengan 6 peubah. Untuk peubah

yang lebih banyak, petanya menjadi sulit dan tidak mudah menyederhanakannya,

seperti akan ditunjukkan kemudian. Untuk itu akan lebih baik memakai cara

tabulasi yang lebih sistematis.

Berbicara mengenai penyederhanaan, maka kita selalu harus berusaha

menghasilkan fungsi dengan jumlah suku (sukumin atau sukumax) yang sekecil

mungkin dan setiap sukunya terdiri atas literal yang sesedikit mungkin. Ini

berarti menekan harga realisasi fungsi karena minimisasi cacah suku berarti

minimisasi cacah gerbang dan minimisasi literal berarti minimisasi cacah

masukan.

Bentuk SOP dan POS Fungsi Boolean

Kami menggambarkan prinsip-prinsip yang mewakili fungsi dalam SOP (= Sup-of-produk) dan POS (= Produk-of-Sums) terbentuk pada contoh F mayoritas tiga-masukan fungsi. Fungsi ini mengambil nilai 1 jika dan hanya jika jumlah orang dalam vektor masukan melebihi jumlah nol.

ABC	F
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	0 0 0 1 0 1 1 1

Secara umum bentuk SOP dari fungsi Boolean terdiri dari koleksi variabel anded (disebut istilah) yang ORed bersama-sama. Misalnya, bentuk SOP dari F fungsi

Setiap fungsi f Boolean (x _1, ..., x _n) dapat direpresentasikan dalam bentuk SOP. Kami jelaskan di bawah cara untuk membangun salah satu representasi tersebut, yang disebut kanonik. Untuk ini mempertimbangkan entri dalam tabel kebenaran di mana fungsi f mengambil nilai 1. Untuk setiap string seperti bentuk SOP akan berisi istilah melibatkan semua n variabel, beberapa di antaranya dinegasikan. Lebih tepatnya, jika f (a _1, ..., _n)= 1 maka dalam jangka sesuai dengan entri (a _1, ..., _n) variabel x _i menegasikan suatu _i = 0 dan tidak dinegasikan sebaliknya. Oleh karena itu, jumlah istilah dalam bentuk SOP kanonik sama dengan jumlah "orang" dari fungsi f, yaitu jumlah entri dari tabel kebenaran di mana f mengambil nilai 1.
Bentuk SOP dari suatu fungsi tidak unik pada umumnya. Misalnya, fungsi mayoritas juga dapat direpresentasikan dalam bentuk berikut (non-kanonik) SOP

(1)

Sebuah ganda dengan bentuk SOP adalah bentuk POS. Bentuk POS terdiri dari koleksi variabel ORed (disebut maxterms) yang ANDed bersama-sama. Salah satu metode untuk mendapatkan bentuk POS adalah mulai dengan pelengkap dari bentuk SOP, dan kemudian menerapkan teorema DeMorgan.
Sebagai contoh, perhatikan fungsi mayoritas di atas, dan merupakan komplemen dalam bentuk POS:

(2)

Melengkapi kedua sisi (2), dan menerapkan hasil Involusi properti

(3)

Menerapkan ke (3) Teorema DeMorgan dalam bentuk  menyediakan

(4)

Akhirnya, berlaku untuk (4) teorema DeMorgan dalam bentuk  hasil dalam bentuk POS untuk F

Metode ini diterapkan pada hasil bentuk kanonik SOP dalam bentuk POS disebut kanonik. Jumlah maxterms dalam bentuk kanonik POS sama dengan jumlah dari angka nol dari fungsi. Selain itu, dalam setiap maxterm setiap variabel muncul tepat satu kali baik dalam bentuk benar atau ditiadakan. Setiap maxterm memiliki 0 nilai hanya satu entri dalam tabel kebenaran.
Salah satu motivasi untuk menggunakan formulir POS adalah bahwa hal itu dapat mengakibatkan formula Boolean sederhana. Dengan demikian, jika jumlah yang dari fungsi Boolean melebihi jumlah nol, maka jumlah istilah dalam POS kanonik dari melebihi satu dalam bentuk kanonik POS.
Bentuk SOP dari suatu fungsi tidak unik pada umumnya. Misalnya, menerapkan metode di atas untuk bentuk SOP fungsi mayoritas (1) hasil sebagai berikut (non-kanonik) bentuk POS

Hal ini dapat ditunjukkan bahwa jumlah SOP yang berbeda (dan juga POS) bentuk n variabel sama dengan 2 ^{3 n.} Namun, karena jumlah fungsi Boolean hanya 2 ^{2 n,} maka tidak semua bentuk-bentuk sesuai dengan fungsi yang berbeda. Dengan kata lain, fungsi dapat memiliki banyak SOP (resp. POS) bentuk yang berbeda. Oleh karena itu, masuk akal untuk meminta yang paling sederhana, dalam arti.