9. Aljabar Boole Aljabar Boolean menyediakan operasi dan aturan untuk bekerja dengan himpunan {0, 1}. Akan dibahas 3 buah operasi : •
komplemen Boolean,
•
penjumlahan Boolean , dan
•
perkalian Boolean
Komplemen Boolean dituliskan dengan bar/garis atas dengan aturan sebagai berikut
0 = 1 dan 1 = 0 Penjumlahan Boolean dituliskan dengan + atau OR, mempunyai aturan sbb :
1 + 1 = 1,
1 + 0 = 1,
0 + 1 = 1,
0+0=0
Sedangkan perkalian Boolean yang dituliskan dengan “⋅” atau AND, mempunyai aturan sbb: 1 ⋅ 1 = 1,
1 ⋅ 0 = 0,
0 ⋅ 1 = 0,
0⋅0=0
Definisi. Misalkan B = {0, 1}. Suatu variabel x disebut sebagai variabel Boolean jika hanya memiliki nilai dari B. Fungsi dari Bn, yaitu himpunan {(x1, x2, …, xn) | xi∈B,1 ≤ i ≤ n}, B
disebut sebagai fungsi Boolean berderajat n.
Fungsi Boolean dapat dinyatakakan dengan ekspresi yang dibentuk dari variabel dan operasi Boolean. Ekspresi Boolean dengan variabel x1, x2, …, xn didefinisikan secara rekursif sebagai berikut: •
0, 1, x1, x2, …, xn adalah ekspresi Boolean.
•
Jika E1 dan E1 ekspresi Boolean, maka E1 , (E1⋅ E2), dan (E1 + E2) adalah ekspresi Boolean.
Setiap ekspresi Boolean menyatakan fungsi Boolean. Nilai fungsi ini diperoleh dengan menggantikan 0 dan 1 pada variabel di dalam ekspresi. Kita bisa membuat ekspresi Boolean
9. Aljabar Boole- 1
dalam variabel x, y, dan z dengan bangunan dasarnya 0, 1, x, y, dan z, dengan aturan konstruksi: Karena x dan y ekspresi Boolean, maka x⋅y juga ekspresi Boolean. Karena z ekspresi Boolean, maka z juga ekspresi Boolean. Karena xy dan z ekspresi Boolean, maka x⋅y + z juga ekspresi Boolean. … dst… Contoh 9.1: Buatlah ekspresi Boolean untuk fungsi Boolean F(x, y) seperti yang didefinisikan oleh tabel berikut: x 0 0 1 1
F(x,y) 0 1 0 0
y 0 1 0 1
Ekspresi yang mungkin adalah F ( x, y ) = x ⋅ y
Contoh 9.2: Buatlah ekspresi Booleannya x 0 0 0 0 1 1 1 1
y 0 0 1 1 0 0 1 1
z 0 1 0 1 0 1 0 1
F(x,y,z) 1 1 0 0 1 0 0 0
Solusi-1:
F ( x, y, z ) = ( x ⋅ z + y ) Solusi-2: F ( x, y , z ) = x ⋅ z y
( )
Ada suatu metoda sederhana untuk menurunkan ekspresi Boolean dari fungsi yang didefinisikan dengan tabel. Metoda ini didasarkan pada minterms.
Definisi. Suatu literal adalah variabel Boolean atau komplemennya. Minterm dari variabel Boolean x1, x2, …, xn adalah perkalian Boolean y1⋅ y2⋅ … ⋅ yn, dimana yi = xi atau yi = xi .
Kita amati lagi tabel pada contoh 9.2 x 0 0 0 0 1
y 0 0 1 1 0
z 0 1 0 1 0
F(x,y,z) 1 1 0 0 1
F(x, y, z) = 1 jika dan hanya jika : x = y = z = 0 atau x = y = 0, z = 1 atau x = 1, y = z = 0
9. Aljabar Boole- 2
1 1 1
0 1 1
1 0 1
0 0 0
Sehingga F ( x, y , z ) = x ⋅ y ⋅ z + x ⋅ y ⋅ z + x ⋅ y ⋅ z
Definisi. Fungsi Boolean F dan G dari variabel n adalah sama jika dan hanya jika F(b1, b2, …, bn) = G(b1, b2 , …, bn) untuk b1, b2, …, bn anggota B. Dua ekspresi Boolean berbeda yang merepresentasikan fungsi yang sama disebut ekivalen. Misalnya, ekspresi Boolean xy, xy + 0, dan xy⋅1 adalah ekivalen. Komplemen dari fungsi Boolean F adalah fungsi F , dimana F( b1,b2,...,bn) =F( b1,b2,...,bn) .
Misalkan F dan G adalah fungsi Boolean berderajat n. Penjumlahan Boolean F + G dan perkalian Boolean FG didefinisikan sebagai:
( F+G)(b1,b2,...,bn) =F(b1,b2,...,bn) +Gb ( 1,b2,...,bn) ( F⋅G)(b1,b2,...,bn) =F(b1,b2,...,bn) ⋅Gb ( 1,b2,...,bn) Contoh 9.3: Ada berapa banyak fungsi Boolean berderajat 1? Jawab: Ada 4 yaitu F1, F2, F3, dan F4 sbb F1 0 0
x 0 1
F2 0 1
F3 1 0
F4 1 1
Contoh 9.3: Ada berapa banyak fungsi Boolean berderajat 2? Jawab: Ada 16 yaitu F1, F2, F3, …, dan F16 sbb x 0 0 1 1
y 0 1 0 1
F1 0 0 0 0
F2 0 0 0 1
F3 0 0 1 0
F4 0 0 1 1
F5 0 1 0 0
F6 0 1 0 1
F7 0 1 1 0
F8 0 1 1 1
F9 1 0 0 0
F10 F11 F12 F13 F14 F15 F16 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1
Pertanyaan: Ada berapa banyak fungsi boolean berderajat n yang berbeda?
9. Aljabar Boole- 3
Solusi: Ada 2n n-tupel berbeda dari 0 dan 1. Fungsi Boolean adalah penggantian 0 atau 1 pada masing-masing
n
2n n-tupel yang berbeda. Sehingga, ada 22 fungsi Boolean yang
berbeda.
Dual dari ekspresi Boolean didapat dengan menukarkan penjumlahan dengan perkalian dan menukarkan 0 dengan 1 . Contoh : •
Dual dari x(y + z) adalah x+y⋅z
•
Dual dari x ⋅1 + ( y + z ) adalah ( x + 0 )( y ⋅ z )
Definisi. Aljabar Boole adalah himpunan B dengan dua operasi biner “∨” dan “∧”, elemen 0 dan 1, dan satu operasi uner yakni komplemen dengam sifat yang berlaku untuk seluruh x, y, dan z dalam B sebagai berikut: x ∨ 0 = x dan x ∧ 1 = x
(Hk. identitas)
x ∨ x = 1 dan x ∧ x = 0
(Hk. dominasi)
(x ∨ y) ∨ z = x ∨ (y ∨ z) dan (x ∧ y) ∧ z = x ∧ (y ∧ z
(Hk. asosiatif)
x ∨ y = y ∨ x dan x ∧ y = y ∧ x
(Hk. komutatif)
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) dan x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
(Hk. distributif)
Rangkaian logika didasarkan pada aljabar Boole. Ada tiga elemen dasar dari gerbang logika, yaitu:
No
Nama
1
Inverter/pembalik
2
Gerbang OR
Lambang rangkaian x
x
x
x +y
y 3
Gerbang AND
x
xy
y
9. Aljabar Boole- 4
Dengan ketiga gerbang tersebut, suatu sirkit kobinatoris sederhana bisa dibangun Sebagai contoh, sirkit dari xy + xy diberikan pada rangkaian berikut ini.
x
xy xy + xy
y
x y
x xy
9. Aljabar Boole- 5
