loginf-10
DESCRIPTION
Logika InformatikaTRANSCRIPT
01/10/2010
1
10. BENTUK NORMAL
Bentuk ekspresi logika yang standar disebutbentuk normal. Bentuk normal mempunyai duajenis yakni : (1) bentuk normal konjungtif dan (2)bentuk normal disjungtif
Semua bentuk ekspresi logika sebenarnya bisadisederhanakan dengan menggunakanperangkai dasar , dan . Inilah yangdimaksud dengan bentuk standar.
Bentuk normal sangat penting dipahami karenakebanyakan aplikasi logika, misalnya merancangrangkaian elektronika, menggunakan bentuknormal khususnya bentuk normal disjungtif.
Setiap ekspresi logika yang berbentuk fpe atauwff dapat diubah menjadi bentuk normal,dengan hanyha menggunakan perangkai dasar.
Contoh 10.1 :
Misalnya ada skema seperti berikut :
P = (A B) (C A)
Q=((A B) (C A))
Jika P Q, maka :
(A B) (C A) ((A B) (C A))
Jadi dapat dipastikan bahwa (A B) (C A)akan sama nilai kebenarnya dengan ((A B) (CA)) dengan semua nilai kebenaran dari A,B dan C.
Setiap bentuk ekspresi logika dapat diubahmenjadi bentuk normal, yang hanya berisiperangkai, dan , dengan proposisi dasaryang dikomposisikan dalam bentuk rumusatomik atau atom-atom. Atom sama sajadengan literal.
Jadi :
1) A dan A adalah atom-atom atau literal, atau
2) p2 adalah literal
3) p12 adalah literal
4) Literal yang berisi satu atom disebut literal positifmisalnya : p2.
5) Literal yang berisi negasi dari satu atom disebutliteral negatif misalnya : p12
tony.d-2010
01/10/2010
2
BENTUK NORMAL KONJUNGTIF Bentuk Normal Konjungtif (Conjunctive Normal
Form) atau CNF adalah bentuk normal yangmemakai perangkat konjungsi dari disjungsi.
Definisi : Suatu ekspresi logika (wff) memilikibentuk normal konjungtif (CNF) bila merupakankonjungsi dari disjungsi literal-literal. Bentuknyseperti berikut :
A1 A2 ... Ai ... An
dimana setiap Ai berbentuk :
12 ... j ... m
dimana setiap j berbentuk literal
Contoh :
Berikut ini contoh-contoh CNF :
1) (p2 p5 p3 ) ( p2 p1 p3 ) (p1 p2 p3 p7p4 )
2) ( p1 p3 ) ( p2 p1 p3 )
3) (p2 p3 p1 p4 p7 ) p2
4) p10
Bentuk CNF pada nomor (1), (2), (3), dan (4) diatastetap dapat disebut bentuk normal konjungtif.
BENTUK NORMAL DISJUNGTIF Bentuk Normal Disjungtif (Disjunctive Normal
Form) atau DNF adalah bentuk normal yangmemakai perangkat disjungsi dari konjungsi.
Definisi : Suatu ekspresi logika (wff) memilikibentuk normal konjungtif (CNF) bila merupakankonjungsi dari disjungsi literal-literal. Bentuknyaseperti berikut :
A1 A2 ... Ai ... An
dimana setiap Ai berbentuk :
1 2 ... j ... m
dimana setiap j berbentuk literal
Contoh :
Berikut ini contoh-contoh CNF :
1) (p2 p5 p3 ) ( p2 p1 p3 ) (p1 p2 p3 p7p4 )
2) ( p1 p3 ) ( p2 p1 p3 )
3) (p2 p3 p1 p4 p7 ) p2
4) p10
Bentuk DNF pada nomor (1), (2), (3), dan (4) diatastetap dapat disebut bentuk normal disjungtif.
tony.d-2010
01/10/2010
3
TABEL KEBENARAN DAN BENTUKNORMAL Membuat DNF dari suatu ekspresi logika
yang dibuat dengan tabel kebenaran cukupmudah, yakni hanya mengambil nilai-nilai Tdari ekspresi logika tersebut.
Contoh :
Ekspresi logika adalah :
(A B) (A C)
A B C A B (A B) A C A C (A B) (A C)
FFFFTTTT
FFTTFFTT
FTFTFTFT
FFFFFFTT
TTTTTTFF
TTTTFFFF
TFTFTFTF
TTTTTFTF
TTTTTFFT
Dari tabel kebenaran di atas, kita hanya perlumengambil nilai dari akhir yang T, kemudianjadikan DNF seperti berikut sesuai urutan :
(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 normalform (FDNF), sedangkan untuk CNF sebenarnya samasaja, yakni mengambil nilai F dari tabel kebenaran danmembuatnya menjadi full conjunctive normal form(FCNF), dengan catatan nilai variabel-variabelproposisionalnya terbalik dari pasangan pada tabelkebenaran : jika F menjadi T dan T menjadi F. Maka CNFakan disusun seperti berikut :
(A B C) (A B C)
Teknik pada DNF di atas menggunakan yangdisebut minterm.
Minterm
Minterm adalah konjungsi dari literal-literalyang variabelnya hanya dinyatakan satu kalisaja.
Contoh :
Misalnya ada 3 variabel proposisional A, Bdan C, maka yang berikut ini adalah minterm:
(1) (A B C)
(2) (A B C)
(3) (A B C)
tony.d-2010
01/10/2010
4
Sedangkan yang berikut ini bukan minterm :
(1) (A A C)
(2) (A B B)
(3) (A C)
(4) B
Jadi, suatu disjungsi dari minterm adalah benarjika salah satu pasangan variabel di dalam tabelkebenaran bernilai benar. Maka misalnya (A B C) (AB C) (A B C)bernilai benar jika (A B C) , (AB C) , (A B C) salah satunya bernilai benar.
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. BentukCNF seperti pada definisi dapat diubahmenjadi bentuk seperti berikut :
C1 C2 ... Ci ... Cn
dimana setiap Ci berbentuk :
12 ... j ... m
dimana setiap j berbentuk literal
MENGUBAH KE BENTUK NORMALKONJUNGTIF
Untuk mengubah suatu ekspresi lolgikamenjadi bentuk CNF, ada 5 langkah yangdigunakan. Tentu saja tidak semua langkahtersebut harus dipakai.
Langkah – 1 :
Gunakan ekuivalensi AB ( A B) (B A)untuk menghilangkan perangkai.
Langkah – 1 :
Gunakan ekuivalensi A B A B untukmenghilangkan perangkai.
Langkah ke-3 :
Gunakan hukum-hukum De Morgan(A B) A B dan (A B) A B untukmendorong masuk tanda negasi ke dalamtanda kurung agar mendapatkan klausa yangberisi literal-literal.
Langkah ke – 4 :
Gunakan hukum negasi ganda A A untukmenghilangkan tanda negasi.
Langkah ke – 5 :
Gunakan hukum distributif A(B C) ( A B ) (A C) untuk mengubahnya menjadi CNF.
tony.d-2010
01/10/2010
5
Ubahlah (A (B C)) D menjadi CNF? (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) (A D) (B C D)
Perhatikan sekarang bahwa ekspresi logika tersebut telahberubah menjadi CNF
LATIHAN
A. Ubahlah bentuk-bentuk logika atau ekspresi-ekspresi berikut menjadi bentuk normalkonjungtif (CNF) !
1. (A C) (B C)
2. (A B) (A B)
3. (A B) C
4. A (B C)
5. (A (B C)) C
B. Ubahlah bentuk-bentuk logika atau ekspresi-ekspresi berikut menjadi bentuk normaldisjungtif (DNF) !
1. ((A B) C) B
2. A (A (B C))
3. (A B) ((A C) B)
4. ((A B) (A B)) ((A C) B)
C. Ubahlah bentuk-bentuk logika atau ekspresi-ekspresi berikut menjadi bentuk normalkonjungtif (CNF) dan bentuk normal disjungtif(DNF) menggunakan tabel kebenaran !
1. A ( B C)
2. (A B) C
3. (((A B) C) B)
4. (A B)
tony.d-2010