Definisi dan Aksioma Aljabar Boolean
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. Untuk download materi ini, klik iniMateri Aksioma Aljabar Boolean (docx) dan Materi Aksioma Aljabar Boolean (ppt)
Logging you in...
0 comments:
Post a Comment
Tim Gudang Materi mengharapkan komentar anda sebagai kritik dan saran untuk kami .. Hubungi kami jika anda mengalami kesulitan !