Penulis
- Menjelaskan tentang bentuk normal
- Menjelaskan bentuk normal konjungtif (CNF) dan normal disjungtif (DNF)
- Menjelaskan teknik mengambil bentuk DNF dari tabel kebenaran yang berasal dari ekspresi logika tertentu
- Menjelaskan cara-cara mengubah ekspresi logika umum menjadi bentuk CNF
- Menjelaskan tentang complementation dan bentuk CNF
Bentuk Normal
Bentuk normal adalah bentuk standar untuk ekspresi logika.
Bentuk standar yang dimaksudkan disini adalah bahwa semua bentuk ekspresi logika bisa disederhanakan dengan menggunakan operator : ¬ (negasi), ∧ (konjungsi), dan ∨ (disjungsi).
Bentuk standar yang dimaksudkan disini adalah bahwa semua bentuk ekspresi logika bisa disederhanakan dengan menggunakan operator : ¬ (negasi), ∧ (konjungsi), dan ∨ (disjungsi).
Bentuk Normal mempunyai dua jenis yaitu :
- Bentuk Normal Konjungtif (CNF)
- Bentuk Normal Disjungtif (DNF)
Bentuk normal sangat penting dipahami karena kebanyakan aplikasi logika. Misalnya merancang rangkaian elektronika (sirkuit), menggunakan bentuk normal khususnya bentuk normal disjungtif.
Bentuk Normal Konjungtif (CNF)
Bentuk CNF merupakan konjungsi (∧) dari disjungsi (∨) literal-literal. Bentuknya seperti berikut:
- A1 ∧ A2 ∧ ... ∧ Ai ∧ An
- Dimana Ai berbentuk : ⋋1 ∨ ⋋2 ∨ ...
Contoh :
- (P2 ∨ P5 ∨ ¬P3) ∧ (¬P2 ∨ P1 ∨ P3) ∧ (P1 ∨ P2 ∨ P3 ∨ P7 ∨ ¬P4) ∧.....
- (¬P1 ∨ ¬P3) ∧ (¬P2 ∨ ¬P1 ∨ P3)
Bentuk Normal Disjungtif (DNF)
Bentuk DNF merupakan disjungsi (∨) dari konjungsi (∧) literal-literal. Bentuknya seperti berikut:
A1 ∨ A2 ∨ ... ∨ Ai ∨ An
Dimana Ai berbentuk : ⋋1 ∧ ⋋2 ∧ ...
Contoh :
- (p2 ∧ p5 ∧ ¬p3) ∨ (¬p2 ∧ p1 ∧p3) ∨ (p1 ∧ p2 ∧ p3 ∧ p7 ∧ ¬p4)
- (¬p1 ∧ ¬p2) ∨ (¬p2 ∧ ¬p1 ∧ p3)
- (p2 ∧ p3 ∧ ¬p4 ∧ p7) ∨ p2
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 ∨ ¬C)
Tabel Kebenaran
(Maaf, tabel tidak sengaja terhapus)
Bentuk normal di atas disebut full disjunctive normal form (FDNF).
Merubah ke Bentuk CNF
Strategi :
- Mengambil nilai F dari tabel kebenaran,
- Nilai variabel-variabel proposisionalnya dibalik : T menjadi F dan F menjadi T
CNF disusun sebagai berikut : = (¬A ∨ B ∨ ¬C) ∧ (¬A ∨ ¬B ∨ 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 :
- (p2 ∧ p5 ∧ ¬p3)
- (¬p1 ∧ p3)
- ¬p2
- P10
Pembahasan tentang klausa dan CNF memegang peranan penting untuk melakukan deduksi resolusi (resolution deduction).
Mengubah ke Bentuk Normal Konjungtif
Contoh : Ubahlah (¬A ∧ (¬B → C)) ↔ D menjadi CNF.
Pembuktian:
(¬A∧(¬B→C))↔D
≡ ((¬A∧(¬B→C))→D)∧(D→(¬A∧(¬B →C)))
≡ (¬(¬A ∧ (¬¬B ∨ C)) ∨ D) ∧ (¬D ∨ (¬A ∧ (¬¬B ∨ C)))
≡ ((¬¬A ∨ ¬ (¬¬B ∨ C)) ∨ D) ∧ ( ¬D ∨ (¬A ∧ (¬¬B ∨ C)))
≡ ((A∨ ¬(B ∨ C)) ∨ D) ∧ ( ¬D ∨ (¬A ∧ (B ∨ C)))
≡ ((A ∨ (¬B ∧ ¬C)) ∨ D) ∧ ( ¬D ∨ (¬A ∧ (B ∨ C)))
≡ ((A ∨ ¬B ) ∧ (A ∨ ¬C)) ∨ D) ∧ (( ¬D ∨ ¬A ) ∧ ( ¬D ∨ (B ∨ C)))
≡ (((A ∨ ¬B) ∨ D) ∧ ((A ∨ ¬C) ∨ D)) ∧ (( ¬D ∨ ¬A ) ∧ ( ¬D ∨ (B ∨ C)))
≡ (A ∨ ¬B ∨ D) ∧ (A ∨ ¬C ∨ D) ∧ ( ¬D ∨ ¬A ) ∧ ( ¬D ∨ B ∨ C)
Bentuk Normal Konjungtif dan Complementation
Sebelum membahas Complementation, sebaiknya kita mengenal dulu konsep dualitas.
Dualitas adalah kembaran suatu ekspresi. Jika memiliki operator ∨ akan diganti ∧, dan jika bernilai T akan diganti bernilai F, demikian sebaliknya.
Dualitas adalah kembaran suatu ekspresi. Jika memiliki operator ∨ akan diganti ∧, dan jika bernilai T akan diganti bernilai F, demikian sebaliknya.
Contoh dualitas :
- A ∨¬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 complementnya ¬A, jika literalnya ¬B maka complementnya B. Complementation adalah penegasian suatu ekspresi dengan memakai complementnya.
Contoh: Negasikan P = (A ∧ B) ∨ ¬C dengan complementation.
Penyelesaian :
Langkah 1 :
- Cari dualitas dari P, yaitu : (A ∨ B) ∧ ¬C
- Hanya mengganti operator, tetapi literal (operand) nya tidak diubah.
Langkah 2 :
- Lakukan complementation dengan mencari complementnya. Caranya dengan menghapus semua literal dan diganti dengan complementnya dan menghasilkan (¬A ∨ ¬B) ∧ C.
Jika masih ragu dengan hasilnya, maka pembuktiannya bisa juga dilakukan dengan cara berikut :
¬P ≡ ¬((A ∧ B) ∨ ¬C)
≡ (¬ (A ∧ B) ∧ ¬¬C)
≡ ((¬A ∨ ¬B) ∧ C)
≡ (¬A ∨ ¬B) ∧ C
Ternyata sama.
Complementation
- 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.
Contoh : Perhatikan tabel kebenaran dari suatu ekspresi atau fungsi R
(Maaf, tabel tidak sengaja terhapus)
Complementation .......
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) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ C)
Complementation .......
Selanjutnya lakukan langkah-langkah berikut :
Langkah 1: Cari dualitasnya, maka hasilnya: (¬A ∨ ¬B ∨ C) ∧ (A ∨ ¬B ∨ ¬C) ∧ (A ∨ ¬B ∨ C)
Langkah 2: Lakukan complementation dengan memberi complementnya pada setiap literalnya, sehingga hasilnya : (A ∨ B ∨ ¬C) ∧ ( ¬A ∨ B ∨ C) ∧ ( ¬A ∨ B ∨ ¬C)
Latihan :
Rubahlah ekspresi logika berikut menjadi CNF
- ¬(A → B) ∨ (A ∧ B)
- (A → B) → C
Rubahlah ekspresi logika berikut menjadi DNF
- ¬((A ∧ B) ∨ C) ∧ B
- A ∧ ¬(A ∨ ¬(B ∧ C))