matematika diskrit - 02 pengantar logika (2013)

16
Pengantar Logika Bekerjasama Dengan Rinaldi Munir 1

Upload: kuliahkita

Post on 30-Jun-2015

444 views

Category:

Engineering


10 download

DESCRIPTION

Pengantar Logika pada matematika diskrit

TRANSCRIPT

Page 1: Matematika Diskrit - 02 pengantar logika (2013)

Pengantar Logika

Bekerjasama Dengan

Rinaldi Munir

1

Page 2: Matematika Diskrit - 02 pengantar logika (2013)

Pendahuluan

Logika • Perhatikan argumen di bawah ini:

Jika anda mahasiswa Informatika maka anda tidak sulit belajar Bahasa Java. Jika anda tidak suka begadang maka anda bukan mahasiswa Informatika. Tetapi, anda sulit belajar Bahasa Java dan anda tidak suka begadang. Jadi, kalau begitu anda bukan mahasiswa Informatika.

Apakah kesimpulan dari argumen di atas valid?

Alat bantu untuk memahami argumen tsb adalah Logika

2

Page 3: Matematika Diskrit - 02 pengantar logika (2013)

• Banyak teorema dalam Ilmu Komputer/Informatika yang membutuhkan pemahaman logika.

• Contoh:

1. Syarat cukup graf dengan n simpul mempunyai sirkuit Hamilton adalah derajat tiap simpul n/2.

2. T(n) = (f(n)) jika dan hanya jika O(f(n)) = (f(n)).

3

Page 4: Matematika Diskrit - 02 pengantar logika (2013)

• Bahkan, logika adalah jantung dari algoritma dan pemrograman.

• Contoh:

if x mod 2 = 0 then

x:=x + 1

else x:=x – 1

4

Page 5: Matematika Diskrit - 02 pengantar logika (2013)

5

Aristoteles, peletak dasar-dasar logika

Page 6: Matematika Diskrit - 02 pengantar logika (2013)

• Logika berhubungan dengan benar (true) dan salah (false).

• Logika merupakan dasar dari semua penalaran (reasoning) di dalam ilmu pengetahuan.

• Penalaran didasarkan pada hubungan antara pernyataan (statements).

• Ilmu pengetahuan apa pun dapat dipahami karena penalarannya sesuai dengan logika manusia.

Page 7: Matematika Diskrit - 02 pengantar logika (2013)

• Di dalam logika, kita hanya meninjau kalimat yang dapat ditentukan benar atau salah proposisi.

• Proposisi: kalimat deklaratif yang bernilai benar (true) atau salah (false), tetapi tidak keduanya.

• Contoh 1. Semua pernyataan di bawah ini adalah proposisi:

(a) 13 adalah bilangan ganjil

(b) Soekarno adalah alumnus UGM.

(c) 1 + 1 = 2

(d) 8 akar kuadrat dari 8 + 8

(e) Ada monyet di bulan

(f) Hari ini adalah hari Rabu

(g) Untuk sembarang bilangan bulat n 0, maka 2n adalah genap

(h) x + y = y + x untuk setiap x dan y bilangan riil

7

Page 8: Matematika Diskrit - 02 pengantar logika (2013)

• Contoh 2. Semua pernyataan di bawah ini bukan proposisi

(a) Jam berapa kereta api Argo Bromo tiba di Gambir?

kalimat tanya

(b) Isilah gelas tersebut dengan air! kalimat perintah

(c) x + 3 = 8 kalimat terbuka (tergantung pada nilai x)

(d) x > 3 kalimat terbuka (tergantung pada nilai x)

• Kesimpulan: Proposisi adalah kalimat berita

8

Page 9: Matematika Diskrit - 02 pengantar logika (2013)

• Pernyataan yang melibatkan peubah (variable) disebut predikat, kalimat terbuka, atau fungsi proposisi

Contoh: “ x > 3”, “y = x + 10”

Notasi: P(x), misalnya P(x): x > 3

• Predikat dengan quantifier: x P(x)

• Kalkulus proposisi: bidang logika yang berkaitan dengan proposisi

• Kalkulus predikat: bidang logika yang berkaitan dengan predikatr dan quantifier

Keduanya dipelajari secara lebih mendalam pada kuliah IF2121 Logika Matematika.

9

Page 10: Matematika Diskrit - 02 pengantar logika (2013)

• Sebuah proposisi bisa berbentuk:

a. atomik (tunggal)

Contoh: Pemuda itu tinggi

b. majemuk (konektor: dan, atau, tidak)

Contoh: - Pemuda itu tinggi dan tampan

- Ia dihukum 5 tahun atau didenda 10 juta

- Hari ini tidak libur

c. bersyarat

Contoh: - Jika nilai UAS bagus maka nilai akhir A

- Jika suhu mencapai 80C, maka alarm berbunyi

- Hujan turun jika dan hanya kelembaban udara tinggi

10

Page 11: Matematika Diskrit - 02 pengantar logika (2013)

11

Jika proposisi dilambangkan dengan p, q, r, …, maka tabel

kebenaran (truth table) proposisi majemuk dan proposisi

bersyarat adalah:

Tabel Kebenaran

p q p q p q p q p q

T T T T T T T F

T F F T F T F T

F T F F T T

F F F F F F

Page 12: Matematika Diskrit - 02 pengantar logika (2013)

12

Tabel kebenaran implikasi

p q p q

T T T

T F F

F T T

F F T

Tabel kebenaran biimplikasi:

p q p q

T T T

T F F

F T F

F F T

Tabel di samping adalah

tabel kebeneran dari

dua proposisi yaitu

Implikasi dan Biimplikasi

Page 13: Matematika Diskrit - 02 pengantar logika (2013)

Aksioma, Teorema, Lemma,

Corollary

13

Aksioma adalah proposisi yang diasumsikan benar.

Aksioma tidak memerlukan pembuktian kebenaran lagi.

Contoh-contoh aksioma:

(a) Untuk semua bilangan real x dan y, berlaku x + y = y +

x (hukum komutatif penjumlahan).

(b) Jika diberikan dua buah titik yang berbeda, maka

hanya ada satu garis lurus yang melalui dua buah titik

tersebut.

Teorema adalah proposisi yang sudah terbukti benar.

Bentuk khusus dari teorema adalah lemma dan corolarry.

Page 14: Matematika Diskrit - 02 pengantar logika (2013)

• Lemma: teorema sederhana yang digunakan untuk pembuktian teorema lain

• Corollary: teorema yang dapat dibentuk langsung dari teorema yang telah dibuktikan.

• atau, corollary adalah teorema yang mengikuti teorema lain.

14

Page 15: Matematika Diskrit - 02 pengantar logika (2013)

15

Contoh-contoh teorema:

a. Jika dua sisi dari sebuah segitiga sama panjang, maka

sudut yang berlawanan dengan sisi tersebut sama besar.

b. Untuk semua bilangan real x, y, dan z, jika x y dan y

z, maka x z (hukum transitif).

Contoh corollary:

Jika sebuah segitiga adalah sama sisi, maka segitiga

tersebut sama sudut.

Corollary ini mengikuti teorema (a) di atas.

Contoh lemma:

Jika n adalah bilangan bulat positif, maka n – 1 bilangan

positif atau n – 1 = 0.

Page 16: Matematika Diskrit - 02 pengantar logika (2013)

Contoh lainnya (dalam kalkulus)

• Teorema: |x| < a jika dan hanya jika –a < x < a, dumana a > 0

• Corollary: |x| a jika dan hanya jika –a x a, dumana a > 0

16