pengantar logika - 2 · konvers dan invers 12. p q tidak ekivalen q p p q tidak ekivalen p q...

31
1 Pengantar Logika - 2 Matematika Komputasional PTIIK - UB Oleh: M. Ali Fauzi

Upload: truongdiep

Post on 12-Mar-2019

272 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

1

Pengantar Logika - 2

Matematika Komputasional

PTIIK - UB

Oleh: M. Ali Fauzi

Page 2: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

2

Tingkat Presedensi

• Urutan pengerjaan logika:

Page 3: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

3

Tingkat Presedensi

Urutan pengerjaan logika:

Jadi, jika ada p ∧ q ∨ r berarti lebih benar (p ∧ q) ∨ r,

dibanding p ∧ (q ∨ r)

Jika ada ¬p ∧ q berarti lebih benar (¬p) ∧ q, bukan berarti

¬ (p ∧ q)

Jika ada p ∨ q → r berarti lebih benar (p ∨ q) → r, bukan p

∨ (q → r)

Page 4: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

• Komputer merepresentasikan informasi

menggunakan bit. Bit adalah simbol dengan dua

kemungkinan nilai, yaitu 0 dan 1.

• Operasi bit dalam komputer menggunakan

operator logika konektif seperti ∧, ∨, and⊕

Operasi Bitwise

4

Page 5: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

• Contoh operasi bitwise pada bit string dengan

panjang 9

01 1011 0110

11 0001 1101

Bitwise OR ?

Bitwise AND ?

Bitwise XOR ?

Operasi Bitwise

5

Page 6: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

• Contoh operasi bitwise pada bit string dengan

panjang 9

01 1011 0110

11 0001 1101

11 1011 1111 Bitwise OR

01 0001 0100 Bitwise AND

10 1010 1011 Bitwise XOR

Operasi Bitwise

6

Page 7: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Dua proposisi yang tabel kebenarannya identik

disebut ekivalen (logically equivalent)

Proposisi

7

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

0 0 1

0 1 0

1 0 0

1 1 1

Page 8: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Dua proposisi yang tabel kebenarannya identik

disebut ekivalen (logically equivalent)

p q ⇔ (p q) ^ (q p)

Atau p q ≡ (p q) ^ (q p)

Proposisi

8

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

0 0 1 1

0 1 0 0

1 0 0 0

1 1 1 1

Page 9: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Dua proposisi yang tabel kebenarannya identik

disebut ekivalen (logically equivalent)

p q ⇔ p q

Proposisi

9

p q p q p q

0 0 1 1

0 1 1 1

1 0 0 0

1 1 1 1

Page 10: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Konvers dari p q adalah q p

Invers dari p q adalah p q

Konvers dan Invers

10

Page 11: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Jika hari ini hujan, maka anak-anak libur sekolah

Konvers nya adalah :

Jika anak-anak libur sekolah, maka hari ini hujan

Invers nya adalah :

Jika hari ini tidak hujan, maka anak-anak tidak libur

sekolah

Konvers dan Invers

11

Page 12: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Konvers dari p q adalah q p

Invers dari p q adalah p q

Apakah konvers dan invers ekivalen?

p q ekivalen q p?

p q ekivalen p q?

Konvers dan Invers

12

Page 13: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

p q tidak ekivalen q p

p q tidak ekivalen p q

Konvers dan Invers

13

p q p q q p p q

0 0 1 1 1

0 1 1 0 0

1 0 0 1 1

1 1 1 1 1

Page 14: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Kontraposisi dari p q adalah q p

Kontraposisi

14

Page 15: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Kontraposisi dari p q adalah q p

Jika hari ini hujan, maka anak-anak libur sekolah

Kontraposisinya nya adalah :

Jika anak-anak tidak libur sekolah, maka hari ini

tidak hujan

Kontraposisi

15

Page 16: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

p q ekivalen q p

Kontraposisi

16

p q p q q p

0 0 1 1

0 1 1 1

1 0 0 0

1 1 1 1

Page 17: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Tautology adalah Proposisi yang selalu bernilai

benar (true) dalam keadaan apapun

Contoh: p p v q

Tautology

17

p q p p v q

0 0 1

0 1 1

1 0 1

1 1 1

Page 18: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Tautology adalah Proposisi yang selalu bernilai

salah (false) dalam keadaan apapun

Contoh: p ^ p

Kontradiksi

18

p p ^ ( p)

0 0

1 0

Page 19: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Latihan

19

Dua pedagang barang kelontong mengeluarkan moto jitu

untuk menarik pembeli. Pedagang pertama mengumbar

motto

“Barang bagus tidak murah”

Pedagang kedua punya motto

“Barang murah tidak bagus”

Apakah kedua motto itu bermakna sama?

Page 20: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi Logika

20

Ekivalensi Nama

p T p

p F p

Identity laws

p T T

p F F

Domination laws

p p p

p p p

Idempotent laws

(p) p Double negation laws

p q q p

p q q p

Commutative laws

(p q) r p (q r)

(p q) r p ( q r)

Associative laws

Page 21: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi Logika

21

Ekivalensi Nama

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

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

Distributive laws

(p q) ( p) ( q)

(p q) ( p) ( q)

De Morgan’s laws

p (p q) p

p (p q) p

Absorption laws

p p T

p p F

Negation laws

Page 22: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi Logika

Page 23: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi Logika

23

Ekivalensi

p q p q

p q q p

p q p q

p q (p q)

(p q) p q

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

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

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

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

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

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

Ekivalensi

p q (p q) (q p)

p q p q

p q (p q) (p q)

(p q) p q

Page 24: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Contoh. Tunjukkan bahwa p ~(p q) dan p ~q keduanya

ekivalen secara logika.

Ekivalensi dengan Hukum Logika

24

Page 25: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Contoh. Tunjukkan bahwa p ~(p q) dan p ~q keduanya

ekivalen secara logika.

Penyelesaian:

p ~(p q ) p (~p ~q) (Hukum De Morgan)

(p ~p) (p ~q) (Hukum distributif)

T (p ~q) (Hukum negasi)

p ~q (Hukum

identitas)

Ekivalensi dengan Hukum Logika

25

Page 26: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi dengan Hukum Logika

26

Contoh . Buktikan hukum penyerapan: p (p q) p

Page 27: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi dengan Hukum Logika

27

Contoh . Buktikan hukum penyerapan: p (p q) p

Penyelesaian:

p (p q) = (p p) (p q) (Hukum distributif)

= p (p q) (Hukum idempoten)

= (p p) (p q) (Hukum distributif)

= p (p q) (Hukum idempoten)

Gagal! Coba cari cara lain:

Page 28: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Ekivalensi dengan Hukum Logika

28

Contoh . Buktikan hukum penyerapan: p (p q) p

Penyelesaian:

p (p q) = (p p) (p q) (Hukum distributif)

= p (p q) (Hukum idempoten)

= (p p) (p q) (Hukum distributif)

= p (p q) (Hukum idempoten)

Gagal! Coba cari cara lain:

p (p q) (p F) (p q) (Hukum Identitas)

p (F q) (Hukum distributif)

p F (Hukum Null)

p (Hukum

Identitas)

Page 29: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Latihan

29

Tunjukkan bahwa (p ˄ ( p ˄ q)) and p ˄ q ekivalen.

Page 30: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

Latihan

30

Tunjukkan bahwa ( p ˄ q) (p ˅ q) tautology.

Page 31: Pengantar Logika - 2 · Konvers dan Invers 12. p q tidak ekivalen q p p q tidak ekivalen p q Konvers dan Invers 13 p q p ... Kontradiksi 18 p p ^

31

Credit :

Slide ini sebagian besar diambilkan dari materi

Pengantar Logika oleh Bapak Rinaldi Munir dan

Materi Logika oleh Ibu Rekyan Regasari serta

materi The Foundations : Logic and Proofs pada

buku Discrete Mathematics and Its Applications

oleh Kenneth H. Rosen dengen beberapa

penyesuaian perubahan