dasar logika

DASAR-DASAR LOGIKA

Logika Informatika

Logika Informatika -34

DAFTAR ISI

Bab I : Teori Himpunan1

1.1 Konsep Himpunan1

1.2 Notasi dan Definisi1

1.3 Operasi-operasi Himpunan3

1.4 Sifat-sifat Himpunan4

1.5 Relasi & Fungsi5

Bab II : Dasar Logika6

2.1 Kalimat Deklaratif6

2.2 Penghubung Kalimat6

2.3 Tautologi dan Kontradiksi12

2.4 Konvers, Invers, dan Kontraposisi12

2.5 Inferensi Logika13

2.5.1 Metoda-metoda Inferensi15

Bab III : Aljabar Boole21

3.1 Konsep Dasar Aljabar Boole21

3.2 Fungsi Boolean23

3.3 Komplemen Fungsi26

3.4 Konversi Bentuk Fungsi27

Bab VI : Penyederhanaan Fungsi Boolean29

4.1 Metoda Aljabar29

4.2 Metoda Peta Karnough30

4.3 Metoda Tabulasi Quine-Mc Cluskey34

Bab I

Teori Himpunan

1.1 Konsep Himpunan

Konsep himpunan merupakan konsep dasar dalam matematika.

Definisi :

Himpunan adalah koleksi obyek yang didefinisikan secara jelas dalam sembarang urutan.

Cara mengoleksi obyek-obyek dapat didasarkan pada sifat mereka yang sama atau berdasarkan suatu aturan tertentu. Obyek-obyek yang menjadi anggota dari himpunan ini disebut dengan elemen dari himpunan tersebut. Jika p anggota himpunan A, ditulis p(A, dibaca p adalah elemen (anggota) dari himpunan A. Jika obyek q bukan anggota dari himpunan A, ditulis q(A.

1.2 Notasi dan Definisi

Himpunan dinyatakan dengan huruf besar : A, B, C,..., sedangkan elemen-elemennya dinyatakan dengan huruf kecil : a, b, c, .....

Contoh :

1. Himpunan A terdiri atas bilangan 1,3,5,7, maka dapat dituliskan sebagai A = {1,3,5,7}

2. Himpunan B adalah himpunan bilangan genap positif, maka dapat dituliskan dalam bentuk : B = {x(x genap >0}

Terdapat tiga cara penulisan himpunan yaitu :

a. Dengan mendaftar anggota-anggotanya .

Contoh :

X = {2, 3, 5, 7, 11}

Y = {a, b, c, d}

b. Dengan menyatakan sifat-sifat yang dipenuhi oleh anggota-anggotanya

X = Himpunan 5 bilangan prima yang pertama}

Y = Himpunan 4 abjad huruf kecil yang pertama}

c. Dengan menggunakan notasi pembentuk himpunan.

X = {x(0< x < 13, x ( bilangan prima}

Y = {x(x ( 4 abjad huruf kecil yang pertama}

Definsi-Definisi pada teori himpunan :

a. Himpunan Semeseta

Himpunan semesta adalah himpunan yang anggotanya semua obyek yang sedang dibicarakan, dinotasikan dengan S atau U.

Contoh :

Semesta pembicaraan dari himpunan A = {a,b,c,d} dan B={c,d,e,f} adalah S = himpunan huruf-huruf kecil.

Semesta pembicaraan dari himpunan A = {2,5,7} adalah S = {1,3,5,7,9}

b. Himpunan Kosong

Himpunan kosong adalah himpunan yang tidak mempunyai anggota yang dinotasikan dengan { } atau (.

Contoh :

A = {x(x2=-1, x(bilangan asli}, maka P = {}

c. Himpunan kuasa (Power Set)

Himpunan kuasa adalah himpunan seluruh himpunan bagian dari suatu himpunan.

Contoh :

Himpunan bagian dari himpunan A = {1,2,3} adalah { },{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}.

Banyaknya himpunan bagian dari dari suatu himpunan yang beranggotakan n anggota adalah 2n himpunan bagian.

d. Himpunan Berhingga (finite) dan Himpunan Tak Berhingga (infinite)

Himpunan berhingga adalah suatu himpunan yang elemennya berbeda yang banyaknya tertentu.

Himpunan tak berhingga adalah suatu himpunan yang elemennya berbeda yang banyaknya tidak tertentu.

Contoh :

P = himpunan bilangan prima, maka infinite

Q = himpunan bilangan prima kurang dari 10, maka Q finite.

1.3 Operasi-operasi Himpunan

a. Union (Gabungan) Himpunan

Union himpunan A dan himpunan B adalah himpunan dari semua elemen yang termasuk dalam A atau B atau keduanya yang dinyatakan dengan simbol (.

Pernyataan tersebut dapat ditulis sebagai berikut :

A ( B ={x(x(A atau x(B}.

Contoh :

A = {a,b,c,d} dan B={c,d,e,f}, maka A ( B = {a,b,c,d,e,f}

b. Interseksi (Irisan) Himpunan

Interseksi himpunan A dan himpunan B adalah himpunan dari elemen-elemen yang termasuk dalam himpunan A maupun B, yang dinyatakan dengan simbol (.


A ( B ={x(x(A dan x(B}.

Contoh :

A = {a,b,c,d} dan B={c,d,e,f}, maka A ( B = {c,d}

c. Selisih Himpunan

Selisih himpunan A dan himpunan B adalah himpunan dari elemen-elemen yang termasuk A tetapi tidak termasuk B, dinyatakan dengan :

A B = { x(x(A dan x(B}.

Contoh :

A = {a,b,c,d} dan B={c,d,e,f}, maka A B = {a,b}

d. Jumlah Himpunan

Jumlah himpunan A dan himpunan B adalah himpunan dari elemen-elemen yang termasuk A atau B tetapi tidak termasuk keduanya, dinyatakan dengan :

A + B = { x(x(A, x(B dan x ( (A ( B) }.

Contoh :

A = {a,b,c,d} dan B={c,d,e,f}, maka A + B = {a,b,e,f}

e. Komplemen Himpunan

Komplemen dari himpunan A adalah himpunan dari elemen-elemen yang tidak termasuk A tetapi masih dalam semesta pembicaraan S. Secara matematis ditulis


A = { x(x(S dan x(A}

Contoh :

A = {b,c,d} dan B={a,b,c,d,e,f}, maka A = {a,e,f}

f. Himpunan Bagian

Himpunan A disebut himpunan bagian dari himpunan B jika setiap anggota A juga merupakan anggota B, ditulis A ( B.

Contoh :

A = {b,c,d} dan B={a,b,c,d,e,f}, maka A ( B

g. Himpunan Sama

Himpunan A disebut sama dengan himpunan B jika A ( B dan B ( A.

Contoh :

A = {b,c,d} dan B={b,c,d}, maka A = B

1.4 Sifat-sifat pada Operasi Himpunan

1A ( S = S8A + S = A15A ( S = A

2A ( A = A9A + A = (16A ( A = A

3A ( A = S10A + A = (17A ( A = (

4A ( ( = A11A + ( = A 18A ( ( = (

5(A(B)=A(B12A + B = (A(B) ( (A(B)19A(B = (A + B) ( (A ( B)

6(A(B)=A(B13A((B(C)= (A(B)((A(C)A(B = (A + B) + (A ( B)

7(A) = A14A( (B(C)= (A(B)((A(C)

1.5 Relasi dan Fungsi

Definisi :

Jika A dan B adalah sebarang himpunan, himpunan semua pasangan terurut (x,y) untuk setiap x(A, y(B disebut Product Cartesius (Cross Product) A dengan B, dinotasikan A ( B, yaitu :

A ( B = {(x,y)(x(A, x(B}

Contoh :

A = {x,y,z} dan B={a,b}, maka A ( B = {(x,a),(x,b),(y,a),(y,b),(z,a),(z,b)}

Soal Penerapan Himpunan

1. Dari diagram Venn yang ada arsirlah :

a. A ( B

b. ( A ( B ) ( C

c. A ( ( B ( C )

d. A ( ( B ( C )

2. Pada suatu perusahaan yang mempunyai 35 orang karyawan terdapat informasi sebagai berikut :

15 orang mempunyai telivisi

22 orang mempunyai radio

14 orang mempunyai almari es

11 orang mempunyai telivisi dan radio

8 orang mempunyai radio dan almari es

5 orang mempunyai telivisi dan almari es

3 orang mempunyai ketiganya.

Berapa orang karyawan yang tidak mempunyai telivisi, tidak mempunyai radio maupun tidak mempunyai almari es ?

Berapa orang karyawan yang hanya mempunyai radio?

3. Sebuah warung mendapat pesanan 21 kotak nasi dos :

9 kotak dengan kare, 16 kotak dengan gule dan 12 kotak dengan sate.

Pesanan itu menyebutkan juga 1 kotak dengan sate saja dan 6 kotak dengan gule saja.

Disamping itu, 5 kotak dengan gule dan sate, sedangkan 2 kotak dengan gule, sate, kare.

Berapa kotak dengan sate dan kare?

Berapa kotak dengan kare dan gule?

4. Pada suatu kelompok mahasiswa yang terdiri atas 150 orang diperoleh data tentang pengambilan program studi sebagai berikut :

83 orang memprogram matakuliah accounting

67 orang memprogram matakuliah statistika

45 orang memprogram matakuliah acounting dan statistika

Ada berapa orang mahasiswa yang tidak memprogram accounting atau statistika?

Ada berapa orang mahasiswa yang hanya memprogram 1 matakuliah?

5. Hasil survei terhadap 60 orang tamu suatu hotel diperoleh keterangan sebagai berikut :

37 orang menginap paling sedikit seminggu

43 orang mengeluarkan uang paling sedikit Rp. 100.000,- sehari

32 orang merasa puas terhadap akomodasi yang disediakan

30 orang menginap paling sedikit seminggu dan merasa puas terhadap akomodasi yang disediakan,

27 orang mengeluarkan uang paling sedikit Rp. 100.000,- sehari dan merasa puas tehadap akomodasi yang disediakan

24 orang menginap paling sedikit seminggu, mengeluarkan uang paling sedikit Rp.100.000 sehari dan merasa puas terhadap akomodasi yang disediakan.

Berapa orang tamu yang menginap paling sedikit seminggu dan mengeluarkan uang paling sedikit Rp. 100.000,- sehari, tetapi tidak merasa puas terhadap akomodasi yang disediakan?

Ada berapa orang tamu yang merasa puas terhadap akomodasi yang disediakan, tetapi menginap kurang dari seminggu, mengeluarkan uang kurang dari Rp. 100.000,- sehari?

Ada berapa orang tamu menginap kurang dari seminggu, mengeluarkan uang kurang dari Rp. 100.000,- sehari dan tidak merasa puas terhadap akomodasi yang disediakan ?

BAB II

DASAR LOGIKA

2.1 Kalimat Deklaratif

Ilmu logika berhubungan dengan kalimat-kalimat (argumen-argumen) dan hubungan yang ada di antara kalimat-kalimat tersebut. Tujuannya adalah memeberikan aturan-aturan sehingga orang dapat menentukan apakah suatu kalimat bernialai benar. Kalimat yang dipelajari dalam logika bersifat umum, baik bahasa sehari-hari maupun bukti matematika yang didasarkan atas hipotesa-hipotesa. Oleh karena itu, aturan-aturan yang berlaku di dalamnya haruslah bersifat umum dan tidak tergantung pada kalimat atau disiplin ilmu tertentu.Ilmu logika lebih mengarah pada bentuk kalimat (sintaks) daripada arti kalimat itu sendiri (semantik)

Suatu Kalimat Deklaratif (Proposisi) adalah kalimat yang bernilai benar atau salah, tetapi tidak keduanya.

Contoh Proposisi:

a. 2 + 2 = 4

(bernilai benar)

b. 4 adalah bilangan prima

(bernilai salah)

c. Jakarta adalah ibukota negara Indonesia.(bernilai benar)

d. Penduduk Indonesia berjumlah 50 juta.(bernilai salah)

Contoh Bukan Proposisi :

a. Dimana letak pulau Bali ?

(kalimat tanya)

b. Simon lebih tinggi dari Lina(ada banyak orang bernama Simon atau Lina di dunia)

c. x + y = 2(nilaikebenaran tergantung niali x dan y)

d. 2 mencintai 3(relasi mencintai tidak berlaku di bilangan)

.

2.2 Penghubung Kalimat

Seringkali beberapa kalimat perlu digabungkan menjadi satu kalimat yang lebih panjang, sehingga diperlukan penghubung kalimat. Dalam Logika dikenal 5 penghubung :

SimbolArtiBentuk

~Tidak / Not / NegasiTidak ..

(Dan / And / konjungsi dan .

(Atau / Or / Disjungsi atau

(ImlikasiJika . Maka ..

(Bi-Implikasi.. bila dan hanya bila .

Dalam matematika digunakan huruf-huruf kecil seperti p, q, r,. Untuk menyatakan sub kalimat dan simbol-simbol penghubung untuk menyatakan penghubung kalimat.

Contoh :

a. Misal p menyatakan kalimat 4 adalah bilangan genap

q menyatakan kalimat 3 adalah bilangan ganjil

maka kalimat 4 adalah bilangan genap dan 3 adalah bilangan ganjil dapat dinyatakan dengan simbol p ( q

b. Misal p : 2 + 2 = 4

q : bunga melati berwarna putih.

maka kalimat Jika 2 + 2 = 4, maka bunga melati berwarna putih dapat dinyatakan dengan simbol p ( q

Pada contoh b diatas, kalau kalimat tersebut diartikan dalam kehidupan sehari maka kalimat tersebut tidak berarti (tidak ada hubungan antara kedua kalimat penyusunnya). Tetapi secara logika matematis hal tersebut dapat diterima, karena di dalam matematika tidak disyaratkan adanya adanya hubungan antara kedua kalimat penyusunnya. Dalam Logika matematika, penekanan lebih ditujukan kepada bentuk/susunan kalimat saja (sintak), dan bukan pada arti kalimat penyusunnya dalam kehidupan sehari-hari (semantik). Kebenaran suatu kalimat berimplikasi semata-mata hanya tergantung pada nilai kebenaran kalimat penyusunnya, dan tidak tergantung pada ada/tidaknya relasi antara kalimat-kalimat penyusunnya.

Jika p dan q merupakan kalimat-kalimat, maka tabel kebenaran penghubung tampak pada tabel berikut :

pq~pp ( qp ( qp ( qp ( q

TTFTTTT

TFFFTFF

FTTFTTF

FFTFFTT

( T = True/benar, F = False/salah )

Secara umum, jika ada n variabel (p,q,), maka tabel kebenaran memuat 2n baris.

Dari tabel :

p ( q bernilai benar jika p maupun q benar, selain itu bernilai salah

p ( q bernilai benar jika ada sedikitnya satu variabel bernilai benar

Dalam kalimat p ( q , p disebut hipotesis (anteseden) dan q disebut konklusi (konsekuen). Kalimat p ( q disebut kalimat berkondisi karena kebenaran kalimat q tergantung pada kebenaran kalimat p. kalimat p ( q akan berniali salah kalau p benar dan q salah. Sebagai contoh perhatikan apa yang diucapkan seorang pria terhadap kekasihnya berikut ini :

Jika besok cerah, maka aku datang >> p : besok cerah , q : aku akan datang

Jika baik p maupun q keduanya benar (baris ke-1 tabel kebenaran), pria tersebut tidak berbohong.

jika p salah (ternyata keesokan harinya hujan, tidak cerah), maka pria tersebut terbebas dari janjinya karena janji tersebut bersyarat, yaitu kalau besok cerah. Jadi, baik pria tersebut datang (berarti q benar, sehingga menyatakan baris ke-3 tabel) maupun tidak datang (q salah ,sehingga menyatakan baris ke-4 tabel), pria tersebut tidak akan disalahkan.

Akan tetapi, pria tersebut akan disalahkan (berarti implikasi berniali salah) apabila keesokkan harinya cuaca cerah ( p benar) tetapi ia tidak datang (q salah). Ini sesuai baris ke-2 tabel.

Kalimat kondisi ganda (biconditional) p ( q ,berarti (p ( q) ( (q ( p). Supaya p ( q berniali benar maka p ( q maupun q ( p, keduanya harus bernilai benar (ingat bahwa kedua implikasi tersebut dihubungkan dengan kata hubung dan). Perhatikan tabel berikut :

pqp ( qq ( pp ( q atau (p ( q) (( q ( p)

TTTTT

TFFTF

FTTFF

FTTTT

Jadi p ( q bernilai benar jika p dan q keduanya bernilai benar atau keduanya bernilai salah

Soal Latihan :

1. Misal k : Monde orang kaya, s : Monde bersuka cita

Tulislah bentuk simbolis kalimat-kalimat berikut :

a. Monde orang yang miskin tetapi bersuka cita

b. Monde orang kaya atau ia sedih

c. Monde tidak kaya ataupun bersuka cita

d. Monde seorang yang miskin atau ia kaya tetapi sedih.

Anggaplah ingkaran kaya adalah miskin, ingkaran dari bersuka cita adalah sedih.

2. Buatlah tabel kebenaran untuk kalimat dalam bentuk simbol-simbol logika dibawah ini !

a. ~(~p ( ~q)

c. (p ( q) ( ~(p ( q)

b. ~(~p ( q)

d. (~p ( (~q ( r)) ( (q ( r) ( (p ( r)

3. Pada kondisi bagaimanakah agar kalimat di bawah ini bernilai benar ?

Tidaklah benar kalau rumah kuno selalu bersalju atau angker, dan tidak juga benar kalau sebuah hotel selalu hangat atau rumah kuno selalu rusak.

4. Jika p dan q bernilai benar (T) ; r dan s bernilai salah (F)

Tentukan nilai kebenaran kalimat berikut ini :

a. p ( (q ( r)

b. (p ( q ( r) ( ~((p ( q) ( ( r ( s))

c. (~(p ( q) ( ~r) ( (((~p ( q) ( ~r) ( s)

Dua kalimat disebut Ekuivalen (secara logika) bila dan hanya bila keduannya mempunyai nilai kebenaran yang sama untuk semua substitusi nilai kebenaran masing-masing kalimat penyusunnya. Jika p dan q adalah kalimat-kalimat yang ekuivalen, maka dituliskan p ( q .

Soal Latihan

5. Tentukan apakah pasangan kalimat-kalimat di bawah ini ekuivalen

a. ~(~p) dengan p

b. ~(p ( q) dengan ~p ( ~q

c. p ( q dengan ~p ( q

Beberapa hukum ekuivalensi logika disajikan dalam daftar dibawah ini :

1. Hukum Komutatif : p ( q ( q ( p ; p ( q ( q ( p

2. hukum Asosiatif : (p ( q) ( r ( p ( (q ( r)

(p ( q) ( r ( p ( (q ( r)

3. Hukum Distributif: p ( (q ( r) ( (p ( q) ( (p ( r)

p ( (q ( r ) ( (p ( q) ( (p ( r)

4. Hukum Identitas: p ( T ( p; p ( F ( p

5. Hukum Ikatan: p ( T ( T; p ( F ( F

6. Hukum Negasi: p ( ~p ( T; p ( ~p ( F

7. Hukum Negasi Ganda : ~(~p) ( p

8. Hukum Idempoten: p ( p ( p ; p ( p ( p

9. Hukum De Morgan: ~(p ( q) ( ~p ( ~q

~(p ( q) ( ~p ( ~q

10. Hukum Absorbsi: p ( (p ( q) ( p ; p ( (p ( q) ( p

11. Negasi T dan F: ~T ( F; ~F ( T

Dengan hukum-hukum tersebut, kalimat-kalimat yang kompleks dapat disederhanakan.

Contoh :

Sederhanakan bentuk ~(~p ( q) ( (p ( q)

Penyelesaian :

~(~p ( q) ( (p ( q) ( (~(~p) ( ~q) ( (p ( q)

( (p ( ~q) ( (p ( q)

( p ( (~q ( q)

( p ( F

( p

Jadi ~(~p ( q) ( (p ( q) ( p

Dalam membuktikan ekuivalensi P ( Q, ada 3 macam cara yang bisa dilakukan :

1. P diturunkan terus menerus (dengan menggunakan hukum-hukum yang ada), sehingga akhirnya didapat Q

2. Q diturunkan terus menerus (dengan menggunakan hukum-hukum yang ada) sehingga akhirnya didapat P.

3. P dan Q masing-masing diturunkan secara terpisah ( dengan menggunakan hukum-hukum yang ada ) sehingga akhirnya sama-sama didapat R

Sebagai aturan kasar, biasanya bentuk yang lebih kompleks diturunkan ke bentuk yang lebih sederhana.

Soal Latihan

6. Buktikan ekuivalensi kalimat-kalimat dibawah ini tanpa menggunakan tabel kebenaran

a. ~(p ( ~q) V (~p ( ~q) ( ~p

b. ~((~p ( q) ( (~p ( ~q) ) ( (p ( q) ( p

c. (p ( (~(~p ( q))) ( (p ( q) ( p

Untuk menunjukkan ekuivalensi 2 kalimat yang melibatkan penghubung ( (implikasi) dan ( (bi-implikasi), Kita harus terlebih ahulu mengubah penghubung ( dan ( menjadi penghubung (, ( dan ~. (kenyataan bahwa (p ( q) ( (~p ( q) mempermudah kita untuk melakukannya)

7. Buktikan ekuivalensi kalimat-kalimat dibawah ini tanpa menggunakan tabel kebenaran

a. (q ( p) ( (~p ( ~q)

b. (p ( (q ( r)) ( ((p ( q) ( r)

8. Ubahlah bentuk ~(p ( q) sehingga hanya memuat penghubung (, ( atau ~

2.3 Tautologi dan Kontradiksi

Tautologi adalah suatu bentuk kalimat yang selalu bernilai benar (T), Tidak peduli bagaimanapun nilai kebenaran masing-masing kalimat penyusunnya. Sebaliknya, Kontradiksi adalah suatu bentuk kalimat yang selalu bernilai salah (F), tidak peduli nilai kebenaran masing-masing kalimat penyusunnya.

Dalam tabel kebenaran, suatu Tautologi selalu bernilai T pada semua barisnya, dan kontradiksi selalu bernilai F pada semua barisnya. Kalau kalimat tautologi diturunkan lewat hukum-hukum yang ada maka pada akhirnya selalu menghasilkan T. Sebaliknya , Kontradisi akan selalu menghasilkan F.

9. Tunjukkan bahwa kalimat-kalimat di bawah ini adalah Tautologi dengan menggunakan tabel kebenaran.

a. (p ( q) ( q

b. q ( (p ( q)

Kesatuan dari 2 buah kalimat ekuivalen p dan q yang dihubungkan dengan penghubung ( selalu merupakan Tautologi karena jika p ( q maka p dan q selalu mempunyai nilai kebenaran yang sama. Jika p dan q mempunyai nilai kebenaran yang sama, maka p ( q selalu akan berniali benar.

10. Tunjukkan bahwa (p ( q) ( (~q ( ~p) berupakan Tautologi, tanpa menggunakan tabel kebenaran

2.4 Konvers, Invers, dan Kontraposisi

Misal diketahui implikasi p ( q

Konvers-nya adalah

q ( p

Invers-nya adalah

~p ( ~q

Kontraposisinya adalah ~q ( ~p

Suatu yang penting dalam logika adalah kenyataan bahwa suatu implikasi selalu ekuivalen dengan konraposisinya. Akan tetapi, tidak demikian dengan Invers dan konvers. Suatu implikasi tidak selalu ekuivalen dengan Invers ataupun Konvers-nya. Hal ini dapat dilihat pada tabel kebenaran yang tampak pada pada tabel berikut :

pq~p~qp ( qq ( p~p ( ~q~q ( ~p

TTFFTTTT

TFFTFTTF

FTTFTFFT

FFTTTTTT

Dalam tabel terlihat bahwa nilai kebenaran kolom p ( q selalu sama dengan nilai kebenaran kolom ~q ( ~p (Kontraposisi), tetapi tidak selalu sama dengan kolom q ( p (konvers) maupun kolom ~p ( ~q (invers).

Disimpulkan bahwa (p ( q) ( (~q ( ~p) merupakan suatu Tautologi.

11. Apakah Konvers, invers, dan Kontraposisi kalimat dibawah ini :

a. Jika A merpakan suatu bujursangkar, maka A merupakan suatu persegi panjang.

b. Jika n adalah bilangan prima > 2, maka n adalah bilangan ganjil

2.5 Inferensi Logika

Logika selalu berhubungan dengan pernyataan-pernyataan yang ditentukan nilai kebenarannya. Sering kali diinginkan untuk menentukan benar tidaknya kesimpulan berdasarkan sejumlah kalimat yang diketahui nilai kebenarannya.Argumen Valid dan Invalid

Argumen adalah rangkaian kalimat-kalimat. Semua kalimat-kalimat tersebut kecuali yang terakhir disebut Hipotesa (atau assumsi/premise). Kalimat terakhir disebut kesimpulan.

Secara umum, hipotesa dan kesimpulan dapat digambarkan sebagai berikut :

p1

p2

.

pn

( q } kesimpulan

(tanda ( q dibaca jadi q)

Suatu Argumen dikatakan Valid apabila untuk sembarang pernyataan yang disu yang disubstitusikan ke dalam hipotesa, jika semua hipotesa tersebut benar, maka kesimpulan juga benar. Sebaliknya, meskipun semua hipotesa benar tetapi ada kesimpulan yang salah, maka argumen tersebut dikatakan Invalid.

Kalau suatu argumen dan semua hipotesanya bernilai benar, maka kebenaran nilai konklusi dikatakan sebagai diinfernsikan (diturunkan) dari kebenaran hipotesa

Untuk mengecek apakah suatu argumen merupakan kalimat yang valid, dapat dilakukan langkah-langkah sebagai berikut :

1. Tentukan hipotesa dan kesimpulan kalimat

2. Buat tabel yang menunjukkan nilai kebenaran untuk semua hipotesa dan kesimpulan.

3. Carilah baris kritis, yaitu baris dimana semua hipotesa bernilai benar.

4. Dalam Baris kritis tersebut, jika semua nilai kesimpulan benar, maka argumen itu valid. Jika diantara baris kritis tersebut ada baris dengan nilai kesimpulan yang salah, maka argumen tersebut invalid.

Contoh :

Tentukan apakah Argumen di bawah ini Valid/Invalid.

a. p ( (q ( r)

b. p ( (q ( ~r)

~r

q ( (p ( r)

--------------

----------------

( p ( q

( p ( r

Penyelesaian :

a. Ada 2 Hipotesa, masing-masing p ( (q ( r) dan ~ r. Kesimpulannya adalah p ( q. Tabel kebenaran hipotesa-hipotesa dan kesimpulan adalah sbb :

Baris kepqrq ( rp ( (q ( r)~rp ( q

1. TTTTTFT

2. *TTFTTTT

3. TFTTTFT

4. *TFFFTTT

5. FTTTTFT

6. *FTFTTTT

7. FFTTTFF

8. FFFFFTF

Baris Kritis adalah baris 2, 4, dan 6 (baris yang semua hipotesanya bernilai T ). Pada baris-baris tersebut kesimpulannya juga bernilai T. Maka argumen tersebut bernilai valid.

b. silahkan anda coba sendiri.

2.5.1 Metode-Metode Inferensi

Pada bagian ini dipelajari beberapa metode infernsi, yaitu teknik untuk menurunkan kesimpulan berdasarkan hipotesayang ada, tanpa harus menggunakan tabel kebenaran.

1. Modus PonensPerhatikan implikasi bila p maka q yang diasumsikan bernilai benar. Apabila selanjutnya diketahui bahwa anteseden (p) benar, supaya implikasi p ( q benar, maka q juga harus bernilai benar. Infersi seperti itu disebut Modus Ponens.

Secara simbolik, Modus Ponens dapat dinyatakan sbb :

p ( q

p

---------

( q

Hal ini dapat dilihat dari tabel kebenaran yang tampak pada tabel berikut.

Baris kepqp ( qpq

1. *TTTTT

2. TFFTF

3. FTTFT

4. FFTFF

Baris Kritis adalah baris pertama. Pada baris tersebut, konklusi (q) bernilai T sehingga argumennya valid.

2. Modsus TollensBentuk Modus Tollens mirip dengan Modus Pones, hanya saja hipotesa kedua dan kesimpulan merupakan kontraposisi hipotesa pertama modus ponens. Hal ini mengingat kenyataan bahwa suatu implikasi selalu ekuivalen dengan kontraposisinya.

Secara simbolik, bentuk inferensi Modus Tollens adalah sebagai berikut :

p ( q

~q

---------

( ~p

Contoh:

Jika Zeus seorang manusia, maka ia dapat mati

Zeus tidak dapat mati

---------------------------------------------------------

( Zeus bukan seorang manusia.

3. Penambahan Disjungtif

Inferensi Penambahan Disjungtif didasarkan atas fakta bahwa suatu kalimat dapat digeneralisasikan dengan penghubung ( . Alasannya adalah karena penghubung ( bernilai benar jika salah satu komponennya bernilai benar.

Sebagai contoh : Ani suka jeruk (bernilai benar). Kalimat tersebut tetap bernilai benar jika ditambahkan kalimat lain dengan penghubung ( . Jadi kalimat Ani suka jeruk atau apel juga tetap bernilai benar dan tidak tergantung pa suka/tidaknya Ani akan apel.

Bentuk Simbolis metode Infernsi Penambahan Disjungtif adalah sebagai berikut :

p

q

a. ----------

b. ----------

(p ( q

( p ( q

4. Penyderhanaan Konjungtif

Inferensi penyederhanaan Konjungtif merupakan kebalikan dari inferensi Penambahan Disjungtif. Jika beberapa kalimat dihubungkan dengan penghubung ( , kalimat tersebut dapat diambil salah satunya secara Khusus. Penyempitan kalimat ini merupakan kebalikan dari penambahan Disjungtif yang merupakan perluasan kalimat.

Bentuk simbolis metode Inferensi penyederhanaan Konjungtif adalah sbb :

p ( q

p ( q

a. ----------

b. ----------

(p

( q

Contoh :

Lina menguasai bahasa Basic dan Pascal

-------------------------------------------------

( Lina mengusai bahasa Basic

5. Silogisme Disjungtif

Prinsip dasar Silogisme Disjungtif adalah kenyataan bahwa apabila kita diperhadapkan pada satu diantara 2 pilihan yang ditawarkan (A atau B), sedangkan kita tidak memilih A, Maka satu-satunya pilihan yang mungkin adalah memilih B. Hal ini sering dijumpai dalam kehidupan sehar-hari. Jika seseorang ditanyai oleh penjual warung : Kamu minum es jeruk atau es the?. Dan orang yang ditanya tersebut harus memilih salah satu, sedangkan ia tidak suka es jeruk, pastilah ia memilih es teh.

Secara simbolis, bentuk metode inferensi Silogisme Disjungtif adalah sebagai berikut :

p ( q

p ( q

a. ~p

b. ~q

----------

-----------

(q

(p

Contoh :

Kunci kamarku ada di sakuku atau tertinggal di rumah

Kunci kamarku tidak ada di sakuku

-----------------------------------------------------------------

( Kunci kamarku tertinggal di rumah

6. Silogisme Hipotesis

Prinsip Silogisme Hipotesis adalah sifat transitif pada implikasi. Jika implikasi p ( q dan q ( r keduanya bernilai benar, maka implikasi p ( r bernilai benar pula.

Secara simbolis, bentuk metode inferensi Silogisme Hipotesis adalah sbb :

p ( q

q ( r

----------

( p ( r

Contoh :

Jika 18486 habis dibagi 18, maka 18486 habis dibagi 9

Jika 18486 habis dibagi 9, maka jumlah digit-digitnya habis dibagi 3

-----------------------------------------------------------------------------------

( 18486 habis dibagi 18, maka jumlah digit-digitnya habis dibagi 9.

7. Dilema (Pembagian Dalam Beberapa Kasus)

Kadeng-kadang, dalam kalimat yang dihubungkan dengan penghubung ( , Masing-masing kalimat dapat mengimplikasikan sesuatu yang sama. Berdasrkan hal itu maka suatu kesimpulan dapat diambil.

Secara simbolis, bentuk metode infernsi Dilema adalah sebahgai berikut :

p ( q

p ( r

q ( r

---------

( r

Contoh :

Nanti malam Adi mengajak saya nonton atau mengajak saya makan di restoran

Jika Adi mengajak saya nonton, maka saya akan senang

Jika Adi mengajak saya makan di restoran, maka saya akan senang

---------------------------------------------------------------------------------

(Nanti malam saya akan senang

8. KonjungsiInferensi Konjungsi sebenarnya sudah dibahas pada sub-bab awal. Jika ada dua kalimat yang masing-masing benar, maka gabungan kedua kalimat tersebut dengan menggunakan ( (konjungsi) juga bernilai benar.

Bentuk Inferensi dengan Konjungsi adalah sbb :

p

q

------------

( p ( q

Kedelapan bentuk infernsi dapat dirngkas pada tabel berikut :

AturanBentuk Argumen

Modus Ponenp ( q

p

---------

( q

Modus Tollen

p ( q

~q

---------

( ~p

Penambahan Disjungtifp

--------

( p ( qq

--------

( p ( q

Penyederhanaan Konjungtifp ( q

------

(pp ( q

------

(q

Silogisme Disjungtifp ( q

~p

-------

( qp ( q

~q

-------

( p

Silogisme Hipotesisp ( q

q ( r

--------

(r

DilemaP ( q

p ( r

q ( r

--------

(r

Konjungsip

q

--------

( p ( q

Soal latihan :

12. Pada suatu hari, Anda hendak pergi ke kampus dan baru sadar bahwa Anda tidak memakai kacamata. Setelah mengingat-ingat, ada beberapa fakta yang Anda pastikan kebenaranya :

a. Jika kacamataku ada di meja dapur, maka aku pasti sudah melihatnya ketika sarapan pagi.

b. Aku membaca koran di ruang tamu atau akau membacanya di dapur.

c. Jika aku membaca koran di ruang tamu, maka pastilah kacamataku kuletakkan di meja tamu.

d. Aku tidak melihat kacamataku pada waktu sarapan pagi

e. Jika aku membaca buku di ranjang, maka kacamata kuletakkan di meja samping ranjang.

f. Jika aku membaca koran di dapur, maka kacamataku ada di meja dapur.

Berdasarkan fakta-fakta tersebut, tentukan dimana letak kacamata tersebut!

13. Buktikan Kevaidan Argumen di bawah ini dengan menggunakan prinsip=prinsip infernsi Logika.

p ( q

(p ( q) ( r

-----------------

( r

Bab III

ALJABAR BOOLE3.1. Konsep Dasar Aljabar Boolean

A. Definisi dan Aksioma

Definisi 6.1

Aljabar Boolean adalah sistem aljabar yang berisi set S dengan operasi penjumlahan (+) dan perkalian (() yang didefinsikan pada set itu sehingga setiap elemen-elemen x, y dan z dari S mempunyai sifat-sifat atau aksioma-aksioma berikut :

NOAKSIOMAAKSIOMASIFAT

1(x + y) ( S(x ( y) ( SClosure

2x + (y + z) = (x + y) + zx ( (y ( z) = (x ( y) ( zAsosiatif

3x + 0 = 0 + x = xx ( 1 = 1 ( x = xIdentitas

4x + y = y + xx ( y = y ( xKomutatif

5x + x = 1x ( x = 0Komplemen

6(x + y) ( z = x ( z + y ( zx ( (y + z) = x ( y + x ( zDistributuf

7x + (y ( z) = (x + y) ( (x + z)(x ( y) + z = (x + y) ( (y+z)Distributif

8(x + y) = x ( y(x ( y) = x + yDeMorgans

9 (x) = x

B. Prinsip Dualitas

Teorema 6.1

Untuk setiap elemen x, berlaku :

a). x + x = x dan b). x ( x = x

Bukti :

a). x + x = (x + x) ( (1)b). x ( x = x ( x + 0

= (x + x) ( (x + x)

= x ( x + x ( x

= x + (x ( x)

= x ( (x + x)

= x + 0

= x ( 1

= x

= x

Teorema 6.2

Untuk setiap elemen x, berlaku :

a). x + 1 = 1 dan b). x ( 0 = 0

Bukti :

a). x + 1 = x + (x + x)b). x ( 0 = x ( (x ( x)

= (x + x) + x

= (x ( x) ( x

= x + x

= x ( x

= 1

= 0

Teorema 6.3

Untuk setiap elemen x dan y, berlaku :

a). x + x ( y = x dan b). x ( (x + y) = x

(Hukum Penyerapan)

Bukti :

a). x + x ( y = x ( 1 + x ( yb). x ( (x + y) = x ( x + x ( y

= x ( (1 + y)

= x + x ( y

= x .1

= x ( 1 + x ( y

=

= x ( (1 + y)

= x ( 1

= x

Teorema 6.4

Untuk setiap elemen x dan y, berlaku :

a). (x + y) = x ( y dan b). (x ( y) = x + y

(Hukum DeMorgan)

Bukti :

a). Diketahui : (x + y) ( (x + y) = 0

Sehingga :(x + y) ( (x ( y) = 0

Bukti :

(x + y) ( (x ( y) = (x ( (x ( y)) + (y ( (x ( y))

= (x ( x) ( y + x ( (y ( y)

= 0 ( y + x ( 0

= 0

b). Diketahui : (x . y) + (x . y) = 1

Sehingga :(x ( y) + (x + y) = 1

Bukti :

(x ( y) + (x + y) = (x + (x + y)) ( (y + (x + y))

= ((x + x) + y) ( (x + (y + y))

= (1 + y) ( (x + 1)

= 1 ( 1 = 1

3.2. Fungsi Boolean

Definisi 6.2

Misalkan merupakan variabel-variabel aljabar Boolean. Fungsi Boolean dengan n variabel adalah fungsi yang dapat dibentuk dari aturan-aturan berikut :

1. Fungsi Konstan :

2. Fungsi Proyeksi : , i = 1,2,.......,n.

3. Fungsi Komplemen :

4. Fungsi Gabungan :

Definisi 6.3

Fungsi identitas adalah fungsi satu variabel, di mana f(x) = x.

Contoh :

Berikut ini adalah fungsi-fungsi Boolean dengan variabel x, y dan Z serta a yang merupakan seuatu elemen dalam aljabar :

f(x)= x + xa

g(x,y)= xy + xy + y

h(x,y,z)= axyz + yz + a + xy

Teorema 6.5

Jika f adalah suatu fungsi Boolean dengan satu variabel, maka untuk semua nilai x, adalah f(x) = f(1)x + f(0)x.

Kemungkinan-kemungkian bentuk f :

Kemungkinan 1.

f adalah fungsi konstan, f(x) = a

f(1)x + f(0)x = ax + ax = a(x+x) = a(1 = a = f(x)

Kemungkinan 2.

f adalah fungsi identitas,

f(1)x + f(0)x = 1x + 0x = x+0 = x = f(x)

Kemungkinan 3.

g(x)=(f(x))

g(x)=(f(x))= (f(1)(x + f(0)(x)

= (f(1)(x) ( (f(0)(x)------(menggunakan Hukum Demorgan)

= (f (1) + x) ( (f (0)+x))

= f (1)(f (0) + f (1)( x + x( f (0) + x( x

= f (1)(f (0)((1) + f (1)( x + x( f (0) + 0

= f (1)(f (0)((x+x) + f (1)( x + x( f (0)

= f (1)(f (0)(x+ f (1)(f (0)(x) + f (1)( x + x( f (0)

= f (1)(x(f (0) + f (1)(x + f (1)(f (0)(x) + f (0)(x

= f (1)(x + f (0)(x

= g(1)(x + g(0)(x

Kemungkinan 4.

h(x) = f(x) + g(x)

h(x) = f(x) + g(x) = f(1)(x + f(0)(x + g(1)(x + g(0)(x

= f(1)(x + g(1)(x + f(0)(x + g(0)(x

= (f(1) + g(1))(x + (f(0) + g(0))(x

= h(1)(x +h(0)(x

Kemungkinan 5.

k(x) = f(x)(g(x)

k(x) = f(x)(g(x) = (f(1)(x + f(0)(x)((g(1)(x + g(0)(x)

= f(1)(g(1)(x(x + f(1)(g(1)(x(x + f(0)(g(1)(x(x + f(0)(g(0)(x(x

= f(1)(g(1)(x + f(0)(g(0)(x

= k(1)(x +k(0)(x

Bentuk di atas adalah bentuk kanonik fungsi Boolean satu variabel. Dengan cara yang sama, jika f adalah fungsi Boolean dengan dua variabel, maka untuk nilai x dan y bentuk kanoniknya adalah sebagai berikut :

f(x,y) = f(1,1)(x(y + f(1,0)(x(y + f(0,1)(x(y + f(0,0)(x(y

Bentuk kanonik digunakan untuk menentukan apakah dua ekspresi merupakan fungsi yang sama. Seringkali fungsi Boolean dinyatakan dengan operasi yang berlebihan. Kita dapat mengkonversi bentuk fungsi Boolean menjadi bentuk minimum dengan fungsi yang masih menghasilkan nilai yang sama tetapi dengan jumlah operasi yang minimum.

Contoh :

Terdapat fungsi Boolean yang dituliskan dalam tabel kebenaran sebagai berikut :

xyzF

0000

0011

0100

0110

1001

1010

1100

1111

Fungsi pada tabel kebenaran tersebut dapat ditulis dalam bentuk aljabar :

(1). atau

atau

(2).

Bentuk (1) dan (2) merupakan fungsi standar, yaitu fungsi yang literalnya ditulis lengkap pada tiap suku. Bentuk (1) disebut SOP (Sum Of Product) / Minterm, sedangkan bentuk (2) disebut POS (Product Of Sum) / Maxterm.

Fungsi Boolean yang diekspresikan dalam bentuk SOP atau POS disebut bentuk Kanonik.

Tabel bentuk standar dan kanonik fungsi Boolean dengan 3 variabel. V xyzSum Of Product (SOPProduct Of Sum (POS)

TermNilaiTermNilai

000x(y(zm0x + y + zM0

001x(y(zm1x + y + zM1

010x(y(zm2x + y + zM2

011x(y(xm3x + y + xM3

100x(y(zm4x + y + zM4

101x (y(zm5x + y + zM5

110x(y(zm6x + y + zM6

111x(y(zm7x + y + zM7

3.3. Komplemen Fungsi

Komplemen dari fungsi Boolean F adalah F, yaitu dengan menukarkan nilai 0 menjadi 1, atau nilai 1 menjadi 0.

Terdapat dua cara untuk memperoleh fungsi komplemen, yaitu :

1. Penerapan hukum De Morgan yang diperluas.

Hukum De Morgan yang diperluas :

(x + y + z) = (x+A) di mana A = y + z ( A = (y + z) = y( z

= x(A

= x( y( z

Rumus hukum De Morgan yang diperluas.

a.

b.

Contoh :

Diketahui fungsi-fungsi Boolean : F1 = xyz + xyz dan F2 = x(yz + yz).

Tentukan dan dengan De Morgan.

Penyelesaian :

= (xyz + xyz)

= (x(yz + yz))

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

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

2. Penerapan prinsip Dualitas.

Pencarian fungsi komplemen dengan prinsip dualitas dilakukan sebagai berikut :

a. Cari bentuk dualnya dengan prinsip dualitas.

b. Lakukan komplemen terhadap tiap literal.

Contoh :

Tentukan F dari fungsi Boolean F = x(yz + yz)

Penyelesaian :

Dual dari F adalah : x + (y + z)((y + z)

Komplemen literal dari dual F adalah F = x+(y + z)((y + z)

3.4. Konversi Bentuk fungsi

Contoh :

a. Cari bentuk kanonik dari f(x,y) = x

Jawab :

Bentuk kanonik SOP (Minterm):Bentuk kanonik POS (Maxterm):

f(x,y) = xf(x,y) = x

= x((y + y)f (x,y)= x+(y.y)

= x(y + x(yf(x,y)= (x + y) ( (x + y)

= m0 + m1

= M2 ( M3

= (m(0,1)

= (M(2,3)

b. Cari bentuk kanonik dari f(x,y,z) = y + xy + xyz

Jawab :

f(x,y,z) = y + xy + xyz

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

= (xy+xy)((z+z) + xyz + xyz +xyz

= xyz + xyz + xyz + xyz + xyz + xyz + xyz

= m5 + m4 + m1 + m0 + m7 + m6 + m2

= m0 + m1 + m2 + m4 + m5 + m6 + m7

= (m(0,1,2,4,5,6,7)

atau

f(x,y,z) = y + xy + xyz

= (y + xy) + xyz

= ((y + xy) + y)(((y+xy)+xz)

= (y + y((x+1))((((y+x)((y+y))+xz)

= (y + y)(((y+x)+xz)

= y+x+xz

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

= y + x + z

= x + y + z

= M3 =(M(3)

c. Cari bentuk kanonik dari f(x,y,z) = xyz + xyz + xyz

Jawab :

Cara 1:

f(x,y) = xyz + xyz + xyz

Tabel fungsi f(x,y) di atas :

xyzMintermMaxtermF

000x(y(zx + y + z0

001x(y(zx + y + z1

010x(y(zx + y + z0

011x(y(xx + y + x0

100x(y(zx + y + z1

101x (y(zx + y + z0

110x(y(zx + y + z0

111x(y(zx + y + z1

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

= M0(M2(M3(M5(M6=(M(0,2,3,5,6)

Cara 2:

Dari tabel diperoleh :

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

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

Sehingga :

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

= M0(M2(M3(M5(M6=(M(0,2,3,5,6)

BAB IV

PENYEDERHANAAN FUNGSI BOOLEAN

Pada fungsi yang kompleks, kadangkala terdapat jenis operasi yang dapat disederhanakan. Penyederhanaan dilakukan untuk memperoleh fungsi yang masih menghasilkan nilai yang sama, tetapi dengan jumlah operasi yang minimum. Bentuk fungsi minimum ini dimaksudkan untuk memperoleh biaya minimum dalam pembuatan sirkuit elektronis dengan kinerja yang lebih cepat dalam pengoperasian.

Dalam penyederhanaan ini, kita asumsikan bahwa :

a. Bentuk yang paling sederhana adalah bentuk SOP

b. Operasi-operasi yang digunakan adalah : + (penjumlahan); ( (perkalian) dan (komplemen).

Terdapat tiga cara dalam penyederhanaan bentuk fungsi, yaitu :

4.1 Metode Aljabar

Penyederhanaan secara aljabar mempunyai karakteristik :

Tidak ada pegangan, bersifat trial and error Menggunakan aksioma teorema aljabar Boolean

Contoh :

Sederhanakan fungsi Boolean berikut :

a. F(x,y,z) = xyz + xyz + xy

b. F(x,y,z) = xy + xz + yz

Jawab :

a. F(x,y,z) = xyz + xyz + xy

= xz(y + y) + xy

= xz(1 + xy

= xz + xy

c. F(x,y,z) = xy + xz + yz

= xy + xz + yz(x + x)

= xy + xz + xyz + xyz

= xy + xyz + xz + xyz

= xy(1+z)+xz(1+y)

= xy + xz

4.2 Metode Peta Karnaugh

Rangkaian logika digital yang kompleks merupakan implementasi dari fungsi Boolean yang memberikan ekspresi yang kompleks pula. Sangat sulit untuk melakukan penyederhanaan fungsi yang kompleks dengan metode aljabar. Metode pemetaan yang dikenalkan oleh Karnaugh dapat digunakan untuk meminimasi fungsi yang kompleks. Metode pemetaan ini dikenal dengan nama Peta Karnaugh (Karnaugh Map).

Peta Karnaugh digambarkan dengan kotak bujur sangkar, di mana setiap kotak merepresentasikan minterm. Jumlah kotak dan minterm tergatung pada berapa jumlah ysteme dari fungsi Boolean. Jika terdapat N ysteme dalam fungsi Boolean, maka diimplementasikan dengan kotak.

a. Peta Karnaugh Dua dan Tiga Variabel

Untuk 2 variabel terdapat 4 bentuk minterm dengan 4 kotak bujur sangkar, sedangkan untuk 3 variabel terdapat 8 bentuk minterm dengan 8 kotak bujur sangkar, seperti yang ditunjukkan gambar berikut :

y x01y x01

0m0m1(0xyxy

1m2m31xyxy

2. (b)

Gambar 7.1. Peta Karnaugh dengan 2 variabel

yz x00011110yz x00011110

0m0m1m3m2(0xyzxyzxyzxyz

1m4m5m7m61xyzxyzxyzxyz

2. (b)

Gambar 7.2. Peta Karnaugh dengan 3 variabel

Cara Penggunaan Peta Karnaugh

Contoh :

Sederhanakan fungsi-fungsi berikut dengan Peta Karnaugh

1. F(x,y) = xy + xy

2. F(x,y,z) = xyz + xyz + xyz + xyz + xyz + xyz

Penyelesaian :

1. F(x,y) = xy + xy+xy

= m1 +m2 + m3 = (m(1,2,3)

Sesuai dengan bentuk minterm, maka 3 bujur sangkar dalam Peta Karnaugh 2 dimensi diisi dengan 1 pada bujur sangkar kecil seperti berikut :

y x01y x01

01(01

111111

Gambar 7.3 (a)(b)

Selanjutnya dilakukan pengelompokan semua 1 yang ada dengan membuat kumpulan kotak bujur sangkar atau persegi panjang seperti terlihat pada gambar 7.3 (b).

Cara menentukan bentuk sederhana dari hasil pengelompokan adalah :

Carilah variabel mana saja yang memiliki nilai yang sama dalam kelompok tersebut, sebagai contoh kelompok A. Pada kelompok A, variabel yang memiliki nilai yang sama adalah variabel y dengan harga 1. pada kelompok B, variabel yang memiliki nilai yang sama adalah variabel x dengan harga 1.

Selanjutnya menentukan bentuk hasil pengelompokan di atas. Pada contoh di atas, hasil kelompok A adalah y dan hasil kelompok B adalah x. Hasil bentuk sederhana dari contoh di atas adalah F(x,y) = A + B = y + x

2. F(x,y,z) = xyz + xyz + xyz + xyz + xyz + xyz

yz x00011110yz x00011110

01111(01111

111111

F(x,y,z) = x + z

b. Peta Karnaugh Empat Variabel

Bentuk Peta Karnaugh untuk fungsi Boolean 4 variabel F(w,x,y,z) adalah :

yz wx00011110yz wx00011110

00m0m1m3m2(00wxyzwxyzwxyzwxyz

01m4m5m7m601wxyzwxyzwxyzwxyz

11m12m13m15m1411wxyzwxyzxyzwxyz

10m8m9m11m1010wxyzwxyzwxyzwxyz

Contoh :

Sederhanakan fungsi Boolean F (w,x,y,z) = ( m(0,1,2,3,4,6,8,9,10,11,12,13,14) adalah

Jawab :

yz wx00011110

001111

0111

11111

101111

F(x,y,z) = x + z + wy

c. Peta Karnaugh Lima dan Enam Variabel

Bentuk Peta Karnaugh untuk fungsi Boolean 5 variabel F(v,w,x,y,z) adalah :

xyz vw000001011010110111101100

00m0m1m3m2m6m7m5m4

01m8m9m11m10m14m15m13m12

11m24m25m27m26m30m31m29m28

10m16m17m19m18m22m23m21m20

Contoh :

Sederhanakan fungsi Boolean F(v,w,x,y,z) = ( m(0,3,7,8,11,15,16,17,20,21,24,25) adalah ..

Jawab :

xyz vw000001011010110111101100

00111

01111

1111

101111

F(v,w,x,y,z) = xyz + vyz + vx + xwy

Penentuan kelompok dapat dilakukan dengan memperlakukan ystem cermin terhadap garis pembatas seperti pada kolom B di atas.

Bentuk Peta Karnaugh untuk fungsi Boolean 5 variabel adalah :

xyz uvw000001011010110111101100

000

001

011

010

110

111

101

100

Contoh :

Sederhanakan fungsi Boolean berikut :

F = ( m(8,9,10,11,12,13,14,15,24,25,26,27,28,29,30,31,40,41,46,47,56,57,62,63)

4.3 Metode Tabulasi Quine-Mc.Cluskey

Dengan Peta Karnaugh, penyelesaian persamaan lebih dari empat variabel adalah kompleks. Metode tabulasi dari Quine-Mc.Cluskey dapat membantuk menyelesaiakan persamaan yang kompleks tersebut.

Metode tabulasi Quine-Mc.Cluskey terdiri dari dua bagian, yaitu :

a. Menentukan term-term sebagai kandidat (prime implicant)

b. Memilih prime implicant untuk menentukan ekspresi dengan jumlah lireal sedikit.

Contoh :

Sederhanakan dengan metode tabulasi

F(w,x,y,z)=(m(0,1,2,8,10,11,14,15)

Jawab:

1. Menentukan Prime Implicant

Langkah-langkah penyelesaian :

a. Kelompokkan representasi biner untuk tiap minterm menurut digit 1 :

Desimal 0 s/d 15 berarti nilai maksimum 15 sehingga banyaknya digit biner yang memenuhi 24 = 16

Tabel konversi :

DesimalBiner

wxyz

00000

10001

20010

81000

101010

111011

141110

151111

Dari tabel konversi tersebut dapat dilihat bahwa jumlah digit 1 adalah :

Jumlah Digit 1Desimal

00

11,2,8

210

311,14

415

Jadi Tabel Kelompoknya adalah :

DesimalwxyzPilih

00000(

10001(

20010(

81000(

101010(

111011(

141110(

151111(

b. Dari dua minterm yang berbeda digit 1, dapat dikombinasikan dengan saling menghilangkan. Minterm dari satu bagian dengan bagian lainnya jika mempunyai nilai bit yang sama dalam semua posisi kecuali satu posisi. Satu posisi yang berbeda tersebut diganti dengan tanda -.

Misalkan,

Bagian I : 0 0 0 0

Bagian II: 0 0 0 1

Menjadi: 0 0 0

Sehingga didapatkan tabel kelompok baru ;

DesimalwxyzPilih

0,1000-*

0,200-0(

0,8-000(

2,10-010(

8,1010-0(

10,11101-(

10,141-10(

11,151-11(

14,15111-(

Tanda ( berarti minterm tersebut dipilih untuk langkah berikutnya.

c. Kelompokkan hasil minterm langkah (b) seperti pada langkah (a)

d. Ulangi langkah (b) dan (c) sampai minterm dari setiap bagian tidak saling menghilangkan.

DesimalwxyzPilih

(0,2),(8,10)-0-0*

(0,8),(2,10)-000

(10,11),(14,15)-010*

(10,14),(11,15)10-0

2. Memilih Prime Implicant

Prime Implicant ditentukan dengan memilih setiap suku tanpa tanda ( atau dengan tanda *. yaitu :

wxyz

000-wxy

-0-0xz

1-1-wy

Jadi bentuk sederhana dari fungsi boolean F(w,x,y,z)=(m(0,1,2,8,10,11,14,15) adalah :

F(w,x,y,z) = wxy + wz + wy}hipotesa

C

B

A

y

x

y

x

z

B

A

A

B

y

x

w

z

A

B

C

x

v

w

z

z

y

A

B

C

D

x

w

v

u

w

z

z

y

S

STMIK Sinus SkaiWawan Laksito YSSTMIK Sinus Ska

Wawan Laksito YS

_1104060038.unknown

_1104132634.unknown

_1104137538.unknown

_1400483190.unknown

_1104146992.unknown

_1104133080.unknown

_1104133097.unknown

_1104132727.unknown

_1104060193.unknown

_1104130734.unknown

_1104060131.unknown

_1104059099.unknown

_1104059932.unknown

_1104058962.unknown

dasar logika

Documents