ALJABAR BOOLEAN

7.1 Definisi Aljabar Boolean

Aljabar Boolean dapat didefinisikan secara abstrak dalam beberapa cara. Cara yang paling
umum adalah dengan menspesifikasikan unsur-unsur pembentuknya dan operasi-operasi
yang menyertainya, seperti pada definisi 7.1 berikut:
Definisi 7.1 Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan

, dan sebuah operator uner, . Misalkan 0 dan 1 adalah dua elemen yang berbeda dari

B. Maka tupel ( B, +, , )
Disebut aljabar Boolean jika untuk setiap a, b, c

B berlaku aksioma-aksioma atau

ponstulat berikut:
1. Closure : (i) a + b B (artinya, hasil operasi + tetap berada didalam B)
(ii) a b B
(artinya, hasil operasi . tetap berada didalam 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)
5. Komplemen : untuk setiap a B terdapat elemen unik a B sehingga
(i)
a + a = 1
(ii)
a a = 0
keenam aksioma diatas diformulasikan secara formal oleh E. V. Huntington pada tahun
1904, sehingga keenam aksioma tersebut dinamakan juga Ponstulat Huntington.
Elemen 0 dan 1 adalah dua elemen unik yang didalam B. Kedua elemen unik dapat berbedabeda pada beberapa aljabar Boolean (misalnya

dan U pada himpunan F dan T pada

proposisi), namun secara umum kita tetap menggunakan 0 dan 1 sebagai dua buah elemen
unik yang berbeda. Elemen 0 disebut elemen zero sedangkan elemen 1 disebut elemen unit.
Operator + disebut operator penjumlahan,

disebut operator perkalian, dan disebut

operator komplemen.
Terdapat perbedaan antara aljabar Boolean dengan aljabar biasa untuk aritmatika bilangan
riil:
1. Hukum distributif yang pertama, a

(b + c) = (a b) + (a c) sudah dikenal

didalam aljabar biasa, tetapi hukum distributif yang kedua,

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

(a + c), benar untuk aljabar Boolean, tetapi tidak benar untuk

aljabar biasa.
2. Aljabar Boolean tidak memiliki kebalikan perkalian (multiplicative inverse) dan
kebalikan penjumlahan. Karena itu, tidak ada operasi pembagian dan pengurangan.
3. Aksioma nomor lima mendefinisikan operator yang dinamakan komplemen yang tidak
tersedia pada aljabar biasa
4. Aljabar biasa memerlukan himpunan bilangan riil dengan elemen yang tidak berhingga
banyaknya. Sedangkan aljabar Boolean memperlakukan himpunan elemen B yang
sampai sekarang belum didefinisikan, tetapi pada aljabar Boolean dua nilai (yang
dijelaskan pada bab 7.2), B didefinisikan sebagai himpunan dengan hanya dua nilai, 0
dan 1
Hal lain yang penting adalah membedakan elemen himpunan dan peubah (variable) pada
sistem aljabar. Sebagai contoh, pada aljabar biasa, elemen himpunan bilangan riil adalah
angka, sedangkan peubah seperti a, b, c dan sebagainya. Dengan cara yang sama pada
aljabar Boolean, orang mendefinisikan elemen-elemen himpunan dan peubah seperti x, y, z
sebagai simbol-simbol yang mempresentasikan elemen.
Berhubung elemen-elemen B tidak didefinisikan nilainya (kita bebas menentukan anggotaanggota B), maka untuk mempunyai sebuah aljabar Boolean, orang harus memperlihatkan
[MAN82]:
1. Elemen- elemen himpunan B
2. Kaidah/aturan operasi untuk dua operator biner dan operator uner,
3. Himpunan B, bersama-sama dengan dua operator tersebut memenuhi ponstulat
huntington.
Jika ketiga persyaratan diatas terpenuhi, maka aljabar yang didefinisikan dapat dikatakan
sebagai aljabar Boolean.
Contoh 7.1
Misalkan B = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} adalah pembagi dari 60. Tunjukkan
cara membentuk B menjadi aljabar Boolean.
Penyelesaian:
Elemen-elemen himpunan B sudah didefinisikan. Sekarang kita tentukan kaidah operasi
untuk operator +, dan . Misalkan kita definisikan:
a + b = KPK (a,b) = kelipatan persekutuan terkecil
a b = PBB (a,b) = Pembagi bersama terbesar
a = 60/a

maka sekarang kita tunjukkan apakah B bersama-sama dengan kedua operator biner dan
operator uner memenuhi ponstulat hutington.
1. Ketertutupan (closure): jelas berlaku karena setiap operasi + dan

terhadap elemen-

elemen himpunan B selalu menghasilkan nilai yang terletak didalam B.

Misalnya:
3 + 4 = KPK (3,4) = 12
3 4 = PBB (3,4)=1
a = 60/3= 20

15+60 = KPK (15,60) = 60

15 60= PBB (15,60) = 15

dan lain-lain coba anda periksa untuk setiap elemen lainnya.

2. Identitas : 1 adalah elemen identitas untuk operasi penjumlahan dan 60 adalah elemen
identitas untuk operasi perkalian,karena :
i.
a + 1 = KPK (a,1) = a
( 1 sebagai elemen zero )
ii.
a . 60 = PBB (a,60) = a
( 60 sebagai elemen unit )
3. Komutatif : jelas berlaku karena
i.
a + b = b + a = KPK (a,b)
ii.
a . b = b . a = PBB (a,b)
4. Distributif : jelas berlaku karena (ditunjukan dengan contoh)
i.
20 . (3+5) = PBB (20,KPK (3,5) = PBB (20,15) = 5
(20.3) + (20.5) = KPK (PBB(20,3), PBB (20,5) = KPK (1,5) = 5
ii.
20 + (3.5) = KPK (20,PBB(3,5)) = KPK (20,1) =20
(20+3) . (20+5) = PBB (KPK(20,3), KPK (20,5)) = PBB (60,20) =20
5. Komplemen : jelas berlaku karena
i.
a +a = KPK (a,60/a) = 60
ii.
a. a = PBB (a,60/a) = 1
Oleh karena ponstulat Huntington dipenuhi, maka B = (1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60)
yang didefinisikan pada operator biner +, . dan operator komplemen adalah sebuah aljabar
Boolean.
Definisi 7.1 mengingatkan kita pada aljabar himpunan (Bab 3) dan aljabar proposisi (Bab 1),
karena terdapat kemiripan sifat antara kedua aljabar tersebut dengan aljabar proposisi
sebenarnya juga merupakan aljabar Boolean. Dengan kata lain, aljabar himpunan dan aljabar
proposisi adalah himpunan bagian (subset) dan aljabar Boolean.
Pada aljabar himpunan B beranggotakan himpunan bagian dari himpunan semesta U. dua
elemen unik berbeda dari B adalah

dan U, dua operasi binernya adalah

, operator unernya adalah komplemen (

dan

), dan semua aksioma yang terdapat pada

Definisi 7.1 dipenuhi oleh semua anggota B.

Sedangkan pada aljabar proposisi, B beranggotakan semua proposisi dengan n peubah. Dua
elemen unik berbeda dari B adalah T dan F, operator binernya adalah dan , operator

unernya adalah a, dan semua aksioma yang terdapat pada definisi 7.1 dipenuhi oleh semua
anggota B.
7.2 Aljabar Boolean Dua-Nilai
Mengingat B tidak ditentukan anggota-anggotanya, maka kita dapat membentuk sejumlah
tidak berhingga aljabar Boolean. Pada aljabar Boolean terhingga, banyaknya anggota B
terbatas, tetapi paling sedikit beranggotakan dua buah elemen karena menurut Definisi 7.1 di
dalam B harus terdapat dua elemen yang berbeda.
Aljabar Boolean yang terkenal dan memiliki terapan yang luas adalah aljabar Boolean duanilai (two-valued Boolean algebra). Aljabar Boolean dua-nilai didefinisikan pada sebuah
himpunan B dengan dua buah elemen 0 dan 1 (sering dianamakan bit singkatan dari binary
digit), yaitu B = {0, 1}, operator biner, + dan , operator uner, . Kaidah untuk operator biner
dan operator uner ditunjukan pada tabel 7.1, 7.2 dan 7.3 dibawah ini.
Tabel 7.1

Tabel 7.2

a.b

a+b

Tabel 7.3
a

Kita harus memperhatikan bahwa postulat Huntington benar untuk himpunan B = {0,1}
dengan dua operator biner dan satu operator uner yang didefinisikan diatas :
1. closure : jelas berlaku karena dari tabel terlihat hasil tiap operasi adalah 1.
Atau 0,1 dan 0 B.
2. identitas : jelas berlaku karena dari tabel dapat kita lihat bahwa :
i.
0+1=1+0=1
ii.
1 . 0 = 0. 1 = 0
Yang memenuhi elemen identitas 0 dan 1 seperti yang didefinisikan pada ponstulat
Huntington.
3. Komutatif : jelas berlaku dengan melihat simetri tabel operator biner.
4. Distributif :
i.
a . (b + c) = (a . b) + (a . c) dapat ditunjukan benar dari tabel operator biner diatas
dengan membentuk tabel kebenaran untuk semua nilai yang mungkin dari a, b dan c
(tabel 7.4)
Tabel 7.4
a

b+c

a . (b+c)

a.b

a.c

(a . b) + (a . c)

Oleh karena nilai-nilai pada kolom a . (b + c) sama dengan nilai-nilai pada kolom (a.b)
+ (a.c), maka kesamaan a. (b + c) = (a . b) + (a.c) adalah benar.
ii.

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

6. postulat 6 dipenuhi karena aljabar Boolean dua-nilai memiliki dua buah elemen yang
berbeda 1 dan 0 dengan 1 0.

Karena keenam postulat Huntingtion dipenuhi, maka terbukti bahwa B = (0, 1) bersamasama dengan operator biner + dan . operator komplemen merupakan aljabar Boolean.
Aljabar Boolean dua-nilai mempunyai terapan yang sangat luas dalam bidang elektronika,
khususnya pada perancangan sirkuit di dalam computer. Beberapa terapan lainnya juga
ditemukan dibidang teknik sipil, teknik mesin, dan sebagainya. Untuk selanjutnya, jika
disebut aljabar Boolean, maka aljabar Boolean yang dimaksudkan disini adalah aljabar
Boolean dua-nilai.
7.3 Ekspresi Boolean
Pada aljabar Boolean dua-nilai, B = (0,1). Kedua elemen B ini seringkali disebut elemen
biner atau bit (singkatan binary bit). Peubah (variabel) x disebut peubah. Boolean atau
peubah biner jika nilainya hanya dari B. Ekspresi Boolean dibentuk dari elemen-elemen B
dan / atau peubah-peubah yang dapat dikombinasikan satu sama lain dengan operator +. .,
dan . Secara formal, ekpresi Boolean didefinisikan secara rekursif oleh definisi 7.2
[LIU85].
Definisi 7.2 Misalkan (B, +, ., ) adalah sebuah aljabar Boolean. Suatu ekpresi Boolean
dalam (B, +, .,) adalah:
i.
ii.
iii.

setiap elemen didalam B

setiap peubah
jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 . e2, e1 adalah ekpresi Boolean.

Jadi, menurut Definisi 7.2 diatas, setiap ekspresi dibawah ini.

0
1
a
b
c
a+b
a.b
a . (b + c)
a. b + a.b.c + b, dan sebagainya
adalah ekpresi Boolean. Ekspresi Boolean yang mengandung n peubah dinamakan ekspresi
Boolean bagi n peubah.
Mengevaluasi ekspresi Boolean artinya memberikan nilai pada peubah-peubah didalam
ekspresi tersebut dengan elemen-elemen didalam B. Hasil dari evaluasi adalah sebuah nilai
yang merupakan salah satu dari anggota B. Hasil dari evaluasi adalah sebuah nilai yang
merupakan salah satu dari anggota B. Pada aljabar Boolean dua-nilai, B = (0,1) sehingga

peubah-peubah didalam ekspresi Boolean dapat diberi nilai 0 atau 1, begitu juga hasil
evaluasi ekspresi Boolean adalah 0 atau 1. Sebagai contoh, pada ekspresi Boolean dengan 3
peubah berikut:
a . (b + c)

jika a = 0, b =1, dan c = 0, maka hasil evaluasi ekspresi tersebut adalah

0 . (1 + 0) = 1.1
Dua ekspresi boolean dikatakan ekuivalen jika keduanya mempunyai nilai yang sama untuk
setiap pemberian nilai-nilai pada n peubah. Misalnya, ekspresi pada aksioma distributif yang
pertama,
a . (b + c)
ekuivalen dengan,
(a . b) + (a . c)
Sehingga kita dapat menuliskan kedua ekspresi tersebut kersamaan (identity):
a . (b + c) = (a . b) + (a . c)
keekuivalenan dua buah eksprsi dapat ditunjukkan dengan tabel kebenaran. Jika semua nilai
ekspresi ruas kiri untuk semua kemungkinan nilai-nilai peubah sama dengan nilai ekspresi
pada ruas kanan kesamaan, maka kedua ekspresi tersebut dikatakan ekuivalen. Untuk
aksioma distributif, hal ini sudah ditunjukkan pada Tabel 7.4.
Contoh 7.2
Perlihatan bahwa a+ a b = a + b.
Penyelesaian :
Tabel kebenaran untuk kesamaan a + a b = a + b ditunjukkan pada Tabel 7.5 karena nilainilai pada kolom a + a b sama dengan nilai-nilai pada kolom a+b, maka a + a b = a + b.
Tabel 7.5
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
Dalam penulisan ekspresi boolean selanjutnya, kita menggunakan perjanjian berikut : selain
menggunakan tanda kurung, operator mempunyai prioritas lebih tinggi daripada operator +
dan jadi, sebagai contoh,
a + b . c berarti a + (b . c), bukan (a . b)
a . b berarti a . (b), bukan (a . b)
untuk menyederhanakan penulisan, kita boleh tidak menuliskan notasi operasi perkalian.
Jadi, kita lebih sering menuliskan notasi a . b sebagai ab saja. Namun, kadang-kadang kita
merasa perlu menuliskan notasi untuk masuk menekankan pada operasi perkalian, misalnya

kita menuliskan a . 0 ketimbang a0. Dengan cara penyederhanaan ini, maka aksioma
distributif pada nomor 4 ditulis sebagai berikut:
(i) a(b + c) = ab + ac
(ii) a + bc =(a + b) (a + c)
Dengan cara seperti diatas,tentunya bila a + b . c ditulis sebagai a + bc maka pengertian
prioritas operator menjadi lebih jelas.