Bab 3 Prinsip Dan Alat Perancangan Logika
Sub Bab 3.1 Aljabar Boolean
Tupel
Gerbang turunan
Sub Bab 3.1 Aljabar Boolean
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 logika AND
¨
Operasi antara dua
variabel (A,B)
¨
Operasi ini akan
menghasilkan logika 1, jika kedua variabel tersebut berlogika 1
Operasi logika OR
Operasi
antara 2 variabel (A,B)
Operasi
ini akan menghasilkan logika 0, jika kedua variabel tersebut berlogika 0.
Operasi logika NOR
Operasi
ini merupakan operasi OR dan NOT, keluarannya merupakan keluaran operasi OR
yang di inverter.
Operasi logika NAND
Operasi
logika ini merupakan gabungan operasi AND dan NOT, Keluarannya merupakan
keluaran gerbang AND yang di inverter.
Operasi logika EXOR
akan
menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah
ganjil.
Operasi logika EXNOR
Operasi
ini akan menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’
berjumlah genap atau tidak ada sama sekali.
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
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).
1. 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
Contoh.
Nyatakan fungsi f(x, y,
z) = xy + x’y ke dalam rangkaian logika.
Gerbang turunan
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
Sumber: