dokeng: 2010

ALJABAR BOOLEAN
&
NOTASI FORMAL

YESSY YANITASARI, ST
MATEMATIKA DISKRIT EDISI KEDUA
RINALDI MUNIR
PENERBIT INFORMATIKA BANDUNG

HIMPUNAN

Himpunan (set) adalah kumpulan objek – objek yang berbeda.

Objek yang terdapat di dalam himpunan disebut elemen, unsur, atau anggota.

PENYAJIAN HIMPUNAN

Terdapat banyak cara untuk menyajikan himpunan. Disini dikemukakan 4 cara penyajian yaitu :

Enumerasi
Simbol – simbol Baku
Notasi Pembentuk Himpunan
Diagram Venn

PENYAJIAN HIMPUNAN
ENUMERASI

Mengenumerasi artinya menuliskan semua elemen himpunan yang bersangkutan diantara dua buah tanda kurung kurawal. Biasanya suatu himpunan diberi nama dengan menggunakan huruf kapital maupun dengan menggunakan simbol – simbol lainnya.

Contoh :

Himpunan A yang berisi empat bilangan asli pertama dapat ditulis sebagai A = {1,2,3,4}.

PENYAJIAN HIMPUNAN
Simbol – simbol Baku

Terdapat sejumlah simbol baku yang biasa digunakan untuk mendefinisikan himpunan yang sering digunakan, antara lain :

P = himpunan bilangan bulat positif = {1,2,3,…}

N = himpunan bilangan alami (natural) = {1,2,…}

Z = himpunan bilangan bulat = {…,-2,-1,0,1,2,…}

Q = himpunan bilangan rasional

R = himpunan bilangan riil

C = himpunan bilangan kompleks

Kadang – kadang kita berhubungan dengan himpunan – himpunan yang semuanya merupakan bagian dari sebuah himpunan yang universal. Himpunan yang universal ini disebut semesta dan disimbolkan dengan U. Himpunan U harus diberikan secara eksplisit atau diarahkan berdasarkan pembicaraan. Sebagai contoh, misalnya U = {1,2,3,4,5} dan A adalah himpunan bagian dari U, dengan A = {1,3,5}.

PENYAJIAN HIMPUNAN
Notasi Pembentuk Himpunan

Cara lain menyajikan himpunan adalah dengan notasi pembentuk himpunan (set builder). Dengan cara penyajian ini, himpunan dinyatakan dengan menulis syarat yang harus dipenuhi oleh anggotanya.

Aturan dalam penulisan syarat keanggotaan :

Bagian di kiri tanda “ I “ melambangkan elemen himpunan
Tanda “ I “ dibaca dimana atau sedemikian sehingga
Bagian dikanan tanda “ I “ menunjukan syarat keanggotaan himpunan
Setiap tanda ‘,’ di dalam syarat keanggotaan dibaca sebagai dan

Contoh :

A adalah himpunan bilangan bulat positif yang kecil dari 5, dinyatakan sebagai

A = { x I x adalah himpunan bilangan bulat positif lebih kecil dari 5 }

Atau dalam notasi yang lebih ringkas :

A = { x I x Є P, x < 5 }

Yang ekivalen dengan A = { 1,2,3,4}

Notasi : { x I syarat yang harus dipenuhi oleh x }

PENYAJIAN HIMPUNAN
Diagram Venn

Diagram Venn menyajikan himpunan secara grafis. Cara penyajian himpunan ini diperkenalkan oleh matematikawan Inggris yang bernama John Venn pada tahun 1881. Di dalam diagram Venn, himpunan semesta ( U ) digambarkan sebagai suatu segi empat sedangkan himpunan yang lainnya digambarkan sebagai lingkaran didalam segi empat tersebut.

Contoh :

Misalkan U = {1,2,…,7,8}, A = {1,2,3,5} dan B = {2,5,6,8}. Ketiga himpunan tersebut di gambarkan dengan diagram Venn.

KARDINALITAS

Jumlah elemen dalam suatu himpunan yang elemen – elemennya berhingga.

Contoh :

B = { x I x merupakan bilangan prima yang lebih kecil dari 20 }, maka I B I = 8, dengan elemen-elemen B adalah 2,3,5,7,11,13,17,19

Notasi : n (A) atau I A I

HIMPUNAN KOSONG

Himpunan yang tidak memiliki satupun elemen atau himpunan dengan kardinal = 0 disebut himpunan kososng (null set ).

Contoh :

A = { } → │A │ = 0

A = {0} → │A │ = 1

A = {Ø }→ │A │ = 1

A = { {1,2} } → │A │ = 1

A = Ø → │A │ = 0

Notasi : Ø atau { }

HIMPUNAN BAGIAN ( subset )

Sebuah himpunan dapat merupakan bagian dari himpunan lain. Anggota yang dikandung pada himpunan tersebut juga terkandung pada himpunan yang lain.

Dalam diagram Venn untuk A C B :

Contoh :

{1,2,3} C {1,2,3,4,5}

Notasi : A C B

HIMPUNAN YANG SAMA

Dua buah himpunan mungkin saja sama, yaitu semua anggota pada kedua himpunan tersebut sama, meskipun urutannya didalam himpunan tidak sama. Kita mendefinisikan kesamaan dan dua buah himpunan melalui definisi berikut :

Definisi :

Himpunan A dikatakan sama dengan himpunan B jika dan hanya jika setiap elemen A merupakan elemen B dan sebaliknya setiap elemen B merupakan elemen A. Dengan katalain, A sama dengan B jika A adalah himpunan bagian dari B dan B adalah himpunan bagian dari A, Jika tidak demikian maka kita katakan A tidak sama dengan B.

Notasi : A = B A C B dan B C A

HIMPUNAN YANG SAMA

Tiga hal yang perlu dicatat dalam memeriksa kesamaan dua buah himpunan :

Urutan elemen di dalam himpunan tidak penting

Jadi, {1,2,3} = {3,2,1} = {1,3,2}

Pengulangan elemen tidak mempengaruhi kesamaan dua buah himpunan

Jadi, {1,1,1,1} = {1,1} = {1}

{1,2,3} = {1,2,1,3,2,1}

Untuk tiga buah himpunan A,B,dan C berlaku aksioma berikut :

A = A, B = B, dan C = C
Jika A = B, maka B = A
Jika A = B dan B = C, maka A= C

HIMPUNAN yang EKIVALEN

Dua buah himpunan dapat mempunyai kardinal yang sama meskipun anggota kedua himpunan tersebut tidak sama. Kita katakan kedua himpunan tersebut ekivalen.

Himpunan A dikatakan ekivalen dengan himpunan B jika dan hanya jika kardinal dari kedua himpunan tersebut sama.

Contoh :

Jika A = {1,3,5,7} dan B = {a,b,c,d}, maka A ~ B sebab

I A I = I B I = 4

Notasi : A ~ B I A I = I B I

HIMPUNAN SALING LEPAS

Dua buah himpunan mungkin saja tidak memiliki anggota yang sama satu buah pun. Kedua himpunan tersebut dikatakan saling lepas (disjoint).

Dua himpunan A dan B dikatakan saling lepas jika keduanya tidak memiliki elemen yang sama.

Diagram Venn yang menggambarkan dua himpunan yang saling lepas.

Contoh :

Jika A = {x I x ε P, x < 8} dan B = {10,20,30,…}, maka A // B

Notasi : A // B

HIMPUNAN KUASA

Satu terminologi yang banyak ditemui dalam literatur ilmu komputer adalah himpunan kuasa (power set). Himpunan kuasa dari suatu himpunan mempunyai elemen yang merupakan semua himpunan bagian dari himpunan yang dimaksud.

Himpunan kuasa (power set) dari himpunan A adalah suatu himpunan yang elemenya merupakan semua himpunan bagian dari A, termasuk himpunan kosong dan himpunan A sendiri.

Contoh :

Jika A = {1,2}, maka P (A) = { Ø, {1}, {2}, {1,2}}

Notasi = P (A) atau 2ª

OPERASI TERHADAP HIMPUNAN

Terhadap dua buah himpunan atau lebih, kita dapat melakukan operasi untuk menghasilkan himpunan lain. Jenis operasi yang lazim digunakan terhadap himpunan adalah operasi irisan (intersection), gabungan (union), komplemen, selisih (difference), perkalian kartesian (cartesian product), dan beda setangkup (symmetric difference).

IRISAN (intersection)

Irisan (intersection) dari himpunan A dan B adalah himpunan yang setiap elemennya merupakan elemen dari himpunan A dan himpunan B.

Diagram Venn untuk A ∩ B :

Notasi : A ∩ B = { x I x Є A dan x Є B }

U
A
B
A ∩ B

GABUNGAN (union)

Gabungan (union) dari himpunan A dan B adalah himpunan yang setiap anggotanya merupakan anggota himpunan A atau himpunan B.

Diagram Venn untuk A U B daerah warna kuning

Notasi : A U B = { x I x Є A atau x Є B }

KOMPLEMEN (complement)

Komplemen dari suatu himpunan A terhadap suatu himpunan semesta U adalah suatu himpunan yang elemennya merupakan elemen U yang bukan elemen A.

Diagram Venn untuk Ā daerah warna biru

Notasi : Ā = { x I x Є U , x Є A }

SELISIH (difference)

Selisih dari dua himpunan A dan B adalah suatu himpunan yang elemennya merupakan elemen A dan bukan elemen B. Selisih antara A dan B dapat juga dikatakan sebagai komplemen himpunan B relatif terhadap himpunan A.

Diagram Venn untuk A – B daerah warna kuning

Notasi : A - B = { x I x Є A dan x Є B } = A ∩ B

BEDA SETANGKUP
( Symmetric Difference)

Beda setangkup dari himpunan A dan B adalah suatu himpunan yang elemennya ada pada himpunan A atau B, tetapi tidak pada keduanya.

Diagram Venn A Ө B daerah warna kuning

Notasi : A B = ( A U B ) – ( A ∩ B ) = ( A – B ) U ( B – A )

PERKALIAN KARTESIAN
(cartesian product)

Perkalian kartesian dari himpunan A dan B adalah himpunan yang elemennya semua pasangan berurutan (ordered pairs) yang mungkin terbentuk dengan komponen pertama dari himpunan A dan komponen kedua dari himpunan B.

Contoh :

Misalkan C = {1,2,3} dan D = {a,b}, maka perkalian kartesian C dan D adalah

C X D = { (1,a),(1,b),(2,a),(2,b),(3,a),(3,b) }

Notasi : A X B = { (a , b) │a Є A dan b Є B}

PERKAL IAN KARTESIAN
(cartesian product)

Catatlah bahwa :

Jika A dan B merupakan himpunan berhingga, maka : │AXB │= │A│. │B│

Pasangan berurutan (a,b) berbeda dengan (b,a), dengan kata lain (a,b) ≠ (b,a)

Perkalian kartesian tidak komutatif , yaitu A X B ≠ B X A dengan syarat A atau B tidak kosong. Pada contoh D x C = { (a,1), (a,2), (a,3), (b,1), (b,2), (b,3) } ≠ C X D

Jika A = Ø atau B = Ø, maka A X B = B X A = Ø

HUKUM – HUKUM HIMPUNAN

Jika satu atau lebih himpunan dioperasikan, maka hukum-hukum yang mengatur operasi tersebut berlaku. Hukum-hukum tersebut sekaligus merupakan sifat-sifat (properties) himpunan. Cukup banyak hukum yang terdapat pada himpunan (yang ditemukan pada sejumlah referensi), namun disini hanya mendaftarkan 11 buah hukum yang penting saja. Seperti pada logika proposisi, beberapa hukum tersebut mirip dengan hukum aljabar pada sistem bilangan riil seperti a(b + c) = ab + bc, yaitu hukum distributif, sehingga kadang – kadang hukum-hukum himpunan dinamakan juga hukum-hukum aljabar himpunan.

HUKUM – HUKUM
ALJABAR HIMPUNAN

HUKUM IDENTITAS A U Ø = A A ∩ U = A A Ø = A	HUKUM NULL DOMINASI A ∩ Ø = Ø A U U = U A A = Ø
3. HUKUM KOMPLEMEN A U Ā = U A ∩ Ā = Ø	4. HUKUM IDEMPOTEN A U A = A A ∩ A = A
5. HUKUM INVOLUSI ( Ā ) = A	6. HUKUM PENYERAPAN (ABSORPSI) A U ( A ∩ B ) = A A ∩ ( A U B ) = A
7. HUKUM KOMUTATIF A U B = B U A A ∩ B = B ∩ A A Ø = B A	8. HUKUM ASOSIATIF A U ( B U C ) = (A U B) U C A ∩ ( B ∩ C) = (A ∩ B) ∩ C A ( B C) = (A B) C
9. HUKUM DISTRIBUTIF A U ( B ∩ C ) = (A U B) ∩ (A U C) A ∩ ( B U C) = ( A ∩ B ) U ( A ∩ C)	10. HUKUM DE MORGAN A ∩ B = Ā U B A U B = Ā ∩ B
HUKUM 0 / 1 ( ATAU HUKUM KOMPLEMEN 2 ) Ø = U U = Ø

Pembuktian Pernyataan
Perihal Himpunan

Terdapat beberapa metode untuk membuktikan kebenaran suatu atau kalimat himpunan. Untuk suatu pernyataan himpunan, kita dapat membuktikannya dengan beberapa metode yang menghasilkan kesimpulan yang sama. Beberapa metode pembentukan pernyataan himpunan diantaranya yaitu :

Pembuktian dengan menggunakan diagram Venn
Pembuktian dengan menggunakan tabel keanggotaan
Pembuktian dengan menggunakan aljabar himpunan
Pembuktian dengan menggunakan definisi

ALJABAR BOOLEAN

Aljabar boolean, sebagai salah satu cabang matematika, pertama kali dikemukakan oleh seorang matematikawan Inggris, George Boole pada tahun 1854. Boole, dalam buku The Laws of Thought, memaparkan aturan – aturan dasar logika (yang dikenal sebagai logika Boolean). Aturan dasar logika ini membentuk aljabar boolean. Pada tahun 1938, Claude Shannon memperlihatkan penggunaan aljabar boolean untuk merancang rangkaian sirkuit yang menerima masukan 0 dan 1. Aljabar Boolean telah menjadi dasar teknologi komputer digital. Saat ini aljabar Boolean digunakan secara luas dalam perancangan rangkaian pensaklaran, rangkaian digital, dan rangkaian IC (integrated circuit) komputer.

HUKUM – HUKUM
ALJABAR BOOLEAN

HUKUM IDENTITAS a + 0 = a a . 1 = a	HUKUM IDEMPOTEN a + a = a a . a = a
3. HUKUM KOMPLEMEN a + a’ = 1 aa’ = 0	4. HUKUM DOMINANSI a . 0 = 0 a + 1 = 1
5. HUKUM INVOLUSI (a’)’ = a	6. HUKUM PENYERAPAN a + ab = a a ( a + b ) = a
7. HUKUM KOMUTATIF a + b = b + a ab = ba	8. HUKUM ASOSIATIF a + ( b + c ) = ( a + b ) + c a (bc) = (ab) c
9. HUKUM DISTRIBUTIF a + ( bc ) = ( a + b ) ( a + c ) a ( b + c ) = ab + ac	10. HUKUM DE MORGAN ( a + b )’ = a’ b’ ( ab )’ = a’ + b ‘
11. HUKUM 0/1 0’ = 1 1’ = 0

APLIKASI ALJABAR BOOLEAN

Aljabar boolean memiliki aplikasi yang luas dalam bidang keteknikan, antara lain :

Di bidang jaringan pensaklaran dan
Rangkaian digital.

Aplikasi Aljabar Boolean pada Jaringan Pensaklaran (Switching Network)

Saklar adalah obyek yang mempunyai dua buah status : buka dan tutup. Kita dapat mengasosiasikan setiap peubah di dalam fungsi Boolean sebagai “gerbang” (gate) dalam sebuah saluran yang dialiri listrik, air, gas, informasi atau benda lain yang mengalir. Secara fisik, gerbang ini dapat berupa keran didalam pipa hidrolik, transistor atau dioda dalam rankaian listrik, dispatcher pada alat rumah tangga, atau sembarang alat lain yang dapat melewatkan atau menghambat aliran.

Kita dapat menyatakan fungsi logika untuk gerbang yang bersesuaian. Pada fungsi tersebut, peubah komplemen menyatakan closed gate, sedangkan peubah bukan komplemen menyatakan opened gate.

Aplikasi Aljabar Boolean pada Jaringan Pensaklaran (Switching Network)

Aplikasi Aljabar Boolean pada Rangkaian
Digital Elektronik

Rangkaian digital elektronik dimodelkan dengan sejumlah gerbang logika. Ada tiga macam gerbang dasar : AND, OR, dan NOT. Rangkaian yang dibentuk oleh gerbang logika disebut rangkaian logika.

Tiga Gerbang Logika Dasar AND, OR, dan NOT

PENYERDEHANAAN
FUNGSI BOOLEAN

Terdapat tiga metode yang dapat digunakan untuk menyederhanakan fungsi Boolean :

Secara aljabar, menggunakan hukum – hukum aljabar Boolean
Metode Peta Karnaugh
Metode Quine-Mc Cluskey ( metode tabulasi

METODE PETA KARNAUGH

Metode Peta Karnaugh merupakan metode grafis untuk menyederhanakan fungsi Boolean. Metode ini ditemukan oleh Maurice Karnaugh pada tahun 1953. Peta Karnaugh adalah sebuah diagram / peta yang terbentuk dari kotak – kotak (berbentuk bujursangkar) yang bersisian. Tiap kotak merepresentasikan sebuah minterm. Tiap kotak dikatakan bertetangga jika minterm -minterm yang merepresentasikannya berbeda hanya 1 buah literal.

Peta Karnaugh dapat dibentuk dari fungsi Boolean yang dispesifikasikan dengan ekspresi Boolean maupun fungsi yang direpresentasikan dengan tabel kebenaran.

Peta Karnaugh dengan Dua Peubah

Misalkan dua peubah didalam fungsi Boolean adalah x dan y. Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah y. Baris pertama diidentifikasi nilai 0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 0 (menyatakan y’), sedangkan kolom kedua dengan 1 (menyatakan y). Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.

Tiga cara yang lazim digunakan sejumlah literatur dalam menggambarkan peta Karnaugh untuk dua peubah.

m0	m1
m2	m3

Peta Karnaugh dengan Dua Peubah

x’y’	x’y
xy’	xy

x’ y’	x’ y
x y’	x y

Penyajian 1

Penyajian 2

Penyajian 3

       y
0            1
      0
x
      1
y’              y
x’
x

Perhatikanlah bahwa dua kotak yang bertetangga hanya berbeda satu literal. Kotak x’y’ dan x’y misalnya, hanya berbeda pada literal kedua (y’ dan y ), sedangkan literal pertama sama (yaitu x). Jika minterm pada setiap kotak direpresentasikan dengan string biner, maka dua kotak yang bertetangga hanya berbeda 1 bit (contohnya 00 dan 01 pada kedua kotak tersebut hanya berbeda satu bit, yaitu pada bit kedua)

Peta Karnaugh dengan Tiga Peubah

Untuk fungsi Boolean dengan tiga peubah (misalkan x,y, dan z), jumlah kotak didalam peta Karnaugh meningkat menjadi 2³ = 8. Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah yz. Baris pertama diidentifikasi nilai 0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 00 (menyatakan x’y’), kolom kedua diidentifikasi nilai 01 (menyatakan xy’), kolom ketiga diidentifikasi nilai 11 (menyatakan xy), sedangkan kolom ke empat diidentifikasi nilai 10 (menyatakan xy’). Perhatikanlah bahwa antara satu kolom dengan kolom berikutnya hanya berbeda satu bit. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolo yang bersesuaian.

m0	m1	m3	m2
m4	m5	m7	m6

Peta Karnaugh dengan Tiga Peubah

x’y’z’	x’y’z	x’y z	x’y z’
xy’z’	xy’z	xyz	xyz’

yz
00              01          11            10
            0
     x

            1

Perhatikan urutan mi – nya. Urutan disusun sedemikian rupa sehingga setiap dua kotak yang bertetangga hanya berbeda satu bit.

Peta Karnaugh dengan Empat Peubah

Misalkan empat peubah di dalam fungsi Boolean adalah w,x,y, dan z. Jumlah kotak di dalam peta Karnaugh meningkat menjadi 2.2.2.2 (2 pangkat 4) = 16. Baris pada peta Karnaugh untuk peubah wx dan kolom untuk peubah yz. Baris pertama diidentifikasi nilai 00 (menyatakan w’x’), baris kedua dengan 01 (menyatakan w’x), baris ketiga dengan 11 (menyatakan wx) dan baris ke empat dengan 10 (menyatakan wx’). Kolom pertama diidentifikasi nilai 00 (menyatakan y’z’), kolom kedua diidentifikasi nilai 01 (menyatakan yz’), kolom ketiga diidentifikasi nilai 11 (menyatakan yz), sedangkan kolom ke empat diidentifikasi nilai 10 (menyatakan yz’). Perhatikanlah bahwa antara satu kolom dengan kolom berikutnya hanya berbeda satu bit. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.

m0	m1	m3	m2
m4	m5	m7	m6
m12	m13	m15	m14
m8	m9	m11	m10

Peta Karnaugh dengan Empat Peubah

w’x’y’z’	w’x’y’z	w’x’y z	w’x’y z’
w’x y’z’	w’x y’z	w’x y z	w’x y z’
wxy’z’	wxy’z	wxyz	wxyz’
wx’y’z’	wx’y’z	wx’yz	wx’yz’