LOGIKA PROPOSIONAL

96
LOGIKA INFORMATIKA NAMA : MAULANA AKHSAN NIM : 4611412010 PRODI : TEKNIK INFORMATIKA JURUSAN : ILMU KOMPUTER

description

224234234

Transcript of LOGIKA PROPOSIONAL

Page 1: LOGIKA  PROPOSIONAL

LOGIKA INFORMATIKA

NAMA : MAULANA AKHSAN

NIM : 4611412010

PRODI : TEKNIK INFORMATIKA

JURUSAN : ILMU KOMPUTER

Page 2: LOGIKA  PROPOSIONAL

LOGIKA PROPOSIONAL

• Logika adalah suatu system berbasis proposisi.

• Suatu proposisi adalah suatu pernyataan (statement) yang dapat ber”nilai” Benar (true) atau

Salah (false) dan tidak keduanya.

• Dikatakan bahwa nilai kebenaran daripada suatu proposisi adalah salah satu dari benar (true

disajikan dengan T) atau salah (false disajikan dengan F).

• Dalam untaian digital (digital circuits) disajikan dengan 0 dan 1

• Variabel-variabel tersebut diatas dihubungkan dengan menggunakan penghubung logis yang

disebut operator atau functor.

Sebagai contoh :

1) Saya mempunyai uang dan saya lapar

2) Jika balok mempunyai berat jenis lebih besar dari 1 maka ia akan tenggelam diair.

3) Ir. Sukarno presiden pertama RI dan ia proklamator negara RI

4) Saya berangkat naik becat atau naik angkot.

5) Lampu mobil mati karena plentongnya mati atau kabelnya putus.

Perhatikan kalimat-kalimat sebagai berikut :

1) Tutuplah pintu itu

2) Dilarang merokok

3) Nilai daripada x terletak diantara nol dan satu Kalimat-kalimat tersebut tidak dimasukkan

dalam pembicaraan kita karena mereka tidak dapat ber “nilai” benar ataupun salah sedang yang

terakhir tidak dimasukkan disini tetapi masuk dalam logika predikat.

The Statement/Proposition Game

• “Gajah lebih besar daripada tikus.”

• Apakah ini suatu pernyataan? yes

• Apakah ini suatu proposisi? yes

• Apa nilai kebenaran daripada proposisi tersebut? True

Page 3: LOGIKA  PROPOSIONAL

The Statement/Proposition Game

• “520 < 111”

• Apakah ini suatu pernyataan ? yes

• Apakah ini suatu proposisi? yes

• Apa nilai kebenaran daripada proposisi tersebut? False

• “y > 5”

• Apakah ini suatu statement? Yes

• Apakah ini suatu proposisi? NO

• Nilai kebenarannya tergantung pada nilai daripada y , tetapi nilai ini tidak diberikan (not

specified).Kita sebut tipe pernyataan ini suatu fungsi proposisional atau kalimat terbuka.

Definisi . Proposisi adalah kalimat deklaratif (atau pernyata an) yang memiliki hanya satu nilai

kebenaran yaitu banar saja atau salah saja, akan tetapi tidak keduanya.

Proposisi yang bukan hasil kombinasi dari proposisi-propo sisi disebut atom.

Jika atom-atom akan dikombinasikan untuk memperoleh proposisi baru maka diperlukan

operator logika atau operator sambung yang dilambangkan dng simbol :

1). : “not”, atau “negasi”

2). : “and”, atau “konjungsi”

3). : “or” , atau “disjungsi” atau “inclusive or”

4). : “xor”, atau “exclusive or”

5). : “implies”, atau “Jika … maka…”, atau “implikasi kondisional”

6). : “jika dan hanya jika”, atau “bikondisional”

Page 4: LOGIKA  PROPOSIONAL

Logika Proposisional

Penggandeng Logis (Logical Connectives)

1. Negasi (not)

Jika p sebarang proposisi, pernyataan “not p” atau “negasi dari pada p” akan bernilai F jika p

bernilai T dan sebaliknya.

Dan ditulis dengan :

p

( “” disebut operator unary/monadika)dan akan digambarkan dengan tabel kebenaran

sebagai berikut :

2. Konjungsi/conjunction (and)

Konjungsi adalah suatu operator binary atau diadika (diadic). Jika p dan q suatu proposisi,

pernyataan p and q akan bernilai kebenaran T jika dan hanya jika kedua p dan q mempunyai

nilai kebenaran T, dan ditulis dengan :

p q

dimana operatornya terletak diantara kedua variabel (operand) tersebut dan mempunyai tabel

kebenaran seperti terlihat pada slide berikut :

Tabel kebenaran juga dapat disajikan dengan suatu

bentuk dua dimensi sebagai berikut :

P p

T F

F T

p Q p^q

T T T

T F F

F T F

F F F

p ˄ q T F q

T T F

F F F

P

Page 5: LOGIKA  PROPOSIONAL

• Bentuk terakhir ini hanya dapat digunakan hanya untuk fungsi dua variabel

• Perhatikan bahwa untuk kalimat “Benda ini berwarna merah” dan “Benda ini berwarna

putih” jika digandeng dengan “and” maka berbunyi “Benda ini berwarna merah “and”

putih” yang artinya lain dengan “Benda ini berwarna merah and Benda ini berwarna

putih”, jelaskan !!

• Sifatnya : 1) Komutatif ( p q = q p)

2) Asosiatif ( (pq)r = p(qr) )

• Operand daripada suatu kunjungsi juga disebut dengan conjunct.

3. Disjungsi (or)

Disjungsi yang juga ada yang menyebut dengan alternatif yang bersesuaian dengan bentuk

“Salah satu dari … atau ….” (“Either.. Or..) . Per nyataan “p or q” bernilai T jika dan hanya jika

salah satu p atau q (atau keduanya) bernilai T. Ditulis : p q

dan mempunyai tabel kebenaran seperti berikut:

Sifat :

1) Komutatif ( p q = q p )

2) Asosiatif ( (p q) r = p (q r) )

Perhatikan bahwa terdapat dua pengertian or yaitu “inclusif or” dan “exclusive or”. Sebagai

contoh :

“Pintu rumah terbuka” or “jendela rumah terbuka”. Hal tersebut dapat keduanya

“Suta pergi kekantor naik becak” or “Suta pergi kekantor naik angkot”. Hal tersebut tidak

mungkin keduanya.

Contoh pertama “or inclusive” dan disimbolkan dengan

Contoh kedua “or exclusive” atau “non-equivalen” dan disimbolkan dengan

( atau XOR atau )

P q p q

T T T

T F T

F T T

F F F

Page 6: LOGIKA  PROPOSIONAL

4. Implikasi (Implication)

Arti daripada pernyataan “If p then q” atau “p implies q” atau “q if p” atau “p hanya jika q”

atau “q sarat perlu untuk p” atau “p sarat cukup untuk q” adalah T jika salah satu dari p bernilai

T dan q bernilai T atau jika p bernilai F. Jika tidak demikian, yaitu p bernilai T dan q bernilai F,

maka nilai F. Ditulis :

p q

dan tabel kebenarannya seperti pada slide berikut (ada yang menggunakan simbol )

Untuk penjelasan ini maka perhatikan kalimat : “Jika Anita pergi keluar negeri maka ia

mempunyai passport”

Penjelasannya adalah sebagai berikut :

1) Jika Anita keluar negeri ( T ) dan Ia mempunyai passport (T), maka legal (T)

2) Jika Anita keluar negeri (T) dan Ia tidak mempu nyai passport (F), maka illegal (F)

3) Jika Anita tidak keluar negeri (F) dan ia mempu nyai passport (T), maka legal (T)

4) Jika Anita tidak keluar negeri (F) dan ia tidak mempunyai passport (F), maka legal (T)

kondisional konversi inversi kontrapositif

P q p q q p p q q p

T T T T T T

T F F T T F

F T T F F T

F F T T T T

Perhatikan bahwa : pernyataan p q selalu mempunyai tabel kebenaran dng (p) q dan juga

dengan (pq), (buat tabel kebe narannya)

Contoh penggunaannya : Buktikan bahwa jika x bilangan real maka jika x^2 bilangan gasal

maka x bilangan gasal.

Bukti andaikan x genap maka x = 2n dimana n sebarang bilangan real. X^2 = (2n)^2= 4n^2 =

2(2n^2) yang juga bilangan genap. Sehingga didapat, dengan kontraposistif, terbukti.

P Q p q

T T T

T F F

F T T

F F T

Page 7: LOGIKA  PROPOSIONAL

5. Ekuivalensi

Pernyataan “ p ekuivalen dengan q” mempunyai nilai kebenaran T jika dan hanya jika p dan q

mempunyai nilai kebenaran yang sama ditulis dengan simbol :

p q

dan tabel kebenarannya seperti berikut ( ada yang menggunakan simbol )

Sifat :

1) Komutatif ; ( p q = q p)

2) Asosiatif ; ( (p q) r = p (q r) )

3) Pernyataan (p q) mempunyai tabel kebenaran yang sama dengan pernyataan p q

(Tunjukan)

Perhatikan bahwa ia juga dapat dipikirkan sebagai pernyataan “ p jika dan hanya jika q”

Pernyataan p q disebut juga dengan bikondisional daripada p dan q, sebab ia selalu

mempunyai tabel kebenaran sama-dng (p q ) (q p) atau (pq) (pq)

Ditulis dengan p q =T (p q) (p q)

Notasi jumlahan dan produk Seperti pada aljabar maka didapat :

p q p q

T T T

T F F

F T F

F F T

Page 8: LOGIKA  PROPOSIONAL

Prioritas Operator

• Terkuat monadika ()

• Untuk diadika terkuat (), kemudian () dan berikutnya () dan yang lainnya

berikutnya lagi seperti misalnya ()

• Contoh :

“Saya lapar saya sedih saya bahagia saya telah kekenyangan” berarti

“(Saya lapar saya sedih) (saya bahagia saya telah kekenyangan)”

Mana yang pernyataan dan mana yang bukan

1. Ngawi adalah ibukota propinsi Jawa Timur.(P)

2. Dilarang merokok(B)

3. 119 adalah bilangan bulat(P)

4. Buka pintu(B)

5. Logika informatika adalah mudah(P)

6. Yogya kota pelajar(P)

7. Makanlah yang banyak(B)

8. Sesama cabup tak boleh saling mendahului(B)

9. Buatlah daftar pernyataan sebanyak 50 buah(B)

Tuliskan kalimat dibawah ini dengan simbol logika

a. Saya akan berlibur ke Bali hanya jika saya lulus ujian

b. Sarat perlu agar 273 habis dibagi 3 adalah 273 merupakan bilangan prima

c. Saya akan memberi anda uang apabila saya lulus ujian atau saya mendapat hadiah TTS

Jawab :

a. P = saya berlibur ke Bali, Q = Saya lulus ujian Kalimatnya menjadi : P Q

b. P = 273 habis dibagi 3, Q = 273 merupakan bilangan primaKalimatnya menjadi :

P Q

Page 9: LOGIKA  PROPOSIONAL

c. P = Saya memberi Anda uang, Q = Saya lulus ujian, dan R = saya mendapat hadiah TTS

.Kalimatnya menjadi : P Q R

Tentukan nilai kebenaran pernyataan-pernyataan dibawah ini :

a. Jika Jakarta bukan ibukota RI, maka 9 juga bukan bilangan prima

b. 2+2 = 2x2 hanya bila 2 =0

c. 2<3 merupakan syarat cukup untuk 2x2 < 3x3

jawaban :

a. Benar, karena anteseden salah (Jakarta bukan ibu kota RI)

b. Salah, karena anteseden (2+2 = 2x2) benar sedangkan konsekuennya (2 = 0 ) salah

c. Benar, karena konsekuennya (2x2 <3x3) benar

3. Tentukan nilai kebenaran daripada :

a. Syarat perlu dan cukup agar 7 merupakan bilangan prima adalah Kebumen berada di Jawa

Timur B ↔ S =S

b. Apabila 12 habis dibagi 4 ekuivalen dengan 12 bilangan bilangan genap maka

(a+b)^2 = a^2 + 2ab +b^2 B → B = B

4. Tuliskan dengan simbol logika kalimat-kalimat dibawah ini :

a. Matahari sangat verah dan kelembabannya tidak tinggi p ^ q

b. Jika saya dapat menyelesaikan koreksi saya sebelum makan malam dan tidak hujan, maka

saya akan pergi nonton tonil (p ^ q) → r

c. Jika Anda tidak menjumpai saya besok, berarti saya sudah pergi ke Bandung.¬ p →q

d. Syarat perlu dan cukup agar bilangan a merupakan bilangan prima adalah a merupakan

bilangan gasal atau sama dengan 2 p ↔ (q ˅ r)

Page 10: LOGIKA  PROPOSIONAL

Buatlah table kebenaran!

1.(p ^ ¬ q) v r

P q r p˄¬q (p˄¬q)˅r

T T T F T

T T F F F

T F T F F

T F F T T

F T T F T

F T F F F

F F T F T

F F F F F

2. .(p ˅ ¬ q) ˄ (¬ p v q )

P Q R p˅¬q ¬p˅q (p˅¬q)˄(¬p˅q)

T T T T T T

T T F T T T

T F T T F F

T F F T F F

F T T F T F

F T F F T F

F F T T T T

F F F T T T

3.(p → q) ˄ r

P q r p→q (p→q)˄r

T T T T T

T T F T F

T F T F F

T F F F F

F T T T T

F T F T F

F F T T T

F F F T F

Page 11: LOGIKA  PROPOSIONAL

4.(¬ q→ ¬ p) ˄ r

P q r (¬q→¬p) (¬q→¬p)˄r

T T T T T

T T F T F

T F T F F

T F F F F

F T T T T

F T F T F

F F T T T

F F F T F

Page 12: LOGIKA  PROPOSIONAL

Contoh :

1. Notasi Polandia : Epq

Disajikan dalam notasi yang lain.

a. p q b. p q c. p q

2. Notasi Polandia : CKpqr

Disajikan dalam notasi yang lain.

C(p&q)r = (p&q) r

3. Notasi Polandia : CpCpr

Disajikan dalam notasi yang lain.

Cp (p r) = p (p r)

4. Notasi Polandia : E CKpqr CpCpr

Disajikan dalam notasi yang lain.

Cari tanda dominan : E yang sama dengan

Ruas kiri : C Kpq r

Tanda dominan : C yang sm dng

Tanda berikutnya : K yg sm dng ( ada dengan &)

didapat : p q C (pq) r

didapat : (pq) r

Ruas kanan : C p Cpr

didapat : C p (p r)

di dapat : p (p r)

Akhirnya didapat : ((p q) r) (p (p r))

Page 13: LOGIKA  PROPOSIONAL

Contoh :

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

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

C ( K p q ) r ( ( p r ) q

C ( K p q ) r ( ( ( p ( N r ) ) q )

C ( K p q ) r ( K p ( N r ) q )

C ( K p q ) r ( K p ( N r ) ( N q ) )

C ( K p q ) r ( C ( K p ( N r ) ( N q ) )

E ( C ( K p q ) r ( C ( K p ( N r ) ( N q ) ) )

E C Kpq r C Kp N r N q

Latihan

ubahlah menjadi notasi operator logika polandia

1. ¬(p˅q)→r menjadi : CNApqr

2. ((p˄¬q)˅r)→(¬p˄q)↔r menjadi : CAKpNqrENKpq

3. ((¬(p˅q)˄¬r))↔r)↔(p→(q˄r)) menjadi :EEKNApqNrrCpKqr

ubahlah menjadi notasi operator logika biasa

1. ECApqrNp menjadi : ((p˅q)→r)↔¬p

2. ECKprApNrq menjadi : (p˄r)→(p˅¬r)↔q

3. ECrACNKprqNpNq menjadi : r→(¬(p˄r)→q)˅¬p))↔¬q

contoh :

1) ¬(p˅q) =NApq

2) ((P˅q)→r)↔(p˄q) = ECApqrKpq

3) NCApqr = ¬((p˅q)→r

4) ECApqKqrNCApNrq =((p˅q)→(q˄r))↔¬((p˅¬r))

Page 14: LOGIKA  PROPOSIONAL

Prioritas dp Operator.

Seperti pd ungkapan dlm ilmu hitung, maka didalam operator logika pun terdapat prioritas

sebagai berikut :

1). Operator mempunyai prioritastertinggi

2). Operator berprioritas berikutnya

3). Operator berprioritas berikutnya

4). Operator berprioritas berikunya

5). Dan seterusnya operator yang lain termasuk dan seterusnya.

Contoh

1). p q r s dapat diinterpretasikan sebagai (p q) (r s)

2). p q akan diinterpretasikan dengan (p) q

3). “Saya lapar” dan “saya malas” atau “Saya bahagia” dan“Saya telah makan enak” diartikan

sebagai ????

Operator yang mempunyai prioritas sama dilakukan dengan urutan dari kiri ke kakan seperti

terlihat dalam contoh dibawah ini >

Contoh

1). p q r s t u v

Diartikan sebagai :

(((((p q) r) s) t) u) v

Tabel kebenaran untuk bentuk yang komplek

1. ¬ (p ^ q) ↔ r

P ^ q ↔ r

2 1 3 1 4 1

F T F T F T

F T F T T F

F T F F F T

F T F F T F

Page 15: LOGIKA  PROPOSIONAL

T F T T T T

T F T T F F

T F F F F T

T F F F T F

2. ¬ (p ˅ q) ˄ (¬ p v ¬r )

¬ (p ˅ q) ˄ (¬ p ˅ ¬ r

4 1 3 1 5 2 1 3 2 1

F T T T F F T F F T

F T T T F F T T T F

F T T F F F T F F T

F T T F F F T T T F

F F T T T T F F F T

F F T T T T F T T F

T F T F T T F F F T

T F F F T T F T T F

3.p → q ¬ r

P → Q → ¬ r

1 3 1 4 2 1

T T T F F T

T T T T T F

T F F T F T

T F F T T F

F T T F F T

F T T T T F

F T F F F T

F T F F T F

Page 16: LOGIKA  PROPOSIONAL

4.¬ p ˄ ¬q v q ˄ ¬r

symbol “ ” berarti bahwa pada table kebenaran dua formula mempunyai nilai kebenaran yang

sama (identik)

contoh :

1. p→q ¬p˅q

2. ¬(p→q) p˄¬q

3. p˄(¬p˅q) = (p˄¬p)˅(p˄q)

= F ˅(p˄q)

= p˄q

¬ p ˄ ¬ q v q ^ ¬ r

2 1 3 2 1 4 1 3 2 1

F T F F T F T F F T

F T F T T T T T T F

T T F F F F F F F T

F T F T F F F F T F

F F T F T F T F F T

F F T T T T T T T F

T F T F F T F F F T

T F T T F T F F T F

Page 17: LOGIKA  PROPOSIONAL

Aljabar Proposisi

Aljabar proposisi adalah hukum-hukum aljabar yang dapat digunakan dalam proposisi.

Hukum-hukum tersebut adalah:

1. Idempoten 3. Distributif

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

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

2. Assosiatif 4. Komutatif

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

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

5. Identitas 7. Komplemen

p f p p ~p t

p t t p ~p f

p f f ~t f

p t p ~f t

6. Involution 8. De Morgan‟s

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

~(p q) ~p ~q

Contoh pemakaian hukum aljabar proposisi

Page 18: LOGIKA  PROPOSIONAL

Sederhanakan proposisi berikut ini:

1. p (p q)

p (p q) (p f) (p q) …( hk.identitas )

p (f q) …( hk.distribusi )

p f …( hk.identitas )

p …( hk.identitas )

2. p (p q)

p (p q) (p ˄ T) ˅ (p ˄ q) …( hk.identitas )

p ˄ (t q) …( hk.distribusi )

p t …( hk.identitas )

p …( hk.identitas )

Page 19: LOGIKA  PROPOSIONAL

Interpretasi

Andaikan P adalah formula proposisi ( perhatikan disini digunakan huruf murda/capital untuk

menyajikan suatu formula sedang huruf kecil untuk variabel proposisi). Suatu interpretasi P

adalah suatu penugasan (assignment) nilai kebenaran pada semua variabel proposisi

( pemberian nilai kebenaran) yang muncul pada P. Perhatikan bahwa setiap baris pada tabel

kebenaran adalah suatu interpretasi.Untuk setiap interpretasi maka P mempunyai nilai

kebenaran(lihat bahwa setiap baris P mempunyai nilai T atau F)

Andaikan S suatu himpunan formula proposisi, suatu interpretasi disebut model S jika setiap

anggota S bernilai TRUE untuk interpretasi tersebut.

Contoh : Andaikan S adalah himpunan formula proposisi :

{ p q , q r , r s }

dan interpretasi :

I1 : {p=T,q=F,r=T,s=T} ; I2 : { p=T, q=T,s =T , r=T} ;

I3 : {p=T,q=T,r=F,s=F} ; I4 : { p=T, q=T,r =T, s=F} ;

Interpretasi yang mana yang merupakan model S ?

Gambarkan tabel kebenarannya.

P Q r s p q q r r s

T F T T F F T

T T T T T T T

T T F F T T T

T T T F T T F

Dari tabel diatas maka interpretasi yang merupakan model S adalah I2 dan I3. Perhatikan karena

I1 sudah memberikan nilai kebenaran F untuk p q maka dua yang lain tak perlu di evaluasi,

karena jelas bahwa I1 bukan model.

Page 20: LOGIKA  PROPOSIONAL

TAUTOLOGI

• Sebarang formula yang selalu bernilai TRUE, tak tergantung pada nilai kebenaran dari

pada variabel-variabel proposisinya, disebut tautologi, dan dikatakan sebagai tautologis

atau valid.

• Suatu tautologi adalah suatu formula proposisional yang mengambil nilai T untuk setiap

interpretasi yang mungkin. Semua entri dalam kolom pada tabel kebenaran yang

merupakan kolom nilai formula tersebut bernilai kebenaran T.

Contoh : p p adalah Tautologi karena untuk

I1 : p = T, maka p p = T

I2 : p = F, maka p p = T

dan tak ada lagi interpretasi lain.

• Untuk menyatakan bahwa suatu formula adalah suatu tautologi/valid maka dituliskan

dengan menggunakan metasimbol ╞ , maka contoh diatas menjadi :

╞ (p p)

Tabel dari kebenaran p p adalah :

p ¬p ¬p v p

T F T

F T T

Tabel dari kebenaran p (p (q p)) adalah :

P ↔ ( ¬ P V (q ^ ¬ p

1 5 2 1 4 1 3 2 1

T F F T F T F F T

T F F F F F F F T

F F T T T T T T F

F F T F T F F T F

Page 21: LOGIKA  PROPOSIONAL

Perhatikan hubungan antara metasimbol =T dng ╞

Yang dapat dilihat pada contoh dibawah ini :

Menggunakan ╞ menggunakan =T

╞ p (p) p =T (p)

╞ (p q) (q p) p q =T q p

╞ (p q) (p)(q) (p q) =T (p) (q)

╞ ((p q )) ((p) (q)) ((p q)) =T (( p) (q))

Baris pertama kiri dibaca : p (p) adalah suatu tautologi, kanan :

Formula p mempunyai tabel kebenaran sama dengan formula (p)

¬ (p ˄ q) ↔ (¬ p ˅ ¬ q)

4 1 3 1 2 1 3 2 1

F T T T T F T F F T

T T F F T F T T T F

T F F T T T F T F T

T F F F T T F T T F

Dikatakan bahwa dua formula P dan Q adalah Ekuivalen Logis jika ekuivalen logisnya „ P Q‟

adalah suatu tautologi ( yang dapat dikatakan juga dengan bahwa mereka mempunyai tabel

kebenaran yang sama) Dikatakan bahwa suatu formula P implai logis suatu formula Q jika

implikasi logis mereka „ P Q‟ adalah tautologi.

Page 22: LOGIKA  PROPOSIONAL

Absurditi/Kontradiksi

Sebarang formula yang selalu bernilai kebenaran F, tak tergantung pada nilai kebenaran dari

pada variabel-variabel proposisinya, disebut Absurditi atau Kontradiksi atau Unsatisfiable dan

dikatakan sbg Absurditi atau Invalid. Suatu Absurditi adalah suatu formula proposisional yang

ber nilai F untuk setiap interpretasi yang mungkin. Semua entri dalam kolom pada tabel

kebenaran yang merupakan kolom nilai formula tersebut bernilai kebenaran F.

Contoh : (p p) dan (p p)

adalah absurditi/kontradiksi karena untuk :

I1 : p = T, maka (p p) = F

I2 : p = F, maka (p p) = F

dan tak ada lagi interpretasi lain.

Perhatikan bahwa suatu formula proposisional P yang adalah suatu absurditi, maka formula P

adalah suatu Tautologi, begitu pula sebaliknya. Jika sebarang formula P adalah suatu absurditi,

maka ditulis :

╞ P

FORMULA CAMPUR

• Sebarang formula yang, tergantung pada nilai kebenaran daripada variabel-variabelnya,

dapat bernilai baik nilai T maupun nilai F disebut suatu formula campur, atau ada yang

menyebut contingent.

Contoh :

• Tentukan mana yang merupakan tautologi, absurditi, atau formula campur :

a) p (q p) ;

P ↔ ( ¬ q → p

1 4 2 1 3 1

T T F T T T

T T T F T T

F F F T T F

F T T F F F

Page 23: LOGIKA  PROPOSIONAL

b) p (p (q p) ;

P ↔ ( ¬ V (q ^ ¬ p

1 5 2 4 1 3 2 1

T F F F T F F T

T F F F F F F T

F F T T T T T F

F F T T F T T F

c) p (p (q p)).

¬ P ↔ (¬ P ^ (q → ¬ P)

2 1 5 2 1 4 1 3 2 1

F T T F T F T F F T

F T T F T F F T F T

T F T T F T T T T F

T F T T F T F T T F

Definisi Valid, Satisfiable, Contradictory, Implies, Equivalent, Consistent

( Zohar Manna and Richard Waldinger)

Valid , Tautology, Satisfiable, dan Contradictory

Suatu formula P dikatakan valid/benar jika ia true/benar untuk setiap interpretasi (I)

daripada P. Formula- formula valid daripada logika proposional disebut Tautologi.

Suatu formula P dikatakan Satisfiable/Dapat-puas/Memuaskan jika ia true dibawah suatu

interpretasi (I) daripada P.

Suatu formula P dikatakan kontradiksi/ contradictory ( unsatis fiable/ tak terpenuhi) jika ia

false dibawah setiap/ semua inter pretasi (I) daripada P.

Catatan : pada bukunya Zohar Manna and Richard Waldinger formula ditulis dengan

sentence/closed formula.

Implies, Equivalent, dan Consistent

Suatu kalimat P implies suatu kalimat Q jika, untuk sebarang Interpretasi (I) daripada P

dan Q, jika P true untuk I maka Q true untuk I.

Dua kalimat P dan G ekuivalen/ equivalent jika setiap interpre tasi (I) untuk P dan G , P

mempunyai nilai kebenaran yang sama dengan nilai kebenarannya G.

Page 24: LOGIKA  PROPOSIONAL

Seperangkat kalimat P1,P2,P3,…. Dikatakan konsisten jika terdapat suatu interpretasi

untuk P1,P2,P3,…. dibawah setiap Pi bernilai true.

Catatan : Kalimat/sentence adl formula tertutup/closed formula (buku Logic for Computer

Science, Arindama Singh, hal 59)

Page 25: LOGIKA  PROPOSIONAL

Fungsi Kebenaran/Truth Functions

Fungsi Kebenaran (kadang disebut suatu operator logis) adalah suatu fungsi yang mengambil

nilai-kebenaran sebagai argumen dan selalu menghasilkan salah satu dari nilai T atau nilai F.

Suatu fungsi kebenaran dapat mempunyai sejumlah operand (kadang-kadang disebut argument

atau tempat).

Suatu fungsi dengan satu operand disebut suatu fungsi kebenaran monadika ( ).Jika

mempunyai dua operand disebut dengan fungsi kebenaran diadika (, , , ), jika tiga

triadika ( If… then … else … ) .

Teorema :

Sebarang fungsi kebenaran f(p1 ,p2 , . . . pn) dari n variabel proposisional p1 , p2 . . . pn selalu

dapat diekspresikan dalam bentuk fungsi kebenaran diadika dan monadika. Pembuktiannya

dengan menggunakan induksi. Contoh dalam disjungsi terkondisi adalah :

Page 26: LOGIKA  PROPOSIONAL

KESETARAAN LOGIS

Dua buah pernyataan yang berbeda dikatakan setara/equivalen bila nilai kebenarannya sama

Contoh:

1. Tidak benar bahwa aljabar linier adalah alat matematika dasar untuk disain logika.(benar)

2. Aljabar boole adalah alat matematika dasar untuk disain logika.(benar)

Contoh:

p= sistem bilangan biner dipergunakan dalam sistem digital (T)

q= sistem digital hanya dapat mengasumsikan nilai yang berlainan.(F)

1. ¬(p˅q)→F

2. ¬p˄¬q→F

¬(p˅q) ¬p˄¬q

Page 27: LOGIKA  PROPOSIONAL

IMPLIKASI DAN BIIMPLIKASI

Implikasi

Jika memakai Ms Word maka windows adalah sistem operasinya

Artinya: Ms word tidak dapat digunakan tanpa windows tetapi windows dapat digunakan tanpa

Ms word.

Contoh pernyataan di atas disebut pernyataan beryarat (conditional statement)

Notasi: p q

Variasi Implikasi

Jika implikasi: p q

Maka: Konversnya : q p

Inversnya : ~ p ~ q

Kontrapositipnya : ~ q ~ p

Contoh:

Tentukan konvers,invers, dan kontrapositif dari proposisi berikut:

Jika Ms Word aplikatifnya maka windows sistem operasinya

Tabel kebenaran variasi implikasi:

p q ~p ~q p q ~ q ~ p q p ~ p ~ q

+ + – – + + + +

+ – – + – – + +

– + + – + + – –

– – + + + + + +

Kesimpulan:

Proposisi yang saling kontrapositif mempunyai nilai kebenaran yang sama(equivalen)

Contoh:

Buktikan bahwa:

Jika x2 bilangan genap, maka x juga bilangan genap

Page 28: LOGIKA  PROPOSIONAL

Jawab:

Kontrapositif dari implikasi di atas adalah:

Jika x bukan bilangan genap, maka x2 juga bukan bilangan genap

Setiap bilangan bulat bukan genap adalah ganjil, sehingga jika x ganjil ditulis sebagai

x = 2k + 1 (k bil. Bulat) akibatnya:

X2 = (2k + 1)

2

= 4k

2 + 4k + 1

= 2(2k2 + 2k) + 1

Karena kontrapositifnya benar akibatnya implikasinya juga benar.

Biimplikasi

Contoh pernyataan biimplikasi:

Ms word jika dan hanya jika ingin membuat dokumen

Notasi: p q

Kebenaran biimplikasi:

p Q p q

+ + +

+ – –

– + –

– – +

Argumentasi adalah kumpulan pernyataan – pernyataan atau premis-premis atau dasar pendapat

serta kesimpulan(konklusi)

Notasi:

P(p,q,…) P,Q,… masing-masing disebut premis

Q(p,q,…) {P,Q,..} bersama-sama disebut hipotesa

C(p,q,…) C adalah kesimpulan/konklusi.

Kebenaran/validitas Argumen

Nilai kebenaran argument tergantung dari nilai kebenaran masing-masing premis dan

kesimpulannya.

Suatu argumen dikatakan benar bila masing-masing premisnya benar dan kesimpulannya juga

benar.

Contoh 1:

Jika biner maka disain logika

Jika disain logika maka digital

Jika biner maka digital

Page 29: LOGIKA  PROPOSIONAL

Argumen tersebut dapat ditulis dengan notasi:

p q disebut premis 1

q r disebut premis 2

p r disebut konklusi

Semua premis dan konklusi benar sehingga argumentasi di atas valid.

Bentuk-bentuk dasar menarik kesimpulan

1. Conjunction 2. Addition

p p

q p q

p q

3. Construction Dilemma

( p q ) ( r s )

p r

q s

Page 30: LOGIKA  PROPOSIONAL

4. Modus Ponens 5. Modus Tollens

p q p q

p ~ q

q ~ p

6. Hypothetical syllogism

p q

q r

p r

7. Simplification 8. Disjunctive syllogism

p q p q

p ~ p

q

9. Destructive Dilemma

( p q ) ( r s )

~ q ~ s

~ p ~ r

10. Absorption

p q

p (p q)

Page 31: LOGIKA  PROPOSIONAL

PEMBUKTIAN VALIDITAS KALIMAT LOGIKA

ASUMSI SALAH

Perlu pembuktian nilai True untuk semua interpretasi (2n)

Membutuhkan langkah pembuktian yang panjang

Akan lebih mudah membuktikan bahwa ada 1 interpretasi yang menyebabkan

nilai kalimat salah Tidak valid

Asumsi salah tidak mungkin terjadi Valid

Contoh Soal 2.1

Buktikan validitas kalimat A : if ((not x) or (not y)) then (not(x and y))

Jawab :

A1: (not x) or (not y)

A2: not (x and y)

notasi : A1 : (¬ x ¬ y)

A2 : ¬ (x y)

A : A1 A2

Misalkan A diasumsikan salah/tidak valid yang berarti :

jika A bernilai F maka satu-satunya kemungkinan yang terjadi adalah A1= T, A2= F

Cara 1 : dimulai dari konklusi

A2=F

karena A2=F maka ¬ (x y) = F

berarti x y = T

karena x y = T maka x=T, y=T

hipotesis A1: (¬ x ¬ y) = F˅F=F (kontradiksi)

karena terjadi kontradiksi maka asumsi A tidak valid adalah salah seharusnya valid.

Page 32: LOGIKA  PROPOSIONAL

Contoh Soal :

1. Buktikan validitas kalimat B : (if x then y) if and only if ((not x) or y)

1) cara langsung :

(x→y)↔(¬x˅y)

x → y ↔ ¬ x ˅ y

1 2 1 4 2 1 3 1

T T T T F T T T

T F F T F T F F

F T T T T F T T

F T F T T F T F

Kesimpulan :

kalimat (if x then y ) if ((not x) or y) valid

2) cara tidak langsung:

Bentuk kalimat biimplikasi B: B1 B2 (x y) (¬x y)

Misalkan B diasumsikan salah, maka ada 2 kemungkinan :

a). hipotesis B1 benar (x y) = T dan konklusi B2 salah (¬x y) = F

b). hipotesis B1 salah (x y) = F dan konklusi B2 benar (¬x y) = T

a1). Dimulai dari hipotesis dulu (x y) = T dan (¬x y) = F

Hipotesis B1

(x y) = T

Akibatnya pada konklusi B2

(¬x y) = F

Kondisi yang diperoleh dari asumsi salah Kontradiksi ?

Ya/tidak

x = T dan y = T T F Ya

x = F dan y = T T F Ya

x = F dan y = F T F Ya

Page 33: LOGIKA  PROPOSIONAL

a2). Dimulai dari konklusi dulu (x y) = T dan (¬x y) = F

Konklusi B2

(~x y) = F

Akibatnya pada hipotesis B1

(x y)

Kondisi yang diperoleh dari asumsi salah Kontradiksi ?

Ya/tidak

x = T dan y = F F T Ya

b1). Dimulai dari hipotesis dulu (x y) = F dan (¬x y) = T

b2). Dimulai dari konklusi dulu (x y) = F dan (¬x y) = T

Jadi asumsi B = F tidak pernah terjadi kalimat B valid

Hipotesis B1

(x y) = F

Akibatnya pada konklusi B2

(¬x y) = F

Kondisi B2 yang diperoleh dari asumsi salah Kontradiksi ?

Ya/tidak

x = T dan y = F F T Ya

Konklusi B2

(¬x y) = T

Akibatnya pada hipotesis B1

(x y)

Kondisi B1 yang diperoleh dari asumsi

salah

Kontradiksi ?

Ya/tidak

x = F dan y = T T F Ya

x = T dan y = T T F Ya

x = F dan y = F T F Ya

Page 34: LOGIKA  PROPOSIONAL

2. if(if x then y) then (if(not x) then(not y))

(x→y)→(¬x→¬y)

cara langsung :

x → y → ¬ x → ¬ y

1 2 1 4 2 1 3 2 1

T T T T F T T F T

T F F T F T T T F

F T T F T F F F T

F T F T T F T T F

kesimpulan :

kalimat if(if x then y) then (if(not x) then(not y)) tidak valid

cara tidak langsung :

Bentuk kalimat implikasi C : C1 C2 (x y) (¬x ¬y)

Misalkan C diasumsikan salah yang berarti :

hipotesis C1 benar (x y) = T

konklusi C2 salah (¬x ¬ y) = F

Dimulai dari hipotesis dulu : (x y) = T dan (¬x ¬ y) = F

Hipotesis C1

(x y) = T

Akibatnya pada

konklusi C2

(~x ¬ y)

Kondisi C2 yang diperoleh dari

asumsi salah

Kontradiksi

?

Ya/tidak

x = T dan y

= T

T F Ya

x = F dan y

= T

F F Tidak

x = F dan y

= F

T F Ya

Page 35: LOGIKA  PROPOSIONAL

Dimulai dari konklusi dulu : (x y) = T dan (¬x ¬y) = F

Konklusi C2

(¬x ¬y) = F

Akibatnya pada hipotesis

C1 (x y)

Kondisi C2 yang diperoleh dari asumsi salah Kontradiksi?

Ya/tidak

x = F dan y = T T F Ya

Jadi asumsi C = F dapat terjadi kalimat C tidak valid

Page 36: LOGIKA  PROPOSIONAL

Pohon Semantik

Metode lain yang digunakan untuk pengujian validitas suatu kalimat adalah dengan

teknik pohon semantik (semantic tree technique)

Misalkan suatu kalimat logika A terdiri dari 3 proposisi p, q dan r

Pohon semantik dimulai dengan cabang tertinggi untuk proposisi pertama (p)

Cabang tertinggi ini terdiri cabang kiri (T) dan cabang kanan (F)

Perhatikan cabang kiri No. 2 :

• Bila dengan p = T nilai kebenaran dari A sudah dapat ditentukan (bernilai benar

atau salah), maka cabang No. 2 ini tidak bercabang, misalkan nilainya salah

• Bila belum dapat ditentukan, maka cabang ini akan bercabang lagi, yaitu cabang

kiri (T) dan cabang kanan (F) untuk proposisi kedua q

Perhatikan cabang kiri No. 4 :

• Bila dengan p = T dan q = T nilai kebenaran dari A sudah dapat ditentukan

(bernilai benar atau salah), maka cabang No. 4 ini tidak bercabang, misalkan

nilainya benar

• Bila belum dapat ditentukan, maka cabang ini akan bercabang lagi, yaitu cabang

kiri (T) dan cabang kanan (F) untuk proposisi ketiga r

Page 37: LOGIKA  PROPOSIONAL

• Langkah-langkah tersebut di atas diulangi lagi untuk cabang-cabang lain

• Kalimat logika dikatakan valid bila semua cabangnya bernilai benar, bila ada

cabangnya yang bernilai salah, maka kalimat tsb dikatakan tidak valid

• Bila semua cabang bercabang lagi, maka pohon semantiknya menjadi :

Metoda pohon semantik dapat lebih efisien dari metoda tabel kebenaran

• Contoh Soal .

• Tentukan validitas kalimat G : if (if x then y) then (if (not x) then (not y))

G : (p q) ( p q)

Periksa cabang No. 2 :

Bila p = T, maka p = F

G2 : ( p q) = T apapun nilai q

Bila ( p q) = T, maka G = T apapun nilai G1 : (p q)

Nilai G sudah dapat ditentukan, yaitu bernilai T

Bentuk kalimat G implikasi :G1 G2

G : (p q) ( p q)

Page 38: LOGIKA  PROPOSIONAL

Periksa cabang No. 3 :

Bila p = F, maka G1: (p q) = T apapun nilai q

p = T, nilai G2 : ( p q) tergantung pada nilai q

Bila q = T, maka G2 = T dan bila q = F, maka G2 = F

Bila G2 = T, maka G = T dan bila G2 = F, maka G = F

Jadi nilai G belum sudah dapat ditentukan, cabang No. 3 bercabang lagi

Karena ada cabang yang bernilai salah, maka kalimat G tidak valid

Bentuk kalimat G implikasi :G1 G2

G : (p q) ( p q)

Periksa cabang No. 4 :

Bila p = F dan q = T, maka G1: (p q) = T dan G2 : ( p q) = F

Akibatnya G : G1 G2 bernilai salah (F)

Page 39: LOGIKA  PROPOSIONAL

Periksa cabang No. 5 :

Bila p = F dan q = F, maka G1: (p q) = T dan G2 : ( p q) = T

Akibatnya G : G1 G2 bernilai benar (T)

Karena ada cabang yang bernilai salah, maka kalimat G tidak valid.

Contoh Soal.

Tentukan validitas kalimat B : [p (q r)] [(p q) r]

Jawab :

Bentuk kalimat B biimplikasi : B1 B2

Page 40: LOGIKA  PROPOSIONAL

No p q R Nilai B1, B2 dan B Langkah berikut

2 T B1 tergantung pada nilai q, r

B belum dapat ditentukan

Bercabang 4 dan

5

3 F B1 = T dan B2 = T apapun nilai q,

r

B = T

4 T T Bila r = T, maka B1 = T dan B2 =

T

Bila r = F, maka B1 = F dan B2 = F

B = T

5 T F B1 = T dan B2 = T apapun nilai r B = T

Karena semua cabang nilainya benar, maka kalimat B valid

Lebih efisien dari tabel kebenaran

Latihan Soal.

Tentukan validitas kalimat B : [p (q r)] [(p q) r]

Jawab :

Page 41: LOGIKA  PROPOSIONAL

Bentuk kalimat biimplikasi B1 B2

B1 : [p (q r)] B2 : [(p q) r]

No p q r Nilai B1, B2 dan

B

Langkah

berikut

2 T

3 F

Latihan Soal.

Periksalah validitas kalimat p (p q) dengan menggunakan pohon semantik

Jawab :

Bentuk kalimat OR Eksklusif A = A1 A2

p q p q

T T F

T F T

F T T

F F F

Page 42: LOGIKA  PROPOSIONAL

Soal-Soal Validitas

Soal 1

(If P then Q) or (if Q then P)

(p→q)˅(q→p)

perntyataan diatas bernilai valid.

(not Q) or not(if P then (not Q) and P)

(¬q)˅(p→(¬q)˄p)

perntyataan diatas bernilai tidak valid

(if P then (not Q)) if and only if not (P and Q)

p→(¬q)↔¬(p˄q)

perntyataan diatas bernilai valid.

[if (P or Q) then R] if and only if [(if P then R) and (if Q then R)]

Page 43: LOGIKA  PROPOSIONAL

[(p˅q)→r)]↔(p→r)˄(q→r)

[(p ˅ q) → r)] ↔ (p → r) ˄ (q → r)

1 2 1 3 1 4 1 2 1 3 1 2 1

T T T T T T T T T T T T T

T T T F F T T F F F T F F

T T F T T T T T T T F T T

T T F F F T T F F F F T F

F T T T T T F T T T T T T

F T T F F T F T F F T F F

F F F T T T F T T T F T T

F F F T F T F T F T F T F

perntyataan diatas bernilai valid

cara ke dua :

Page 44: LOGIKA  PROPOSIONAL

Soal 2

Andaikan dua pernyataan berikut adalah True

Suprapto cinta Amanda atau Suprapto cinta Yulia

Jika Suprapto cinta Amanda , maka Suprapto cinta Yulia

Apakah bisa langsung diturunkan bahwa “Suprapto cinta Amanda ?”

Apakah bisa langsung disimpulkan bawaha “Suprapto cinta Yulia?”

jawab :

p˅q

p→q

(p˅q)˄(p→q)→p

(p˅q)˄(p→q)→q

a) . (p˅q)˄(p→q)→p

(p ˅ q) ˄ (p → q) → p

1 2 1 3 1 2 1 4 1

T T T T T T T T T

T T F F T F F T T

F T T T F T T F F

F F F F F T F T F

perntyataan diatas bernilai tidak valid.

b) (p˅q)˄(p→q)→q

(p ˅ q) ˄ (p → q) → q

1 2 1 3 1 2 1 4 1

T T T T T T T T T

T T F F T F F T F

F T T T F T T T T

F F F F F T F T F

perntyataan diatas bernilai valid.

jadi tidak bisa langsung dikatakan bahwa suprapt cinta Amanda.

Page 45: LOGIKA  PROPOSIONAL

KUANTOR PERNYATAAN

Misalkan P(x) adalah pernyataan yang menyangkut variabel x dan D adalah sebuah himpunan,

maka P adalah fungsi proposisi jika untuk setiap xD, berlaku P(x) adalah sebuah proposisi.

Contoh:

Misalkan P(x) merupakan pernyataan :

x adalah sebuah bilangan bulat genap.

Misalkan D = himpunan bilangan bulat positif

Maka fungsi proposisi P(x) dapat ditulis:

jika x = 1 maka proposisinya

1 adalah bilangan bulat genap. (F)

jika x = 2 maka proposisinya

2 adalah bilangan bulat genap. (T)

dst.

Untuk menyatakan kuantitas suatu objek dalam proposisi tersebut digunakan notasi-notasi yang

disebut kuantor

Macam-macam Kuantor

Untuk setiap x, P(x)

disebut kuantor universal Simbol:

Untuk beberapa x, P(x)

disebut kuantor eksistensial Simbol:

Contoh:

Misalkan x himpunan warga negara Indonesia, P predikat membayar pajak, R predikat membeli

Ms Word, Maka:

1. x,P(x)

artinya: semua warga negara membayar pajak

2. x,R(x),P(x)

artinya: ada beberapa warga negara membeli Ms word membayar pajak

3. x,R(x)P(x)

artinya: semua warga negara jika membeli ms word maka membayar pajak

Page 46: LOGIKA  PROPOSIONAL

4. x,R(x)P(x)

artinya: ada warga negara membeli ms word dan tidak membayar pajak Predikat &

Kuantifier.

5. x,R(x)↔P(x)

artintya : semua warga Negara Indonesia memb eli ms.word jika dan hanya jika mem

banyar pajak

6. x,P(x)P(x)

artintya : beberapa warga Negara Indonesia membanyar pajak dan tidak membanyar

pajak.

7. x,(p(x)R(x))

artintya : ada warga Negara Indonesia mem banyar pajak atau membeli ms.word .

Pernyataan “x > 3” punya 2 bagian, yakni “x” sebagai subjek dan “ adalah lebih besar 3” sebagai

predikat P.

Kita dpt simbolkan pernyataan “x > 3” dengan P(x). Sehingga kita dapat mengevaluasi nilai

kebenaran dari P(4) dan P(1).

Subyek dari suatu pernyataan dapat berjumlah lebih dari satu.

Misalkan Q(x,y): x - 2y > x + y

Page 47: LOGIKA  PROPOSIONAL

Kuantor Universal

“P(x) benar untuk semua nilai x dalam domain pembicaraan”

x P(x).

Soal 1. Tentukan nilai kebenaran x (x2 x) jika:

x bilangan real

x bilangan bulat

Untuk menunjukkan x P(x) salah, cukup dengan mencari satu nilai x dalam domain shg P(x)

salah.

Nilai x tersebut dikatakan contoh penyangkal (counter example) dari pernyataan x P(x).

Kuantor Eksistensi

“Ada nilai x dalam domain pembicaraan sehingga P(x) bernilai benar” x P(x).

Soal .

Tentukan nilai kebenaran dari x P(x) bila P(x) menyatakan “x2 > 12” dan domain pembicaraan

meliputi semua bilangan bulat positif tidak lebih dari 4.

Page 48: LOGIKA  PROPOSIONAL

Kuantifier Bersusun

(Nested Quantifier)

x y (x+y = y+x)

berarti x+y = y+x berlaku untuk semua bilangan real x dan y.

x y (x+y = 0)

berarti untuk setiap x ada nilai y sehingga x+y = 0.

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

berarti untuk setiap x, y dan z berlaku hukum asosiatif x+(y+z) = (x+y)+z.

Soal :

1) Artikan kalimat ini dalam bhs Indonesia: x (C(x) y ( C(y) F(x,y))),

bila C(x) : “x mempunyai komputer”,

F(x,y): “x dan y berteman”,

dan domainnya adalah semua mhs di kampus.

jawab : semua mahasiswa dikampus x mempunyai komputer atau beberapa mahasiswa di

kampus y mempunyai komputer dan F bertem an dengan x.

Page 49: LOGIKA  PROPOSIONAL

Negasi Kuantor

~x = x

~x = x

Sehingga:

~(x,P(x)) = x,P(x)

~(x,P(x)) = x,P(x)

~(x,P(x)Q(x)) = x,( P(x) Q(x))

= x, P(x) Q(x)

negasi dari ~x( >x) = x( ≥2)

Negasi

“Setiap mhs dalam kelas ini telah mengambil Kalkulus I”

[x P(x)]

Apakah negasi dari pernyataan ini….?

“Ada seorang mhs dalam kelas ini yang belum mengambil Kalkulus I”

[ x P(x)]

Jadi, x P(x) x P(x).

Perhatikan argumen matematik berikut ini:

1. P(n) :Jumlah bilangan bulat positif dari 1 sampai n adalah n(n + 1)/2 misal untuk n = 5 adalah

5(5+1)/2=15 terlihat: 1+2+3+4+5=15

2. P(n) : Jumlah dari n buah bilangan ganjil positif pertama adalah n2 misal untuk n = 3 adalah

32= 9 terlihat : 1 + 3 + 5 = 9

Page 50: LOGIKA  PROPOSIONAL

Induksi matematik merupakan teknik pembuktian yang baku dalam matematik, khususnya

menyangkut bilangan bulat positif.

Prinsip Induksi Sederhana

Misalkan P(n) adalah pernyataan perihal bilangan bulat positif dan kita ingin membuktikan

bahwa p(n) benar untuk semua bilangan bulat positif n. untuk membuktikan pernyataan ini, kita

hanya perlu membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa:

Bukti:

Basis induksi. Untuk n=1 kita peroleh 1 = 1(1+1)/2, ini jelas benar sebab

1 = 1 (1+1)/2

= 1 (2)/2

= 2/2

= 1

Langkah induksi. Andaikan untuk n 1 pernyataan

1+2+3+…+n = n(n+1)/2 adalah benar (hipotesis induksi)

Kita harus menunjukkan bahwa:

1+2+3+…+n + (n+1) = (n+1)[(n+1)]/2 juga benar

Untuk membuktikan ini tunjukkan bahwa:

1+2+3+…+ n + (n+1) = (1+2+3+…+n )+(n+1)

= [n(n+1)/2]+(n+1)

= [ (n2+n)/2]+(n+1)

= [ (n2+n)/2]+[(2n+2)/2]

= (n2+3n+2)/2

= ( n+1)[(n+1)+1]/2

Karena langkah basis dan langkah induksi keduanya telah dibuktikan benar, maka untuk semua

bilangan bulat positif n, terbukti bahwa:

1+2+3+…+n = n(n+1)/2

Page 51: LOGIKA  PROPOSIONAL

Logika Predikat

• Logika predikat digunakan untuk merepresentasikan hal-hal yang tidak dapat

direpresentasikan dengan menggunakan logika proposisi.

• Pada logika predikat kita dapat merepresentasikan fakta-fakta sebagai

• suatu pernyataan yang disebut dengan wff (well-formed formula).

Misalkan diketahui fakta-fakta sebagai berikut:

• Andi adalah seorang laki-laki : A

• Ali adalah seorang laki-laki : B

• Amir adalah seorang laki-laki : C

• Anto adalah seorang laki-laki : D

• Agus adalah seorang laki-laki : E

• Pada contoh di atas, dapat dituliskan:

laki2(X)

• dimana X adalah variabel yang bisa disubstitusikan dengan Andi, Ali, Amir, Anto, Agus

dan laki-laki yang lain.

• Operator Logika Predikat

→ (implikasi),

⌐ (not),

∧ (and),

∨ (or),

∀ (untuk setiap),

∃ (terdapat)

Page 52: LOGIKA  PROPOSIONAL

Soal Latihan

1. Andi adalah seorang mahasiswa.

2. Andi masuk Jurusan Ilmu Komputer.

3. Setiap mahasiswa teknik informatika pasti mahasiswa ilmu komputer.

4. Kalkulus adalah matakuliah yang sulit.

5. Setiap mahasiswa teknik informatika pasti akan suka kalkulus atau akan membencinya.

6. Setiap mahasiswa pasti akan suka terhadap suatu matakuliah.

7. Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti

tidak suka terhadap matakuliah tersebut.

8. Andi tidak pernah hadir kuliah matakuliah kalkulus.

Jawaban

1. mahasiswa(Andi).

2. IlmuKomputer(Andi).

3. ∀x:TeknikInformatika(x)→IlmuKomputer(x).

4. sulit(Kalkulus).

5. ∀x:TeknikInformatika (x) → suka(x,Kalkulus) ∨ benci(x,Kalkulus).

6. ∀x:∃y:suka(x,y).

7. ∀x:∀y:mahasiswa(x)∧sulit(y) ∧ ¬hadir(x,y) →¬suka(x,y).

8. ¬hadir(Andi,Kalkulus).

• Andaikan kita akan menjawab pertanyaan:

“Apakah Andi suka matakuliah kalkulus?”

• maka dari pernyataan ke-7 kita akan membuktikan bahwa Andi tidak suka dengan

matakuliah kalkulus. Dengan menggunakan penalaran backward bisa dibuktikan bahwa:

¬suka(Andi,Kalkulus)

Page 53: LOGIKA  PROPOSIONAL

¬suka(Andi,Kalkulus)

↑ (7, substitusi)

mahasiswa(Andi) ∧ sulit(Kalkulus) ∧¬hadir(Andi,Kalkulus)

↑ (1)

sulit(Kalkulus) ∧ ¬hadir(Andi,Kalkulus)

↑ (4)

¬hadir(Andi,Kalkulus)

↑ (8)

• Dari penalaran tersebut dapat dibuktikan bahwa Andi tidak suka dengan matakuliah

kalkulus.

Page 54: LOGIKA  PROPOSIONAL

Aljabar Boolean

Pendahuluan

• Komputer digital modern dirancang, dipelihara, dan operasinya dianalisis dengan

memakai teknik dan simbologi dari bidang matematika yang dinamakan aljabar modern

atau aljabar Boolean

• pengetahuan mengenai aljabar boolean ini merupakan suatu keharusan dalam bidang

komputer.

KONSEP POKOK ALJABAR BOOLEAN

• Variabel – variabel yang dipakai dalam persamaan aljabar boolean memiliki karakteristik

• Variabel tersebut hanya dapat mengambil satu harga dari dua harga yang mungkin

diambil. Kedua harga ini dapat dipresentasikan dengan simbol “ 0 ” dan “ 1 ”.

Definisi Aljabar Boolean

Misalkan terdapat

- Dua operator biner: + dan

- Sebuah operator uner: ‟.

- B : himpunan yang didefinisikan pada operator +, , 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

Page 55: LOGIKA  PROPOSIONAL

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

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. Komplemen1: (i) a + a‟ = 1

(ii) a a‟ = 0

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

Page 56: LOGIKA  PROPOSIONAL

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.

Page 57: LOGIKA  PROPOSIONAL

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 e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 e2, e1‟ adalah ekspresi

Boolean

Contoh: 0

1

a

b

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)

Page 58: LOGIKA  PROPOSIONAL

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

Page 59: LOGIKA  PROPOSIONAL

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)

Page 60: LOGIKA  PROPOSIONAL

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

Page 61: LOGIKA  PROPOSIONAL

Contoh. Diketahui fungsi Booelan h(x, y, z) = xy z‟, nyatakan h dalam tabel kebenaran.

Penyelesaian:

X y z h(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, x1 dan x2, 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.

Page 62: LOGIKA  PROPOSIONAL

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

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

m0

m1

m2

m3

x + y

x + y‟

x‟ + y

x‟ + y‟

M0

M1

M2

M3

Page 63: LOGIKA  PROPOSIONAL

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

Page 64: LOGIKA  PROPOSIONAL

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: Nyatakan fungsi Boolean f(x, y, z) = x + y‟z dalam 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

Page 65: LOGIKA  PROPOSIONAL

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)

Page 66: LOGIKA  PROPOSIONAL

Konversi Antar 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. 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)

Page 67: LOGIKA  PROPOSIONAL

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) = m0+ m1 + m2+ m4+ m5+ m6+ m7

(b) POS

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

Bentuk Baku

• Tidak harus mengandung literal yang lengkap.

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

Page 68: LOGIKA  PROPOSIONAL

Aplikasi Aljabar Boolean

1. Jaringan Pensaklaran (Switching Network)

Saklar: 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

c

b y

Output c hanya ada jika dan hanya jika x atau 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

A

Lampu

B

Sumber Tegangan

Page 69: LOGIKA  PROPOSIONAL

2. Rangkaian Logika

Gerbang AND Gerbang OR Gerbang NOT (inverter)

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

Jawab: (a) Cara pertama

(b) Cara kedua

y

xxy

y

xx+ y x'x

x'

x

yxy

x

yx'y

xy+x'y

x'

xyx

y

x'y

xy+x'y

Page 70: LOGIKA  PROPOSIONAL

(c) Cara ketiga

Gerbang turunan

Gerbang NAND Gerbang XOR

Gerbang NOR Gerbang XNOR

Penyederhanaan Fungsi Boolean

x'

xy

x y

x'y

xy+x'y

x

y(xy)'

x

y(x+y)'

x

y+x y

x

y+(x y)'

x'

y'x'y' ekivalen dengan

x

y(x+y)'

x'

y'x' + y' ekivalen dengan

x

y(xy)'

x

y(x + y)' ekivalen dengan

x

y(x + y)'

x + y

Page 71: LOGIKA  PROPOSIONAL

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 + xy‟

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

Page 72: LOGIKA  PROPOSIONAL

a. Peta Karnaugh dengan dua peubah

y

0 1

m0 m1 x 0 x‟y‟ x‟y

m2 m3 1 xy‟ xy

b. Peta dengan tiga peubah

yz

00

01

11

10

m0 m1 m3 m2 x 0 x‟y‟z‟ x‟y‟z x‟yz x‟yz‟

m4 m5 m7 m6 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

Page 73: LOGIKA  PROPOSIONAL

b. Peta dengan empat peubah

yz

00

01

11

10

m0 m1 m3 m2 wx 00 w‟x‟y‟z‟ w‟x‟y‟z w‟x‟yz w‟x‟yz‟

m4 m5 m7 m6 01 w‟xy‟z‟ w‟xy‟z w‟xyz w‟xyz‟

m12 m13 m15 m14 11 wxy‟z‟ wxy‟z wxyz wxyz‟

m8 m9 m11 m10 10 wx‟y‟z‟ wx‟y‟z wx‟yz wx‟yz‟

Page 74: LOGIKA  PROPOSIONAL

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

Page 75: LOGIKA  PROPOSIONAL

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

Page 76: LOGIKA  PROPOSIONAL

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

Page 77: LOGIKA  PROPOSIONAL

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

Page 78: LOGIKA  PROPOSIONAL

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

Page 79: LOGIKA  PROPOSIONAL

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

Page 80: LOGIKA  PROPOSIONAL

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

Page 81: LOGIKA  PROPOSIONAL

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

Page 82: LOGIKA  PROPOSIONAL

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

Page 83: LOGIKA  PROPOSIONAL

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 0 1 1 1

1 0 1 1 0

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

Peta Karnaugh untuk lima peubah

000 001 011 010 110 111 101 100

00 m0 m1 m3 m2 m6 m7 m5 m4

01 m8 m9 m11 m10 m14 m15 m13 m12

11 m24 m25 m27 m26 m30 m31 m29 m28

10 m16 m17 m19 m18 m22 m23 m21 m20

Garis pencerminan

Page 84: LOGIKA  PROPOSIONAL

Contoh 5.21. (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari f(v, w, x, y, z) =

(0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)

Jawab:

Peta Karnaugh dari fungsi tersebut adalah:

xyz

00

0

00

1

01

1

01

0

11

0

11

1

10

1

10

0

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

Page 85: LOGIKA  PROPOSIONAL

Kondisi 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

Page 86: LOGIKA  PROPOSIONAL

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:

Page 87: LOGIKA  PROPOSIONAL

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:

x y z

x'yz

x'yz'

xy'z'

xy'z

Page 88: LOGIKA  PROPOSIONAL

yz

00

01

11

10

x 0

0

0

1

1

1

1

1

0

0

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 f1(w, x, y, z) f2(w, x, y,z) f3(w, x, y, z) f4(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

Page 89: LOGIKA  PROPOSIONAL

(a) f1(w, x, y, z)

yz

00

01

11

10

wx 00

01 1 1 1

11 X X X X

10 1 1 X X

f1(w, x, y, z) = w + xz + xy = w + x(y + z)

(b) f2(w, x, y, z)

yz

00

01

11

10

wx 00 1 1 1

01 1

11 X X X X

10 1 X X

f2(w, x, y, z) = xy‟z‟ + x‟z + x‟y = xy‟z‟ + x‟(y + z)

Page 90: LOGIKA  PROPOSIONAL

(c) f3(w, x, y, z)

yz

00

01

11

10

wx 00 1 1

01 1 1

11 X X X X

10 1 X X

f3(w, x, y, z) = y‟z‟ + yz

(d) f4(w, x, y, z)

yz

00

01

11

10

wx 00 1 1

01 1 1

11 X X X X

10 1 X X

f4(w, x, y, z) = z‟

Page 91: LOGIKA  PROPOSIONAL

Contoh 7.43

Minimisasi fungsi Boolean berikut (hasil penyederhanaan dalam bentuk baku SOP dan bentuk

baku POS):

f(w, x, y, z) = (1, 3, 7, 11, 15)

dengan kondisi don’t care adalah d(w, x, y, z) = (0, 2, 5)

Penyelesaian:

Peta Karnaugh dari fungsi tersebut adalah:

00 01 11 10

00

01

11

10

X 1 1 X

0 X 1 0

0 0 1

0 0 1 0

0

yz

wx

Hasil penyederhanaan dalam bentuk SOP

f(w, x, y, z) = yz + w‟z (SOP) (garis penuh)

dan bentuk baku POS adalah

f(w, x, y, z) = z (w‟ + y) (POS) (garis putus2)

x y zw

f3

f4

f2

f1

Page 92: LOGIKA  PROPOSIONAL

Metode Quine-McCluskey

• Metode Peta Karnaugh tidak mangkus untuk jumlah peubah > 6 (ukuran peta semakin

besar).

• Metode peta Karnaugh lebih sulit diprogram dengan komputer karena diperlukan

pengamatan visual untuk mengidentifikasi minterm-minterm yang akan dikelompokkan.

• Metode alternatif adalah metode Quine-McCluskey . Metode ini mudah diprogram.

Contoh 7.46

Sederhanakan fungsi Boolean f(w, x, y, z) = (0, 1, 2, 8, 10, 11, 14, 15).

Penyelesaian:

(i) Langkah 1 sampai 5:

(a) (b) (c)

term w x y z term w x y z term w x y z

0 0 0 0 0 0,1 0 0 0 - 0,2,8,10 - 0 - 0

0,2 0 0 - 0 0,8,2,10 - 0 - 0

1 0 0 0 1 0,8 - 0 0 0

2 0 0 1 0 10,11,14,15 1 - 1 -

8 1 0 0 0 2,10 - 0 1 0 10,14,11,15 1 - 1 -

8,10 1 0 - 0

10 1 0 1 0

10,11 1 0 1 -

11 1 0 1 1 10,14 1 - 1 0

14 1 1 1 0

11,15 1 - 1 1

15 1 1 1 1 14,15 1 1 1 -

Page 93: LOGIKA  PROPOSIONAL

(ii) Langkah 6 dan 7:

minterm

Bentuk prima 0 1 2 8 10 11 14 15

0,1

0,2,8,10

10,11,14,15

* * * * * *

Bentuk prima yang terpilih adalah:

0,1 yang bersesuaian dengan term w‟x‟y

0, 2, 8, 10 yang bersesuaian dengan term x‟z‟

10, 11, 14, 15 yang bersesuaian dengan term wy

Semua bentuk prima di atas sudah mencakup semua minterm dari fungsi Boolean semula.

Dengan demikian, fungsi Boolean hasil penyederhanaan adalah f(w, x, y, z) = w‟x‟y‟ + x‟z‟ +

wy.

Page 94: LOGIKA  PROPOSIONAL

Contoh 7.47

Sederhanakan fungsi Boolean f(w, x, y, z) = (1,4,6,7,8,9,10,11,15)

Penyelesaian:

(i) Langkah 1 sampai 5:

(a) (b) (c)

term w x y z term w x y z term w x y z

1 0 0 0 1 1,9 - 0 0 1 8,9,10,11 1 0 - -

4 0 1 0 0 4,6 0 1 - 0 8,10,9,11 1 0 - -

8 1 0 0 0 8,9 1 0 0 -

8,10 1 0 - 0

6 0 1 1 0

9 1 0 0 1 6,7 0 1 1 -

10 1 0 1 0 9,11 1 0 - 1

10,1 1 1 0 1 -

7 0 1 1 1

11 1 0 1 1 7,15 - 1 1 1

11,15 1 - 1 1

15 1 1 1 1

Page 95: LOGIKA  PROPOSIONAL

(ii) Langkah 6 dan 7

minterm

Bentuk prima 1 4 6 7 8 9 10 11 15

1,9

4,6

6,7

7,15

11,15

8,9,10,11

* * * *

Sampai tahap ini, masih ada dua minterm yang belum tercakup dalam bentuk prima terpilih,

yaitu 7 dan 15. Bentuk prima yang tersisa (tidak terpilih) adalah (6,7), (7,15), dan (11, 15). Dari

ketiga kandidat ini, kita pilih bentuk prima (7,15) karena bentuk prima ini mencakup minterm 7

dan 15 sekaligus.

Page 96: LOGIKA  PROPOSIONAL

minterm

Bentuk prima 1 4 6 7 8 9 10 11 15

1,9

4,6

6,7

7,15

11,15

8,9,10,11

* * * *

Sekarang, semua minterm sudah tercakup dalam bentuk prima terpilih. Bentuk prima yang

terpilih adalah:

1,9 yang bersesuaian dengan term x‟y‟z

4,6 yang bersesuaian dengan term w‟xz‟

7,15 yang bersesuaian dengan term xyz

8,9,10,11 yang bersesuaian dengan term wx‟

Dengan demikian, fungsi Boolean hasil penyederhanaan adalah f(w, x, y, z) = x‟y‟z + w‟xz‟ + xyz

+ wx‟.