Bentuk normal mempunyai dua jenis, yaitu bentuk normal konjungtif dan bentuk normal disjungtif
Bentuk normal sangat penting difahami karena kebanyakan aplikasi logika, misalnya merancang rangkaian elektronika atau sirkuit menggunakan bentuk normal, khususnya bentuk normal disjungtif
Bentuk normal disebut juga bentuk kanonikal (canonical form)
Bentuk normal hanya berisi perangkai ~, ^ , dan V, dengan proposisi dasar yang dikomposisikan dalam bentuk rumus atomik atau atom-atom.
Literal adalah atom dan atau negasi dari atom
Bentuk Normal Konjungtif
Definisi: suatu ekspresi logika (wff) berbentuk normal konjungtif (CNF) bila ia merupakan konjungsi dari disjungsi literal-literal. Bentuknya seperti berikut:
(a1 V a2) ^ (a3 V a4) .. ^ (an V an+1)
Bentuk CNF pada nomor (1), (2), (3), dan (4) di atas tetap dapat disebut bentuk normal konjungtif. Untuk nomor (4) diterima sebagai default.
Bentuk Normal Disjungtif
Suatu ekspresi logika (wff) berbentuk bentuk normal disjungtif (DNF) bila ia merupakan disjungsi dari konjungsi literal-literal. Bentuknya seperti berikut:
(a1 ^ a2) V (a3 ^ a4) .. V (an ^ an+1)
Bentuk DNF pada nomor (1), (2), (3), dan (4) di atas tetap dapat disebut bentuk normal disjungtif. Untuk nomor (4) diterima sebagai default.
Bentuk Normal dan Tabel Kebenaran
Untuk membuat DNF dari suatu ekspresi logika yang dibuat dengan tabel kebenaran cukup mudah, yakni hanya mengambil nilai-nilai T dari ekspresi logika tersebut.
Contoh
~(A ^ B) ↔ (~A V ~C)
Darii tabel kebenaran di atas, hanya mengambil dari ~(A ^ B) ↔ (~A V C) yang bernilai T, yakni ada 6 (lihat nomor urut), kemudian jadikan DNF sesuai urutan nomor:(~A ^ ~B ^ ~C) V (~A ^ ~B ^C) V (~A ^ B ^ ~C) V (~A ^ B ^ C) V (A ^ ~B ^ ~C) V (A ^ B ^C)
Bentuk normal di atas disebut full disjunctive normal form (FDNF)
Untuk CNF sama saja, yakni mengambil nilai F dari tabel kebenaran dan membuatnya menjadi full conjunctive normal form (FCNF), dengan catatan nilai variabel-variabel proposisionalnya terbalik dari pasangan pada tabel kebenaran. T menjadi F dan F menjadi T
CNF disusun sebagai berikut:
(~A V B V ~C) ^ (~A V ~B V C)
Teknik di atas pada DNF sebenarnya menggunakan pasangan variabel proposisional yang berada di tabel kebenaran dan yang memiliki nilai T, yang disebut minterm.
minterm adalah konjungsi dari literal-literal dengan variabel yang hanya dinyatakan satu kali.
Contoh
Misal ada 3 variabel proposisional A, B, dan C. berikut adalah contoh minterm
(A ^ B ^ C); (~A ^ ~B ^~C); (~A ^ B ^ C)
Contoh bukan minterm
(A^A^C); (~A^~B^B); (~A^C); B
Klausa
Klausa adalah disjungsi dari literal-literal. Setiap klausa dapat berisi sekurang-kurangnya satu literal, misalnya A dan ~A, dan setiap literal disebut klausa unit (unit clause)
Contoh klausa-klausa unit
1. (p2^p5^~p3)
2. (~p1 ^ p3)
3. ~p2
4. p10
Pembahasan tentang klausa dan CNF memegang peranan penting untuk melakukan deduksi resolusi (resolution deduction)
Bentuk Normal Konjungtif dan Complementation
Sebelum membahas Complementation, sebaiknya kita mengenal dulu konsep dualitas.
Dualitas adalah kembaran suatu ekspresi. Jika memiliki V perangkai akan diganti ^, dan jika bernilai T akan diganti bernilai F, demikian sebaliknya.
Contoh dualitas
A V~A = T hukum tautologi
A ^~A = F hukum kontradiksi
Konsep dualitas berhubungan erat dengan complementation dan dengan konsep ini akan dibuat CNF dari tabel kebenaran.
Setiap literal mempunyai complement. Jika ada literal A maka complement-nya ~A, jika literalnya ~B maka complement-nya B.
Complementation adalah penegasian suatu ekspresi dengan memakai complement-nya.
Contoh
Negasikan P = (A^B)V ~C dengan complementation.
Penyelesaian:
Langkah 1:
Cari dualitas dari P, yaitu: (A^B)V ~C
Hanya mengganti perangkai, tetapi literalnya tidak diubah.
Langkah 2:
Lakukan complementation dengan mencari complement-nya. Caranya dengan menghapus semua literal dan diganti dengan complement-nya dan menghasilkan (~A V ~B)^C.
Jika masih ragu dengan hasilnya, maka pembuktiannya bisa juga dilakukan dengan cara berikut:
~P = ~((A^B)V~C)
(~(A^B)^~~C)
((~AV~B)^C)
(~AV~B)^C
Ternyata sama.
Complementation dapat digunakan untuk mencari CNF dari suatu ekspresi atau fungsi R. maka buatlah dulu DNF dari ~R, jika hasil DNF adalah P, maka P = ~R dan complement dari P adalah negasinya yang pasti ekuivalen secara logis dengan R.
Perhatikan tabel kebenaran dari suatu ekspresi atau fungsi R
Berdasarkan tabel di atas, R adalah bernilai benar atau pada tabel kebenaran di atas adalah pada nilai-nilai F yang berada pada baris 2, 5, dan 6 dengan pasangan nilainya sebagai berikut:Baris-2: A = F B = F C = T
Baris-5: A = T B = F C = F
Baris-6: A = T B = F C = T
Maka ekspresi DNF yang diperoleh adalah:
(~A^~B^C) V (A^~B^~C) V (A^~B^C)
Selanjutnya lakukan langkah-langkah berikut:
Langkah 1:
Cari dualitasnya, maka hasilnya:
(A V~B V C)^(A V ~B V~C)^(A V~B V C)
Langkah 2:
Lakukan complementation dengan memberi complement-nya pada setiap literalnya, sehingga hasilnya:
(A V B V ~C) ^ (~A V B V C) ^ (~A V B V~C)
Terima kasih anda telah membaca materi kami ini, kami berharap anda mencantumkan Blog kami sebagai sumber referensi anda. Untuk mendownload klik disini .. Materi Bentuk Normal
0 comments:
Post a Comment
Tim Gudang Materi mengharapkan komentar anda sebagai kritik dan saran untuk kami .. Hubungi kami jika anda mengalami kesulitan !