materi 06 matdis bentuk bentuk normaljhon

MATERI 6MATERI 6BENTUK-BENTUK NORMALBENTUK-BENTUK NORMAL

DNF/SOP/MINTERMDNF/SOP/MINTERM

CNF/POS/MAXTERMCNF/POS/MAXTERM

BENTUK KANONIK FUNGSI BENTUK KANONIK FUNGSI BOOLEBOOLE

KONVERSI ANTAR BENTUK KONVERSI ANTAR BENTUK NORMALNORMAL

MENGAPA BENTUK NORMAL? MENGAPA BENTUK NORMAL? (1)(1)

Kemungkinan nilai dalam tabel Kemungkinan nilai dalam tabel kebenaran:kebenaran:– Semua salah (kontradiksi)Semua salah (kontradiksi)– Semua benar (tautologi)Semua benar (tautologi)– Memuat paling sedikit 1 benar Memuat paling sedikit 1 benar

(satisfiable)(satisfiable) Cara mencari nilai kebenaran, Cara mencari nilai kebenaran,

biasanya menggunakan tabel biasanya menggunakan tabel kebenaran.kebenaran.

MENGAPA BENTUK NORMAL? MENGAPA BENTUK NORMAL? (2)(2)

Pembuatan tabel kebenaran tidak Pembuatan tabel kebenaran tidak terlalu praktis, bahkan dengan terlalu praktis, bahkan dengan bantuan komputer, terutama untuk bantuan komputer, terutama untuk jumlah variabel yang besar.jumlah variabel yang besar.

Prosedur yang lebih mudah adalah Prosedur yang lebih mudah adalah dengan mereduksi ke bentuk-bentuk dengan mereduksi ke bentuk-bentuk normal.normal.

JENIS BENTUK NORMALJENIS BENTUK NORMAL

Disjunctive normal form (DNF)Disjunctive normal form (DNF)

atau Sum of products (SOP)atau Sum of products (SOP)

atau Mintermatau Minterm Conjunctive normal form (CNF)Conjunctive normal form (CNF)

atau Product of sums (POS)atau Product of sums (POS)

atau Maxtermatau Maxterm

DNF/SOPDNF/SOP

DNF terdiri dari penjumlahan dari DNF terdiri dari penjumlahan dari beberapa perkalian (sum of products beberapa perkalian (sum of products = SOP).= SOP).

Dalam tabel kebenaran, DNF Dalam tabel kebenaran, DNF merupakan perkalian-perkalian yang merupakan perkalian-perkalian yang menghasilkan nilai 1.menghasilkan nilai 1.

Contoh: xy + x’yContoh: xy + x’y Setiap suku (Setiap suku (termterm) disebut ) disebut mintermminterm Simbol minterm : Simbol minterm : mm

CNF/POSCNF/POS

CNF terdiri dari perkalian dari beberapa CNF terdiri dari perkalian dari beberapa penjumlahan (product of sum = POS).penjumlahan (product of sum = POS).

Dalam tabel kebenaran, CNF Dalam tabel kebenaran, CNF merupakan penjumlahan-penjumlahan merupakan penjumlahan-penjumlahan yang menghasilkan nilai 0.yang menghasilkan nilai 0.

Contoh: (x+y) . (x’+y)Contoh: (x+y) . (x’+y) Setiap suku (Setiap suku (termterm) disebut ) disebut maxtermmaxterm Simbol maxterm : Simbol maxterm : MM

MINTERM & MAXTERM Cara yang dipakai untuk mempermudah Cara yang dipakai untuk mempermudah

menyatakan suatu ekspresi logika menyatakan suatu ekspresi logika Pada dasarnya adalah mendaftar nomor Pada dasarnya adalah mendaftar nomor

baris atau nilai desimal dari kombinasi baris atau nilai desimal dari kombinasi variabel input yang outputnya variabel input yang outputnya ::

– berharga "1" untuk berharga "1" untuk mintermminterm – berharga "0" untuk berharga "0" untuk maxtermmaxterm. .

Tabel Minterm dan Maxterm Tabel Minterm dan Maxterm (1)(1)

Tabel Minterm dan Maxterm Tabel Minterm dan Maxterm (2)(2)

Membentuk Persamaan Boole dari Membentuk Persamaan Boole dari Tabel kebenaran (1)Tabel kebenaran (1)

Jika yang dilihat adalah output "1" Jika yang dilihat adalah output "1" maka persamaan mempunyai bentuk maka persamaan mempunyai bentuk "Sum of Product (SOP)“"Sum of Product (SOP)“/DNF/ /DNF/ MintermMinterm

Jika diberi input berikut :Jika diberi input berikut :

X Y Z = 0 0 0 X Y Z = 0 0 0 ditulis : X’Y’Z’ ditulis : X’Y’Z’

X Y Z = 1 1 1 X Y Z = 1 1 1 ditulis : XYZ ditulis : XYZ

X Y Z = 0 1 1 X Y Z = 0 1 1 ditulis : X’YZ ditulis : X’YZ

Membentuk Persamaan Boole dari Membentuk Persamaan Boole dari Tabel kebenaran (2)Tabel kebenaran (2)

Jika yang dilihat adalah output “Jika yang dilihat adalah output “00" " maka persamaan mempunyai bentuk maka persamaan mempunyai bentuk " Product of Sum" Product of Sum ((PPOOSS)“)“/CNF/ /CNF/ MaxtermMaxterm

Jika diberi input berikut :Jika diberi input berikut :

X Y Z = 0 0 0 X Y Z = 0 0 0 ditulis : (X+Y+Z) ditulis : (X+Y+Z)

X Y Z = 1 1 1 X Y Z = 1 1 1 ditulis : (X’+Y’+Z’) ditulis : (X’+Y’+Z’)

X Y Z = 0 1 1 X Y Z = 0 1 1 ditulis : (X+Y’+Z’) ditulis : (X+Y’+Z’)

Contoh 1Contoh 1

Nyatakan dalam bentuk SOP dan POSNyatakan dalam bentuk SOP dan POS

Penyelesaian Contoh 1 (1)Penyelesaian Contoh 1 (1)

SOP/DNF/MINTERMSOP/DNF/MINTERMKombinasi nilai-nilai peubah yang Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama menghasilkan nilai fungsi sama dengan 1 adalah 01, maka fungsi dengan 1 adalah 01, maka fungsi Booleannya dalam bentuk SOP:Booleannya dalam bentuk SOP:f(x, y) = x’y f(x, y) = x’y 01 01 1 1atau atau

f(x, y) = mf(x, y) = m1 1 = = mm (1) (1)

Penyelesaian Contoh 1 (2)Penyelesaian Contoh 1 (2)

POS/CNF/MAXTERMPOS/CNF/MAXTERMKombinasi nilai-nilai peubah yang Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama menghasilkan nilai fungsi sama dengan 0 adalah 00, 10, 11, maka dengan 0 adalah 00, 10, 11, maka fungsi Booleannya dalam bentuk POS:fungsi Booleannya dalam bentuk POS:f(x,y)=(x+y)(x’+y)(x’+y’)f(x,y)=(x+y)(x’+y)(x’+y’)atauatau

f(x, y) = Mf(x, y) = M00 M M22 M M33 = = MM(0, 2, 3)(0, 2, 3) 0 0 1 0 1 1

Contoh 2Contoh 2

Nyatakan dalam bentuk Nyatakan dalam bentuk

SOP dan POSSOP dan POS

Penyelesaian Contoh 2 (1)Penyelesaian Contoh 2 (1)

SOPSOPKombinasi nilai-nilai peubah yang Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk SOP:fungsi Booleannya dalam bentuk SOP:f(x, y, z) = x’y’z + xy’z’ + xyzf(x, y, z) = x’y’z + xy’z’ + xyzatau atau

f(x, y, z) = mf(x, y, z) = m1 1 + m+ m44 + m + m77 = = mm (1, 4, 7) (1, 4, 7)

001 100 111

Penyelesaian Contoh 2 (2)Penyelesaian Contoh 2 (2) POSPOS

Kombinasi nilai-nilai peubah yang Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 menghasilkan nilai fungsi sama dengan 0 adalah 000, 010, 011, 101, dan 110, maka adalah 000, 010, 011, 101, dan 110, maka fungsi Booleannya dalam bentuk POS:fungsi Booleannya dalam bentuk POS:

f(x,y,z)= (x+y+z)(x+y’+z)(x+y’+z’)f(x,y,z)= (x+y+z)(x+y’+z)(x+y’+z’)

(x’+y+z’)(x’+y’+z)(x’+y+z’)(x’+y’+z)atauatau

f(x, y, z) = Mf(x, y, z) = M00 M M22 M M33 M M55 M M66

= = MM(0, 2, 3, 5, 6)(0, 2, 3, 5, 6)

0 0 0

0 1 0

0 1 1

1 0 1

1 1 0

BENTUK KANONIK FUNGSI BOOLEAN BENTUK KANONIK FUNGSI BOOLEAN (1)(1)

Bentuk kanonik/bentuk lengkap Bentuk kanonik/bentuk lengkap adalah bentuk fungsi boolean adalah bentuk fungsi boolean dimana setiap term dimana setiap term mengandung/memuat semua mengandung/memuat semua variabel yang adavariabel yang ada– melengkapi literal untuk setiap melengkapi literal untuk setiap

suku agar jumlahnya samasuku agar jumlahnya sama– Jumlah literal sama dengan jumlah Jumlah literal sama dengan jumlah

variabelvariabel

BENTUK KANONIK FUNGSI BOOLEAN BENTUK KANONIK FUNGSI BOOLEAN (2)(2)

Contoh bentuk kanonik:Contoh bentuk kanonik:– f(x,y) = xy’ + xyf(x,y) = xy’ + xy Minterm Minterm– f(x,y,z) = xyz’ + x’y’z +xyzf(x,y,z) = xyz’ + x’y’z +xyz Minterm Minterm– f(x,y) = (x+y) . (x’+y)f(x,y) = (x+y) . (x’+y) Maxterm Maxterm

Contoh bentuk non-kanonik :Contoh bentuk non-kanonik :– f(x,y,z) = x + y’z f(x,y,z) = x + y’z

MintermMinterm– f(x,y,z) = (x+y+z’) . (x+z) . (y’ + z) f(x,y,z) = (x+y+z’) . (x+z) . (y’ + z)

MaxtermMaxterm

Contoh 3Contoh 3

Nyatakan fungsi Boolean f(x,y,z) = x Nyatakan fungsi Boolean f(x,y,z) = x + y’z dalam bentuk kanonik SOP dan + y’z dalam bentuk kanonik SOP dan POSPOS..

Penyelesaian Contoh 3 (1)Penyelesaian Contoh 3 (1) SOP/DNF/MintermSOP/DNF/Minterm

x = x (y + y’)x = x (y + y’) = xy + xy’= xy + xy’ = xy (z + z’) + xy’(z + z’)= xy (z + z’) + xy’(z + z’) = xyz + xyz’ + xy’z + xy’z’= xyz + xyz’ + xy’z + xy’z’y’z = y’z (x + x’)y’z = y’z (x + x’) = xy’z + x’y’z= xy’z + x’y’zJadi f(x, y, z) Jadi f(x, y, z)

= x + y’z= x + y’z = xyz + xyz’ + xy’z + xy’z’ + xy’z + = xyz + xyz’ + xy’z + xy’z’ + xy’z +

x’y’zx’y’z = x’y’z + xy’z’ + xy’z + xyz’ + xyz= x’y’z + xy’z’ + xy’z + xyz’ + xyzatau atau

f(x, y, z)f(x, y, z) = m= m11 + m + m44 + m + m55 + m + m66 + m + m77 = = mm(1,4,5,6,7)(1,4,5,6,7)

Penyelesaian Contoh 3 (2)Penyelesaian Contoh 3 (2)

POS/CNF/MaxtermPOS/CNF/Maxtermf(x, y, z) = x + y’z f(x, y, z) = x + y’z = (x + y’)(x + z)= (x + y’)(x + z)x + y’ = x + y’ + zz’x + y’ = x + y’ + zz’ = (x + y’ + z)(x + y’ + z’)= (x + y’ + z)(x + y’ + z’)x + z = x + z + yy’x + z = x + z + yy’ = (x + y + z)(x + y’ + z)= (x + y + z)(x + y’ + z)Jadi, f(x, y, z) Jadi, f(x, y, z)

= (x+y’+z)(x+y’+z’)(x+y+z)(x+y’+ z)= (x+y’+z)(x+y’+z’)(x+y+z)(x+y’+ z) = (x + y + z)(x + y’ + z)(x + y’ + z’)= (x + y + z)(x + y’ + z)(x + y’ + z’)

atau f(x, y, z) = Matau f(x, y, z) = M00MM22MM33 = = MM(0, 2, 3)(0, 2, 3)

Konversi Antar Bentuk Normal Konversi Antar Bentuk Normal (1)(1)

Konversi SOP menjadi POSKonversi SOP menjadi POSKomplemen Minterm Komplemen Minterm Maxterm Maxterm

Konversi POS menjadi SOP Konversi POS menjadi SOP – Komplemen Maxterm Komplemen Maxterm Minterm Minterm

Konversi Antar Bentuk Normal Konversi Antar Bentuk Normal (2)(2)

MisalkanMisalkan

f(x, y, z) = f(x, y, z) = mm (1, 4, 5, 6, 7) dan f’ (1, 4, 5, 6, 7) dan f’ adalah fungsi komplemen dari f, makaadalah fungsi komplemen dari f, maka

f’(x, y, z) = f’(x, y, z) = mm (0, 2, 3) (0, 2, 3)

= m= m00+ m+ m22 + m + m33

Dengan menggunakan hukum De Dengan menggunakan hukum De Morgan, diperoleh fungsi f dalam Morgan, diperoleh fungsi f dalam bentuk POS.bentuk POS.

Konversi Antar Bentuk Normal Konversi Antar Bentuk Normal (3)(3)

f(x, y, z) f(x, y, z)

= (f’(x, y, z))’= (m= (f’(x, y, z))’= (m00+m+m22+m+m33)’)’

= m= m00’ . m’ . m22’ . m’ . m33’’

= (x’y’z’)’ (x’y z’)’ (x’y z)’= (x’y’z’)’ (x’y z’)’ (x’y z)’

= (x + y + z) (x +y’+z) (x+ y’+ z’)= (x + y + z) (x +y’+z) (x+ y’+ z’)

= M= M00 M M22 M M33

= = M M (0,2,3)(0,2,3) Jadi, f(x, y, z) Jadi, f(x, y, z)

= = mm (1, 4, 5, 6, 7) = (1, 4, 5, 6, 7) = MM (0,2,3). (0,2,3). KesimpulanKesimpulan: m: mjj’ = M’ = Mjj

Contoh 4Contoh 4 NyatakanNyatakan f(x, y, z)=f(x, y, z)=MM(0,2,4,5) dalam SOP (0,2,4,5) dalam SOP Penyelesaian :Penyelesaian : f(x, y, z) = f(x, y, z) = mm (1, 3, 6, 7) (1, 3, 6, 7)

NyatakanNyatakang(w, x, y, z)=g(w, x, y, z)=mm(1,2,5,6,10,15) dalam (1,2,5,6,10,15) dalam POSPOSPenyelesaian:Penyelesaian:g(w, x, y, z) = g(w, x, y, z) = MM (0,3,4,7,8,9,11,12,13,14)(0,3,4,7,8,9,11,12,13,14)