Aljabar boolean adalah sistem aljabar yang berisi himpunan S dengan dua operasi penjumlahan (+) dan perkalian (.) yang didefinisikan pada himpunan, sehingga setiap elemen a, b, dan c dari S mempunyai sifat-sifat atau aksioma-aksioma berikut:
Aksioma-aksioma
1. a + b C S (tertutup)
2. a.b C S (tertutup)
3. a + (b + c) = (a + b) + c (asosiatif)
4. a.(b.c) = (a.b).c (asosiatif)
5. Jika 0 C S maka untuk setiap a C S, adalah a + 0 = 0 + a = a (identitas)
6. Jika 1 C S maka untuk setiap a C S, adalah a.1 = 1.a = a (identitas)
7. a + b = b + a (komutatif)
8. a.b = b.a (komutatif)
9. a.(b + c) = a.b + a.c (distributif)
10. (a + b).c = a.c + b.c (distributif)
11. a + (b.c) = (a + b).(a + c) (distributif)
12. (a.b) + c = (a + c).(b + c) (distributif)
13. untuk setiap a C S, dan a’ C S, maka a + a’ = 1 dan a.a’ = 0
Prinsip Dualitas
Teorema 1
Untuk setiap elemen a, berlaku:
a + a = a dan a.a = a
Teorema 2
Untuk setiap elemen a, berlaku:
a + 1 = 1 dan a.0 = 0
Teorema 3
Untuk setiap elemen a dan b, berlaku:
a + a.b = a dan a(a + b) = a
(disebut hukum penyerapan)
Teorema 4
Untuk setiap elemen a dan b, berlaku:
(a.b)’ = a’ + b’ dan (a + b)’ = a’.b’
(disebut hukum de Morgan)
Teorema 5
0’ = 1 dan 1’ = 0
Teorema 6
Jika suatu aljabar Boolean berisi paling sedikit dua elemen yang berbeda, maka 0 ≠ 1
Pembuktian Rumus Dualitas
Pembuktian rumus dualitas dilakukan berdasar aksioma dan sifat dari aljabar Boolean, yaitu:
1a. Pernyataan a + a = a
Bukti:
a+a = (a+a)(1) (identitas)
= (a+a)(a+a’) (komplemen)
= a + (a.a’) (distributif)
= a + 0 (komplemen)
= a (identitas)
1b. Pernyataan: a.a = a
Bukti
a.a = a.a + 0 (identitas)
= a.a +a.a’ (komplemen)
= a (a + a’) (distribusi)
= a.1 (komplemen)
= a (identitas)
2a. Pernyataan: a + 1 = 1
Bukti
a + 1 = a + (a + a’) (komplemen)
= (a + a) + a’ (asosiatif)
= a + a’ (teorema 1a)
= 1 (komplemen)
2b. Pernyataan: a.0 = 0
Bukti
a.0 = a.(a.a’) (komplemen)
= (a.a).a’ (asosiatif)
= a.a’ (idempoten)
= 0 (komplemen)
3a. Pernyataan: a + a.b =a
Bukti
A + a.b = a.1 + a.b (identitas)
= a(1 + b) (distributif)
= a.1 (teorema 2a)
= a (identitas)
3b. Pernyataan: a.(a + b) = a
Bukti
a.(a + b) = a.a + a.b (distributif)
= a + a.b (idempoten)
= a.1 + a.b (identitas)
= a.(1 + b) (distributif)
= a.1 (teorema 2a)
= a (identitas)
4a. Pernyataan: (a.b)’ = a’ + b’
diketahui : (ab)(ab)’ = 0
diperlihatkan : (ab)(a’ + b’) = 0
Bukti
(ab)(a’ + b’) = aba’ + abb’ (distributif)
= 0.b +a.0 (komplemen)
= 0 + 0 (teorema 2b)
= 0 (identitas)
4b. Pernyataan: (a + b)’ = a’b’
diketahui : (a + b) + (a + b)’ = 1
diperlihatkan: (a + b) + a’b’ = 1
Bukti
(a+b) + a’b’ = (a+b+a’).(a+b+b’) (distributif)
= (1 + b).(a + 1) (komplemen)
= 1.1 (teorema 2a)
= 1 (identitas)
Aturan <= (lebih kecil daripada) Definisi: x dan y adalah elemen-elemen dari aljabar Boolean. Dinyatakan bahwa: x lebih kecil daripada y (x <= y) jika dan hanya jika x + y = y Teorema 7 adalah suatu bagian dari urutan Bukti Dari teorema 1: x + x = x, sehingga x <= x Jika x <= y, maka x + y = y; Jika y <= x, maka x + y = y + x = x Sehingga jika x <= y dan y <= x, maka x = y Dapat disimpulkan: x <= y dan y <= z, maka x + y = y dan y + z = z x + z = x + (y + z) = (x + y) + z = y + z = z, Sehingga x <= z Teorema 8 Jika x, y, dan z adalah elemen-elemen dari aljabar Boolean, maka <= mempunyai sifat-sifat berikut ini: i. Jika x <= y dan x <= z, maka x <= yz ii. Jika x <= y, maka x <= y + z untuk elemen z iii. Jika x <= y, maka xz + x = x atau xz <= x iv. x < = y jika dan hanya jika y’ <= x’ Bukti i. x + y = y dan x + z = z, sehingga x + yz = (x+y)(x+z) = yz ii. Jika x + y = y, maka x + (y+z) = (x+y) + z = y + z iii. Dengan hukum penyerapan, xz + x = x atau xz <= x iv. x <= y, maka x + y = y dan y’ = (x+y)’ Sehingga y’ + x’ = (x+y)’ + x’ = ((x+y)x)’ = x’ (dengan hukum penyerapan) Fungsi Boolean Definisi: Misalkan x1, x2, x3, …, xn merupakan variabel-variabel aljabar Boolean. Fungsi Boolean dengan n variabel adalah fungsi yang dapat dibentuk dari aturan-aturan berikut: 1. Fungsi konstan 2. Fungsi proyeksi 3. Fungsi komplemen 4. Fungsi gabungan Definisi 1. Fungsi konstan : f(x1, x2, x3, …, xn) = a, 2. Fungsi proyeksi : f(x1, x2, x3, …, xn) = xi, i = 1, 2, …, n 3. Fungsi komplemen: g(x1, x2, x3, …, xn) = (f(x1, x2, x3, …, xn))’ 4. Fungsi gabungan: h(x1, x2, x3, …, xn) = f(x1, x2, x3, …, xn)+ g(x1, x2, x3, …, xn) h(x1, x2, x3, …, xn) = f(x1, x2, x3, …, xn). g(x1, x2, x3, …, xn) Catatan: Fungsi identitas: fungsi proyeksi satu variabel, dimana f(x) = x Contoh Fungsi-fungsi Boolean dengan variabel x, y, dan z, dan a merupakan suatu elemen dalam aljabar Boolean: f(x) = x + x’a g(x,y) = x’y +xy’ + y’ h(x,y,z) = axy’z + yz’ + a + xy Teorema 9 Jika f adalah fungsi Boolean dengan satu variabel, maka untuk semua nilai x adalah f(x) = f(1)x +f(0)x’ Untuk kemungkinan bentuk f: Kasus 1 f adalah fungsi konstan, f(x) = a f(1)x + f(0)x’ = ax + ax’ = a(x+x’)= a.1 = a = f(x) Kasus 2 f adalah fungsi identitas f(1)x + f(0)x’ = 1x + 0x’ = x + 0 = x = f(x) Kasus 3 g(x) = (f(x))’ g(x) = (f(x))’ = (f(1)x + f(0)x’)’ = (f(1)x)’( f(0)x’)’ = ((f(1))’ + x’) + ((f(0))’ + x) = (f(1))’(f(0))’ + (f(1))’x + (f(0))’x’ + xx’ = (f(1))’(f(0))’(1) + (f(1))’x + (f(0))’x’ = (f(1))’(f(0))’(x+x’) + (f(1))’x + (f(0))’x’ = (f(1))’(f(0))’x + (f(1))’x + (f(1))’(f(0))’x’ + (f(0))’x’ = (f(1))’x + (f(0))’x’ (hukum penyerapan) = g(1)x + g(0)x’ Kasus 4 h(x) = f(x) + g(x) h(x) = f(x) + g(x) = f(1)x + f(0)x’ + g(1)x + g(0)x’ = (f(1)+g(1))x + (f(0) + g(0))x’ = h(1)x + h(0)x’ Kasus 5 k(x) = f(x)g(x) k(x) = f(x)g(x) = (f(1)x + f(0)x’)(g(1)x + g(0)x’) = f(1)g(1)xx + f(1)g(0)xx’ + f(0)g(1)x’x + f(0)g(0)x’x’ = f(1)g(1)x + f(0)g(0)x’ = k(1)x + k(0)x’ Bentuk Kanonik Fungsi Boolean Satu variabel f(x) = f(1)x +f(0)x’ Dua variabel f(x,y) = f(1,1)xy + f(1,0)xy’ + f(0,1)x’y + f(0,0)x’y’ Terima kasih , telah membaca materi saya ini. Ada baiknya mencantumkan nama blog saya insebagai sumber referensi
Tidak ada komentar:
Posting Komentar