logika matematika - blog unpasblogs.unpas.ac.id/ririnda/files/2012/09/4aljabar-boolean-4-1.pdfbentuk...
TRANSCRIPT
![Page 1: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/1.jpg)
Logika Matematika Aljabar Boolean
TEKNIK INFORMATIKA
UNIVERSITAS PASUNDAN
TAHUN AJARAN 2007/2008
Pertemuan ke-5
Oleh : Mellia Liyanthy
1
![Page 2: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/2.jpg)
Bentuk Kanonik dan Bentuk baku atau standar
Fungsi boolean yang setiap sukunya
memiliki literal lengkap (mengandung
semua variabel yang didefinisikan pada
fungsi tersebut), maka disebut fungsi
boolean dalam bentuk kanonik, jika tidak
demikian, maka disebut bentuk standar.
2
![Page 3: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/3.jpg)
Bentuk Kanonik
Terdapat dua macam bentuk kanonik :
1. Minterm atau Sum Of Product (SOP),
yaitu penjumlahan dari hasil perkalian, sehingga setiap
sukunya merupakan hasil operasi perkalian, kemudian
antara satu suku dengan suku yang lainnya dipisahkan
oleh operator penjumlahan.
2. Maxterm atau Product Of Sum (POS),
yaitu perkalian dari hasil penjumlahan, sehingga setiap
sukunya merupakan hasil operasi penjumlahan, kemudian
antara satu suku dengan suku yang lainnya dipisahkan
oleh operator perkalian.
3
![Page 4: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/4.jpg)
Bentuk Standar
Terdapat dua macam bentuk Standar :
1. Sum Of Product (SOP),
yaitu penjumlahan dari hasil perkalian, sehingga setiap
sukunya merupakan hasil operasi perkalian, kemudian
antara satu suku dengan suku yang lainnya dipisahkan
oleh operator penjumlahan.
2. Product Of Sum (POS),
yaitu perkalian dari hasil penjumlahan, sehingga setiap
sukunya merupakan hasil operasi penjumlahan, kemudian
antara satu suku dengan suku yang lainnya dipisahkan
oleh operator perkalian.
4
![Page 5: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/5.jpg)
Contoh :
1. f (x, y, z) = x’ y’ z + x y’ z’ + xyz
kanonik SOP
2. f (x, y, z) = (x + y + z)(x’ + y + z)
kanonik POS
3. f (x, y, z) = x’ y’ z + x y’ z’ + yz
standar SOP
4. f (x, y, z) = x( y + z)
standar POS 5
![Page 6: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/6.jpg)
Minterm atau SOP
f ( x , y ) = x’ y + x y’ + x’ y’
Setiap suku dipisahkan oleh operator penjumlahan
Setiap suku memiliki literal
lengkap
Setiap suku merupakan hasil perkalian
6
![Page 7: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/7.jpg)
Maxterm atau POS
f ( x , y ) = (x’+ y) . (x+ y’) . (x’+ y’)
Setiap suku dipisahkan oleh operator perkalian
Setiap suku memiliki literal
lengkap
Setiap suku merupakan hasil penjumlahan
7
![Page 8: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/8.jpg)
Minterm (SOP) dan Maxterm (POS)
Minterm dan Maxterm untuk dua variabel :
x y Minterm Maxterm
Suku Lambang Suku Lambang
0 0 x’ y’ m0 x + y M0
0 1 x’ y m1 x + y’ M1
1 0 x y’ m2 x’ + y M2
1 1 x y m3 x‘ + y’ M3
8
![Page 9: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/9.jpg)
Minterm (SOP) dan Maxterm (POS)
Minterm dan Maxterm untuk tiga variabel :
x y z Minterm Maxterm
Suku Lambang Suku Lambang
0 0 0 x’ y’ z’ m0 x + y + z M0
0 0 1 x’ y’ z m1 x + y + z’ M1
0 1 0 x’ y z’ m2 x + y’ + z M2
0 1 1 x’ y z m3 x + y’ + z’ M3
1 0 0 x y’ z’ m4 x’ + y + z M4
1 0 1 x y’ z m5 x’ + y + z’ M5
1 1 0 x y z’ m6 x’ + y’ + z M6
1 1 1 x y z m7 x’ + y’ + z’ M7
9
![Page 10: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/10.jpg)
Contoh Nyatakan fungsi berikut dalam bentuk Kanonik SOP dan POS !
a b c f (a, b, c)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
SOP : f (a,b,c) = a‟b‟c + a‟bc + ab‟c + abc‟ + abc
atau f (a,b,c) = m1 + m3 + m5 + m6 + m7 = (1, 3, 5, 6, 7)
POS : f (a,b,c) = (a+b+c) (a+b‟+c) (a‟+b+c)
atau f (a,b,c) = M0 ● M2 ● M4 = (0, 2, 4) 10
![Page 11: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/11.jpg)
Perlu dipahami, bahwa ....
“ Untuk membentuk minterm, tinjau kombinasi variabel-
variabel yang menghasilkan nilai 1. “
“ Untuk membentuk maxterm, tinjau kombinasi variabel-
variabel yang menghasilkan nilai 0. “
“ Notasi dan berguna untuk mempersingkat penulisan
ekspresi dalam bentuk SOP dan POS “
“ Lambang untuk minterm menggunakan huruf m,
sedangkan untuk maxterm menggunakan huruf M ”
11
![Page 12: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/12.jpg)
Latihan
Nyatakan fungsi boolean
f (a,b,c) = a + b’c dalam bentuk kanonik SOP
dan POS !
13
![Page 13: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/13.jpg)
Solusi untuk SOP....
Lengkapi literal untuk setiap sukunya.
f (a,b,c) = a + b’c
a = a . 1 hk. identitas
= a . ( b + b’ ) hk. komplemen
= (a.b) + (a.b’ ) hk. Distributif
= ab + ab’ perjanjian kita
Sehingga bentuk fungsinya menjadi :
f (a,b,c) = ab + ab’ + b’c
a 14
![Page 14: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/14.jpg)
Latihan
Apakah sudah terbentuk SOPnya ?
15
![Page 15: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/15.jpg)
Solusi untuk SOP....
Lengkapi lagi literal untuk setiap sukunya.
f (a,b,c) = ab + ab’ + b’c
ab = ab . 1 hk. identitas
= ab . ( c + c’ ) hk. komplemen
= (a.b.c) + (a.b.c’ ) hk. Distributif
= abc + abc’ perjanjian kita
Sehingga bentuk fungsinya menjadi :
f (a,b,c) = abc + abc’ + ab’ + b’c
ab 16
![Page 16: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/16.jpg)
Solusi untuk SOP....
Lengkapi lagi literal untuk setiap sukunya.
f (a,b,c) = abc + abc’ + ab’ + b’c
ab’= ab’ . 1 hk. identitas
= ab’ . ( c + c’ ) hk. komplemen
= (a.b’.c) + (a.b’.c’ ) hk. Distributif
= ab’c + ab’c’ perjanjian kita
Sehingga bentuk fungsinya menjadi :
f (a,b,c) = abc + abc’ + ab’ c + ab’c’ + b’c
ab’ 17
![Page 17: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/17.jpg)
Solusi untuk SOP....
Lengkapi lagi literal untuk setiap sukunya.
f (a,b,c) = abc + abc’ + ab’ c + ab’c’ + b’c
b’c = b’c . 1 hk. identitas
= b’c . ( a + a’ ) hk. komplemen
= (a.b’.c) + (a’.b’.c) hk. Distributif
= ab’c + a’b’c perjanjian kita
Sehingga bentuk fungsinya menjadi :
f (a,b,c) = abc + abc’ + ab’ c + ab’c’ + ab’c + a’b’c
b’c 18
![Page 18: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/18.jpg)
Solusi untuk SOP....
f (a,b,c) = abc + abc’ + ab’ c + ab’c’ + a’b’c = m7 + m6 + m5 + m4 + m1
= ( 1, 4, 5, 6, 7 )
f (a,b,c) = abc + abc’ + ab’ c + ab’c’ + ab’c + a’b’c
Sehingga bentuk SOP fungsi tersebut menjadi :
f (a,b,c) = a + b’ c
Jika terdapat lebih dari satu suku yang memiliki literal yang sama, maka tuliskan salah satunya saja.
Periksa literal untuk setiap sukunya.
19
![Page 19: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/19.jpg)
Latihan
Tapi ingat anda masih harus membentuk
POSnya !
20
![Page 20: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/20.jpg)
Solusi untuk POS....
Ubah menjadi bentuk standar POS.
f (a,b,c) = a + b’c
a + b’c = a + (b’.c) perjanjian kita
= (a+ b’ ) (a+c) hk. Distributif
Sehingga bentuk standar POSnya menjadi :
f (a,b,c) = (a + b’ ) (a + c)
21
![Page 21: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/21.jpg)
Solusi untuk POS....
Lengkapi literal untuk setiap sukunya.
f (a,b,c) = (a + b’ ) (a + c)
a + b’ = a + b’ + 0 hk. identitas
= a + b’ + (c.c’ ) hk. komplemen
= (a+b’+c) (a+b’+c’ ) hk. Distributif
Sehingga bentuk fungsinya menjadi :
f (a,b,c) = (a + b’ + c) (a + b’ + c’) (a + c)
a+b’ 22
![Page 22: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/22.jpg)
Solusi untuk POS....
Lengkapi lagi literal untuk setiap sukunya.
f (a,b,c) = (a + b’ + c) (a + b’ + c’) (a + c)
a + c = a + c + 0 hk. identitas
= a + c + (b.b’ ) hk. komplemen
= (a+b+c) (a+b’+c) hk. Distributif
Sehingga bentuk fungsinya menjadi :
f (a,b,c) = (a+b’+c) (a+b’+c’) (a+b+c) (a+b’+c)
a+c 23
![Page 23: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/23.jpg)
Solusi untuk POS....
f (a,b,c) = (a+b’+c) (a+b’+c’) (a+b+c) = M2 . M3 . M0
= ( 0, 2, 3 )
f (a,b,c) = (a+b’+c) (a+b’+c’) (a+b+c) (a+b’+c)
Sehingga bentuk POS fungsi tersebut menjadi :
f (a,b,c) = (a + b’ ) (a + c)
Jika terdapat lebih dari satu suku yang memiliki literal yang sama, maka tuliskan salah satunya saja.
Periksa literal untuk setiap sukunya.
24
![Page 24: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/24.jpg)
Solusi Akhir....
Sehingga bentuk kanonik SOP dan POS dari :
f (a,b,c) = a + b’c
SOP :
f (a,b,c) = ( 1, 4, 5, 6, 7 )
POS :
f (a,b,c) = ( 0, 2, 3)
25
![Page 25: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/25.jpg)
Konversi antar Bentuk Kanonik
Kita dapat memperoleh fungsi boolean dalam
bentuk kanonik POS dari suatu fungsi kanonik
SOP.
Langkah – langkahnya :
1. Cari fungsi komplemen dari fungsi tersebut,
2. Gunakan hukum de Morgan.
27
![Page 26: Logika Matematika - Blog Unpasblogs.unpas.ac.id/ririnda/files/2012/09/4Aljabar-Boolean-4-1.pdfBentuk Kanonik dan Bentuk baku atau standar Fungsi boolean yang setiap sukunya ... a =](https://reader031.vdokumen.com/reader031/viewer/2022012317/5c97fa9609d3f2312a8cf0d1/html5/thumbnails/26.jpg)
Contoh :
Ubah kedalam bentuk kanonik POS !
f (x,y,z) = (1, 4, 5, 6, 7)
Solusi :
1. Cari fungsi komplemennya :
f ’ (x,y,z) = (0, 2, 3) = m0 + m2 + m3
2. Gunakan hk. De Morgan
(f ‘ (x,y,z))’ = (m0 + m2 + m3 )‟
= m0„ . m2 „ . m3 „
= (x‟y‟z‟)‟ . (x‟yz‟)‟ . (x‟yz)‟
= (x+y+z) . (x+y‟+z) . (x+y‟+z‟)
= M0 . M2 . M3 = (0, 2, 3) 28