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
Simbol
Tabel operasi AND 
A B A
. B
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
 |
A A + B A B A
+ B
0 0 0 
0 1 1
B 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 A + B ( A + B )’ A B
( A + B)’
0 0 1 0 1 0
B 1 0 0
1 1
0
Atau
A ( A + B )’
B
Operasi logika NAND
Operasi
logika ini merupakan gabungan operasi AND dan NOT, Keluarannya merupakan
keluaran gerbang AND yang di inverter.
Simbol Tabel
Operasi NAND
|
A A . B ( A . B )’ A B
( A . B)’
0 0 1 0 1 1
B 1 0 1
1 1
0
Atau
A ( A . B )’
B
Operasi logika EXOR
akan
menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah
ganjil.
Simbol Tabel
Operasi EXOR
|
A Y
A B A + B
0 0 0 0 1 1
B 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.
Simbol Tabel
Operasi EXNOR
|
A Y
A B A + B
0 0 1 0 1 0
B 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. A
B |
X
X = (A.B)’ . B = (A’ + B’) . B
= ( A.B )’
+ B’.B
= ( A.B )’
+ 0
= A’.B
A |
|||
 |
|||
B |
X
= A’.B
ATAU
A X = A’.B
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’)
Aplikasi
Aljabar Boolean
2.
Rangkaian Digital Elektronik
 |
 |
 |
|||
Gerbang AND Gerbang OR
Gerbang NOT (inverter)
Contoh.
Nyatakan fungsi f(x, y,
z) = xy + x’y ke dalam rangkaian logika.
Jawab:
(a) Cara pertama
 |
 |
(b) Cara kedua
 |
(b) Cara ketiga
Gerbang
turunan
 |
 |
||
Gerbang NAND Gerbang XOR
 |
 |
||
Gerbang NOR Gerbang XNOR
 |
 |
Penyederhanaan
Fungsi Boolean
Contoh. f(x,
y) = x’y + xy’ + y’
 |
disederhanakan
menjadi
f(x,
y) = x’ + y’
Penyederhanaan fungsi Boolean dapat
dilakukan dengan 3 cara:
1. Secara aljabar
2. Menggunakan Peta Karnaugh
3. Menggunakan metode Quine Mc
Cluskey (metode Tabulasi)
1.
Penyederhanaan Secara Aljabar
Contoh:
1. f(x, y)
= x + x’y
= (x
+ x’)(x + y)
= 1 ×
(x + y )
= x
+ y
2. f(x, y,
z) = x’y’z + x’yz + xy’
= x’z(y’
+ y) + xy’
= x’z + xz’
3. f(x, y,
z) = xy + x’z + yz = xy
+ x’z + yz(x + x’)
= xy
+ x’z + xyz + x’yz
= xy(1
+ z) + x’z(1 + y) = xy
+ x’z
Tidak ada komentar:
Posting Komentar