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
LOGIKA :
Memberikan batasan yang pasti dari suatu
keadaan, sehingga suatu keadaan tidak dapat berada dalam dua ketentuan
sekaligus.
Dalam
logika dikenal aturan sbb :
¨
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’
Operasi-operasi dasar logika dan gerbang
logika :
Pengertian GERBANG (GATE) :
¨
Rangkaian satu atau lebih sinyal masukan
tetapi hanya menghasilkan satu sinyal keluaran.
¨
Rangkaian digital (dua keadaan), karena
sinyal masukan atau keluaran hanya berupa tegangan tinggi atau low ( 1 atau 0
).
¨
Setiap keluarannya tergantung sepenuhnya
pada sinyal yang diberikan pada masukan-masukannya.
Operasi logika NOT ( Invers
)
Operasi merubah logika 1 ke 0 dan
sebaliknya à x = x’
Tabel Operasi NOT
X
|
X’
|
0
|
1
|
1
|
0
|
Operasi logika AND
¨
Operasi antara dua
variabel (A,B)
¨
Operasi ini akan
menghasilkan logika 1, jika kedua variabel tersebut berlogika 1
Tabel operasi AND
A B A
. B
0 0 0
0 1 0
1 0 0
1 1 1
Operasi logika OR
Operasi
antara 2 variabel (A,B)
Operasi
ini akan menghasilkan logika 0, jika kedua variabel tersebut berlogika 0.
Simbol
Tabel Operasi OR
Tabel Operasi OR
A B A
+ B
0 0 0
0 1 1
1 0 1
1 1
1
Operasi logika NOR
Operasi
ini merupakan operasi OR dan NOT, keluarannya merupakan keluaran operasi OR
yang di inverter.
Simbol Tabel
Operasi NOR
A B ( A + B)’
0 0 1
0 1 0
1 0 0
1 1 0
Operasi logika NAND
Operasi
logika ini merupakan gabungan operasi AND dan NOT, Keluarannya merupakan
keluaran gerbang AND yang di inverter.
Tabel
Operasi NAND
A B ( A . B)’
0 0 1
0 1 1
1 0 1
1 1 0
Operasi logika EXOR
akan
menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah
ganjil.
Tabel
Operasi EXOR
A B A
+ B
0 0 0
0 1 1
1 0 1
1 1
0
Operasi logika EXNOR
Operasi
ini akan menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’
berjumlah genap atau tidak ada sama sekali.
Tabel
Operasi EXNOR
A B A
+ B
0 0 1
0 1 0
1 0 0
1 1 1
DALIL BOOLEAN ;
1.
X=0 ATAU X=1
2.
0 . 0 = 0
3.
1 + 1 = 1
4.
0 + 0 = 0
5.
1 . 1 =
1
6.
1 . 0 = 0 . 1 = 0
7.
1 + 0 = 0 + 1 = 0
TEOREMA
BOOLEAN
1.
HK. KOMUTATIF
A
+ B = B + A
A
. B = B . A
|
6.
HK. IDENTITAS
A
+ A = A
A . A = A
|
2.
HK. ASSOSIATIF
(A+B)+C
= A+(B+C)
(A.B)
. C = A . (B.C)
|
7.
0
+ A = A ----- 1. A = A
1
+ A = 1 ----- 0 . A = 0
|
3.
HK. DISTRIBUTIF
A
. (B+C) = A.B + A.C
A
+ (B.C) = (A+B) . (A+C)
|
8.
A’
+ A = 1
A’
. A
=0
|
4.
HK. NEGASI
(
A’ ) = A’
(A’)’ = A
|
9.
A
+ A’ . B = A + B
A
. (A + B)= A . B
|
5.
HK. ABRSORPSI
A+
A.B = A
A.(A+B)
= A
|
10.
DE MORGAN’S
(
A+ B )’ = A’ . B’
(
A . B )’ = A’ + B’
|
CONTOH
:
1.
A +
A . B’ + A’ . B = A . ( 1 + B’ ) + A’ .
B
= A . 1 + A’ . B
=
A + A’ . B
=
A + B
2. X
= (A.B)’ . B = (A’ + B’) . B
= ( A.B )’
+ B’.B
= ( A.B )’
+ 0
= A’.B
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)
5. Komplemen[1]: (i) a + a’
= 1
(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.
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.
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 e1
dan 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 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:
(i) a(b
+ c) = ab + ac
(ii)
a
+ bc = (a + b) (a + c)
(iii)
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
×
dengan +
+
dengan ×
0 dengan
1
1
dengan 0
dan membiarkan operator komplemen tetap apa
adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S.
Contoh.
(i) (a ×
1)(0 + a’) = 0 dualnya (a + 0) + (1 × a’) = 1
(ii) a(a‘ + b) = ab dualnya a + a‘b = a
+ b
Hukum-hukum Aljabar Boolean
1. 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) aa’
= 0
|
4. Hukum
dominansi:
(i) a × 0 = 0
(ii) a
+ 1 = 1
|
5. Hukum
involusi:
(i) (a’)’ = a
|
6. Hukum
penyerapan:
(i) a + ab = a
(ii) a(a + b) = a
|
7. Hukum
komutatif:
(i) a + b = b + a
(ii) ab
= ba
|
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)
(ab)’ = a’ + b’
|
11.
Hukum 0/1
(i)
0’ = 1
(ii) 1’ = 0
|
Contoh 7.3. 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)
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-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
|
Komplemen
Fungsi
1. Cara pertama: menggunakan hukum De Morgan
Hukum De Morgan untuk dua buah peubah, x1 dan x2, adalah
Contoh. Misalkan f(x, y, z) = x(y’z’ + yz),
maka
f ’(x,
y, z) = (x(y’z’ + yz))’
=
x’ + (y’z’ + yz)’
=
x’ + (y’z’)’ (yz)’
= x’
+ (y + z) (y’ + z’)
Tidak ada komentar:
Posting Komentar