Selasa, 25 Oktober 2011

Aljabar Boolean

Aljabar Boolean – Document Transcript

  1. 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 )  x = x’àOperasi merubah logika 1 ke 0 dan sebaliknya
  2. Aljabar Boolean halaman 2 Tabel Operasi NOT Simbol X X’ 0 1 1 0 Operasi logika AND ♦ Operasi antara dua variabel (A,B) ♦ Operasi ini akan menghasilkan logika 1, jika kedua variabel tersebut berlogika 1 Simbol Tabel operasi AND A B A.B A A.B 0 0 0 0 1 0 1 0 0 B 1 1 1 Operasi logika OR Operasi antara 2 variabel (A,B) Operasi ini akan menghasilkan logika 0, jika kedua variabel tersebut berlogika 0. Simbol Tabel Operasi OR A A+B A B A+B 0 0 0 0 1 1 B 1 0 1 1 1 1 Operasi logika NOR Operasi ini merupakan operasi OR dan NOT, keluarannya merupakan keluaran operasi OR yang di inverter. Simbol Tabel Operasi NOR A A+B ( A + B )’ A B ( A + B)’ 0 0 1 0 1 0 B 1 0 0 1 1 0
  3. Aljabar Boolean halaman 3 Atau A ( A + B )’ B Operasi logika NAND Operasi logika ini merupakan gabungan operasi AND dan NOT, Keluarannya merupakan keluaran gerbang AND yang di inverter. Simbol Tabel Operasi NAND A A.B ( A . B )’ A B ( A . B)’ 0 0 1 0 1 1 B 1 0 1 1 1 0 Atau A ( A . B )’ B Operasi logika EXOR akan menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah ganjil. Simbol Tabel Operasi EXOR A Y A B A+B 0 0 0 0 1 1 B 1 0 1 1 1 0 Operasi logika EXNOR Operasi ini akan menghasilkan keluaran ‘1’ jika jumlah masukan yang bernilai ‘1’ berjumlah genap atau tidak ada sama sekali.
  4. Aljabar Boolean halaman 4 Simbol Tabel Operasi EXNOR A Y A B A+B 0 0 1 0 1 0 B 1 0 0 1 1 1 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 6. HK. IDENTITAS A+B=B+A A+A=A A. B=B .A A .A=A 2. HK. ASSOSIATIF 7. (A+B)+C = A+(B+C) 0 + A = A —– 1. A = A (A.B) . C = A . (B.C) 1 + A = 1 —– 0 . A = 0 3. HK. DISTRIBUTIF 8. A . (B+C) = A.B + A.C A’ + A = 1 A + (B.C) = (A+B) . (A+C) A’ . A =0 4. HK. NEGASI 9. ( A’ ) = A’ A + A’ . B = A + B (A’)’ = A A . (A + B)= A . B 5. HK. ABRSORPSI 10. DE MORGAN’S A+ A.B = A ( A+ B )’ = A’ . B’ A.(A+B) = A ( 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
  5. Aljabar Boolean halaman 5 2. A B X X = (A.B)’ . B = (A’ + B’) . B = ( A.B )’ + B’.B = ( A.B )’ + 0 = A’.B A B X = A’.B ATAU A X = A’.B B
  6. Aljabar Boolean halaman 6 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. Komplemen1: (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: 1
  7. Aljabar Boolean halaman 7 – B = {0, 1} – operator biner, + dan ⋅ – operator uner, ’ – Kaidah untuk operator biner dan operator uner: a B a⋅b a b a+b a a’ 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 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). 5. 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.
  8. Aljabar Boolean halaman 8 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
  9. Aljabar Boolean halaman 9 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: 2. Hukum idempoten: (i) a+0=a (i) a + a = a (ii) a ⋅ 1 = a (ii) a ⋅ a = a 3. Hukum komplemen: 4. Hukum dominansi: (i) a + a’ = 1 (i) a⋅0 =0 (ii) aa’ = 0 (ii) a + 1 = 1 5. Hukum involusi: 6. Hukum penyerapan: (i) (a’)’ = a (i) a + ab = a (ii) a(a + b) = a 7. Hukum komutatif: 8. Hukum asosiatif: (i) a+b=b+a (i) a + (b + c) = (a + b) + c (ii) ab = ba (ii) a (b c) = (a b) c 9. Hukum distributif: 10. Hukum De Morgan: (i) a + (b c) = (a + b) (a + c) (i) (a + b)’ = a’b’ (ii) a (b + c) = a b + a c (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
  10. Aljabar Boolean halaman 10 • 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 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 Komplemen Fungsi 1. Cara pertama: menggunakan hukum De Morgan Hukum De Morgan untuk dua buah peubah, x1 dan x2, adalah
  11. Aljabar Boolean halaman 11 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 x x xy x+ y x x’ y y Gerbang AND Gerbang OR Gerbang NOT (inverter) Contoh. Nyatakan fungsi f(x, y, z) = xy + x’y ke dalam rangkaian logika. Jawab: (a) Cara pertama x xy y xy+x’y x’ x x’y y (b) Cara kedua x xy y x y+x ‘y x’ x ‘y
  12. Aljabar Boolean halaman 12 (b) Cara ketiga x y xy xy+x’y x’ x’y Gerbang turunan x x ( xy )’ x + y y y Gerbang NAND Gerbang XOR x x ( x+y )’ ( x + y )’ y y Gerbang NOR Gerbang XNOR x x x+ y ( x + y )’ ekivalen dengan ( x + y )’ y y x’ x x ‘y ‘ ekivalen dengan ( x+y )’ y’ y Penyederhanaan Fungsi Boolean Contoh. f(x, y) = x’y + xy’ + y’ x’ x x ‘+ y ‘ ekivalen dengan ( xy )’ y’ y
  13. Aljabar Boolean halaman 13 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 : www.Google.com
Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)