LAPORAN
PENGANTAR SISTEM DIGITAL
(FUNGSI BOOLEAN)
KATA PENGANTAR
Puji syukur yang sebesar-besarnya kami hantarkan kepada tuhan yang maha esa karena dengan izinnyalah laporan ini dapat diselesaikan tepat pada waktunya. Kami ucapkan pula terima kasih yang sebesar-besarnya pada rekan-rekan telah bekerja sama dalam pengerjaan laporan ini dan semoga laporan ini dapat bermanfaat bagi kita semua. Laporan kami ini akan kami serahkan kepada dosen mata kuliah yaitu Bapak Muhammad Dermawan Mulyodiputro guna pemberian nilai oleh beliau. Dan hasil dari laporan kami ini akan dipresentasikan saat kegiatan kuliah Pengantar Sistem Digital yang bertepatan pada hari Senin tanggal 10 November 2014. Kami berharap agar hasilnya nanti bisa maksimal. Sekian dan Terima Kasih.
DAFTAR ISI
Pendahuluan.................................................................................... 1
Pembahasan..................................................................................... 2
Aljabar Boolean................................................................................................ 2
Operasi Dasar Logika ...................................................................................... 3
Fungsi Boolean................................................................................................. 4
Aljabar Boolean Dua Nilai................................................................................ 5
Ekspresi Boolean.............................................................................................. 6
Prinsip Dualitas…............................................................................................. 7
Hukum-Hukum Aljabar Boolean...................................................................... 8
Penyederhanaan Fungsi Boolean...................................................................... 9
Daftar Pustaka................................................................................. 11
PENDAHULUAN
1. Latar Belakang
Aljabar boolean merupakan aljabar yang berhubungan dengan variabel-variabel biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR dan NOT (komplemen).
Fungsi boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung. Suatu fungsi boolean bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boolean merupakan daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner.
Aljabar boolean mempunyai 2 fungsi berbeda yang saling berhubungan. Dalam arti luas, aljabar boolean berarti suatu jenis simbol-simbol yang ditemukan oleh George Boole untuk memanipulasi nilai-nilai kebenaran logika secara aljabar. Dalam hal ini aljabar boolean cocok untuk diaplikasikan dalam komputer. Oleh karena itulah si penulis berharap si pembaca dapat mengetahui fungsi dan menambah wawasan tentang Aljabar Boolean.
2. Rumusan Masalah
Dengan makalah yang di buat oleh si penulis dapat ditemui beberapa permasalahan diantaranya yaitu:
1. Apa yang di maksud dengan Aljabar Boolean?
2. Apa fungsi dari Aljabar Boolean tersebut?
3. Apa saja hukum-hukum dari Aljabar Boolean?
Pembahasan
ALJABAR BOOLEAN
Aljabar boolean merupakan aljabar yang berhubungan dengan variabel-variabel biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR dan NOT (komplemen). Fungsi boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung.
Suatu fungsi boolean bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boolean merupakan daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner.
Aljabar boolean mempunyai 2 fungsi berbeda yang saling berhubungan. Dalam arti luas, aljabar boolean berarti suatu jenis simbol-simbol yang ditemukan oleh George Boole untuk memanipulasi nilai-nilai kebenaran logika secara aljabar. Dalam hal ini aljabar boolean cocok untuk diaplikasikan dalam komputer. Disisi lain, aljabar boolean juga merupakan suatu struktur aljabar yang operasi-operasinya memenuhi aturan tertentu.
DASAR OPERASI LOGIKA:
Memberikan batasan yang pasti dari suatu keadaan, sehingga suatu keadaan tidak dapat berada dalam dua ketentuan sekaligus.
Dalam logika dikenal aturan sebagai berikut :
¨ Suatu keadaan tidak dapat dalam keduanya benar dan salah sekaligus
¨ Masing-masing adalah benar / salah.
¨ Suatu keadaan disebut benar bila tidak salah.
Dalam ajabar boolean keadaan ini ditunjukkan dengan dua konstanta : LOGIKA ‘1’ dan ‘0’
2.1 Aljabar Boolean
Misalkan terdapat
- Dua operator biner: + dan ×/*
- Sebuah operator uner: ’.
- B : himpunan yang didefinisikan pada opeartor +, ×/*, dan ’
- 0 dan 1 adalah dua elemen yang berbeda dari B.
Tupel
(B, +, ×, ’) disebut Aljabar Boolean jika untuk setiap a, b, c ÎB berlaku aksioma-aksioma atau postulat Huntington berikut:
1. Closure: (i) a + b Î B
(ii) a × b Î B
2. Identitas: (i) a + 0 = a
(ii) a × 1 = a
3. Komutatif: (i) a + b= b + a
(ii) a × b = b . a
4. Distributif: (i) a × (b+ c) = (a × b) + (a × c)
(ii) a + (b × c) = (a + b) × (a+ c)
(ii) a × a’ = 0
Untuk mempunyai sebuah aljabar Boolean, harus diperlihatkan:
1. Elemen-elemen himpunan B,
2. Kaidah operasi untuk operator biner dan operator uner,
3. Memenuhi postulat Huntington.
2.2 Fungsi Boolean
· Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai
f : Bn® B
yang dalam hal ini Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B.
· Setiap ekspresi Boolean tidak lain merupakan fungsi Boolean.
· Misalkan sebuah fungsi Boolean adalah
f(x, y, z) = xyz + x’y+ y’z
Fungsi f memetakan nilai-nilai pasangan terurut ganda-3
(x, y, z) ke himpunan {0, 1}.
Contohnya, (1, 0, 1) yang berarti x = 1, y = 0, dan z = 1
sehingga f(1, 0, 1) = 1 × 0 ×1 + 1’ × 0 + 0’×1 = 0 + 0 + 1 = 1 .
Contoh-contoh fungsi Boolean yang lain:
1. f(x) = x
2. f(x, y) = x’y + xy’+ y’
3. f(x, y) = x’ y’
4. f(x, y) = (x + y)’
5. f(x, y, z) = xyz’
· Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.
Contoh: Fungsi h(x, y, z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’.
Contoh. Diketahui fungsi Booelan f(x, y, z) = xy z’, nyatakan h dalam tabel kebenaran.
Penyelesaian:
| x | y | z | f(x, y, z) = xy z’ |
| 0 0 0 0 1 1 1 1 | 0 0 1 1 0 0 1 1 | 0 1 0 1 0 1 0 1 | 0 0 0 0 0 0 1 0 |
2.3 Aljabar Boolean Dua-Nilai
Aljabar Boolean dua-nilai:
- B = {0, 1}
- operator biner, + dan *
- operator uner, ’
- Kaidah untuk operator biner dan operator uner:
| a | b | a * b | a | b | a + b | a | a’ | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | ||
| 1 | 0 | 0 | 1 | 0 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 |
Cek apakah memenuhi postulat Huntington:
1. Closure : jelas berlaku
2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:
(i) 0 + 1 = 1 + 0 = 1
(ii) 1 * 0 = 0 * 1 = 0
3. Komutatif: jelas berlaku dengan melihat simetri tabel operator biner.
4. Distributif: (i) a * (b + c) = (a * b) + (a * c) dapat ditunjukkan benar dari tabel operator biner di atas dengan membentuk tabel kebenaran:
| A | b | c | b + c | a * (b + c) | a * b | a * c | (a * b) + (a * c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
(ii) Hukum distributif a + (b × c) = (a + b) × (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).
5. Komplemen: jelas berlaku karena Tabel 7.3 memperlihatkan bahwa:
(i) a + a‘ = 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
(ii) a*a = 0, karena 0*0’= 0*1 = 0 dan 1*1’ = 1*0 = 0
Karena kelima postulat Huntington dipenuhi, maka terbukti bahwa B = {0, 1} bersama-sama dengan operator biner + dan ×operator komplemen ‘ merupakan aljabar Boolean.
2.4 Ekspresi Boolean
Misalkan (B, +, *, ’) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +,*, ’) adalah:
(i) setiap elemen di dalam B,
(ii) setiap peubah,
(iii) jika e1dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 × e2, e1’ adalah ekspresi Boolean
Contoh:
0
1
a
b
c
a + b
a*b
a’* (b + c)
a*b’ + a*b* c’ + b’, dan sebagainya
Mengevaluasi Ekspresi Boolean
Contoh: a’*(b + c)
jika a= 0, b = 1, dan c = 0, maka hasil evaluasi ekspresi:
0’*(1 + 0) = 1*1 = 1
Dua ekspresi Boolean dikatakan ekivalen (dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuk setiap pemberian nilai-nilai kepada npeubah.
Contoh:
a*(b + c) = (a . b) + (a*c)
Contoh. Perlihatkan bahwa a + a’b = a+ b .
Penyelesaian:
| a | b | a’ | a’b | a + a’b | a + b |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
Perjanjian: tanda titik (×) dapat dihilangkan dari penulisan ekspresi Boolean, kecuali jika ada penekanan:
(i) a(b+ c) = ab + ac
(ii) a + bc = (a + b) (a + c)
(iii) a*0 , bukan a0
2. 5 Prinsip Dualitas
Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +, ×, dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti
× dengan +
+ dengan *
0 dengan 1
1 dengan 0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dualdari S.
Contoh.
(i) (a*1)(0 + a’) = 0 dualnya (a + 0) + (1*a’) = 1
(ii) a*(a‘ + b) = a*b dualnya a + a‘b = a+ b
2. 6 Hukum-hukum Aljabar Boolean
| Hukum identitas: (i) a + 0 = a (ii) a*1 = a | 2. Hukum idempoten: (i) a + a = a (ii) a*a = a |
| 3. Hukum komplemen: (i) a + a’ = 1 (ii) a*a’ = 0 | 4. Hukum dominansi: (i) a*0 = 0 (ii) a + 1 = 1 |
| 5. Hukum involusi: (i) (a’)’ = a | 6. Hukum penyerapan: (i) a + a*b = a (ii) a*(a + b) = a |
| 7. Hukum komutatif: (i) a + b = b + a (ii) a*b = b*a | 8. Hukum asosiatif: (i) a + (b + c) = (a + b) + c (ii) a* (b* c) = (a*b)*c |
| 9. Hukum distributif: (i) a + (b*c) = (a + b) (a + c) (ii) a*(b + c) = a*b + a*c | 10. Hukum De Morgan: (i) (a + b)’ = a’b’ (ii) (a*b)’ = a’ + b’ |
| 11. Hukum 0/1 (i) 0’ = 1 (ii) 1’ = 0 | |
Contoh Buktikan (i) a + a’b= a + b dan (ii) a(a’ + b) = ab
Penyelesaian:
(i) a + a’b = (a + ab) + a’b (Penyerapan)
= a + (ab+ a’b) (Asosiatif)
= a + (a+ a’)b (Distributif)
= a + 1 ·b (Komplemen)
= a + b (Identitas)
(ii) adalah dual dari (i)
PENYEDERHANAAN FUNGSI BOOLEAN
1.Fungsi Kompleks
Pada fungsi Kompleks dari sebuah system aljabar Boolean seringkali mempunyai operasi-operasi biner yang tidak perlu dan atau dapat disederhanakan sehingga fungsi tersebut tidak mempunyai literal atau suku-suku yang berlebihan
Contoh :
F(x,y) = x’y + xy’ + y’
Dapat disederhanakan menjadi
F(x,y) = x’y + y’(x + 1)
= x’y + y’
= (x’ + y’)(y + y’)
= x’ + y’
( a . b ) + c = ( a + c )( b + c)
2.Cara Penyederhanaan
Dari segi penerapan fungsi aljabar Boolean menjadi bentuk yang sederhana dilakukan dengan 3 cara
a.Secara Aljabar : menggunakan aturan/aksioma yang berlaku pada system aljabar Boolean
b.Menggunakan Peta Karnaugh
c.Menggunakan metode Quine Mc Cluskey
Contoh diatas penyederhanaan dengan cara aljabar dan contoh yang lainnya sebagai berikut :
Sederhanakan F(x, y, z) = xy + x’z + yz
Jawab :
F(x, y, z) = xy + x’z + yz (x + x’)
= xy + x’z + xyz + x’yz
= xy + xyz + x’z + x’zy
= xy ( 1 + z ) + x’z ( 1 + y )
Sederhanakan F(x, y, z) = x’y’z + x’yz + xy’
Jawab :
F(x, y, z) = x’y’z + x’yz + xy’
= x’zy’ + x’zy + xy’
= x’z ( y’ + y ) + xy’
= x’z + xy’
DAFTAR PUSTAKA
kur2003.if.itb.ac.id/file/Aljabar%20Boolean.doc