materi aljabar boolean

Modul Logika Informatika @ Mustahal, S.Si

Universitas Islam Lamongan (UNISLA) Page 38 of 55

BAB 3 : ALJABAR BOOLE

PENDAHULUAN

Aljabar Boole, sebagai salah satu cabang matematika, pertama kali

dikemukakan oleh George Boole pada tahun 1854. Boole dalam bukunya The Law Of Thought, memaparkan aturan-aturan dasar logika (yang dikenal dengan logika boolean). Aturan dasar logika ini membentuk Aljabar Boole. Pada tahun 1938, Claude Shannon memperlihatkan penggunaan Aljabar Boole untuk merancang rangkaian sirkuit listrik yang menerima masukan 0 dan 1 serta menghasilkan keluaran 0 dan 1 juga. Aljabar Boole telah menjadi dasar teknologi komputer digital. Saat ini aljabar boole digunakan secara luas dalam rangkaian perancangan pensaklaran, rangkaian digital, dan rangkaian IC (Intergrated Circuit) komputer.

DEFINISI ALJABAR BOOLE

Aljabar boole merupakan aljabar yang terdiri atas suatu himpunan dengan dua operator biner yang didefinisikan pada himpunan tersebut yaitu :

+ (penambahan) ekuivalen dengan ∨ (OR) • (perkalian) ekuivalen dengan ∧ (AND)

Pada aljabar boole juga berlaku hukum-hukum logika, hanya berubah tanda saja yaitu :

∧ (AND) menjadi * atau • ∨ (OR) menjadi + ¬(Negasi) menjadi ’ atau dalam aljabar boole disebut komplemen

Misal : • a∧b menjadi a*b atau a.b atau cukup ditulis ab • a∨b menjadi a+b • ¬a menjadi a’ atau ā

Identitas p.1 ≡ p p+0 ≡ p

Ikatan P+1 ≡ 1 p.0 ≡ 0

Idempoten p+p ≡ p p.p ≡ p

Komplemen p+p’ ≡ 1 p.p’ ≡ 0

(p’)’ ≡ p 1’=0 dan 0’=1

Komutatif p+q ≡ q+p p.q ≡ q.p

Asosiatif (p+q)+r ≡ p+(q+r) (p.q).r ≡ p.(q.r)

Distributif p+(q.r) ≡ (p+q).(p+r) p.(q+r) ≡ (p.q)+(p.r)

De Morgan’s (p.q)’ ≡ p’+q’ (p+q)’ ≡ p’ . q’

Aborbsi p∧(p∨q) ≡ p p∨(p∧q) ≡ p



Terdapat perbedaan antara aljabar boole dengan aljabar biasa untuk aritmatika bilangan riil : 1. Hukum distributif + dan . seperti pada a+(b.c)=(a+b).(a+c) benar unutk

aljabar boole tetapi tidak benar untuk aljabar biasa. 2. Aljabar boole tidak memiliki kebalikan perkalian atau penjumlahan

sehingga tidak ada operasi pembagian dan pengurangan.

DUALITAS

Dual dari setiap pernyataan S dalam sebuah aljabar boole B adalah pernyataan yang didapat dengan mengubah operasi-operasi + dan ., dan mengubah elemen identitas yang menghubungkan 0 dan 1 dalam pernyataan awal di S. Dalam hal ini berarti mengganti : * dengan +

+ dengan * 0 dengan 1 1 dengan 0 Contoh 3.1:

Tuliskan dual dari setiap persamaan boolean berikut 1) (a*1)*(0+a’)=0

Untuk mencari dual dari persamaan di atas maka : • Pada (a.1), ubah * menjadi + dan 1 menjadi 0 • Ubah * pada (a*1)*(0+a’) menjadi + • Pada (0+a’), ubah 0 menjadi 1 dan + menjadi * • Komplemen pada a’ tidak berubah Sehingga secara keseluruhan dualnya adalah : (a * 1) * ( 0 + a’)=0 (a + 0) + (1 * a’)=1 ⇒ dual

2) a+(a’*b)=a+b Dengan cara yang sama seperti contoh di atas maka dulanya : a*(a’+b)=a*b

Sekarang, coba Anda cari dual dari persamaan boolen berikut 3) a(a’+b)=ab 4) (a+1)(a+0)=a 5) (a+b)(b+c)=ac+b

FUNGSI BOOLEAN

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 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. Fungsi h(x, y, z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’. Contoh 3.2: 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 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 0 0 0 0 0 1 0

FUNGSI KOMPLEMEN

Untuk menentukan komplemen dari suatu persamaan boolean, maka dapat digunakan prinsip dualitas dan hukum De Morgan.

1. Cara pertama: menggunakan hukum De Morgan Contoh 3.3. 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’)


Universitas Islam Lamongan (UNISLA) 1 of 55

2. Cara kedua: menggunakan prinsip dualitas.

Tentukan dual dari ekspresi Boolean yang merepresentasikan f, lalu komplemenkan setiap literal di dalam dual tersebut.

Contoh 3.4. Misalkan f(x, y, z) = x(y’z’ + yz), maka Dual dari f: x + (y’ + z’) (y + z) Komplemenkan tiap literalnya: x’ + (y + z) (y’ + z’) = f ’ Jadi, f ‘(x, y, z) = x’ + (y + z)(y’ + z’)

BENTUK KANONIK

Beberapa fungsi boolean mungkin memiliki ekspresi aljabar yang

berbeda tetapi sebenarnya mempunyai nilai fungsi yang sama. Sebagai contoh : f(x,y)=(xy)’ dan h(x,y)=x’+y’, adalah dua buah fungsi yang sama (Bisa dibuktikan dengan hukum De Morgan). Contoh lain : f(x,y,z)=x(y+z’) dan g(x,y,z)=xyz+xyz’+xy’z’ adalah dua buah fungsi yang sama. Fungsi f muncul dalam bentuk perkalian dari hasil jumlah sedangkan g muncul dalam bentuk penjumlahan dari hasil kali. Perhatikan juga bahwa setiap suku (term) mengandung literal yang lengkap. Fungsi boolean yang dinyatakan dalam bentuk perkalian dari hasil jumlah dan penjumlahan dari hasil kali, dengan setiap suku mengandung literal lengkap disebut bentuk KANONIK.

Ada dua macam bentuk kanonik:

1. Penjumlahan dari hasil kali (sum-of-product atau SOP) 2. Perkalian dari hasil jumlah (product-of-sum atau POS)

Contoh 3.5:

1. f(x, y, z) = x’y’z + xy’z’ + xyz � SOP

Setiap suku (term) disebut minterm

2. g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’) (x’ + y + z’)(x’ + y’ + z) � POS

Setiap suku (term) disebut maxterm

Setiap minterm/maxterm mengandung literal lengkap

Minterm Maxterm x y Suku Lambang Suku Lambang

0 0 1 1

0 1 0 1

x’y’ x’y xy’ x y

m0 m1

m2 m3

x + y x + y’ x’ + y x’ + y’

M0 M1 M2

M3



Minterm Maxterm

x y z Suku Lambang Suku Lambang

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

x’y’z’ x’y’z x‘y z’ x’y z x y’z’ x y’z x y z’ x y z

m0 m1

m2 m3

m4 m5 m6 m7

x + y + z x + y + z’ x + y’+z x + y’+z’ x’+ y + z x’+ y + z’ x’+ y’+ z x’+ y’+ z’

M0 M1 M2

M3

M4 M5 M6 M7

Contoh 3.6: Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS.

x y z f(x, y, z)

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 1 0 0 1 0 0 1

Penyelesaian: (a) SOP

Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah

f(x, y, z) = x’y’z + xy’z’ + xyz atau (dengan menggunakan lambang minterm),

f(x, y, z) = m1 + m4 + m7 = ∑ (1, 4, 7)

(b) POS Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000, 010, 011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah

f(x, y, z) = (x + y + z)(x + y’+ z)(x + y’+ z’)

(x’+ y + z’)(x’+ y’+ z) atau dalam bentuk lain,

f(x, y, z) = M0 M2 M3 M5 M6 = ∏(0, 2, 3, 5, 6)



Contoh 3.7: Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS.


x = x(y + y’) = xy + xy’ = xy (z + z’) + xy’(z + z’) = xyz + xyz’ + xy’z + xy’z’ y’z = y’z (x + x’) = xy’z + x’y’z Jadi f(x, y, z) = x + y’z = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z = x’y’z + xy’z’ + xy’z + xyz’ + xyz atau f(x, y, z) = m1 + m4 + m5 + m6 + m7 = Σ (1,4,5,6,7)

(b) POS f(x, y, z) = x + y’z = (x + y’)(x + z)

x + y’ = x + y’ + zz’ = (x + y’ + z)(x + y’ + z’) x + z = x + z + yy’ = (x + y + z)(x + y’ + z) Jadi, f(x, y, z) = (x + y’ + z)(x + y’ + z’)(x + y + z)(x + y’ + z) = (x + y + z)(x + y’ + z)(x + y’ + z’) atau f(x, y, z) = M0M2M3 = ∏(0, 2, 3)

KONVERSI BENTUK KANONIK

Misalkan

f(x, y, z) = Σ (1, 4, 5, 6, 7) dan f ’adalah fungsi komplemen dari f,

f ’(x, y, z) = Σ (0, 2, 3) = m0+ m2 + m3



Dengan menggunakan hukum De Morgan, kita dapat memperoleh fungsi f dalam bentuk POS:

f ’(x, y, z) = (f ’(x, y, z))’ = (m0 + m2 + m3)’ = m0’ . m2’ . m3’ = (x’y’z’)’ (x’y z’)’ (x’y z)’

= (x + y + z) (x + y’ + z) (x + y’ + z’) = M0 M2 M3 = ∏ (0,2,3)

Jadi, f(x, y, z) = Σ (1, 4, 5, 6, 7) = ∏ (0,2,3). Kesimpulan: mj’ = Mj

Contoh 3.8. Nyatakan

f(x, y, z)= ∏ (0, 2, 4, 5) dan g(w, x, y, z) = Σ(1, 2, 5, 6, 10, 15)

dalam bentuk SOP.

Penyelesaian:

f(x, y, z) = Σ (1, 3, 6, 7)

g(w, x, y, z)= ∏ (0, 3, 4, 7, 8, 9, 11, 12, 13, 14)

Contoh 3.9. Carilah bentuk kanonik SOP dan POS dari f(x, y, z) = y’ + xy + x’yz’


f(x, y, z) = y’ + xy + x’yz’ = y’ (x + x’) (z + z’) + xy (z + z’) + x’yz’

= (xy’ + x’y’) (z + z’) + xyz + xyz’ + x’yz’ = xy’z + xy’z’ + x’y’z + x’y’z’ + xyz + xyz’ + x’yz’

atau f(x, y, z) = m0+ m1 + m2+ m4+ m5+ m6+ m7

(b) POS f(x, y, z) = M3 = x + y’ + z’

Bentuk Baku

Contohnya :

f(x, y, z) = y’ + xy + x’yz (bentuk baku SOP

f(x, y, z) = x(y’ + z)(x’ + y + z’) (bentuk baku POS)

materi aljabar boolean

Education