1.mat disk 2015 bab 1.1 + 1.2 + 1.3 (1)
DESCRIPTION
Matdisk bab 1 ITSTRANSCRIPT
bilqis 1
Pertemuan1.1 + 1.2 + 1.3
Proposional Logic & aplikasinya + Propositional equivalence
2015
bilqis 2
Cara Belajar
• Perhatikan ketika dosen mengajar• Kerjakan latihan seluruhnya• Cocokkan untuk soal ganjil dengan jawaban
dibelakang buku• Cek web site :
– www.mhhe.com/rosen
bilqis 3
Buku
Discrete Mathematics and Its Applications, Kenneth H Rosen, McGraw-Hill edisi 7
bilqis 4
Proposional logic dan aplikasinya
Sub-bab 1.1 – 1.2
bilqis 5
Logika
• Mempelajari penalaran/pemikiran (reasoning) secara benar
• Logic mempelajari bgm cara mengambil kesimpulan yang benar menurut aturan yang ada , ex:or,and,not,dll
• Fokus pada relasi antar pernyataan (statement) / kalimat (sentence).
Contoh: 1) Doni adalah mahasiswa ITS. 2) Semua mahasiswa ITS
pandai.3) Doni orang pandai.
bilqis 6
Logika
• Perhatikan bahwa logika tidak harus memperhatikan isi kalimat; jika diketahui bahwa dua kalimat pertama di atas benar, maka kalimat ketiga harus benar.
bilqis 7
Proposisi• Proposisi merupakan sebuah pernyataan atau
kalimat yang punya nilai kebenaran (benar = 1 / salah = 0). Proposisi disimbolkan dengan huruf p, q, dsb.
• Proposisi kalimat yg dapat bernilai benar atau salah
bilqis 8
Proposisi
• Biasanya berbentuk kalimat deklaratif
Contoh proposisi: – Bilangan bulat yang membagi habis 23 adalah 1 dan
23.– Untuk setiap bilangan bulat n, ada bilangan prima
yang lebih besar daripada n
Contoh bukan proposisi: – Berapa harga tiket ke Manila?– Silakan duduk.
bilqis 9
Konektif• Jika p dan q adalah proposisi, dapat
dibentuk proposisi (majemuk) baru (compound proposition) dengan menggunakan konektif
• Macam-macam konektif: – AND (konjungsi) Simbol – Inclusive OR (disjungsi) Simbol v– EXclusive OR (XOR) Simbol – NOT (negasi) Simbol – Implikasi Simbol – Implikasi ganda Simbol
bilqis 10
Maju ke depanp q p ^ q P v q P q ~ p P q P q
0 0
0 1
1 0
1 1
bilqis 11
Tingkat Presedensi
NEGASI (NOT) KONJUNGSI (AND) DISJUNGSI (OR, XOR) IMPLIKASI IMPLIKASI GANDA
Catatan: mengatasi tingkat presedensi dengan cara memberikan kurung pada proposisi yang ingin didahulukan
bilqis 12
Tabel Kebenaran(truth table)
konjungsip q p q0 0 00 1 01 0 01 1 1
P ^ q bernilai benar jika p dan q benar
bilqis 13
Contoh• p = Harimau adalah binatang buas• q = Malang adalah ibukota Jawa Timur• p q = Harimau adalah binatang buas dan
Malang adalah ibukota Jawa Timur• p q salah. Perhatikan bahwa tidak perlu ada keterkaitan
antara p dan q
bilqis 14
Tabel Kebenarandisjungsi (inclusive or)
Contoh: p = Joni seorang mahasiswa q = Mira seorang sarjana hukum
p v q = Joni seorang mahasiswa atau Mira seorang sarjana hukum
p q p v q0 0 00 1 11 0 11 1 1
P ^ q bernilai salah jika p dan q salah
bilqis 15
Tabel Kebenaranexclusive or
p q is true only when p is true and q is false, or p is false and q is true.
Example: p = “bilqis pergi ke Jakarta, q = “bilqis pergi ke Malang"
p q = “pilih salah satu, bilqis pergi ke jakarta atau bilqis pergi ke malang"
p q p q0 0 00 1 11 0 11 1 0
bilqis 16
Tabel Kebenaran
Negasi
Contoh: p = Joni seorang mahasiswa p = Joni bukan seorang mahasiswa
p p0 11 0
bilqis 17
Kalimat majemuk
compound statements
• p, q, r merupakan kalimat / pernyataan sederhana (simple statements)
• Beberapa contoh bentukan compound statements, seperti:– (p q) r– p (q r)– (p) (q)– (p q) (r)– dll
bilqis 18
Tabel Kebenaran (p r)qp q r (p r)q0 0 0 (0 1) 0 = 00 0 1 (0 0) 0 = 00 1 0 (0 1) 1 = 10 1 1 (0 0 1 = 11 0 0 (1 1) 0 = 11 0 1 (1 0) 0 = 01 1 0 (1 1) 1 = 11 1 1 (1 0) 1 = 1
bilqis 19
Implikasi• Disebut juga proposisi kondisional (conditional
proposition) dan berbentuk “jika p maka q” • Notasi simboliknya : p q• Contoh:
– p = " John rajin belajar"– q = " John dapat hadiah "– p q = “If John rajin belajar then John dapat hadiah "
bilqis 20
Tabel Kebenaran
implikasi
p q p q0 0 10 1 11 0 01 1 1
P q benar jika p dan q benar atau p salah
bilqis 21
Hipotesa dan konklusi
• Dalam implikasi p q
p disebut anteseden, hipotesa, premis (antecedent, hypothesis, premise)
q disebut konsekuensi atau konklusi (consequence, conclusion)
bilqis 22
Cara menyebut p q
jika p maka q if p then q jika p, q if p, q q jika p q if p p hanya jika q p only if q p mengimplikasikan q p implies q
bilqis 23
Perlu dan Cukup
• Kondisi “perlu” dinyatakan oleh konklusi.• Kondisi “cukup” dinyatakan oleh hipotesa.• Perlu = necessary; Cukup = sufficient
– Contoh: Jika Joni seorang mahasiswa maka Mira seorang sarjana hukum
– Kondisi perlu: Mira seorang sarjana hukum
– Kondisi cukup: Joni seorang mahasiswa
bilqis 24
Maju ke depanp q ~p v q P q Q p ~p ~q ~q ~p
0 0
0 1
1 0
1 1
Ekivalen
konversi
inversi
Kontrapositif = ekivalen
bilqis 25
Ekivalensi Logikal
Dua proposisi yang tabel kebenarannya identik disebut ekivalen (logically equivalent). Contoh: p q ekivalen (logically equivalent to)
p q p q p q p q
0 0 1 10 1 1 11 0 0 01 1 1 1
bilqis 26
• P q ekivalen dengan ~ q ~ p ~ p v q
bilqis 27
Konversi dan Inversi• Konversi dari p q adalah q p• Inversi dari p q adalah p q• p q tidak ekivalen q p• p q tidak ekivalen p q
p
q p q q p p q
0 0 1 1 10 1 1 0 01 0 0 1 11 1 1 1 1
Logical EquivalenceNotation p q ( p and q are compound propositions )
Example : p q is logically equivalent to p q
p q p q p q
0 0 1 10 1 1 11 0 0 01 1 1 1
bilqis 29
Kontrapositif
• kontrapositif dari proposisi p q adalah q p. • p q dan q p ekivalen
p q p q q p0 0 1 10 1 1 11 0 0 01 1 1 1
bilqis 30
Ekivalensi Logika
Ekivalensi Logika lain dapat dilihat di buku teks Sub-bab 1.2. halaman 24
Tabel 6 Tabel 7 Tabel 8
bilqis 31
Implikasi Ganda• Implikasi Ganda (double implication) dibaca “p jika dan hanya jika q”• Notasi simboliknya p q• p q ekivalen dengan (p q)^(q p)
p q p q (p q) (q p)0 0 1 10 1 0 01 0 0 01 1 1 1
bilqis 32
Tautology
Proposisi yang selalu bernilai benar (true) dalam keadaan apapun
Contoh: p p v qp q p p v q 0 0 10 1 11 0 11 1 1
bilqis 33
Kontradiksi
Proposisi yang selalu bernilai salah (false) dalam keadaan apapun
Contoh : p ( p )p p ( p)0 01 0
bilqis 34
Hukum De Morgan (p q) ekivalen dengan ( p) ( q) (p q) ekivalen dengan ( p) ( q)
Bukti (yang pertama, buktikan yang kedua sendiri):
p q p q pq (pq) (p)(q)
0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0
35
Ex 1. How can this English sentence be translated into a logical expression?• “You can access the Internet from campus
only if you are a computer science major or you are not a freshman.”
• Jawab :– A = You can access the Internet from campus – c = you are a computer science major – f = you are a freshman– Logical expression : a (c v ~ f)bilqis
bilqis 36
Ex. 2
• “You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”
• Jawab :– Q = You ride the roller coaster – R = you are under 4 feet tall– S = you are older than 16 years old– Logical expression : ( r ^ ~s) ~ q