logika lanjutan

30
LOGIKA Tenia wahyuningrum Bahan kuliah matematika diskrit http://st3telkom.ac.id Bagian II

Upload: tenia-wahyuningrum

Post on 04-Jul-2015

305 views

Category:

Education


2 download

DESCRIPTION

lanjutan materi kuliah logika (logic) untuk digunakan di st3telkom.ac.id

TRANSCRIPT

Page 1: Logika lanjutan

LOGIKA

Tenia wahyuningrum

Bahan kuliah matematika diskrit

http://st3telkom.ac.id

Bagian II

Page 2: Logika lanjutan

Bikondisional (Bi-implikasi)2

B entuk proposisi: “p jika dan hanya jika q”

N otasi: p q

p q p q

T T T

T F F

F T F

F F T

p q (p q) (q p).

Page 3: Logika lanjutan

3

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

T T T T T T

T F F F T F

F T F T F F

F F T T T T

D engan kata lain, pernyataan “p jika dan hanya jika q”

dapat dibaca “Jika p m aka q dan jika q m aka p”.

Page 4: Logika lanjutan

4

C ara-cara m enyatakan bikondisional p q :

(a) p jika dan hanya jika q .

(b) p adalah syarat perlu dan cukup untuk q .

(c) Jika p m aka q , dan sebaliknya.

(d) p iff q

Page 5: Logika lanjutan

5

C ontoh 22. Proposisi m ajem uk berikut adalah bi-

im plikasi:

(a) 1 + 1 = 2 jika dan hanya jika 2 + 2 = 4.

(b) Syarat cukup dan syarat perlu agar hari hujan

adalah kelem baban udara tinggi.

(c) Jika anda orang kaya m aka anda m em punyai

banyak uang, dan sebaliknya.

(d) B andung terletak di Jaw a B arat iff Jaw a B arat

adalah sebuah propinsi di Indonesia.

Page 6: Logika lanjutan

6

C ontoh 23. Tuliskan setiap proposisi berikut ke dalam bentuk “ p jika dan

hanya jika q”:

(a) Jika udara di luar panas m aka anda m em beli es krim , dan jika

anda m em beli es krim m aka udara di luar panas.

(b) Syarat cukup dan perlu agar anda m em enangkan pertandingan

adalah anda m elakukan banyak latihan.

(c) A nda naik jabatan jika anda punya koneksi, dan anda punya

koneksi jika anda naik jabatan.

(d) Jika anda lam a m enonton televisi m aka m ata anda lelah, begitu

sebaliknya.

(e) K ereta api datang terlam bat tepat pada hari-hari ketika saya

m em butuhkannya.

Penyelesaian :

(a) A nda m em beli es krim jika dan hanya jika udara di luar panas.

(b) A anda m em enangkan pertandingan jika dan hanya jika anda

m elakukan banyak latihan.

(c) A nda naik jabatan jika dan hanya jika anda punya koneksi.

(d) M ata anda lelah jika dan hanya jika anda lam a m enonton televisi.

(e) K ereta api datang terlam bat jika dan hanya jika saya

m em butuhkan kereta hari itu .

Page 7: Logika lanjutan

7

Bila dua proposisi majemuk yang ekivalendi-bikondisionalkan, maka hasilnya adalahtautologi (hasilnya benar untuk semuakasus).

Teorema:

Dua buah proposisi majemuk, P(p, q, ..) danQ(p, q, ..) disebut ekivalen secara logika,dilambangkan dengan P(p, q, …) Q(p, q,…), jika P Q adalah tautologi.

Page 8: Logika lanjutan

Soal latihan 38

Sebagian besar orang percaya bahwa harimau Jawasudah lama punah. Tetapi, pada suatu hari Amirmembuat pernyataan-pernyataan kontroversial sebagaiberikut:

(a) Saya melihat harimau di hutan.

(b) Jika saya melihat harimau di hutan, maka saya jugamelihat srigala.

Misalkan kita diberitahu bahwa Amir kadang-kadangsuka berbohong dan kadang-kadang jujur. Gunakantabel kebenaran untuk memeriksa apakah Amir benar-benar melihat harimau di hutan?

Page 9: Logika lanjutan

Penyelesaian soal latihan 39

(a) Saya melihat harimau di hutan.

(b) Jika saya melihat harimau di hutan, maka sayajuga melihat srigala.

Misalkan

p : Amir melihat harimau di hutan

q : Amir melihat srigala

Pernyataan untuk (a): p

Pernyataan untuk (b): p q

Page 10: Logika lanjutan

10

Tabel kebenaran p dan p q

p q p q

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

Kasus 1: Amir dianggap berbohong, maka apa yang dikatakan Amir itu keduanya salah ( p salah, q salah) Kasus 2: Amir dianggap jujur, maka apa yang dikatakan Amir itu keduanya benar (p benar, q benar).

Tabel menunjukkan bahwa mungkin bagi p dan p q benar, tetapi tidak mungkin keduanya salah. Ini berarti Amir mengatakan yang sejujurnya, dan kita menyimpulkan bahwa Amir memang benar melihat harimau di hutan.

Page 11: Logika lanjutan

Soal latihan 411

[LIU85] Sebuah pulau didiami oleh dua suku asli.

Penduduk suku pertama selalu mengatakan hal

yang benar, sedangkan penduduk dari suku lain

selalu mengatakan kebohongan. Anda tiba di

pulau ini dan bertanya kepada seorang

penduduk setempat apakah di pulau tersebut

ada emas atau tidak. Ia menjawab, “Ada emas

di pulau ini jika dan hanya jika saya selalu

mengatakan kebenaran”. Apakah ada emas di

pulau tersebut?

Page 12: Logika lanjutan

Penyelesaian soal latihan 412

Ada emas di pulau ini jika dan hanya jika saya selalu mengatakan kebenaran

Misalkan

p : saya selalu menyatakan kebenaran

q : ada emas di pulau ini

Ekspresi logika: p q

Tinjau dua kemungkinan kasus:

Kasus 1, orang yang memberi jawaban adalah orangdari suku yang selalu menyatakan hal yang benar.

Kasus 2, orang yang memberi jawaban adalah orang

dari suku yang selalu menyatakan hal yang bohong.

Page 13: Logika lanjutan

13Kasus 1: orang tersebut selalu menyatakan hal yang benar. Ini

berarti p benar, dan jawabannya terhadap pertanyaan kita pastijuga benar, sehingga pernyataan bi-implikasi tersebut bernilaibenar. Dari Tabel bi-implikasi kita melihat bahwa bila p benardan p q benar, maka q harus benar. Jadi, ada emas di pulautersebut adalah benar.

Kasus 2: orang tersebut selalu menyatakan hal yang bohong. Iniberarti p salah, dan jawabannya terhadap pertanyaan kita pastijuga salah, sehingga pernyataan bi-implikasi tersebut salah.Dari Tabel bi-implikasi kita melihat bahwa bila p salah dan p qsalah, maka q harus benar. Jadi, ada emas di pulau tersebutadalah benar.

Dari kedua kasus, kita selalu berhasil menyimpulkanbahwa ada emas di pulau tersebut, meskipun kitatidak dapat memastikan dari suku mana orangtersebut.

Page 14: Logika lanjutan

14

A rgum en

A rgum en adalah suatu deret proposisi yang dituliskan sebagai

p 1

p 2

p n

q

yang dalam hal ini, p 1, p 2, … , p n d isebut hipotesis (atau prem is),

dan q d isebut konklusi.

A rgum en ada yang sahih (valid ) dan palsu (invalid).

Page 15: Logika lanjutan

15

D efinisi. Sebuah argum en dikatakan sahih jika konklusi

benar bilam ana sem ua hipotesisnya benar; sebaliknya

argum en dikatakan palsu ( fallacy atau invalid ).

Jika argum en sahih, m aka kadang -kadang kita m engatakan

bahw a secara logika konklusi m engikuti hipotesis atau

sam a dengan m em perlihatkan bahw a im plikasi

(p 1 p 2 p n) q

adalah benar (yaitu, sebuah tautologi). A rgum en yang

palsu m enunjukkan proses penalaran yang tidak benar.

Page 16: Logika lanjutan

16

Contoh 1

Perlihatkan bahwa argumen berikut:

Jika air laut surut setelah gempa di laut, maka

tsunami datang. Air laut surut setelah gempa di

laut. Karena itu tsunami datang.

adalah sahih.

Penyelesaian:

Misalkan:

p : Air laut surut setelah gempa di laut

q : Tsunami datang:

Argumen:

p q

p

q

Ada dua cara yang dapat digunakan untuk membuktikan kesahihan

argumen ini.

Page 17: Logika lanjutan

17

C ara 1 : B entuklah tabel kebenaran untuk p, q , dan p q

p q p q

T T T (baris 1)

T F F (baris 2)

F T T (baris 3)

F F T (baris 4)

A rgum en dikatakan sahih jika sem ua hipotesisnya benar, m aka

konklusinya benar. K ita periksa apabila hipotesis p dan p q

benar, m aka konklusi q juga benar sehingga argum en dikatakan

benar. Periksa tabel, p dan p q benar secara bersam a-sam a pada

baris 1. Pada baris 1 ini q juga benar. Jadi, argum en di atas sahih .

Page 18: Logika lanjutan

18

C ara 2: Perlihatkan dengan tabel kebenaran apakah

[ p (p q ) ] q

m erupakan tautologi. Tabel 1.16 m em perlihatkan bahw a [ p (p q ) ] q suatu

tautologi, sehingga argum en dikatakan sahih.

Tabel 1.16 [ p (p q ) ] q adalah tauto logi

p q p q p (p q ) [ p (p q) ] q

T T T T T

T F F F T

F T T F T

F F T F T

Perhatikanlah bahw a penarikan kesim pulan di dalam argum en ini m enggunakan m odus

ponen. Jadi, k ita kita juga telah m em perlihatkan bahw a m odus ponen adalah argm en yang

sahih.

Page 19: Logika lanjutan

19

C ontoh 2:

Perlihatkan bahw a penalaran pada argum en berikut:

“Jika air laut surut setelah gem pa di laut, m aka tsunam i datang.

Tsunam i datang. Jadi, air laut surut setelah gem pa di laut”

tidak benar, dengan kata lain argum ennya palsu.

Penyelesaian :

A rgum en di atas berbentuk

p q

q

p

D ari tabel tam pak bahw a hipotesis q dan p q benar pada

baris ke-3, tetapi pada baris 3 ini konklusi p salah. Jadi,

argum en tersebut tidak sahih atau palsu, sehingga penalaran

m enjadi tidak benar.

p q p q

T T T (baris 1)T F F (baris 2)F T T (baris 3)F F T (baris 4)

Page 20: Logika lanjutan

20

C ontoh 3:

Periksa kesahihan argum en berikut in i:

Jika 5 lebih kecil dari 4 , m aka 5 bukan bilangan prim a.

5 tidak lebih kecil dari 4 .

5 adalah bilangan prim a

Penyelesaian :

M isalkan p : 5 lebih kecil dari 4

q : 5 adalah bilangan prim a.

A rgum en:

p ~q

~p

q

Tabel m em perlihatkan tabel kebenaran untuk kedua hipotesis dan

konklusi tersebut. B aris ke -3 dan ke-4 pada tabel tersebut adalah baris d i

m ana p ~q dan ~ p benar secara bersam a-sam a, tetapi pada baris ke -4

konklusi q salah (m eskipun pada baris ke-3 konklusi q benar). In i

berarti argum en tersebut palsu.

p q ~ q p ~ q ~p

T T F F FT F T T FF T F T TF F T T T

Page 21: Logika lanjutan

21

Perhatikanlah bahw a m eskipun konklusi dari argum en

tersebut kebetulan m erupakan pernyataan yang benar (“5

adalah bilangan prim a” adalah benar),

tetapi konklusi dari argum en ini tidak sesuai dengan bukti

bahw a argum en tersebut palsu.

Page 22: Logika lanjutan

Beberapa argumen yang sudah

terbukti sahih22

1. Modus ponen

p q

p

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

q

Page 23: Logika lanjutan

23

2. Modus tollen

p q

~q

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

~ p

Page 24: Logika lanjutan

24

3. Silogisme disjungtif

p q

~p

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

q

Page 25: Logika lanjutan

25

4. Simplifikasi

p q

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

p

Page 26: Logika lanjutan

26

5. Penjumlahan

p

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

p q

Page 27: Logika lanjutan

27

6. Konjungsi

p

q

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

p q

Page 28: Logika lanjutan

Aksioma, Teorema, Lemma, Corollary

28

A ksiom a adalah proposisi yang diasum sikan benar.

A ksiom a tidak m em erlukan pem buktian kebenaran lagi.

C ontoh-contoh aksiom a:

(a) U ntuk sem ua bilangan real x dan y , berlaku x + y = y +

x (hukum kom utatif penjum lahan).

(b) Jika diberikan dua buah titik yang berbe da, m aka

hanya ada satu garis lurus yang m elalui dua buah titik

tersebut.

T eorem a adalah proposisi yang sudah terbukti benar.

B entuk khusus dari teorem a adalah lem m a dan corolarry .

Page 29: Logika lanjutan

29

C ontoh-contoh teorem a:

a. Jika dua sisi dari sebuah segitiga sam a panjang, m aka

sudut yang berlaw anan dengan sisi tersebut sam a besar.

b . U ntuk sem ua bilangan real x , y , dan z , jika x y dan y

z , m aka x z (hukum transitif).

C ontoh corollary :

Jika sebuah segitiga adalah sam a sisi, m aka segitiga

tersebut sam a sudut.

C orollary ini m engikuti teorem a (a) di atas.

C ontoh lem m a :

Jika n adalah bilangan bulat positif, m aka n – 1 bilangan

positif atau n – 1 = 0.

Page 30: Logika lanjutan

Istilah-istilah30

logika

proposisi

pernyataan

konjungsi

disjungsi

disjungsi eksklusif

negasi

tautologi

kontradiksi

implikasi/kondisional

biimplikasi

konvers

invers

kontraposisi

aksioma

teorema

lemma

corollary