DEFINISI ALJABAR BOOLEAN
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:
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. Komplemen1:
(i) a + a’ = 1
(ii) a ⋅ a’ = 0
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
operatorbiner
4. Distributif:
(i) a ⋅
(b + c) = (a ⋅ b) + (a ⋅
c) dapat ditunjukkan benar dari tabel operator biner di atas dengan
membentuk tabel kebenaran:
(ii) Hukum
distributif a + (b ⋅ c) = (a + b)
⋅
(a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran
dengancara yang sama seperti (i).
5. Komplemen:
(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 bahwaB = {0, 1} bersama-sama dengan
operator biner + dan ⋅operator
komplemen ‘ merupakan aljabar Boolean
EKSPRESI BOOLEAN
o
Misalkan (B, +, ⋅, ’)
adalah sebuah aljabar Boolean. Suatuekspresi 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
a + b
a ⋅ b
a’⋅ (b +
c)
a ⋅ b’ + a ⋅
b ⋅ c’ + b’, dan sebagainya
o
Dua ekspresi Boolean dikatakan ekivalen(dilambangkan dengan
‘=’) jika keduanya mempunyai nilai yang sama untuksetiap pemberian nilai-nilai
kepada n peubah. Contoh:
a ⋅ (b + c) = (a . b)
+ (a ⋅ c)
HUKUM-HUKUM ALJABAR BOOLEAN
FUNGSI BOOLEAN
Fungsi
Boolean(disebut juga fungsi biner) adalah pemetaandari Bn ke Bmelalui
ekspresi Boolean, kita menuliskannyasebagai f : Bn → B yang
dalam hal ini Bnadalah himpunan yang beranggotakanpasangan terurut
ganda-n (ordered n-tuple) di dalam daerah asal B.
Setiap ekspresi Boolean tidak lain merupakan fungsiBoolean.
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 .
BENTUK KANONIK
Ada dua macam bentuk
kanonik:
1. Penjumlahan dari
hasil kali (sum-of-product atau SOP)
2. Perkalian dari
hasil jumlah (product-of-sum atau POS)
Contoh:
1. f(x,
y, z) = x’y’z + xy’z’ + xyz
→ SOP Setiap suku (term) disebut minterm
2. g(x,
y, z) = (x + y + z)(x + y’ + z)(x
+ y’ + z’) (x’ + y + z’)(x’ + y’
+ z) → POS Setiap suku (term) disebut maxterm
Setiap minterm/maxterm mengandung
literal lengkap
Contoh :
Nyatakan tabel kebenaran di
bawah ini dalam bentuk kanonik SOP dan POS.
Penyelesaian:
(a) SOP
Kombinasi nilai-nilai peubah yang
menghasilkan nilai fungsisama dengan 1 adalah 001, 100, dan 111, maka
fungsiBooleannya dalam bentuk kanonik SOP adalah
f(x,
y, z) = x’y’z + xy’z’ + xyz
atau
(dengan
menggunakan lambang minterm), f(x, y, z) = m1
+ m4 + m7 = Σ (1, 4, 7)
(b) POS
Kombinasi nilai-nilai peubah yang
menghasilkan nilai fungsisama dengan 0 adalah 000, 010, 011, 101, dan 110,
makafungsi Booleannya dalam bentuk kanonik POS adalah
f(x, y, z)
= (x + y + z)(x + y’+ z)(x + y’+
z’) (x’+ y + z’)(x’+ y’+ z)
atau dalam bentuk lain,
f(x, y, z) = M0
M2 M3 M5 M6 = Π(0, 2, 3, 5, 6)
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.
PenyederhanaanSecaraAljabar
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
2.PetaKarnaugh
a. Peta Karnaugh dengan
dua peubah
b. Peta dengan tiga peubah
c. Peta dengan empat peubah
