LOGIKA DAN PEMBUKTIAN

BAB I

LOGIKA DAN PEMBUKTIAN

A. PENGANTAR Prinsip dari logika matematika memiliki korelasi dengan pembuktian kebenaran yang dilakukan menggunakan tabel kebenaran ataupun tanpa menggunakan tabel kebenaran dan juga prisip logika matematika berkolerasi dengan kalimat berkuantor tunggal dan ganda. B. PROPOSISI Proposisi (statement) merupakan sebuah kalimat yang memiliki tepat satu kebenararan , yaitu bisa bernilai True atau False tetapi tidak dapat sekaligus keduanya (yaitu true dan false) . Contoh Proposisi :

Monas berada di Jakarta

Kalimat tersebut bernilai TRUE

2 + 30 = 230

Kalimat tersebut bernilai FALSE

1+1=2

Kalimat tersebut bernilai TRUE

5 > 35

Kalimat tersebut bernilai FALSE

Contoh Bukan Proposisi :

Siapa Namamu ? x+y=5 Kerjakan dengan teliti Proposisi sendiri di bagi menjadi beberapa macam, yaitu : 1. Proposisi Primitif : suatu proposisi yang tidak menggunakan kata penghubung . Contoh : Monas berada di Jakarta Matematika Diskrit Oleh . Dwi Nurul Huda, ST

1

2. Proposisi

Majemuk

:

suatu

proposisi

yang

menggunakan

kata

penghubung(connectives) Contoh : BJ Habibie adalah seorang mantan presiden dan wakil presiden C. KATA PENGHUBUNG ( CONNECTIVES) Kata penghubung (connectives) dipergunakan untuk mengkombinasikan dua atau lebih kalimat/pernyataan/statement menjadi satu adalah : Nama

Simbol

Contoh

Arti

Negasi



a

Negasi a

Konjungsi



ab

a dan b

Disjungsi



ab

a atau b

Implikasi

→

a→b

Jika a maka b

Biimplikasi

↔

a↔b

a Jika dan hanya jika b

Contoh pengaplikasian kata penghubung dalam suatu proposisi : Diketahui proposisi berikut : p : hari ini hujan q : murid-murid di liburkan dari sekolah Maka : Nama Negasi

Simbol p

Bentuk Proposisi Majemuk Hari ini tidak hujan

Konjungsi

pq

Hari ini hujan dan murid-murid diliburkan dari sekolah

Disjungsi

pq

Hari ini hujan atau murid-murid di liburkan dari sekolah

Implikasi

p→q

Jika hari ini hujan, maka murid-murid diliburkan dari sekolah

Biimplikasi

q↔p

murid-murid diliburkan dari sekolah jika dan hanya jika Hari ini hujan

Matematika Diskrit Oleh . Dwi Nurul Huda, ST

2

D. TABEL KEBENARAN Tabel kebenaran digunakan untuk mengevaluasi apakah sebuah proposisi majemuk bernilai benar atau salah. Contoh : p

q

q

p^q

pvq

p→q

p↔q

S S B B

S B S B

B S B S

S S S B

S B B B

S B S B

S B B S

DO YOU KNOW 1.

Sebuah proposisi majemuk jika bernilai benar pada semua kasus disebut tautologi

2.

Sebuah proposisi majemuk jika bernilai salah pada semua kasus disebut kontradiksi

E. PENJELASAN TENTANG KATA PENGHUBUNG ( CONNECTIVES) Seperti yang sudah disebutkan sebelumnya penghubung kalimat/connectives terdiri dari beberapa macam, yaitu : 1. NEGASI (NOT) Negasi disebut juga sebagai ingkaran. Suatu pernyataan dapat menggunakan kata penghubung negasi. Kata penghubung negasi sendiri biasanya di bentuk dengan menambahkan kata TIDAK atau BUKAN dalam suatu kalimat yang tepat. Simbol dari sebuah negasi adalah “  “ . Apabila di gambarkan menggunakan tabel kebenaran : p

p

B

S

p : Hari senin libur

S

B

p : Hari senin TIDAK libur

DO YOU KNOW

Contoh :

1.

Terdapat beberapa literature dalam penulisan notasi negasi, yaitu p , ~p , p

2.

Kata ‘Tidak’ dapat dituliskan ditengah pernyataan. Jika kata ‘Tidak‘ dicantumkan diawal kalimat biasanya diberi tambahan kata ‘benar‘, sehingga menjadi kalimat ‘tidak benar‘.


3

2. KONJUNGSI (AND) Konjungsi merupakan kata

penghubung yang dapat digunakan pada kombinasi

proposisi menggunakannya dengan cara menambahkan kata DAN dalam suatu kombinasi kalimat yang tepat. Simbol dari sebuah konjungsi adalah “ ^ “ . Suatu pernyataan yang mengandung konjungsi akan bernilai B (Benar) apabila nilai seluruh proposisi bernilai B(Benar) juga. Apabila di gambarkan menggunakan tabel kebenaran : Contoh :

p

q

p ^q

S

S

S

p : Hari Minggu libur

S

B

S

q : Hari Senin Upacara Bendera

B

S

S

p^q : Hari Minggu libur DAN Hari Senin Upacara

B

B

B

Bendera

3. DISJUNGSI (OR) Disjungsi merupakan kata penghubung yang dapat digunakan pada kombinasi proposisi menggunakannya dengan cara menambahkan kata OR dalam suatu kombinasi kalimat yang tepat. Simbol dari sebuah disjungsi adalah “ v “ . Suatu pernyataan yang mengandung konjungsi akan bernilai S (Salah) apabila nilai seluruh proposisi bernilai S(Salah) juga dan akan bernilai B(Benar) apabila salah satunya bernilai B(Benar). Apabila di gambarkan menggunakan tabel kebenaran : p

q

pvq

S

S

S

S

B

B

B

S

B

B

B

B

Contoh : p : para pegawai Google diwajibkan mahir bahasa pemrograman PHP q : para pegawai Google diwajibkan mahir bahasa pemrograman ASP pvq : para pegawai Google diwajibkan mahir bahasa

pemrograman PHP atau ASP Matematika Diskrit Oleh . Dwi Nurul Huda, ST

4

4. IMPLIKASI Implikasi atau kondisional merupakan kata penghubung yang dapat digunakan pada kombinasi proposisi. Penggunaannya dengan cara menambahkan kata JIKA ... MAKA ... dalam suatu kombinasi kalimat yang tepat. Simbol dari sebuah implikasi adalah “ → “ . Suatu pernyataan p → q memiliki nilai kebenaran S(Salah) jika nilai kebenaran p bernilai B(Benar) dan nilai kebenaran dari q bernilai S (Salah) jika selainnya maka akan bernilai B(Benar). Apabila di gambarkan menggunakan tabel kebenaran : Contoh :

p

q

p→q

S

S

B

p

: Anda membayar lunas

S

B

B

q

: Anda mendapatkan potongan 10% dari biaya

B

S

S

B

B

B

pengembangan p→q : JIKA anda membayar lunas MAKA mendapatkan

potongan 10% dari biaya pengembangan 5. BI-IMPLIKASI Bi-implikasi atau bikondisional merupakan kata penghubung yang dapat digunakan pada kombinasi proposisi. Penggunaannya dengan cara menambahkan kata ...JIKA DAN HANYA JIKA ... dalam suatu kombinasi kalimat yang tepat. Simbol dari sebuah biimplikasi adalah “ ↔ “ . Suatu pernyataan p ↔ q memiliki nilai kebenaran B(Benar) jika nilai kebenaran p bernilai B(Benar) dan q bernilai B(Benar) atau nilai kebenaran dari p bernilai (Salah) dan q bernilai S (Salah) jika selainnya maka akan bernilai S(Salah). Apabila di gambarkan menggunakan tabel kebenaran : Contoh :

p

q

p↔q

S

S

B

p

: Anda menggunakan jas hujan

S

B

S

q

: Hari ini hujan

B

S

S

p↔q : Anda menggunakan jas hujan JIKA DAN HANYA JIKA

B

B

B

hari ini hujan


5

F. PENJELASAN TENTANG EKUIVALENSI LOGIKA Disebut ekuivalensi apabila logika tersebut memiliki arti yang sama, artinya ketika dibandingkan memiliki arti yang sama. Berikut tabel yang berisi hukum ekuivalensi logika : 1. Hukum Komutatif : 7. Hukum Negasi Ganda/Involusi : (p) =p p ^q = q ^ p Pvq=qvP 2. Hukum Asosiatif : 8. Hukum Idempoten : (p ^q) ^r = p^( q ^ r) p ^p = p (p v q) v r = p v ( q v r) p v p =p 3. Hukum Distributif : 9. Hukum De Morgan : p ^ (q v r) = (p ^ q) v (p ^ r) (p ^q) = p v q p v ( q ^ r) =( p v q) ^ (p v r) (p v q) =p ^q 4. Hukum Identitas : 10. Hukum Penyerapan/ Absorpsi : p ^T = p p v (p ^q) =p pvF=p p^ (p v q) =p 5. Hukum Ikatan (Dominasi/null) : 11. Negasi T dan F : T = F p ^F = F F = T pvT=T 6. Hukum Negasi : p v p = T p ^ p = F CONTOH : Buktikan ekuivalensi pernyataan berikut : (p v q) v (p ^ q) Ξ p Jawab : (p v q) v (p ^ q) = (p ^ q) v (p ^ q) = p ^ (q vq) = p ^ T = p Sehingga terbukti bahwa : (p v q) v (p ^ q) Ξ p

G. PENJELASAN TENTANG DISJUNGSI EKSKLUSIF DAN DENIAL JOIN Simbol disebut sebagai disjungsi ekslusif. Penulisanp q di baca sebagai p atau q tetapi tidak keduanya.


6

Apabila di gambarkan menggunakan tabel kebenaran : p

Contoh :

p

q

q

S

S

S

p

: Jika hujan Anda dapat menggunakan jas hujan

S

B

B

q

: Jika hujan Anda dapat menggunakan payung

B

S

B

p q : Jika hujan Anda dapat menggunakan jas hujan atau

B

B

S

payung

Denial Join / penyangkalan dalam proposisi menggunakan simbol ↓, sehingga apabila menuliskan p ↓q akan dibaca bukan p maupun q. Apabila di gambarkan menggunakan tabel kebenaran : q p↓q p S

S

B

S

B

S

B

S

S

B

B

S

H. KONVERS, INVERS DAN KONTRAPOSISI Dari suatu implikasi dapat ditentukan konvers, invers dan kontraposisi dengan cara : Implikasi : p→q Konvers : q→p Invers : p → q Kontraposisi : q → p Dengan menggunakan tabel kebenaran atau tidak maka dapat dibuktikan bahwa implikasi ekuivalen dengan kontraposisi dan konvers ekuivalen dengan invers. Pembuktian menggunakan tabel kebenaran : p

q

p

q

p→q

q→p

p → q

q → p

S

S

B

B

B

B

B

B

S

B

B

S

B

S

S

B

B

S

S

B

S

B

B

S

B

B

S

S

B

B

B

B Matematika Diskrit Oleh . Dwi Nurul Huda, ST

7

CONTOH Terdapat pernyataan implikasi((p→q) : “Jika ia rajin belajar, maka ia akan lulus UN“. Tentukan konvers, invers dan kontraposisinya. Jawab : Konvers : Jika ia lulus UN, maka ia rajin belajar (q → p) Invers : Jika ia tidak rajin belajar, maka ia tidak akan lulus UN (p → q) Kontraposisi : Jika ia tidak lulus UN, maka ia tidak rajin belajar (q → p) I. INFERENSI LOGIKA Misalkan p dan q merupakan proposisi. Proposisi majemuk “Jika p, maka q“ disebut sebagai proposisi bersyarat(implikasi). Disimbolkan : p →q. Proposisi p disebut hipotesis/antesenden/kondisi/premis. Proposisi q disebut konklusi/konsekuen.

Metode Inferensi merupakan teknik yang digunakan untuk menurunkan kesimpulan berdasarkan hipotesa yang ada dengan tidak menggunakan tabel kebenaran. Beberapa metode inferensi adalah sebagai berikut : --- Simbol ∴ di baca sebagai jadi atau karena itu a. Modus Ponens/ Law Of Detachment Inferensi modus Ponens. Apabila dituliskan : p→q …..Hipotesis p …..Hipotesis ∴ q …..Konklusi CONTOH Terdapat implikasi : Jika 15 habis dibagi 3, maka 15 adalah bilangan ganjil Penulisan dalam bentuk inferensi : Jika 15 habis dibagi 3, maka 15 adalah bilangan ganjil 15 habis dibagi 3 ∴ 15 adalah bilangan ganjil


8

b. Modus Tollen Inferensi modus Tollen. Apabila dituliskan : p→q …..Hipotesis q …..Hipotesis ∴ p …..Konklusi CONTOH Terdapat implikasi : Jika Komputer adalah manusia, maka dia dapat berlari Penulisan dalam bentuk inferensi : Jika Komputer adalah manusia, maka dia dapat berlari Komputer tidak dapat berlari ∴ Komputer bukan manusia c. Silogisme Hipotesis Jika p→q benar dan q→r benar, maka p→r benar. Apabila ditulis : p→q …..Hipotesis q→r …..Hipotesis ∴ p→r …..Konklusi CONTOH Terdapat implikasi : Jika saya rajin belajar, maka saya lulus ujian SNMPTN (p→q) Dan implikasi Jika saya lulus ujian SNMPTN, maka saya masuk PTN (q→r) Penulisan dalam bentuk inferensi : Jika saya rajin belajar, maka saya lulus ujian SNMPTN Jika saya lulus ujian SNMPTN, maka saya masuk PTN ∴ Jika saya rajin belajar, maka saya masuk PTN d. Silogisme Disjungtif Kaidah silogisme disjungtif dapat ditulis dengan cara : pVq …..Hipotesis p …..Hipotesis ∴ q …..Konklusi CONTOH Terdapat disjungsi : Saya belajar dengan giat atau saya menikah tahun depan Penulisan dalam bentuk inferensi : Saya belajar dengan giat atau saya menikah tahun depan Saya tidak belajar dengan giat ∴ Saya menikah tahun depan


9

e. Konjungsi Kaidah konjungsi dapat ditulis dengan cara : p …..Hipotesis q …..Hipotesis ∴ p ^q …..Konklusi CONTOH Terdapat kesimpulan berikut : Saya belajar dengan giat. saya menikah tahun depan. Karena itu, Saya belajar dengan giat dan menikah tahun depan. Penulisan dalam bentuk inferensi : Saya belajar dengan giat saya menikah tahun depan ∴ Saya belajar dengan giat dan menikah tahun depan f. Dilema (Pembagian dalam beberapa kasus) Kaidah dilema dapat ditulis sbb : pVq p→r q→r

∴ r CONTOH Terdapat kesimpulan berikut : Nanti malam Tora mengajak virnie menonton atau menraktir makan di restoran. Jika Tora mengajak virnie nonton, maka virnie akan senang. Jika tora menraktir virnie makan direstoran, maka virnie akan senang. Penulisan dalam bentuk inferensi : Nanti malam Tora mengajak virnie menonton atau menraktir makan di restoran .Jika Tora mengajak virnie nonton, maka virnie akan senang Jika tora menraktir virnie makan direstoran, maka virnie akan senang ∴ Virnie akan senang


9

LATIHAN SOAL 1. Berikan contoh 2 buah kalimat proposisi dan 2 buah kalimat bukan proposisi. 2. Buatlah tabel kebenaran dari rumus berikut : (q^(p→q))→ p 3. Diketahui : p : Inong bisa berbahasa Jerman q : Inong bisa berbahasa Inggris r : Inong bisa berbahasa Jepang Terjemahkan kalimat majemuk berikut ke bentuk simbolik : a. Inong bisa berbahasa Inggris dan Jerman b. Tidak benar Inong bisa berbahasa Jepang dan Jerman c. Jika Inong bisa berbahasa Jerman, maka Inong bisa berbahasa Inggris 4. Diketahui : p: Dadi sedang bermain di kolam q: Dadi ada didalam rumah r: Dadi sedang mengerjakan PR s: dadi sedang menonton televisi Nyatakan bentuk simbolik berikut ke dalam pernyataan majemuk : a. p^q b. (p^r) c. (p V q) ^ (r V s) d. (p→r) V (q→s) 5. Buktikan ekuivalensi pernyataan berikut : a. p V (p^q) Ξ p b. p^ (p V q) Ξ p^q 6. Ada sebuah kampung yang penduduknya selalu mengatakan hal yang benar atau selalu bohong. Penduduk kampung hanya memberikan jawaban ‘YA‘ atau ‘TIDAK‘ terhadap pertayaan yang diajukan oleh para pendatang. Misalkan Ajushi adalah seorang pendatang yang baru sampai ke kampung tersebut dan hendak pergi ke kampung lain. Ajushi sedang berada pada sebuah pertigaan jalan. Satu cabang menuju ke kota, sedang cabang lainnya menuju ke jurang, namun Ajushi tidak tahu cabang mana yang mengarah ke kota tujuan karena tidak adanya penunjuk arah. Kebetulan dioertigaan jalan tersebut terdapat seorang warga kampung sedang berdiri, sebut saja dia Bunga. Sebutkan sebuah pertanyaan yang harus Ajushi ajukan kepada Bunga untuk menentukan arah cabang jalan mana yang harus Ajushi ambil? Petunjuk : Misalkan p adalah pertanyaan, “ Bunga selalu mengatakan yang sebenarnya“ dan q pernyataan “jalan yang berbelok ke kiri menuju ke kota“. Formulasikan pertanyaan A yang tersusun dari p dan q sedemikian rupa, sehingga Bunga akan menjawab pertanyaan “Apakah A benar“ dengan“YA“ jika dan hanya jika q bernilai benar.

LOGIKA DAN PEMBUKTIAN

Recommend Documents