Minggu, 01 Januari 2017

Pengertian, Jenis, Tabel Kebenaran Bentuk Normal

Objective
  • 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 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 :
  1. (P2 ∨ P5 ∨ ¬P3) ∧ (¬P2 ∨ P1 ∨ P3) ∧ (P1 ∨ P2 ∨ P3 ∨ P7 ∨ ¬P4) ∧.....
  2. (¬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 :
  1. (p2 ∧ p5 ∧ ¬p3) ∨ (¬p2 ∧ p1 ∧p3) ∨ (p1 ∧ p2 ∧ p3 ∧ p7 ∧ ¬p4)
  2. (¬p1 ∧ ¬p2) ∨ (¬p2 ∧ ¬p1 ∧ p3)
  3. (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)

Dari tabel kebenaran di atas, untuk merubah ke dalam DNF yang diambil hanya yang bernilai T, yakni ada 6 (lihat nomor urut) : (¬A ∧ ¬B ∧ ¬C) ∨ (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ ¬C) ∨ (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ B ∧ C) 

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.

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
  1. ¬(A → B) ∨ (A ∧ B)
  2. (A → B) → C
Rubahlah ekspresi logika berikut menjadi DNF
  1. ¬((A ∧ B) ∨ C) ∧ B
  2. A ∧ ¬(A ∨ ¬(B ∧ C))
Baca Juga
Previous Post
Next Post