Logika Matematika
B b 2: Bab 2 Kalkulus K lk l Proposisi P i i
By, y Andrian Rakhmatsyah Teknik Informatika STT Telkom
1
R f Referensi i z
z
z
Zohar Manna Manna. The Logical Basis For Computer Programming. Addison Wesley Publishing. 1985 Rosen, Kenneth H.,Discrete Mathematic and Its Applications, Applications 4th edition, edition McGraw Hill International Editions, 1999 Soekadijo R Soekadijo, R.G., G Logika Dasar tradisional tradisional, simbolik dan induktif, Penerbit Gramedia Pustaka Utama,, Jakarta,, 1999. 2
K lk l P Kalkulus Proposisi-Pendahuluan i iP d h l z
z
kalkulus proposisi merupakan metoda untuk menghitung dengan menggunakan p p proposisi/kalimat. / yang ditinjau adalah nilai kalimat deklaratif (true/false)
JJadi, yyangg akan dipelajari p j adalah bagaimana g menentukan nilai kebenaran suatu kalimat (True/False) 3
K lk l P Kalkulus Proposisi-Pendahuluan i iP d h l Berdasarkan nilai kebenaran yang dimiliki suatu kalimat maka dapat ditentukan : z Sifat yang dimiliki dari sebuah kalimat z Apakah 2 buah kalimat merupakan kalimat yang ekivalen satu sama lain Kalimat dalam Kalkulus Proposisi dinotasikan sebagai Kalimat Abstrak. Contoh, Ada monyet di planet Jupiter Atau Tidak ada monyet di planet Jupiter 4
K lk l P Kalkulus Proposisi-Pendahuluan i iP d h l Tanpa harus mengetahui mengetahui, apakah ada kehidupan di planet jupiter jupiter, maka kalimat tersebut dapat disimbolkan dengan kalimat abstrak. P or not (P) Nilai kebenaran dari P or not (P) adalah z Jika Jik P Å TRUE, TRUE maka k TRUE or nott (TRUE) = TRUE z Jika P Å FALSE, maka FALSE or not (FALSE) = TRUE Kalimat tersebut selalu bernilai TRUE untuk setiap kemungkinan nilai P, maka kalimat tersebut Bersifat VALID
5
K lk l P Kalkulus Proposisi-Pendahuluan i iP d h l Contoh, diberikan pernyataan sebagai berikut Contoh berikut. 1. Jika hari hujan, maka jalanan basah 2 Jika jalanan tidak basah maka hari tidak hujan 2. Jika dianalisis nilai kebenaran yang dimiliki kedua kalimat di atas dengan mengubahnya menjadi kalimat abstrak, maka kedua kalimat tersebut adalah ekivalen. 1. if P then Q 2. if (not Q) then (not P) 6
K lk l P Kalkulus Proposisi-Pendahuluan i iP d h l a. a b. c c. d. e e. f.
Jawablah pertanyaan ini ! Jam Berapakah ini ? Semarang adalah ibukota Propinsi Jawa Tengah Bandung adalah ibukota Propinsi Jawa Timur Tidak ada musim hujan di Indonesia Gunung Merapi terletak di 2 propinsi dan 3 kabupaten p g. Badu kaya raya dan memiliki banyak harta
7
K lk l Proposisi-Definisi Kalkulus P i i D fi i i Definisi Proposisi, p , Kalimat pada Kalkulus Proposisi terbentuk dari simbol-simbol z Simbol kebenaran ; True dan False z Simbol kalimat ; E, F, G, H atau A, B, C, z Simbol Variabel ; p, q, r, s, p1, q1, r1, s1, …. Definisi Kalimat, Kalimat pada Kalkulus Proposisi dibentuk dg menggunakan penghubung logik, logik 1. NOT, 2. AND, 3. OR, 4. IF-THEN, 5. IF-AND-ONLY-IF, 6. IF-THEN-ELSE Operasi pada kalimat proposisi didasarkan pada urutan prioritas penghubung logiknya.
8
K lk l Proposisi-Definisi Kalkulus P i i D fi i i C t h jik Contoh, jika dib diberikan rik kkalimat lim t A : if not p and q then not r Maka penyelesaian operasi kalimat A adalah if ((not p) and q) then (not r) bukan if not (p and q) then (not r) 9
K lk l Proposisi-Definisi Kalkulus P i i D fi i i Kalimat dibentuk menurut aturan-aturan aturan aturan berikut ini : 1. setiap proposisi adalah kalimat, 2. jika F adalah kalimat, maka negasi (not F) adalah kalimat, 3 3. jika F dan G adalah kalimat, kalimat maka konjungsi (F and G) adalah kalimat kalimat, 4. jika F dan G adalah kalimat, maka disjungsi (F or G) adalah kalimat, 5. jika F dan G adalah kalimat, maka implikasi (If F then G) adalah kalimat. F disebut di b t sebagai b i antisenden ti d dan d G sebagai b i konsekuen, k k 6. jika F dan G adalah kalimat, maka ekivalensi (F if and only if G) adalah kalimat. F disebut sebagai left-hand-side dan G sebagai rigth-hand-side dari ekivalensi, ekivalensi 7. jika F, G, dan H adalah kalimat, maka kondisional if F then G else H adalah kalimat. F disebut sebagai if-clausa, G sebagai then-clausa, dan H adalah sebagai else-clausa else clausa 10
K lk l Proposisi-Definisi Kalkulus P i i D fi i i Kalimat-kalimat Kalimat kalimat yang digunakan untuk membangun kalimat lain yang lebih kompleks, menggunakan salah satu aturan di atas dinamakan subkalimat dari kalimat tsb. Subkalimat dari kalimat A adalah p kalimat antara,, yyangg dipakai p untuk membangun g kalimat A termasuk Setiap kalimat A itu sendiri. Subkalimat S bk li murnii (proper (p p subsentence) b t ) dari d i kalimat k li A adalah d l h Setiap kalimat antara, yang dipakai untuk membangun kalimat A tetapi tidak termasuk kalimat A itu sendiri. 11
K lk l Proposisi-Definisi Kalkulus P i i D fi i i Contoh,, diketahui ekspresi p E : ((not (p or q) if and only if ((not p) and (not q))) a. Apakah E merupakan kalimat ? b. Cari subkalimat dari E ? Jawab, a. E adalah kalimat karena, p adalah kalimat dan q adalah kalimat, (p or q), q) (not p) dan (not q) adalah kalimat (not (p or q), ((notp) and (notq)) adalah kalimat ((not (p or q)) if and only if ((not p) and (not q))) adalah kalimat b. E memiliki 8 subkalimat, yaitu p, q, (p or q), (not p), (not q), not (p or q), (not p) and (not q), ((not (p or q)) if and only if ((not p) and (not q))) SSebuah b h kkalimat li proposisi i i memiliki iliki artii atau nilai il i kkebenaran b (true/false) ( /f l ) tergantung dari interpretasi yang diberikan untuk kalimat tsb. 12
K lk l Proposisi-Arti Kalkulus P i i A ti Suatu kalimat P or (not Q) dapat diketahui kebenarannya, kebenarannya jika diketahui nilai kebenaran dari simbol proposisi p dan q. Definisi, D fi i i IInterpretasii Interpretasi I untuk kalimat A adalah pemberian nilai kebenaran true atau false, untuk setiap kumpulan simbol kalimat A tsb. Untuk sebarang kalimat A, A interpretasi I disebut sebagai interpretasi untuk A jika I memberikan nilai kebenaran untuk setiap variabel proposisi yang muncul pada kalimat A. 13
K lk l Proposisi-Arti Kalkulus P i i A ti Contoh,, diketahui kalimat F : p or (not q) Ada beberapa macam interpretasi yang dapat diberikan untuk F I1 : p Å false q Å true I2 : p Å false q Å false I3 : p Å false I4 : p Å false q Å true r Å false Dapat disimpulkan bahwa, I3 bukan interpretasi yang valid untuk F. Sedangkan I1, I2, dan I4 adalah interpretasi untuk F F, walaupun I4 memberikan nilai pada variabel yang tidak muncul pada F. 14
Kalkulus Proposisi-Aturan Semantik Definisi Jika E berupa kalimat dan I adalah intepretasi dari E, maka nilai kebenaran dari E (dan semua subkalimatnya) dengan interpretasi I ditentukan dengan melakukan pengulangan aturan-aturan semantik berikut ini : z
z z z z
Aturan Proposisi Nilai kebenaran dari setiap simbol proposisi p, q, r, … dalam E adalah sama dengan nilai kebenaran yang diberikan untuk I Aturan TRUE Kalimat true adalah true untuk I Aturan FALSE Kalimat false adalah false untuk I Aturan NOT Negasi kalimat : not F adalah true jika F adalah false dan false jika F adalah true Aturan AND Konjungsi F and G adalah true jika F dan G keduanya benar, dan false jika sebaliknya (yaitu jika F false atau G false)
15
Kalkulus Proposisi-Aturan Semantik z
z
z
z
Aturan or Disjungsi F or G adalah true jika F true atau jika G true, dan false jika keduanya false Aturan if-then Implikasi if F then G adalah true jika F false atau jika G true dan false jika F true dan G false Aturan if-andonly-if Ekivalensi F if and only if G adalah true jika nilai kebenaran F adalah sama dengan nilai kebenaran G, sebaliknya false jika memiliki nilai kebenaran keduanya berbeda. A Aturan if h if-then-else l Nilai kebenaran kondisional if F then G else H adalah nilai kebenaran G jika F true dan nilai kebenaran H jika F false. 16
Kalkulus Proposisi-Aturan Semantik Contoh,, misalkan sebuah kalimat : A : if (x and (not y)) then ((not x) or z) interpretasi I untuk A adalah I: xÆT yÆF zÆF Dengan menggunakan aturan semantik, maka kalimat A dapat ditentukan nilai k b kebenarannya, karena y Æ F, maka berdasarkan aturan not, (not y) Æ T karena x Æ T dan (not y) Æ T, maka berdasarkan aturan and, (x and (not y)) Æ T karena x Æ T, maka berdasarkan aturan not, (not x) Æ F karena (not x) Æ f dan z Æ F, maka berdasarkan aturan or, ((not x) or z) Æ F karena (x and (not y)) Æ T dan ((not x) or z) Æ F, maka berdasarkan aturan if-then, if (x and (not y)) then ((not x) or z) Æ F 17
Kalkulus Proposisi-Sifat Kalimat z z z
z
z
z
VALID (TAUTOLOGI) ( ) Kalimat A valid jika bernilai true berdasarkan semua interpretasi untuk A SATISFIABLE Kalimat A satisfiable jika bernilai true berdasarkan beberapa interpretasi untuk A CONTRADICTORY T T (UNSATISFIABLE) T Kalimat A contradictory jika bernilai False berdasarkan semua interpretasi untuk A IMPLIES Kalimat A implies kalimat B, jika untuk sebarang interpretasi I untuk A dan B, jika A bernilai true berdasarkan I maka B juga bernilai true berdasarkan I EQUIVALENT K li t A dan Kalimat d B ekivalen ki l jika, jik untuk t k setiap ti interpretasi i t t i A dan d B, B A mempunyaii nilai kebenaran yang sama dengan B CONSISTENT Sekumpulan p kalimat A1, A2, … konsisten jjika ada interpretasi p untuk A1, A2, … sehingga Ai (I = 1, 2, 3, …) bernilai true 18
Kalkulus Proposisi-Aturan Semantik Contoh, C t h z Kalimat w or (not w) adalah kalimat valid z Kalimat x and (not x) adalah kalimat contadictory
19
Kalkulus Proposisi-Kalimat Abstrak
20
Kalkulus Proposisi-Kalimat Abstrak
21
Kalkulus Proposisi-Kalimat Abstrak Bentuklah ke dalam kalimat abstrak
1. Sore hari ini mendung dan lebih dingin dari kemarin. Jika saya akan pergi berenang maka cuaca cerah. Jika saya tidak berenang maka saya akan pergi belanja. Jika saya pergi belanja maka saya akan berada dirumah tepat pada saat matahari terbenam. Misalkan Mi lk : p Å Sore hari ini cuaca cerah q Å Lebih dingin dari kemarin r Å Saya akan pergi berenang s Å Saya akan pergi belanja u Å Saya akan berada dirumah tepat pada saat matahari terbenam. Sore hari ini mendungg dan lebih dingin g dari kemarin : not p and q Jika saya akan pergi berenang maka cuaca cerah : if r then p Jika saya tidak berenang maka saya akan pergi belanja : if not r then s Jika saya pergi belanja maka saya akan berada dirumah tepat pada saat matahari terbenam : if s then u 22
Kalkulus Proposisi-Kalimat Abstrak SSeorang r rraja j yang m mutlak tl k h harus r sungguh-sungguh h h dapat berlaku sebagai binatang, harus berbuat seperti si rubah dan si singa, singa sebab singa tidak dapat melindungi dirinya terhadap jerat, dan si rubah tidak dapat mempertahankan diri terhadap srigala.
23
Kalkulus Proposisi-Kalimat Abstrak P Å seorangg raja j … sebagai g binatangg Q Å si rubah R Å si singa S Å tidak dapat melindungi dirinya terhadap jerat T Å tidak dapat p mempertahankan p diri terhadap p srigala. g
“Seorang raja yang mutlak harus sungguh-sungguh dapat berlaku sebagai binatang, harus berbuat seperti si rubah dan si singa…” Æ A : if p then q and r “…singa tidak dapat melindungi dirinya terhadap jerat..” Æ B : If r then s “…si rubah tidak dapat mempertahankan diri terhadap srigala.” Æ C : If q then t Sehingga : if B and C then A Æ If (If r then s) and (If q then t) then (if p then q and r) 24
Kalkulus Proposisi-Kalimat Abstrak 1 1.
Jika kamu mengirim e-mail e mail maka saya akan menyelesaikan program lebih awal. Jika kamu tidak mengirim e-mail maka saya akan tidur lebih awal. Jika saya tidur lebih awal maka saya y akan merasa lebih segar. g
2.
Kalau rakyat rajin bekerja dan Pemerintah cakap, maka masyarakat tenang atau pembangunan berjalan lancar lancar. Kalau rakyat tenang atau pembangunan berjalan lancar, maka negara sejahtera dan rakyat bahagia. Rakyat rajin bekerja.
3.
Jika hari hujan dan angin kencang maka terjadilah banjir. Jika terjadi banjir, rakyat menderita. Anginnya kencang, akan tetapi rakyat tidak menderita. menderita 25
Kalkulus Proposisi-Kalimat Abstrak 4.
Jika penawaran emas dibiarkan konstan dan permintaan emas bertambah maka harga emas naik. Jika permintaan emas bertambah yang menyebabkan harga emas naik, maka ada keuntungan bagi spekulator. Penawaran emas dibiarkan konstan.
5.
Kalau rakyat berkuasa dan ada pemilihan umum, itu berarti bahwa ada sistem demokrasi. Kalau ada pemilihan umum dan ada sistem demokrasi, maka pemerintah dapat diganti oleh rakyat rakyat. Rakyat berkuasa. berkuasa
6.
Kalau rakyat berpegang pada UUD ’45, maka rakyat menerima apa yang tercantum didalamnya. didalamnya Kalau rakyat menerima apa yang tercantum di dalam UUD ’45, maka rakyat menerima Pancasila. Rakyat berpegang pada UUD ’45 dan ada yang berpegang kepada ideologi lain.
26
Kalkulus Proposisi-Kalimat Abstrak 7 7. 8. 9.
Jika Dewi lulus Sarjan Informatika Informatika, maka orangtuanya akan senang dan dia akan segera mendapatkan pekerjaan, akan tetapi bila tidak cepat lulus maka usahanya akan sia-sia. y tidak keliru,, Dewi sudah diwisuda Sarjana j Jika saya Informatika dan pacarnya atau orangtuanya berada disampingnya. Jika Dewi tinggal di Jakarta, dia akan bahagia. Jika dia bahagia, dan menyukai pekerjaannya maka dia akan memperoleh gaji yang baik dari pekerjaannya atau dia sedang jatuh cinta. Jika dia jatuh cinta maka dia akan lebih menyukai pekerjaannya Dengan demikian, pekerjaannya. demikian maka dia akan memperoleh gaji yang baik dari pekerjaannya.
27
Kalkulus Proposisi-Kalimat Abstrak 10 Misalkan A 10. A, B dan C adalah variabel proposisi A = Anda Sakit Flu B = Anda Ujian C = Anda Lulus Ubahlah ekspresi berikut ini ke dalam Bahasa Indonesia a. if A then not B b if B then b. h not C c. if not B then C d. if A and B then C e. (If A then not C) or (if B then not C) f. (A and B) or (not B and C)
28
Kalkulus Proposisi-Kalimat Abstrak 11 Kalau harga di Toko itu rendah, 11. rendah tentu banyak pembelinya. pembelinya Toko itu dekat pemukiman penduduk atau tidak banyak pembelinya. Toko itu tidak dekat dengan pemukiman penduduk atau tidak banyak p y pembelinya. p y Toko itu tidak dekat dengan pemukiman penduduk. 12 Kalau rakyat berpegang pada UUD ’45 12. 45, maka rakyat menerima apa yang tercantum didalamnya. Kalau rakyat menerima apa yang tercantum di dalam UUD ’45, maka rakyat y menerima Pancasila. Kalau dalam berpolitik p ada yang y g berpegang kepada ideologi lain, maka negara Indonesia akan pecah. Rakyat berpegang pada UUD ’45 atau ada yang berpegang p g g kepada p ideologi g lain. 29
Kalkulus Proposisi-Nilai Kebenaran Penentuan nilai kebenaran suatu kalimat dapat dilakukan dengan 3 cara yaitu : 1. Tabel T b lK Kebenaran b 2. Tabel Jarang (sparse) 3. Pohon Semantik
30
Kalkulus Proposisi-Tabel Kebenaran if (p and q) then (p or (not r) M Menggunakan k T Tabel b lK Kebenaran b
31
Kalkulus Proposisi-Tabel Jarang if (p and q) then (p or (not r) M Menggunakan k T Tabel b l JJarang ((sparse p ttable) bl )
32
Kalkulus Proposisi-Pohon Semantik if (p and q) then (p or (not r) M Menggunakan k P Pohon h Semantik S tik
33
Kalkulus Proposisi-Pohon Semantik if (if x then th y)) then th (if (not ( t x)) then th (not ( t y)) ))
34
Kalkulus Proposisi-Nilai Kebenaran 1 1. 2. 3.
4.
5.
A : not (not p and not q) B : p and (p or q) C : [not p and (not q and r)] or (q and r) or (p and r) D : [ p and q ] or [ (if not p and q then p) or not q ] E : [ if p then q ] if and only if [if not q then not p ] 35
S l i no. 1 Solusi
36
S l i no. 2 Solusi
37
S l i no. 3 Solusi
38
S l i no. 4 Solusi
39
S l i no. 5 Solusi
40
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti z z
z
Digunakan untuk membuktikan validitas sebuah kalimat. kalimat Untuk membuktikan validitas sebuah kalimat diperlukan pembuktian nilai true, untuk semua interpretasi yang mungkin pada kalimat tersebut. Akan lebih mudah untuk membuktikan, jika ada 1 interpretasi yang mengakibatkan nilai kalimat tersebut false maka kalimat tersebut tidak valid.
41
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti A : if ((not x) or (not y)) then (not (x and y)) Dimisalkan A bernilai False berdasarkan suatu interpretasi, interpretasi sehingga : ((not x)) or (not ( y)) then (not ( (x ( and y)) Å False if (( Dicobakan sehingga gg asumsi awal (false) ( ) dapat p terbukti. Antisenden : (not x) or (not y) Å True Konsekuen : not ((x and y) Å False 42
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti Antisenden : ((not x)) or (not ( y) Å True Konsekuen : not (x and y) Å False Dari antisenden belum dpt ditarik kesimpulan, shg dicari dari Konsekuen yaitu didapat not ((x and y)) Å False (x and y) Å True I : x Å True y Å True. Dari interpretasi yang didapat, maka Antisenden (not x) or (not y) Å True (asumsi awal) not (True) or not (True) Å False (dari I) Terdapat Ketidaksesuaian antara asumsi awal dengan Interpretasi yang didapat, maka terjadi j di kontradiksi. k dik i Karena K kontradiksi k dik i maka k dapat d diambil di bil kesimpulan k i l bahwa b h kalimat k li bersifat VALID 43
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti B : (if x then y) if and only if ((not x) or y) Ada 2 kasus yang menjadikan kalimat B adalah False, yaitu I1 : Sisi kiri : (if x then y) Å True Sisi kanan : ((not x) or y) Å False
I2 :
Sisi kiri : ((not x) or y) Å True Sisi kanan : (if x then y) Å False
Maka harus diuji-cobakan untuk keseluruhan kasus kasus. 44
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti Kasus I1 : Sisi kiri : if x then y Å True Sisi kanan : not x or y Å False Dari sisi kanan dpt diambil kesimp kesimpulan lan : not x or y Å False I1 : y Å False x Å True Sehingga sisi kiri, if x then y Å True (asumsi awal) Dari I1 , dapat disimpulkan bahwa If True then False Å False Sehingga terjadi KONTRADIKSI antara asumsi awal dengan I1 45
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti Kasus I2 : Sisi kiri : ((not x) or y) Å True Sisi kanan : (if x then y) Å False Dari sisi kiri dpt p diambil kesimpulan p : (if x then y) Å False I2: y Å False x Å True Sehingga sisi kanan, (not x) or y Å True (asumsi awal) Dari I2 , dapat disimpulkan bahwa
(not True) or False Å False
Sehingga terjadi KONTRADIKSI antara asumsi awal dengan I2
46
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti Kasus 1 : Terjadi K T rj di KONTRADIKSI antara t r asumsi mi awal dengan I1 K Kasus 2 : Terjadi T j di KONTRADIKSI antara t asumsii awal dengan I2 Sehingga disimpulkan bahwa kalimat B adalah VALID
47
K lk l P Kalkulus Proposisi-Falsification i i F l ifi ti 1 1. 2. 3 3.
4.
5.
(if x then y or if x then z) iff (if x then y and z) if (w and x or not z) then (not w iff z) and not x if (not x and y) and (if x then z) and (if z then w) and (if w then u) then u if ((if p then q) and (if ( not p then r)) and (if ( r then s)) then (if not q then s) if ((if p then q) and (if ( r then s)) and (if ( not p then not s)) then (if r then q)
48
EKIVALENSI DAN KONSEKUENSI LOGIK Definisi Ekivalensi Logik g Dua buah kalimat A dan B merupakan ekivalensi logik jika dan hanya jika memiliki nilai yang sama pada semua interpretasi yang diberikan. Teorema A Ekivalensi B, jika dan hanya jika ( A iff B) merupakan Tautologi Definisi Konsekuensi Logik B adalah konsekuensi logik dari A jika untuk setiap pemberian nilai kebenaran ke variabel pada A dan pada B sedemikian sehingga jika A mempunyai nilai TRUE maka B juga mempunyai nilai TRUE Teorema B Konsekuensi Logis dari A, jika dan hanya jika (if A then B) merupakan Tautologi Catatan : Jika pernyataan lebih dari 1, misal A1, A2, A3 maka bentuk konsekuensi logiknya : IF (A1 AND A2 AND A3) THEN B
49
EKIVALENSI DAN KONSEKUENSI LOGIK Co to Kasus : Contoh Periksa apakah B merupakan kesimpulan dari 6 argumen dibawah ini ? A1 : if P then (Q and R and S) A2 : if T then ((if U then (if ( not Y then not S)) )) A3 : if Q then T A4 : if R then (if X then U) A5 : if Y then not X A6 : X B : not P Jawaban Harus dibuktikan bahwa kalimat : IF (A1 and A2 and A3 and A4 and A5 and A6) THEN B adalah VALID 50
KONSEKUENSI LOGIK
A1 : if p th then (q ( andd r andd s)) Å true t A2 : if t then (if u then (if not y then not s)) Å true A3 : if q then t Å true A4 : if r then (if x then u) Å true A5 : if y then not x Å true A6 : x Å true B : not p Å false 51
KONSEKUENSI LOGIK A6 : x Å True B : not p Å False ; p Å True A5 : if y then not x Å True if y then not True Å True ; y Å False A1 : if p then (q and r and s) Å True if True then (q and r and s) Å True (q and r and s) Å True q Å True; r Å True; s Å True A3 : if q then t Å True if True T then h t Å True; T t Å True T A4 : if r then (if x then u) Å True if True then (if True then u) Å True (if True then u) Æ True u Å True
A2 : if t then (if u then (if not y then not s)) Å True if True then (if True then (if not False then not True)) Å True if True then False Å True False ≠ True Æ Kontradiksi
Karena terjadi Kontradiksi maka V lid K Valid, Karena valid lid maka k B adalah d l h Konsekuensi Logik (Kesimpulan) dari A1, A2, A3, A4, A5, dan A6
52
Kalkulus Proposisi-Konsekuensi Logik Selidiki apakah kesimpulan yang diberikan merupakan konsekuensi logik dari pernyataan-pernyataan yang diberikan dengan menggunakan Metode Asumsi Salah ! 1.
J kamu mengirim Jika e g ee-mail maka ssaya y akan menyelesaikan e ye es program p og lebih eb awal. w . Jika kamu tidak mengirim e-mail maka saya akan tidur lebih awal. Jika saya tidur lebih awal maka saya akan merasa lebih segar. Jadi, Jika saya tidak menyelesaikan program lebih awal maka saya akan merasa lebih segar
2 2.
Kalau rakyat Kala rak at rajin bekerja dan Pemerintah cakap, cakap maka mas masyarakat arakat tenang ata atau pembangunan berjalan lancar. Kalau rakyat tenang atau pembangunan berjalan lancar, maka negara sejahtera dan rakyat bahagia. Rakyat rajin bekerja. Jadi, Negara sejahtera 53
Kalkulus Proposisi-Konsekuensi Logik 3 3.
Jika hari hujan dan angin kencang maka terjadilah banjir banjir. Jika terjadi banjir, rakyat menderita. Anginnya kencang, akan tetapi rakyat tidak menderita. Jadi, Hari tidak hujan
4.
Jika penawaran emas dibiarkan konstan dan permintaan emas bertambah maka harga emas naik. Jika permintaan emas bertambah yang menyebabkan harga emas naik, maka ada keuntungan bagi spekulator. Penawaran emas dibi k kkonstan. dibiarkan Jadi, Ada keuntungan bagi spekulator
54
Kalkulus Proposisi-Konsekuensi Logik 5.
Kalau rakyat berkuasa dan ada pemilihan umum, itu berarti bahwa ada sistem demokrasi. Kalau ada pemilihan umum dan ada sistem demokrasi, maka pemerintah dapat diganti oleh rakyat. Rakyat berkuasa. Jadi Pemerintah dapat diganti oleh rakyat Jadi,
6.
Kalau rakyat berpegang pada UUD ’45, maka rakyat menerima apa yang y Kalau rakyat y menerima apa p yang y g tercantum di dalam tercantum didalamnya. UUD ’45, maka rakyat menerima Pancasila. Rakyat berpegang pada UUD ’45 dan ada yang berpegang kepada ideologi lain. Jadi Rakyat menerima Pancasila Jadi,
55
Kalkulus Proposisi-Konsekuensi Logik 7.
Kalau harga g di Toko itu rendah,, tentu banyak y pembelinya. p y Toko itu dekat pemukiman penduduk atau tidak banyak pembelinya. Toko itu tidak dekat dengan pemukiman penduduk atau tidak banyak pembelinya. Toko itu tidak dekat dengan pemukiman penduduk. Jadi, harga Toko itu tidak rendah.
8.
Kalau rakyat y berpegang p g g pada p UUD ’45,, maka rakyat y menerima apa p yang y g tercantum didalamnya. Kalau rakyat menerima apa yang tercantum di dalam UUD ’45, maka rakyat menerima Pancasila. Kalau dalam berpolitik ada yang berpegang kepada ideologi lain, maka negara Indonesia akan pecah. y berpegang p g g pada p UUD ’45 atau ada yang y g berpegang p g g kepada p ideologi g Rakyat lain. Jadi, Rakyat menerima Pancasila atau negara Indonesia akan pecah 56
A Asumsi i Asumsi su s 1 p Å kamu mengirim email q Å saya akan menyelesaikan progam lebih awal r Å saya y akan tidur lebih awal s Å saya merasa lebih segar Asumsi 2 p Å rakyat rajin bekerja, q Å pemerintah cakap r Å rakyat y tenangg s Å pembangunan berjalan lancar t Å negara sejahtera u Å rakyat bahagia 57
A Asumsi i Asumsi su s 3
p Å hari hujan, q Å angin kencang r Å terjadi j di banjir b ji s Å rakyat menderita. Asumsi 4
p Å penawaran emas dibiarkan konstan q Å permintaan emas bertambah r Å harga emas naik s Å ada keuntungan bagi spekulator 58
A Asumsi i Asumsi su s 5
pÅ qÅ rÅ sÅ
rakyat berkuasa ada pemilihan umum ada d sistem i demokrasi d k i pemerintah dapat diganti oleh rakyat
Asumsi 6
p Å rakyat berpegang pada UUD ’45, q Å rakyat menerima apa yang tercantum didalamnya, didalamnya r Å rakyat menerima Pancasila, t Å ada yang berpegang kepada ideologi lain 59
A Asumsi i Asumsi su s 7
p Å Harga di Toko itu rendah, q Å banyak pembelinya, r Å Toko T k itu i dekat d k pemukiman ki penduduk d d k Asumsi 8
p Å rakyat berpegang pada UUD ’45, q Å rakyat menerima apa yang tercantum didalamnya, r Å rakyat menerima Pancasila, Pancasila t Å ada yang berpegang kepada ideologi lain, s Å negara Indonesia akan pecah 60
KONJUNGSI DAN DISJUNGSI JAMAK Misal diberikan kalimat yyangg mengandung g g operator p konjungsi j g atau konjungsi j g lebih dari satu, A : p and q and r B : p or q or r Maka urutan perngerjaan operasi pada kalimat tersebut dilakukan dari kiri ke kanan sesuai aturan sebagai berikut Konjungsi Jamak A1 and A2 and A3 and A4 and … and An Memiliki arti : ((… ((A1 and A2) and A3) and A4) and … ) and An) Disjungsi Jamak A1 or A2 or A3 or A4 or … or An Memiliki l k arti : ((… ((A1 or A2) orA3) or A4) or … ) and An)
61
KONJUNGSI DAN DISJUNGSI JAMAK Kalimat-kalimat K lim t k lim t berikut b rik t adalah d l h ekivalen ki l karena k r adanya d hukum asosiasi : A : ((w and x) and y) and z B : w and (x and (y and z)) C : w and ((x and y) and z)
62
KONJUNGSI DAN DISJUNGSI JAMAK Aturan semantik untuk hubungan jamak : Konjungsi jamak A1 and A2 and A3 and … and An bernilai True jika tiap conjuct A1, A2, A3, … An adalah True Disjungsi j g Jamak J A1 or A2 or A3 or … or An bernilai True jika jika setidaknya salah satu dari A1, A2, A3, … An adalah True 63
SUBSTITUSI Substitusi adalah operasi pengantian subkalimat dari suatu kalimat dengan subkalimat yang lain. Substitusi Total Penggantian seluruh kemunculan suatu subkalimat Substitusi Parsial Penggantian nol, satu, atau lebih kemunculan suatu subkalimat 64
SUBSTITUSI TOTAL Definisi S Substitusi bstit si Total Jika A, B, C adalah kalimat, maka A w{B Å C} Adalah kalimat yang dihasilkan dengan mengganti g C. seluruh kemunculan B di A dengan 65
SUBSTITUSI TOTAL Contoh : 1. [ x and (y or x) ] w { x Å (if w then z) } menghasilkan : (if w then z) and (y or (if w then z)) 2 2.
[ if x then (y and z) ] w { (y and z) Å w } menghasilkan : if x tthen e w 66
SUBSTITUSI TOTAL Catatan : 1. Substitusi dikerjakan dalam 1 langkah [x and y] w { x Å (x and z)} menghasilkan (x and z) and y 2.
Substitusi tidak memiliki efek jika subkalimat yang akan diganti tidak muncul dalam kalimat, [ and [x d y]] w { z Å w } menghasilkan h ilk menghasilkan h ilk x andd y
3.
Substitusi untuk konjungsi dan disjungsi jamak : [x and y and z] w{(x w and y) Å w} Sebenarnya [(x and y) and z]w{(x and y) Å w} menghasilkan w and z 67
SUBSTITUSI PARSIAL Definisi S Substitusi bstit si Parsial Jika A, B, C, adalah kalimat maka A {B Å C} Akan menghasilkan g salah satu kalimat dengan g mengganti nol, sebagian, atau seluruh kemunculan subkalimat B di A dengan subkalimat C 68
SUBSTITUSI PARSIAL Definisi S Substitusi bstit si Parsial Jika A, B, C, adalah kalimat maka A {B Å C} Akan menghasilkan g salah satu kalimat dengan g mengganti nol, sebagian, atau seluruh kemunculan subkalimat B di A dengan subkalimat C 69
SUBSTITUSI PARSIAL Contoh : [ x or x ]
{x Å y}
akan menghasilkan salah satu dari kalimat-kalimat berikut : 1 x or x 1. {mengganti nol kemunculan x } 2. y or x {mengganti kemunculan x pertama} 3. x or y {mengganti kemunculan x kedua} 4. y or y {mengganti seluruh kemunculan dari x} 70
SUBSTITUSI PARSIAL Substitusi parsial bersifat invertible, invertible yaitu salah satu kalimat yang mungkin dihasilkan adalah kalimat semula. (A {BÅC}) {C Å B} hasilnya adalah A Contoh : 1. [ (x or y) {x Å y}] {y Å x} salah satu kalimat yang mungkin adalah : x or y 2. [(x or y) w {x Åy}] w {y Å x } hasil yang diperoleh tepat 1 kalimat yaitu : x or x 71
SUBSTITUSI JAMAK Definisi : Misal A, B1, B2, …, dan C1, C2, …, Cn adalah kalimat dengan B1, B2, …, Bn saling berlainan. Substitusi Total Substitusi total dituliskan sebagai : A w [ B1 Å C1 B2 Å C2 … Bn Å Cn ] Adalah kalimat yang diperoleh dengan menggantikan secara simultan (serempak) setiap kemunculan Bi di A dengan Ci 72
SUBSTITUSI JAMAK Substitusi Partial Substitusi partial dituliskan sebagai : A [ B1 Å C1 B2 Å C2 … Bn Å Cn ] Adalah salah satu kalimat yang diperoleh dengan menggantikan nol, satu, atau lebih kemunculan Bi di A dengan Ci 73
SUBSTITUSI JAMAK Contoh : 1. Substitusi jamak dilakukan serentak dalam 1 langkah x
w[
xÅy yÅx]
menghasilkan h ilk kkalimat li t : y Bedakan dengan substitusi bertahap sebagai berikut : x w { x Åy } w { y Å z }
menghasilkan kalimat : z 74
SUBSTITUSI JAMAK 2 2.
[ if x then if y or x ◄ then y or z ]
xÅz (y or z ) Å not z
menghasilkan : [ if z then if (y or z) then not z ] 75
SUBSTITUSI JAMAK 3.
[ if x then if (y or x) then (y or z) ]
xÅz (y or z) Å not z
menghasilkan salah satu dari 8 kalimat. a. if x then if y or x then y or z b b. if z then if y or x then y or z c. if x then if y or z then y or z d. if z then if y or z then y or z e e. if x then if y or x then not z f. if z then if y or x then not z g. if x then if y or z then not z h h. if z then th if y or z then th nott z 76
PERLUASAN INTERPRETASI Definisi Interpretasi yang diperluas Jika I adalah suatu interpretasi, x adalah simbol proposisi dan τ adalah nilai kebenaran (true/false) maka perluasan interpretasi : [xÅI]oI adalah interpretasi yang memberikan nilai τ pada x dan memberikan nilai kebenaran yang sesuai dengan interpretasi I untuk semua simbol proposisi selain x. 77
PERLUASAN INTERPRETASI Contoh : IA : x Å T yÅF Jika IB = [y Å T] o IA maka menghasilkan perluasan interpretasi IB : x Å T yÅT 78
METODA DEDUKSI z
z
z
Salah satu metoda yang digunakan untuk menarik suatu kesimpulan berdasarkan pernyataan atau premis-premis yang diketahui. Metoda deduksi ini menggunakan aturan-aturan penalaran, ekivalensi l ik dan logik d tautologi l i Untuk mempermudah operasi penurunan digunakan operator-operator lama sbb:
79
METODA DEDUKSI z
z
Metoda Deduksi hanya dapat menunjukkan bahwa kesimpulan dari suatu penalaran valid; yaitu Jika kesimpulan yyangg diperoleh p dapat p dicapai/dibuktikan p dengan g aturan yang ada Jika tidak dapat menarik suatu kesimpulan dengan metoda d d k maka deduksi, k tidak d k berarti b penalaran l tersebut b tidak d k valid. ld Ketidakvalidan suatu penalaran harus tetap dibuktikan secara eksplisit dengan Tabel Kebenaran atau Analisis Asumsi Salah (Falsification)
80
ATURAN PENALARAN DASAR KONJUNGSI Jika diketahui proposisi p dan q TRUE maka dapat disimpulkan bahwa penalaran berbentuk k j konjungsi i (p ( ∧ q)) juga j akan k bernilai b il i TRUE
81
ATURAN PENALARAN DASAR SIMPLIFIKASI Jika penalaran berbentuk konjungsi (p ∧ q) bernilai TRUE maka dapat disimpulkan bahwa proposisi unsur pembentuknya, b k yaitu i p dan d q TRUE
82
ATURAN PENALARAN DASAR ADDITION DISJUNGSI Jika diketahui suatu proposisi p bernilai TRUE maka d t disimpulkan dapat di i lk bahwa b h proposisi i i disjungsi di j i dengan proposisi lain juga bernilai TRUE
83
ATURAN PENALARAN DASAR SILOGISME DISJUNGTIVE Jika diketahui disjungsi p ∨ q bernilai TRUE dan salah satu t proposisi i i pembentuknya b t k FALSE maka k dapat d t ditarik kesimpulan proposisi yang lain TRUE
84
ATURAN PENALARAN DASAR MODUS PONEN Jika kondisional p ⊃ q TRUE; dimana antisendennya TRUE maka k dapat d t disimpulkan di i lk bahwa b h konsekuen k k harus TRUE
85
ATURAN PENALARAN DASAR MODUS TOLLENS Jika kondisional p ⊃ q TRUE; dimana konsekuennya FALSE maka k dapat d t disimpulkan di i lk bahwa b h antisenden harus FALSE
86
ATURAN PENALARAN DASAR SILOGISME HIPOTETIK Jika diketahui 2 buah kondisional yang b k i berkesinambungan b maka k ddapatt disimpulkan di i lk suatu t kalimat kondisional yang baru
87
88
ATURAN PENALARAN DASAR Note N t : Metoda Deduksi mengandung kesulitan karena tidak ada d suatu t pegangan yang pasti ti untuk t k menurunkan k kesimpulan, yaitu apakah harus menggunakan suatu aturan penalaran tertentu (misal : Simplifikasi, Simplifikasi Modus Ponen, dll) atau menggunakan aturan ekivalensi atau aturan lainnya
89
METODA DEDUKSI DEDUKSI-CONTOH CONTOH Diketahui : Jika ibu datang dari pasar, maka ani senang sekali Ibu datang dari pasar dan membawa kue bolu Jadi : Ani senang sekali Apakah kesimpulan tersebut Valid? Jawab : Ubah penalaran tersebut menjadi kalimat proposisi Premis: Jika ibu datangg dari pasar, p maka ani senangg sekali : p ⊃ q Ibu datang dari pasar dan membawa kue bolu : p ∧ r Kesimpulan: A i senang sekali Ani k li : q 90
METODA DEDUKSI DEDUKSI-CONTOH CONTOH
91
METODA DEDUKSI DEDUKSI-CONTOH CONTOH Diketahui : Ani masuk sekolah atau ani tidak masuk sekolah Jika ani tidak masuk sekolah maka sekolah pasti libur Sekolah Tidak Libur Apa Kesimpulan dari penalaran tersebut ? Jawab : Gunakan metode deduksi ! Premis: Ani masuk sekolah atau ani tidak masuk sekolah : p ∨ ~ p Jika ani tidak masuk sekolah maka sekolah pasti libur : ~ p ⊃ q Sekolah Tidak Libur : ~ q 92
METODA DEDUKSI DEDUKSI-CONTOH CONTOH
93
C t hK Contoh Kasus D Deduksi d k i 1 1.
Tentukan kesimpulan dari Pernyataan berikut ini : Sore hari ini mendung dan lebih dingin dari kemarin. Jika Saya akan pergi berenang maka cuaca cerah. Jika saya tidak berenang maka saya akan pergi belanja. Jika saya pergi belanja maka saya akan berada dirumah tepat pada saat matahari terbenam. Jawab : Misalkan : p Å Sore hari ini cuaca cerah q Å Lebih dingin dari kemarin r Å Saya akan pergi berenang s Å Saya akan pergi belanja u Å Saya akan berada dirumah tepat pada saat matahari terbenam. 94
S l i No. Solusi N 1
95
S l i No. Solusi N 1
96
N 2 No. 2 Jika kamu mengirim e-mail 2. e mail maka saya akan menyelesaikan program lebih awal. Jika kamu tidak mengirim e-mail maka saya akan tidur lebih awal. Jika saya tidur lebih awal maka saya akan merasa lebih segar. Jawab : Misalkan : p Å kamu mengirim email q Å saya y akan menyelesaikan y progam p g lebih awal r Å saya akan tidur lebih awal s Å saya merasa lebih segar 97
S l i No. Solusi N 2
98
N 3 No. 3 Jika hari hujan dan angin kencang maka terjadilah 3. banjir. Jika terjadi banjir, rakyat menderita. Anginnya kencang, akan tetapi rakyat tidak menderita. Jawab : Mi lk Misalkan p Å hari hujan, q Å angin kencang r Å terjadi banjir s Å rakyat menderita. 99
S l i No. Solusi N 3
100
N 4 No. 4 Jika penawaran emas dibiarkan konstan dan permintaan emas 4. bertambah maka harga emas naik. Jika permintaan emas bertambah yang menyebabkan harga emas naik, maka ada keuntungan bagi spekulator. Penawaran emas dibiarkan konstan. Jawab : Misalkan p Å penawaran emas dibiarkan konstan q Å permintaan emas bertambah r Å harga emas naik s Å ada keuntungan bagi spekulator 101
N 5 No. 5 Kalau rakyat berkuasa dan ada pemilihan umum, 5. umum itu berarti bahwa ada sistem demokrasi. Kalau ada pemilihan umum dan ada sistem demokrasi, maka pemerintah dapat diganti oleh rakyat. Rakyat berkuasa. Jawab : Misalkan p Å rakyat berkuasa q Å ada pemilihan umum r Å ada sistem demokrasi s Å pemerintah dapat diganti oleh rakyat
102
N 6 No. 6 Kalau rakyat berpegang pada UUD ’45 6. 45, maka rakyat menerima apa yang tercantum didalamnya. Kalau rakyat menerima apa yang tercantum di dalam UUD ’45, maka rakyat menerima Pancasila. Rakyat berpegang pada UUD ’45 dan ada yang berpegang kepada ideologi lain. Jawab : Misalkan p Å rakyat berpegang pada UUD ’45, q Å rakyat menerima apa yang tercantum didalamnya, r Å rakyat menerima Pancasila, t Å ada yang berpegang kepada ideologi lain, 103
N 7 No. 7 Kalau harga di Toko itu rendah 7. rendah, tentu banyak pembelinya. Toko itu dekat pemukiman penduduk atau tidak banyak pembelinya. Toko itu tidak dekat dengan pemukiman penduduk atau tidak banyak pembelinya. Toko itu tidak dekat dengan pemukiman penduduk. Jawab : Misalkan p Å Harga di Toko itu rendah, q Å banyak pembelinya, r Å Toko itu dekat pemukiman penduduk 104
N 8 No. 8.
Kalau rakyat y berpegang p g gp pada UUD ’45,, maka rakyat y menerima apa p yang tercantum didalamnya. Kalau rakyat menerima apa yang tercantum di dalam UUD ’45, maka rakyat menerima Pancasila. Kalau dalam berpolitik ada yang berpegang kepada ideologi lain, maka negara Indonesia akan pecah. Rakyat berpegang pada UUD ’45 atau t ada d yang b berpegang kkepada d id ideologi l i llain. i
Jawab : Misalkan p = rakyat berpegang pada UUD ’45, q = rakyat menerima apa yang tercantum didalamnya, r = rakyat menerima Pancasila, t = ada yang berpegang kepada ideologi lain, s = negara Indonesia akan pecah
105
N 9 No. 9 Hanya kalau orang lulus ujian saringan 9. saringan, maka ia diterima di universitas. Kalau orang menjadi mahasiswa, ia wajib membayar uang SPP. Kalau orang tidak lulus ujian saringan, maka ia tidak wajib membayar uang SPP. Jawab : Misalkan p Å orang lulus ujian saringan q Å ia diterima di universitas r Å orang menjadi mahasiswa t Å wajib membayar uang SPP 106
N 10 No. 10. Tentukan apakah p „„Sore hari ini cerah atau saya y akan berada di rumah tepat pada saat matahari terbenam“ merupakan penalaran yang sahih dari pernyataan-pernyataan berikut ini : Saya tidak akan pergi berenang ataupun juga tidak pergi belanja, jika sore hari ini cuaca mendung. g Jika saya y tidak akan p pergi g berenang g ataupun juga tidak pergi belanja maka cuaca hari ini tidak lebih dingin dari kemarin. Cuaca hari ini lebih dingin dari kemarin atau saya akan berada di rumah tepat pada saat matahari terbenam. Jawab Misalkan p = sore hari ini cuaca mendung; q = Saya S akan pergi berenang; r = Saya akan pergi belanja; s = Lebih dingin dari kemarin; t = Saya akan berada dirumah tepat pada saat matahari terbenam 107
S l i No. Solusi N 4
108
S l i No. Solusi N 5
109
S l i No. Solusi N 6
110
S l i No. Solusi N 7
111
S l i No. Solusi N 8
112
S l i No. Solusi N 9
113
S l i No. Solusi N 10
114
