logika lanjutan

LOGIKA

Tenia wahyuningrum

Bahan kuliah matematika diskrit

http://st3telkom.ac.id

Bagian II

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

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

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

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.

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 .

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.

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?

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

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.

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?

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.

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.

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

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.

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.

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 .

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.

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)

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

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.

Beberapa argumen yang sudah

terbukti sahih22

1. Modus ponen

p q

p

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

q

23

2. Modus tollen

p q

~q

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

~ p

24

3. Silogisme disjungtif

p q

~p

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

q

25

4. Simplifikasi

p q

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

p

26

5. Penjumlahan

p

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

p q

27

6. Konjungsi

p

q

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

p q

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 .

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.

Istilah-istilah30

logika

proposisi

pernyataan

konjungsi

disjungsi

disjungsi eksklusif

negasi

tautologi

kontradiksi

implikasi/kondisional

biimplikasi

konvers

invers

kontraposisi

aksioma

teorema

lemma

corollary