ALJABAR BOOLE

Posted: Januari 13, 2010 in Logika Matematika

Pengantar

Adalah suatu jenis simbol-simbol untuk memanipulasi nilai-nilai kebenaran logika secara aljabar.

ALJABAR BOOLE sebagai suatu struktur aljabar

secara umum, aljabar boole didefinisikan sebagai suatu himpunan dengan operasi v, Λ, dan ~ (atau ‘ ) serta elemen 0 dan 1, ditulis sebagai (B,v,Λ,~,0,1) atau (B,v,Λ,’,0,1).


Hukum-hukum yang berlaku pada Aljabar Boole

Hukum Komutatif

a. x v y = y v x

b. x Λ y = y Λ x

Hukum Assosiatif

a. (x v y) v z = x v (y v z)

b. (x Λ y) Λ z = x Λ (y Λ z)

Hukum Distributif

a. x v (y Λ z) = (x v y) Λ (x v z)

b. x Λ (y v z) = (x Λ y) v (x Λ z)

Hukum Identitas

a. x v 0 = x

b. x Λ 1 = x

Hukum Negasi (komplemen)

a. x v x’ = 1

b. x Λ x’ = 0

Kadang-kadang dalam simbol “v” ditulis “+” dan “Λ”ditulis sebagai “*” atau tidak ditulis sama sekali.

Simbol-simbol logika (p,q,r,…) dan operasi-operasi dan (Λ), atau (v), negasi (~) serta elemen F (false) dan T (true), adalah merupakan struktur aljabar.

Jika elemen 0 disubtitusi dengan F dan 1 disubstitusi dengan T, maka syarat-syarat aljabar Boole dapat dipenuhi, karena syarat-syarat terebut tidak lain adalah hukum ekuivalensi logika.

Aturan-aturan aljabar boole yang diturunkan dari

theorema, diketahui aljabar Boole (B,v,Λ,~,0,1) dan

x, y, x’, y’ B, maka berlaku hukum-hukum ini :

Hukum Idmpoten

a. x v x = x

b. x Λ x = x

Hukum Ikatan

a. x v 1 = 1

b. x Λ 0 = 0

Hukum Absorbsi

a. (x Λ y) v x = x

b. (x v y) Λ x = x

Hukum de Morgan

a. (x v y)’ = x’ Λ y’

b. (x Λ y)’ = x’ v y’

FUNGSI BOOLEAN

Misal B = (B,v,Λ,~,0,1) adalah aljabar Boole

Suatu fungsi Boole n variable adalah fungsi f :

Fungsi Boolean disebut sederhana jika B = {0,1}.

Jadi f : , masukannya adalah dan

keluaran fungsi adalah {0,1}.

Operasi Not, And (dan), Or (atau) dalam logika

dapat dipandang sebagai fungsi boolean.

Fungsi NOT : {0,1} → {0,1}, didefinisikan sebagai:

0 , jika x = 1

Not (x) =

1 , jika x = 0

Fungsi ini biasa ditulis ~(x)

Fungsi AND : didefinisikan sebagai :

1 , jika x = y = 1

And (x,y) =

0 , jika x dan y yang lainnya

Fungsi OR : didefinisikan sebagai :

0 , jika x = y = 0

Or (x,y) =

1 , untuk x dan y yang lainnya

Fungsi XOR : didefinisikan sebagai :

0 , jika p = q

XOR (x,y) =

1 , jika p ≠ q

Penjelasan XOR :

Penghubung XOR (simbol ) mirip dengan penghubung “atau”. Akan tetapi, jika kedua kalimat penyusunnya benar, maka hasilnya salah.

Tabel kebenaran penghubung dan v adalah :

Jika T dinyatakan dengan 1 dan F dinyatakan dengan 0, maka dapat dinyatakan dengan tabel masukan/keluaran.

Tabel masukan/keluaran untuk XOR :

EKSPRESI BOOLE, dalam n buah variable

didefinisikan secara rekursif sebagai berikut :

1. 0 dan 1 adalah ekspresi boole

2. masing-masing adalah ekspresi boole

3. Jika dan adalah ekspresi Boole, maka

Λ , v , ‘ adalah ekspresi boole juga

Dalam praktek, penulisan tanda Λ pada ekspresi boole ditulis dengan tanda titik (۰) atau dihilangkan sama sekali.

Dua ekspresi boole dan dikatakan ekuivalen (simbol = ) jika untuk semua kombinasi masukan, kedua ekspresi tersebut menghasilkan nilai fungsi keluaran yang sama. Dengan kata lain, salah satu ekspresi bisa didapat dari yang lain dengan menggunakan hukum-hukum dalam aljabar boole.

Contoh :

1. Apakah ekspresi dibawah ini merupakan ekspresi boole dalam variable x,y, dan z?

a. z b. x v y c. (x Λ y)’ v (z’ Λ x)

d. (x v y) Λ (x’ v z) Λ 1

2. Telitilah apakah kedua ekspresi boole dibawah ini ekuivalen : xy v xyz v z dan : xy v z

Penyelesaian :

xy v xyz v z = xy (1 v z) v z hukum distributif

= xy.1 v z hukum ikatan

= xy v z hukum identitas

karena bisa didapat dari maka, disimpulkan

= .

(dengan tabel masukan/keluaran)

BENTUK NORMAL DISJUNGTIF (Disjungtive Normal Form/DNF)

Ekspresi boole yang hanya terdiri dari satu variable

(atau komplemennya) disebut dengan Literal.

Setengah dari nilai fungsi ekspresi yang berbentuk

literal akan bernilai 1 dan setengah yang lain

bernilai 0.

Contoh : Buatlah tabel masukan/keluaran fungsi literal f : yang didefinisikan sebagai f(x,y) = y’

Penyelesaian :

Tampak bahwa setengah dari nilai fungsi (2 buah)

berharga 1 dan setengah yang lain berharga 0.

Ekspresi boole n variable yang merupakan gabungan dari beberapa literal yang dihubungkan dengan “Λ” disebut Minterm. Jadi minterm berbentuk dengan berharga 0 atau 1

adalah dan

Contoh : tentukan apakah ekspresi-ekspresi dibawah ini merupakan minterm dalam 3 variable x, y, z.

a. xy’z’ b. xz’ c. xyx’z

Penyelesaian :

Merupakan minterm dalam x, y dan z karena memuat literal x, y dan z

Bukan minterm dalam x, y dan z, karena tidak memuat literal y.(xz’ merupakan minterm dalam 2 variable x dan z)

Bukan minterm karena x muncul dalam 2 literal

Ekspresi boole yang berbentuk minterm menarik

untuk diperhatikan karena setiap minterm dalam n

variable hanya mempunyai tepat satu

keluaran bernilai 1 dari keseluruhan kombinasi

masukan yang mungkin.

Akibatnya, setiap ekspresi boole dalam n variable

tersebut (kecuali 0) dapat dinyatakan sebagai

gabungan beberapa minterm yang berbeda.

Gabungan itu tunggal dan tidak tergantung dari

urutan penulisan minterm.

Gabungan minterm yang ekuivalen dengan suatu

ekspresi boole E dinamakan Bentuk Normal Disjungtif

(DNF = disjunctive normal form). Atau dengan sebutan

Bentuk Kanonik Minterm untuk E.

Contoh :

Buatlah tabel untuk ekspresi boole E dalam 3 variable x,y,z untuk E = x’yz’ v xy’z’ v xy’z v xyz’

E merupakan gabungan dari 4 buah minterm masing-masing x’yz’,xy’z’,xy’z dan xyz’. Setiap minterm mempunyai tepat satu keluaran bernilai 1. Untuk minterm yang berbeda, posisi nilai 1 tersebut juga pasti akan terletak pada baris yang berbeda.

Karena E merupakan gabungan dari ke-4 minterm yang dihubungkan dengan “v”, maka E bernilai = 1 pada baris dimana salah satu minterm bernilai = 1.

Carilah ekspresi boole E dalam 3 variable x,y,z yang mempunyai tabel kebenaran :

Contoh : carilah ekspresi boole E dalam 3 variable x,y,z yang mempunyai tabel kebenaran

Penyelesaian : nilai E = 1 berasal dari minterm penyusunnya. Suatu minterm bernilai = 1 bila dan hanya bila nilai-nilai tiap literalnya = 1.

Lihat tabel, nilai E = 1 terletak pada baris ke-5 dan 6. Minterm yang menyebabkan nilai E = 1, pada baris ke-5 berasal dari literal yang komponennya bernilai = 1. Dalam baris tersebut nilai y dan z = 1, tapi x = 0 maka x’ = 1. Ini berarti bahwa pada baris ke-5, minterm yang menyebabkan E = 1 adalah x’yz.

Kita lihat pada baris ke-6, minterm yang menyebabkan nilai E = 1, adalah x’yz’.

Sehingga ekspresi boole E yang menghasilkan keluaran adalah gabungan minterm-minterm yang nilainya = 1, yang dihubungkan dengan “v”, jadi E = x’yz v x’yz’.

Catatan :

Ada 2 cara untuk mengubah sembarang ekspresi

boole kedalam DNF, yaitu :

Dengan membuat tabel masukan/keluaran untuk semua kemungkinan. Sehingga DNF dapat ditentukan

Dengan mengubah ekspresi boole secara langsung menggunakan hukum-hukum aljabar boole

Contoh : Jadikan ekspresi E = (x v yz’)(yz)’ dalam bentuk DNF.

Penyelesaian :

Dengan tabel masukan/keluaran :

Nilai E = 1 terjadi pada baris 2,3,4 dan 6 yang masing-masing bersesuain dengan minterm xyz’, xy’z, xy’z’ dan x’yz’ sehingga E = xyz’ v xy’z v xy’z’ v x’yz’

Penurunan langsung dengan menggunakan hukum-hukum aljabar boole :

(x v yz’)(yz)’ = (x v yz’)(y’ v z’) hk. De Morgan

= x(y’ v z’) v (yz’)(y’ v z’) sifat distributif = (xy’ v xz’) v (yz’y’ v yz’) sifat distributif = xy’ v xz’ v yz’

xy’ v xz’ v yz’ adalah ekspresi yang merupakan gabungan dari literal-literal, tapi bukan merupakan gabungan dari minterm dalam x, y, z(suku ke-1 tidak memuat z, yang ke-2 tidak memuat y, suku ke-3 tidak memuat x). Untuk mengubah supaya menjadi minterm, dapat dilakukan dengan cara menambahkan variable yg belum ada.

xy’ = xy’.1 = xy’(z v z’) = xy’z v xy’z’

xz’ = x.1z’ = x(y v y’)z’ = xyz’ v xy’z’

yz’ = 1.yz’ = (x v x’)yz’ = xyz’ v x’yz’

sehingga :

E = (xy’z v xy’z’) v (xyz’ v xy’z’) v (xyz’ v x’yz’)

dengan menghilangkan suku-suku yang berulang, maka :

E = xy’z v xy’z’ v xyz’ v x’yz’

Tinggalkan Jawapan

Masukkan butiran anda dibawah atau klik ikon untuk log masuk akaun:

WordPress.com Logo

Anda sedang menulis komen melalui akaun WordPress.com anda. Log Out / Tukar )

Twitter picture

Anda sedang menulis komen melalui akaun Twitter anda. Log Out / Tukar )

Facebook photo

Anda sedang menulis komen melalui akaun Facebook anda. Log Out / Tukar )

Google+ photo

Anda sedang menulis komen melalui akaun Google+ anda. Log Out / Tukar )

Connecting to %s