Matematika Diskrit : Aljabar Boolean

📋 Daftar Isi

Definisi Aljabar Boolean

Aljabar Boolean pertama kali dikemukakan oleh seorang matematikawan Inggris, George Boole, pada tahun 1854.

Boole melihat bahwa himpunan dan logika proposisi mempunyai sifat-sifat yang serupa. Boole memaparkan aturan-aturan dasar logika dan suatu struktur aljabar yang operasi-operasinya memenuhi aturan tertentu.

Dalam arti luas, aljabar Boole berarti suatu jenis simbol-simbol untuk memanipulasi nilai-nilai kebenaran logika secara aljabar.

Boolean pada dasarnya merupakan tipe data yang hanya terdiri dari dua nilai yaitu “True” dan “False” yang biasanya dilambangkan dengan angka “1” dan “0” pada teknologi komputer dan bahasa pemrograman.

Misalkan terdapat:

Dua operator biner (+) dan (-)
Sebuah operator uner: (’)
B : himpunan yang didefinisikan pada operator (+), (·), 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 :

Closure

a + b ϵ B
a · b ϵ B

Identitas

a + 0 = a
a · 1 = a

Komutatif

a + b = b + a
a · b = b · a

Distributif

a · (b + c) = (a · b) + (a · c)
a + (b · c) = (a + b) · (a + c)

Komplemen

a + a’ = 1
a · a’ = 0

Untuk mempunyai sebuah aljabar Boolean, harus diperlihatkan:

Elemen-elemen himpunan B
Kaidah operasi untuk operator biner dan operator uner
Memenuhi postulat Huntington

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
0	0	0
0	1	0
1	0	0
1	1	1

a	b	a + b
0	0	0
0	1	1
1	0	1
1	1	1

a	a‘
0	1
1	0

Cek apakah memenuhi postulat Huntington:

1. Closure : jelas berlaku

2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:

0 + 1 = 1 + 0 = 1
1 · 0 = 0 · 1 = 0

3. Komutatif: jelas berlaku dengan melihat simetri tabel operator biner

4. Distributif:

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

Hukum distributif a + (b · c) = (a + b) · (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti poin sebelumnya

5. Komplemen: jelas berlaku:

a + a‘ = 1, karena 0 + 0’ = 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
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.

Ekspresi Boolean

Misalkan (B, +, ·, ’) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +, ·, ’) adalah:

Setiap elemen di dalam B
Setiap peubah
Jika e₁ dan e₂ adalah ekspresi Boolean, maka (e₁ + e₂), (e₁ · e₂), e₁’ adalah ekspresi Boolean

Contoh

0
1
a
b
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 n peubah. 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:

a(b + c) = ab + ac
a + bc = (a + b) (a + c)
a · 0, bukan a0

Prinsip Dualitas

Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +, ·, dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti