LogikaMatematika

ALJABAR BOOLEAN

1.1 DefinisiAljabar boolean merupakan aljabar yang terdiri atas

himpunan R dengan dua operasi, yaitu :Penambahan (+)Perkalian (.)

yang didefinisikan pada himpunan tersebut sehingga untuk elemen a, b, c R berlaku aksioma-aksioma berikut :1. Closure2. Idempoten3. Komunikatif4. Assosiatif5. Distributif6. Identitas7. Komplemen

2.1 Prinsip DualitasDefinisi:

Jika ada sebuah pernyataan S yang sah tentang aljabar boolean yang melibatkan operasi +, ., dan komplemen, maka jika pernyataan S* diperoleh dengan cara melakukan penukaran sebagai berikut :

. ++ .0 11 0

maka pernyataan S * juga merupakan pernyataan yang sah.S* disebut dual dari S

Ada Teorema:1. Idempoten2. Identitas3. Hukum penyerapan4. De Morgan

1.3 Fungsi BooleanDefinisi :

Misalkan x1 .. xn merupakan variabel-variabel aljabar boolean maka fungsi boolean dengan variabel tersebut adalah fungsi yang dapat dibentuk dari aturan-aturan berikut :

1. Fungsi konstanta : jika x1 .. xn, f(x1 .. xn) = a

2. Fungsi proyeksi : jika x1 .. xn, f(x1 .. xn) = x1

3. Jika f adalah fungsi boolean maka g(x1 .. xn) = (f(x1 .. xn))’

adalah fungsi boolean juga untuk x1 .. xn.

4. Jika f dan g adalah fungsi adalah fungsi boolean maka : h(x1 .. xn) = f(x1 .. xn) + g(x1 .. xn), dan

k(x1 .. xn) = f(x1 .. xn) . g(x1 .. xn) adalah fungsi boolean

untuk x1 .. xn.

Catatan: Fungsi f(x) = x, yaitu fungsi proyeksi untuk satu variabel disebut juga fungsi identitas

Ada teorema berikut :Jika f adalah fungsi boolean dengan satu variabel maka x, f(x) = f(1)x + f(0)x’

Latihan 1. Apa yang disebut aksioma?, dan coba jelaskan mengenai aksioma-aksioma berikut ini : a. Closure b. Idempoten c. Komunitatif d. Assosiatif e. Distributif f. Identitas g. Komplemen2. Apa yang disebut teorema ?, dan coba jelaskan mengenai teorema berikut : a. Idempoten b. Identitas c. Hukum penyerapan

d. De Morgan3. Buktikan keempat teorema tadi !4. Berikan contoh dari fungsi boolean yang beracuan pada aturan-aturan dari keempat aturan fungsi boolean !5. Buktikan fungsi boolean dari definisi sebagai aturan untuk keempat fungsi boolean dengan teorema fungsi berikut f(x) = f(1)x + f(0)x’.

Kepintaran Bisa Kita Raih kalau Kita mau BelajarKebisaan bisa Kita Capai kalau Kita mau Berlatih

Jawaban : Atas Latihan1. Aksioma adalah suatu aturan yang perlu dibuktikan

kebernarannya.a. Closure : a + b R

a . b R b. Idempoten : a . a = a c. Komunitatif : a + b = b + a

a . b = b . a d. Assosiatif : a + (b + c) = (a + b) + c

a . (b . c) = (a . b) . c e. Distributif : a . (b + c) = a . b + a . c

a + (b . c) = (a + b) . (a + c) (a . b) + c = (a + c) . (b + c)

Jawaban : Atas Latihanf. Identitas : ada elemen unik 0 R, sehingga berlaku a+0=a ada elemen unik 1 R, sehingga berlaku a.1=a g. Komplemen : Untuk setiap a R ada elemen unik a’ R sehingga berlaku a + a’ = 1 dan a . a’ = 0

2. Teorema adalah suatu aturan yang sudah dibuktikan Kebernarannya dan dijadikan teori.a. a + a = a a . a = ab. a + 1 = a a . 0 = 0c. Hukum penyerapan: a + a . b = a a(a + b) = ad. Teorema De Morgan: (a . b)’ = a’ + b’ (a + b)’ = a’ . b'

Jawaban : Atas Latihan3. Bukti :

(a.1) a + a = a a + a = (a + a)(1) ………………………….. identitas = (a + a)(a + a’) ……………………. komplemen = a + (a . a’) ………………………….. distributif = a + 0 ………………………………….. komplemen = a ………………………………………... identitas(a.2) a . a = a a . a = a . a + 0 ……………………………….. identitas = a . a + a . a’ …….……………………. komplemen = a (a + a’) …………………………….. distributif = a . 1 ..………………………………….. komplemen = a ………………………………………... identitasJadi (a.2) adalah dual dari (a.1)

Jawaban : Atas LatihanBukti :

(b.1) a + 1 = 1 a + 1 = a + (a + a’) ………………………….. komplemen = (a + a) + a’ …………………………… assosiatif = a + a’ ……………………………………. idempoten = 1 ………………………………………..... komplemen(b.2) a . 0 = 0 a . 0 = a . (a . a’) …………………………….. komplemen = (a . a) . a’ …….………………………. assosiatif = a . a’ ..………………………………….. idempoten = 0 ………………………………………... komplemenJadi (b.2) adalah dual dari (b.1)

Jawaban : Atas LatihanBukti :

(c.1) a + a . b = a a + ab = a . 1 + a . b ……………………… identitas = a (1 + b) ………………………….. distributif = a . 1 ……………………………………. idempoten = a ……………………………………….. identitas(c.2) a . (a + b) = a a . (a + b) = a . a + ab …………………… distributif = a + ab …….…………………. idempoten = a . 1 + ab ……………………. identitas = a (1 + b) …………………….. distributif = a . 1 ……………………………. idempoten = aJadi (c.2) adalah dual dari (c.1)

Jawaban : Atas LatihanBukti :

(d.1) (a . b)’ = a’ + b’ diketahui : (ab) (ab)’ = 0 perlihatkan : (ab) (a’ + b’) = 0 bukti : (ab) (a’ + b’) = a b a’ + a b b’ ……………………… distributif = 0 . b + a . 0 …………………………. komplemen = 0 + 0 ………………………………….. identitas = 0 ………………………………………… identitas(d.2) (a + b)’ = a’ . b’ diketahui : (ab) + (ab)’ = 1 perlihatkan : ab + a’ + b’ = 1 bukti : (ab) + (a’ + b’) = (a + a’ + b’) (b + a’ + b’) …. distributif = (1 + b’) (1 + a’) ………………… komplemen = 1 . 1 …………………………………. identitas = 1 ……………………………………… identitas

Jadi (d.2) adalah dual dari (d.1)

Jawaban : Atas Latihan4. Contoh fungsi boolean yaitu:

a. f(x) = x + x’ab. g(x,y) = x’y + xy’ + y’c. h(x,y) = x’y’d. k(x,y) = (x + y)’

5.

Jawaban : Atas Latihanf. Identitas : ada elemen unik 0 R, sehingga berlaku a+0=a

ada elemen unik 1 R, sehingga berlaku a.1=a g. Komplemen : Untuk setiap a R ada elemen unik a’ R

sehingga berlaku a + a’ = 1 dan a . a’ = 0

2. Teorema adalah suatu aturan yang sudah dibuktikan Kebernarannya dan dijadikan teori.a. a + a = a a . a = ab. a + 1 = a a . 0 = 0S : positifS*: negatifS : saya hari ini mengajar mata kuliah logika matematikaS*: saya hari ini tidak mengajar mata kuliah logika matematika

Fungsi Booleanadalah suatu ekspresi yang dibentuk untuk variabel-variabel biner (variabel yang mempunyai nilai 1 atau 0). Dengan dua buah operator (+ dan .) ditambah dengan operator not (‘), dan tanda “=“Contoh f(x,y,z) = xyz’

f berharga 1 jika x=1, y=1, dan z’=0 f berharga 0 jika lainnya

Fungsi biner dapat dinyatakan secara: Aljabar, dan Tabel kebenaran

Tabel kebenaran, kombinasi nilai variabel sebanyak 2n

n = banyak variabel biner Fungsi boolean dapat ditransformasikan ke dalam suatu diagram logika atas gerbang AND, OR, dan NOT

1.4 Fungsi KomplemenFungsi komplemen dari suatu fungsi f, yaitu dapat dicari dengan menukarkan nilai 0 dengan 1, dan nilai 1 dengan 0 Hukum De Morgan yang diperluas: (a+b+c)’ = (a+x)’ = a’x’ = a’ . (b+c)’ = a’ . (b’ . c’) = a’ . b’ . c’Sehingga: (a+b+…+e)’ = a’ . b’ . .. .e’ dan (a . b . .. . c)’ = a’ + b’ + .. + e’