MATEMATIKA DISKRIT

FITRI UTAMININGRUM, ST, MT

Tujuan Instruksional khusus Memahami tentang logika proposional Memahami tentang penggunaan operator

logika pada proposisi Memahami tentang ekuivalensi pada logika

proposional

Logika Logika adalah dasar dari penjabaran matematika

(mathematical reasoning) Logika mempelajari penjabaran (reasoning) secara

benar Fokus pada relasi antar pernyataan (statement) /

kalimat (sentence). Contoh: Dino adalah mahasiswa UB. Semua mahasiswa UB pandai.

Dino orang pandai. Perhatikan bahwa logika tidak harus memperhatikan

isi kalimat; jika diketahui bahwa dua kalimat pertama di atas benar, maka kalimat ketiga harus benar.

Proposisi Proposisi merupakan sebuah pernyataan atau kalimat

yang punya nilai kebenaran (benar = 1 / salah = 0). Proposisi disimbolkan dengan huruf p, q, dsb.

Biasanya berbentuk kalimat deklaratif Contoh proposisi:

Bilangan bulat yang membagi habis 23 adalah 1 dan 23 proposisi primitip(primitif )

Taufik Hidayat pandai main bulu tangkis atau tenis proposisi majemuk(composite).

Contoh bukan proposisi: Berapa harga tiket ke Malaysia? Silakan duduk.

MACAM PROPOSISI Kalimat deklaratif yang tidak memuat

penghubungdisebut proposisi primitif(primitif )

Kalimat deklaratif yang memuat penghubung ”atau” dan ”jika...maka...” disebut proposisi majemuk (composite).

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 Simbol NOT (negasi) Simbol Implikasi Simbol Implikasi ganda Simbol

Tingkat Presedensi NEGASI (NOT) KONJUNGSI (AND) DISJUNGSI (OR, XOR) IMPLIKASI IMPLIKASI GANDA

Catatan: mengatasi tingkat presedensi dengan cara memberikan kurung di pada proposisi yang ingin didahulukan

Tabel KebenaranKonjungsi

p q p q0 0 0

0 1 0

1 0 0

1 1 1

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

Tabel KebenaranDisjungsi (Inclusive OR)

p q p v q

0 0 0

0 1 1

1 0 1

1 1 1

Contoh: p = Jono seorang mahasiswa q = Mira seorang sarjana hukum p v q = Jono seorang mahasiswa atau Mira

seorang sarjana hukum

Tabel KebenaranExclusive Disjunction

“Either p or q” (but not both), dengan simbol p q

p q bernilai benar hanya jika p benar dan q salah, atau p salah dan q benar p = "John is programmer, q = "Mary is a lawyer" p q = "Either John is a programmer or Mary is a lawyer"

p q p q

0 0 0

0 1 1

1 0 1

1 1 0

Tabel KebenaranNegasi

p p

0 1

1 0

Contoh: p = Jono seorang mahasiswa p = Jono bukan seorang mahasiswa

Kalimat majemuk (compound statements)

p, q, r merupakan kalimat / pernyataan sederhana (simple statements)

Apabila ada dua buah proposisi misalkan proposisi A dan proposisi B maka dapat dibentuk proposisi baru (Compound Proposition) dengan menggunakan konektor atau perangkai.

Beberapa contoh bentukan compound statements, seperti: (pq)^r p(q^r) (p)( q) (pq)^( r) dll

HITUNG

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

0 0

0 1

1 0

1 1

Lengkapilah tabel dibawah ini serta berikan kesimpulan akhirnya

Tabel Kebenaran (p r) q

p q r (p r) q

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Implikasi

Disebut juga proposisi kondisional (conditional proposition) dan berbentuk

“jika p maka q” Notasi simboliknya : p q

Contoh: p = Jono seorang mahasiswaq = Mira seorang sarjana hukump q = Jika Jono seorang mahasiswa maka Mira seorang sarjana hukum

Tabel KebenaranImplikasi

p q p q

0 0 1

0 1 1

1 0 0

1 1 1

Hypotesa dan konklusi

Dalam implikasi p q p disebut antecedent, hypothesis, premise q disebut konsekuensi atau konklusi (consequent, conclusion)

Perlu dan Cukup

Kondisi “perlu” dinyatakan oleh konklusi. Kondisi “cukup” dinyatakan oleh hipotesa. Perlu = necessary; Cukup = sufficient

Contoh: Jika Jono seorang mahasiswa maka Mira seorang

sarjana hukum Kondisi perlu: Mira seorang sarjana hukum Kondisi cukup: Jono seorang mahasiswa

Tabel kebenaranImplikasi Ganda (Biimplikasi)

Implikasi Ganda (double implication) dibaca “p jika dan hanya jika q” Notasi simboliknya p q

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

0 0 1

0 1 0

1 0 0

1 1 1

KESIMPULAN BIIMPLIKASI p q ekivalen dengan (p q)^(q p)

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

0 0 1 1

0 1 0 0

1 0 0 0

1 1 1 1

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 1

0 1 1 1

1 0 0 0

1 1 1 1

Konversi dan Inversi Konversi dari p q adalah q p Inversi dari p q adalah p q

Apakah Konversi dan Inversi diatas equivalent??? BUKTIKAN!!!!

PEMBUKTIAN

p q tidak ekivalen q p p q tidak ekivalen p q

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

Kontrapositif

kontrapositif dari proposisi p q adalah q p Buat Tabel Kebenarannya dan apakah p q dan

q p ekivalen???

JAWAB KONTRAPOSITIF p q dan q p ekivalen

p q p q q p

0 0 1 1

0 1 1 1

1 0 0 0

1 1 1 1

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 pp q q p

Commutative laws

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

Associative laws

Ekivalensi Logika

Ekivalensi Logika

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

Ekivalensi LogikaEkivalensi

p q p qp q q pp q p qp 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 qp q (p q) (p q) (p q) p q

Tautology Proposisi yang selalu bernilai benar (true)

dalam keadaan apapun Contoh: p p v q

p q p p v q ((p => q) ^ p) => q

0 0 1

0 1 1

1 0 1

1 1 1

Kontradiksi Proposisi yang selalu bernilai salah

(false) dalam keadaan apapun Contoh : p ^ p

p p ^ ( p)

0 0

1 0

Latihan-11. Dari bbrp kalimat dibawah ini mana yang

termasuk proposisi ? Tentukan nilai kebenaran dari proposisi tsb. 7 merupakan sebuah bilangan prima. Jangan lakukan. Jika 10 habis dibagi dengan 4, maka juga habis

dibagi dengan 2. x + y = y + x untuk setiap pasangan dari bilangan

real x dan y Jam berapa sekarang?

Latihan2. Tentukan apakah (p (p q)) q adalah

tautologi?3. Tunjukkan bahwa manakah yang ekivalen

dari ketiga logika berikut?a. p q b. (p q) (p q) c. (p q) ^ (q p)