BENTUK NORMAL - WordPress.com

Report
BENTUK NORMAL
Oleh :
Fidia Deny Tisna A.
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
• Bentuk Normal adalah bentuk ekspresi logika yang
standar.
• Bentuk ekspresi logika yang standar adalah bentuk
ekspresi logika yang menggunakan perangai dasar ~, ,
.
• Karena hanya mengandung {, } maka bentuk normal
dibedakan menajdi 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 :
*
A
B
C
AB
~(AB)
~A
~C
~A~C
*
Keterangan
T
T
T
T
F
F
F
F
T
DNF
T
T
F
T
F
F
T
T
F
CNF
T
F
T
F
T
F
F
F
F
CNF
T
F
F
F
T
F
T
T
T
DNF
F
T
T
F
T
T
F
T
T
DNF
F
T
F
F
T
T
T
T
T
DNF
F
F
T
F
T
T
F
T
T
DNF
F
F
F
F
T
T
T
T
T
DNF
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
A
B
C
R
T
T
T
T
T
T
F
T
T
F
T
F
ambil sebagai DNF
T
F
F
F
ambil sebagai DNF
F
T
T
T
F
T
F
T
F
F
T
F
F
F
F
T
ambil sebagai DNF
Ingat !!
Meskipun yang
diambil adalah
proposisi F, akan
tetapi karena
DNF, nilai-nilai
variabel yang
diambil adalah
yang T.
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)) ?
Tugas
1) Ubahlah ekspresi logika berikut menjadi bentuk CNF :
dengan menggunakan Tabel kebenaran, 5 langkah CNF,
dan complementation CNF
a) (A  C)  (B  C)
b) ~(A  B)  (A  B)
c) ~A  (B  C)
2) Ubahlah ekspresi logika berikut menjadi DNF : dengan
menggunakan Tabel Kebenaran
a) ~((AB)  C)  B
b) (AB)  ((A  C)  B)
Tugas
3) Dapatkah kita membuat DNF dengan cara mengambil
CNF dari yang benilai T, kemudian dicari dualitasnya, dan
dicari complementationnya? Cara mengeceknya, lakukan
eksperimen pada tabel kebenaran pada soal nomor 2.

similar documents