· 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. Komplemen[1]: (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:

- 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.

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 e₁dan e₂ adalah ekspresi Boolean, maka e₁ + e₂, e₁ × e₂, e₁’ adalah ekspresi Boolean

Contoh:

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

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: (i) a + 0 = a (ii) a × 1 = a	2. Hukum idempoten: (i) a + a = a (ii) a × a = a
3. Hukum komplemen: (i) a + a’ = 1 (ii) aa’ = 0	4. Hukum dominansi: (i) a × 0 = 0 (ii) a + 1 = 1
5. Hukum involusi: (i) (a’)’ = a	6. Hukum penyerapan: (i) a + ab = a (ii) a(a + b) = a
7. Hukum komutatif: (i) a + b = b + a (ii) ab = ba	8. Hukum asosiatif: (i) a + (b + c) = (a + b) + c (ii) a (b c) = (a b) c
9. Hukum distributif: (i) a + (b c) = (a + b) (a + c) (ii) a (b + c) = a b + a c	10. Hukum De Morgan: (i) (a + b)’ = a’b’ (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

· Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bⁿke B melalui ekspresi Boolean, kita menuliskannya sebagai

f: Bⁿ® B

yang dalam hal ini Bⁿ 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 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

Komplemen Fungsi

1. Cara pertama: menggunakan hukum De Morgan

Hukum De Morgan untuk dua buah peubah, x₁ dan x₂, adalah

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’)

2. Cara kedua: menggunakan prinsip dualitas.

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

Contoh. 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

· Jadi, 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: 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	m₀ m₁ m₂ m₃	x + y x + y’ x’ + y x’ + y’	M₀ M₁ M₂ M₃

			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	m₀ m₁ m₂ m₃ m₄ m₅ m₆ m₇	x + y + z x + y + z’ x + y’+z x + y’+z’ x’+ y + z x’+ y + z’ x’+ y’+ z x’+ y’+ z’	M₀ M₁ M₂ M₃ M₄ M₅ M₆ M₇

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

Tabel 7.10

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) = m₁+ m₄+ m₇= å (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) = M₀M₂ M₃ M₅M₆ = Õ(0, 2, 3, 5, 6)

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

Penyelesaian:

(a) SOP

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) = m₁ + m₄+ m₅+ m₆+ m₇ = S (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) = M₀M₂M₃ = Õ(0, 2, 3)

Konversi Antar Bentuk Kanonik

Misalkan

f(x, y, z) = S (1, 4, 5, 6, 7)

dan f’adalah fungsi komplemen dari f,

f’(x, y, z) = S (0, 2, 3) = m₀+ m₂+ m₃

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

f ’(x, y, z) = (f ’(x, y, z))’ = (m₀ + m₂+ m₃)’

= m₀’ . m₂’ . m₃’

= (x’y’z’)’ (x’y z’)’ (x’y z)’

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

= M₀ M₂M₃

= Õ (0,2,3)

Jadi, f(x, y, z) = S (1, 4, 5, 6, 7) = Õ (0,2,3).

Kesimpulan: m_j’ = M_j

Contoh. Nyatakan

f(x, y, z)= Õ (0, 2, 4, 5) dan

g(w, x, y, z) = S(1, 2, 5, 6, 10, 15)

dalam bentuk SOP.

Penyelesaian:

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

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

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

Penyelesaian:

(a) SOP

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) = m₀+ m₁+ m₂+ m₄+ m₅+ m₆+ m₇

(b) POS

f(x, y, z) = M₃ = 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)

Aplikasi Aljabar Boolean

1. Jaringan Pensaklaran (Switching Network)

Saklar adalah objek yang mempunyai dua buah keadaan: buka dan tutup.

Tiga bentuk gerbang paling sederhana:

1. a x b

Output b hanya ada jika dan hanya jika x dibuka Þ x

2. a x y b

Output b hanya ada jika dan hanya jika x dan y dibuka Þ xy

3. a x

b y

Output c hanya ada jika dan hanya jika xatau y dibuka Þ x+ y

Contoh rangkaian pensaklaran pada rangkaian listrik:

1. Saklar dalam hubungan SERI: logika AND

Lampu

A B

Sumber tegangan

2. Saklar dalam hubungan PARALEL: logika OR

Lampu

Sumber Tegangan

Contoh. Nyatakan rangkaian pensaklaran pada gambar di bawah ini dalam ekspresi Boolean.

x’ y

x’

x y

x y’ z

Jawab: x’y+ (x’ + xy)z + x(y + y’z + z)

2. Rangkaian Digital Elektronik

Gerbang AND Gerbang OR Gerbang NOT (inverter)

Contoh. Nyatakan fungsi f(x, y, z) = xy + x’yke dalam rangkaian logika.

Jawab: (a) Cara pertama

(b) Cara kedua

(b) Cara ketiga

Gerbang turunan

Gerbang NAND Gerbang XOR

Gerbang NOR Gerbang XNOR

Penyederhanaan Fungsi Boolean

Contoh. f(x, y) = x’y + xy’ + y’

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

2. Peta Karnaugh

a. Peta Karnaugh dengan dua peubah

0 1

	m₀	m₁	x 0	x’y’	x’y
	m₂	m₃	1	xy’	xy

b. Peta dengan tiga peubah

					yz 00	01	11	10
m₀	m₁	m₃	m₂	x 0	x’y’z’	x’y’z	x’yz	x’yz’
m₄	m₅	m₇	m₆	1	xy’z’	xy’z	xyz	xyz’

Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.

x	y	z	f(x, y, z)
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

	yz 00	01	11	10
x 0	0	0	0	1
1	0	0	1	1

b. Peta dengan empat peubah

						yz 00	01	11	10
m₀	m₁	m₃	m₂	wx 00		w’x’y’z’	w’x’y’z	w’x’yz	w’x’yz’
m₄	m₅	m₇	m₆		01	w’xy’z’	w’xy’z	w’xyz	w’xyz’
m₁₂	m₁₃	m₁₅	m₁₄		11	wxy’z’	wxy’z	wxyz	wxyz’
m₈	m₉	m₁₁	m₁₀		10	wx’y’z’	wx’y’z	wx’yz	wx’yz’

Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.

w	x	y	z	f(w, x, y, z)
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	0
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

	yz 00	01	11	10
wx 00	0	1	0	1
01	0	0	1	1
11	0	0	0	1
10	0	0	0	0

Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh

1. Pasangan: dua buah 1 yang bertetangga

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	0	0	1	1
10	0	0	0	0

Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’

Hasil Penyederhanaan: f(w, x, y, z) = wxy

Bukti secara aljabar:

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

= wxy(z + z’)

= wxy(1)

= wxy

2. Kuad: empat buah 1 yang bertetangga

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	0	0	0	0

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’

Hasil penyederhanaan: f(w, x, y, z) = wx

Bukti secara aljabar:

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

= wx(z’ + z)

= wx(1)

= wx

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	0	0	0	0

Contoh lain:

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	0	0
10	1	1	0	0

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z

Hasil penyederhanaan: f(w, x, y, z) = wy’

3. Oktet: delapan buah 1 yang bertetangga

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	1	1	1	1

Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ +

wx’y’z’ + wx’y’z+ wx’yz + wx’yz’

Hasil penyederhanaan: f(w, x, y, z) = w

Bukti secara aljabar:

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

= w(y’ + y)

= w

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	0	0	0
11	1	1	1	1
10	1	1	1	1

Contoh 5.11. Sederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’.

Jawab:

Peta Karnaugh untuk fungsi tersebut adalah:

	yz 00	01	11	10
x 0			1
1	1		1	1

Hasil penyederhanaan: f(x, y, z) = yz + xz’

Contoh 5.12. Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean yang bersesuaian sesederhana mungkin.

	yz 00	01	11	10
wx 00	0	1	1	1
01	0	0	0	1
11	1	1	0	1
10	1	1	0	1

Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = wy’ + yz’ + w’x’z

Contoh 5.13. Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	1	0	0
11	1	1	1	1
10	1	1	1	1

Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = w + xy’z

Jika penyelesaian Contoh 5.13 adalah seperti di bawah ini:

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	1	0	0
11	1	1	1	1
10	1	1	1	1

maka fungsi Boolean hasil penyederhanaan adalah

f(w, x, y, z) = w + w’xy’z (jumlah literal = 5)

yang ternyata masih belum sederhana dibandingkan f(w, x, y, z) = w + xy’z (jumlah literal = 4).

Contoh 5.14. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

	yz 00	01	11	10
wx 00	0	0	0	0
01	1	0	0	1
11	1	0	0	1
10	0	0	0	0

Jawab: f(w, x, y, z) = xy’z’ + xyz’ ==> belum sederhana

Penyelesaian yang lebih minimal:

	yz 00	01	11	10
wx 00	0	0	0	0
01	1	0	0	1
11	1	0	0	1
10	0	0	0	0

f(w, x, y, z) = xz’ ===> lebih sederhana

Contoh 5.15: (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	1	0	0
11	0	1	1	0
10	0	0	1	0

Jawab: f(w, x, y, z) = xy’z+ wxz + wyz ® masih belum sederhana.

Penyelesaian yang lebih minimal:

	yz 00	01	11	10
wx 00	0	0	0	0
01	0	1	0	0
11	0	1	1	0
10	0	0	1	0

f(w, x, y, z) = xy’z + wyz ===> lebih sederhana

Contoh 5.16. Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.

	cd 00	01	11	10
ab 00	0	0	0	0
01	0	0	1	0
11	1	1	1	1
10	0	1	1	1

Jawab: (lihat Peta Karnaugh di atas) f(a, b, c, d) = ab + ad + ac+ bcd

Contoh 5.17. Minimisasi fungsi Boolean f(x, y, z) = x’z + x’y + xy’z + yz

Jawab:

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

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

yz = yz(x + x’) = xyz + x’yz

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

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

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

Peta Karnaugh untuk fungsi tersebut adalah:

	yz 00	01	11	10
x 0		1	1	1
1		1	1

Hasil penyederhanaan: f(x, y, z) = z + x’yz’

Peta Karnaugh untuk lima peubah

000 001 011 010 110 111 101 100

00	m₀	m₁	m₃	m₂	m₆	m₇	m₅	m₄
01	m₈	m₉	m₁₁	m₁₀	m₁₄	m₁₅	m₁₃	m₁₂
11	m₂₄	m₂₅	m₂₇	m₂₆	m₃₀	m₃₁	m₂₉	m₂₈
10	m₁₆	m₁₇	m₁₉	m₁₈	m₂₂	m₂₃	m₂₁	m₂₀

Garis pencerminan

Contoh 5.21. (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari f(v, w, x, y, z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)

Jawab:

Peta Karnaugh dari fungsi tersebut adalah:

	xyz 000	001	011	010	110	111	101	100
vw 00	1			1	1			1
01		1	1			1	1
11		1	1			1	1
10		1					1

Jadi f(v, w, x, y, z) = wz + v’w’z’ + vy’z

Keadaan Don’t Care

Tabel 5.16

w	x	y	z	desimal
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1	0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1	0 1 2 3 4 5 6 7 8 9 don’t care don’t care don’t care don’t care don’t care don’t care

Contoh 5.25. Diberikan Tabel 5.17. Minimisasi fungsi f sesederhana mungkin.

Tabel 5.17

a	b	c	d	f(a, b, c, d)
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1	0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1	1 0 0 1 1 1 0 1 X X X X X X X X

Jawab: Peta Karnaugh dari fungsi tersebut adalah:

	cd 00	01	11	10
ab 00	1	0	1	0
01	1	1	1	0
11	X	X	X	X
10	X	0	X	X

Hasil penyederhanaan: f(a, b, c, d) = bd + c’d’ + cd

Contoh 5.26. Minimisasi fungsi Boolean f(x, y, z) = x’yz + x’yz’ + xy’z’ + xy’z. Gambarkan rangkaian logikanya.

Jawab: Rangkaian logika fungsi f(x, y, z) sebelum diminimisasikan adalah seperti di bawah ini:

Minimisasi dengan Peta Karnaugh adalah sebagai berikut:

	yz 00	01	11	10
x 0			1	1
1	1	1

Hasil minimisasi adalah f(x, y, z) = x’y + xy’.

Contoh 5.28. Berbagai sistem digital menggunakan kode binary coded decimal (BCD). Diberikan Tabel 5.19 untuk konversi BCD ke kode Excess-3 sebagai berikut:

Tabel 5.19

	Masukan BCD				Keluaran kode Excess-3
	w	x	y	z	f₁(w, x, y, z)	f₂(w, x, y,z)	f₃(w, x, y, z)	f₄(w, x, y, z)
0 1 2 3 4 5 6 7 8 9	0 0 0 0 0 0 0 0 1 1	0 0 0 0 1 1 1 1 0 0	0 0 1 1 0 0 1 1 0 0	0 1 0 1 0 1 0 1 0 1	0 0 0 0 0 1 1 1 1 1	0 1 1 1 1 0 0 0 0 1	1 0 0 1 1 0 0 1 1 0	1 0 1 0 1 0 1 0 1 0