Pendahuluan
• Ekspresi logika pada bab-bab sebelumnya mempunyai bentuk yang bermacam-macam, mulai dari yang rumit (banyak jenis perangai, variabel proporsional, tanda kurung) sampai dengan sederhana.
Contoh :
a) (A
Ù C) Ú (B Ù C)
b) ~(A ® B) Ú (A Ú B)
c) ~A « (B Ú C)
d) ~((AÙB) Ú C) Ù B
e) (A®B) « ((A ® C) Ù B)
•Bentuk Normal adalah bentuk ekspresi logika yang standar.
•Bentuk ekspresi logika yang standar adalah bentuk ekspresi logika yang menggunakan perangkai dasar ~, Ù, Ú.
•Karena hanya mengandung {Ù, Ú} maka bentuk normal dibedakan menjadi 2
yaitu :
a)Bentuk Normal Konjungtif (Ù)
b)Bentuk Normal Disjungtif (Ú)
Bentuk Normal Konjungtif (CNF)
•Bentuk Normal Konjungtif (Conjunctive Normal
Form atau CNF) adalah bentuk
normal yang memakai perangai konjungsi (Ù) dari disjungsi (Ú).
•Bentuknya :
A1 Ù A2
Ù … Ù An
Dimana Ai berbentuk
p1 Ú p2
Ú … Ú pn
Catatan : pi dinamakan literal, pi dapat benilai positif (pi)
atau negatif (~pi),
Ai
dinamakan klausa.
Bentuk Normal Disjungtif (DNF)
•Bentuk Normal Disjungtif (Disjunctive Normal
Form atau DNF) adalah bentuk
normal yang memakai perangai disjungsi (Ú) dari konjungsi (Ù).
•Bentuknya :
A1 Ú A2 Ú … Ú An
Dimana Ai berbentuk
p1 Ù p2 Ù … Ù pn
Catatan : pi dinamakan literal, pi dapat benilai positif (pi)
atau negatif (~pi),
Ai
dinamakan klausa.
Cara
Membuat Bentuk Normal Dari Tabel Kebenaran
•Contoh : ~(A Ù B)
« (~A Ú ~C)
Tabel Kebenarannya :
Cara Membuat DNF : “Mengambil Nilai T dari proposisi, kemudian merangkai semua variabel dasar, sedemikian sehingga variabel dasarnya yang bernilai T”
Contoh :
(AÙBÙC) Ú (AÙ~BÙ~C) Ú (~AÙBÙC) Ú (~AÙBÙ~C) Ú (~AÙ~BÙC) Ú (~AÙ~BÙ~C)
Cara Membuat CNF
: “Mengambil Nilai F dari proposisi, kemudian merangkai semua variabel dasar, sedemikian sehingga variabel dasarnya yang bernilai F”
Contoh :
(~AÚ~BÚC) Ù (~AÚBÚ~C)
Definisi Minterm
•Minterm adalah konjungsi dari literal-literal dengan variabel yang hanya dinyatakan satu kali.
Contoh :
1)(AÙBÙC) minterm
2)(AÙ~BÙ~C) minterm
3)(~AÙBÙC) minterm
4)(AÙBÙB) bukan minterm
5)(AÙ~BÙB) bukan minterm
Mengubah Ekspresi Logika Ke Bentuk Normal Konjungtif
Ada 5 langkah untuk mengubah ekspresi logika menjadi bentuk CNF,
langkah-langkah tersebut :
Langkah 1. A«B º (A®B)Ù(B®A)
Langkah 2. A®B º ~AÚB
Langkah 3. Hukum De Morgan : ~(AÙB) º ~AÚ~B dan ~(AÚB) º ~AÙ~B
Langkah 4. Hukum Negasi Ganda : ~~A º A
Langkah 5. Hukum Distributif : AÚ(BÙC) º (AÚB) Ù (AÚC)
Contoh
•Hilangkan perangai « dan ® dari ekspresi logika berikut : (AÙ~C)«(B®(A®~C))
Jawab :
(AÙ~C) « (B®(A®~C))
º((AÙ~C) ® (B®(A®~C))) Ù (((B®(A®~C)) ® (AÙ~C))
º(~(AÙ~C)Ú(~BÚ(~AÚ~C))) Ù (~((~BÚ(~AÚ~C))Ú(AÙ~C))
º(
(~AÚ~~C)Ú(~BÚ(~AÚ~C))) Ù ((~~BÙ(~~A Ù ~~C))Ú(AÙ~C))
º(
(~AÚC)Ú(~BÚ(~AÚ~C))) Ù ((BÙ(AÙC))Ú(AÙ~C))
Sudah hilang perangai « dan ®
Contoh mengubah menjadi CNF
•Ubahlah (~AÙ(~B®C)) « D
menjadi CNF
Jawab : (~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) (CNF)
Adakah cara lain untuk membentuk CNF
???
Dualitas
•Dualitas adalah kembaran dari suatu ekspresi. Jika memiliki perangai Ú akan
diganti Ù, dan sebaliknya. Jika bernilai T akan diganti F, dan sebaliknya.
Contoh :
(A
Ù B) Ú ~C
dualitasnya (A
Ú B) Ù ~C
Complementation
•Complementation
adalah penegasian suatu ekspresi dengan memakai
komplemennya.
Contoh : Negasikan P º (A Ù B) Ú ~C
dengan complementation?
Jawab :
Langkah 1. Cari dualitas dari P, yaitu (A Ú B) Ù ~C
Langkah 2. Lakukan complementation (~A Ú ~B) Ù C
Cek !!! ~P º ~((A Ù B) Ú ~C)
~P º ~(A Ù B) Ù ~~C
~P º (~A Ú ~B) Ù C
(sama dengan hasil di langkah 2)
Mencari CNF dengan metode complementation
Akan dicari CNF dari fungsi R (ekspresi logika R)
Dengan menggunakan complementation, caranya :
1.Buatlah DNF dari tabel kebenaran R. catatan : DNF kan biasanya ambil
proposisi T, tapi karena complementation ambil yang F.
2.Cari dualitasnya
3.Gunakan complementation
4.Hasilnya adalah CNF.
Contoh :
Tabel kebenaran dari fungsi R
1)Sehingga DNF yang diperoleh : (AÙ~BÙC) Ú (AÙ~BÙ~C) Ú (~AÙ~BÙC)
2) Cari dualitasnya : (A Ú ~B Ú C) Ù (A Ú ~B Ú ~C) Ù (~A Ú ~B Ú C)
3) Gunakan complemenatation :(~A Ú B Ú ~C) Ù (~A Ú B
Ú C) Ù (A Ú B
Ú ~C)
Cek !!!
~((~A Ú B Ú ~C) Ù (~A Ú B Ú C) Ù (A Ú B Ú ~C)) ?
