Selamat datangdi

PerkuliahanLOGIKA MATEMATIKA

• Logika Matematika• Teori Himpunan

• Teori fungsi

Dosen : Dr. Julan HERNADIPUSTAKA : Kenneth H Rossen, Discrete mathematics and its applications, fifth edition.

LOGIKA MATEMATIKA

1.Mempelajari prinsip dan teknik beralasan2.Dasar untuk memberikan pembenaran

pada matematika dan ilmu pengetahuanlainnya.

3. Mempunyai banyak penerapan praktis,diantaranya untuk :

- perancangan mesin komputasi, - kecerdasan buatan, - pemrograman komputer dan- bidang lainnya pada ilmu komputer.

Materi kuliahLOGIKA MATEMATIKA

1. Proposisi dan nilai kebenarannya2. Ingkaran proposisi.3. Konektivitas atau operator logika4. Ekuivalensi logis5. Predikat dan kuantifikasi6. Metoda inferensi

PROPOSISI

PERNYATAAN adalah kalimat deklaratif, umumnya mempunyai pola S-P-O-K

PROPOSISI adalah pernyataan yang sudah dapat dipastikan benar, atau salahtetapi tidak keduanya sekaligus.

NILAI KEBENARAN suatu pernyataan didasarkan pada fakta ilmiah ataukesepakatan umum.

NILAI KEBENARAN : BENAR (T=True) dan SALAH (F=False). Dalam duniadigital nilai kebenaran biasanya dinyatakan oleh 1 untuk benar dan 0 untuk salah.

CONTOH : Semua pernyataan berikut adalah proposisi1. Jakarta adalah ibukota negara Republik Indonesia2. Ponorogo terletak di propinsi Jawa Tengah3. 1 + 2 = 34. 2 + 2 = 5

Proposisi 1 dan 3 bernilai benar (T)Proposisi 2 dan 4 bernilai salah (F)

CONTOH : Perhatikan kalimat berikut1. Jam berapakah sekarang ?2. Silahkan masuk ke ruangan !3. x + 2 = 34. x + y = z

Kalimat 1 bukan pernyataan, tapi pertanyaan. Jadi ia bukan proposisi.Kalimat 2 bukan pernyataan, tapi permintaan. Jadi ia bukan proposisi.

Kalimat 3 adalah pernyataan, tetapi nilai kebenarannya masih bergantungpada nilai x yang diberikan. Bila x=1 ia bernilai benar (T), namun bila x=2 iabernilai salah (F). Karena nilai kebenarannya tidak pasti maka ia bukan proposisi.

Pernyataan yang nilai kebenarannya belum pasti disebut kalimat terbuka.

COBA ANALISA KALIMAT 4, KEMUDIAN SIMPULKAN APAKAH IAPROPOSISI ATAU BUKAN !

NOTASI UNTUK PROPOSISI : p, q, r, s, . . .

Misalkan p suatu proposisi. Proposisi yang menyatakan “bukan p”disebut NEGASI atau ingkaran dari pernyataan p, dan disimbolkanoleh . ¬ p

Hari ini adalah bukan hari SeninHari ini adalah hari Senin

INGKARANPROPOSISI

CONTOH :

3 kurang dari atau sama dengan 23 lebih dari 2

2 adalah bilangan ganjil2 adalah bilangan genap

INGAT : Jika suatu proposisi bernilai T maka ingkarannya bernilai F,begitu juga sebaliknya.

TABEL KEBENARAN (TB)digunakan untuk menyajikan hubungan antaranilai kebenaran sejumlah proposisi.

TABEL 1 : TB untuk proposisi dan negasinya

TF

FTp ¬p

MASALAH LOGIKA 1Pada suatu komunitas mahasiswa baru terbagi dua kelompok, yaitukelompok pembohong yaitu mhs yang selalu berkata salah dan kelompokpenjujur yaitu mhs yang selalu berkata benar.

MASALAH LOGIKA 1 (Lanjutan)Suatu ketika seorang dosen bertemu dengan tiga orang mahasiswayang sedang duduk di tangga; sebut saja mereka dengan A, B dan C.Dosen tersebut bertanya kepada A, apakah A penjujur atau pembohong.A menjawab dengan muka tertunduk sehingga jawabannya tidak jelas. Kemudian sang dosen bertanya kepada B :”apa yang dikatakan A tadi ?”B menjawab bahwa “ A seorang penjujur”. Eh, si C nyeletuk dan menga-takan bahwa “B seorang pembohong”

DAPATKAH ANDA MEMASTIKAN SIAPA PENJUJUR DAN SIAPAPEMBOHONG DIANTARA MEREKA BERTIGA ?

Petunjuk : Cukup dianalisa dengan menggunakanpernyataan dan negasinya.

OPERATOR LOGIKA

Proposisi p Proposisi p¬¬

Proposisi p, q Proposisi r

Operator logika digunakan untuk membentuk proposisi baru dari satu ataulebih proposisi yang sudah ada. Operator logika disebut juga konektivitas.

BEBERAPA KONEKTIVITAS:1. Negasi2. Konjungsi3. Disjungsi4. Disjungsi eksklusif5. Implikasi6. Implikasi dua arah

KONJUNGSI

DEFINISI : Misalkan p dan q adalah proposisi. Proposi“p dan q” ditulis p q adalah proposisi yangbernilai benar jika kedua p dan q benar danbernilai salah untuk kasus lainnya. Proposisip q disebut konjungsi dari p dan q.

∧

∧

TABEL 2 : TB Konjungsi

FFFFTFFFTTTT

p qqp ∧

CONTOH : 1. Misalkan p : Hari ini Jumat, q : Hari ini hujan.

maka p q : Hari ini Jumat dan hujan.Bagaimana nilai kebenarannya. Sangat tentatif, tergan-tung pada keadaan disaat pernyataan ini diungkapkan.

2. Misalkan p : Ada 7 hari dalam seminggu, q : 2+2 = 4, maka p q : Ada 7 hari dalam seminggudan 2+2 = 4. Proposisi ini yang bernilai benar.

∧

∧

DISJUNGSI

DEFINISI : Misalkan p dan q adalah proposisi. Proposi“p atau q” ditulis p q adalah proposisi yangbernilai salah jika kedua p dan q salah danbernilai benar untuk kasus lainnya.

TABEL 3. TB Disjungsi

FFFTTFTFTTTT

p qqp

∨

∨

CONTOH :Diperhatikan proposisi berikut :“Mahasiswa yang sudah mengambil kuliah kalkulusatau kuliah algoritma pemrograman boleh mengambilkuliah metoda numerik.

∨Sesungguhnya kita mempunyai bentuk disjungsi p q,dimanap : Mhs yang sudah kuliah kalkulus boleh ambil numerikq : Mhs yang sudah ambil algoritma boleh ambil numerik

Beberapa kemungkinan mhs yang boleh ambil numerik :1. Mhs yang sudah mengambil kuliah kalkulus saja2. Mhs yang sudah mengambil kuliah algoritma saja3. Mhs yang sudah mengambil keduanya.

EKSKLUSIF OR (XOR)

DEFINISI : Misalkan p dan q adalah proposisi. Proposisi“salah satu p atau q” ditulis p q adalahproposisi yang bernilai benar jika tepat satudiantara p atau q BENAR, dan bernilai salahuntuk kasus lainnya.

TABEL 4 : TB Eksklusif OR

FFFTTFTFTFTT

p qqp

⊕

⊕

IMPLIKASI

DEFINISI : Misalkan p dan q adalah proposisi. Proposi“jika p maka q” ditulis p q adalah proposisiyang bernilai salah jika p benar tetapi q salahdan bernilai benar untuk kasus lainnya.

TABEL 5. TB Impilkasi

TFFTTFFFTTTT

p qqp

→

→

IMPLIKASI (Lanjutan)

PENYEBUTAN LAIN UNTUK p q :1. p berimplikasi q2. p berakibat q3. q hanya jika p4. p adalah syarat cukup q5. q adalah syarat perlu p

→

TFFTTFFFTTTT

p qqp →

Diperhatikan TB implikasi :• apapun nilai kebenaran q, asalkan p bernilai salahmaka implikasinya bernilai benar.

Contoh menarik

→

Misalkan p : soal ujian yang diberikan oleh guruq : jawaban yang diberikan oleh siswa

Nilai kebenaran dari p q diilustrasikan sbg penilaian guru :1. Bila soal ujian benar, jawaban juga benar maka nilainya lulus2. Bila soal ujian benar, jawaban salah maka nilainya harus gagal3. Bila soal ujiannya salah, dijawab benar maka nilainya lulus4. Bila soal ujiannya salah, dijawab salah maka nilainya lulus.

CONTOH : Diperhatikan kalimat implikasi berikut :“Jika belanja anda melebihi 1 juta rupiah maka akan diberikan diskon 2%.”

Toko hanya memberikan perlakuan terhadap pelanggan dengan nilaibelanja melebihi 1 juta tetapi tidak membahas belanja yang kurangdari 1 juta rupiah.

CONTOH : “Jika hari ini Senin maka 2 + 3 = 5” merupakan proposisiyang benar walaupun kedua proposisi aslinya tidak ber-hubungan.

Bentuk Jika …. MakaDalam pemrograman komputer

Diperhatikan pernyataan berikut :

“Jika x < 3 maka x = x + 1”

• Bila sebelum pernyataan ini diberikan x = 2 makaakan dihasilkan nilai x yang baru, yaitu x = 2 + 1 = 3

• Bila sebelumnya diberikan x = 4 maka tidak adapembaharuan (updating) nilai x. Hasilnya tetap, yaitux = 4.

Dalam banyak pemrograman komputer, bentuk “jika … maka” biasanyamuncul dalam bentuk berlapis, seperti

“jika ……(jika…..(jika …..maka.…)…..maka)….maka….”

Coba analisa pernyataan berikut :“Jika 2+2=4 maka x = x^2+1”. Berapa hasilnya jika diberikan x=1, 2, 4.

BI-IMPLIKASI

DEFINISI : Misalkan p dan q adalah proposisi. Proposi“p jika hanya jika q” ditulis p q adalahproposisi yang bernilai benar jika p dan q keduanya benar atau keduanya bernilai salah.

TABEL 6. TB bi-Implikasi

TFFFTFFFTTTT

p qqp

↔

↔

Masalah praktis Logika

Dikarenakan masalah mesin, sang pilot membuat pendaratan darurat dipantai suatu pulau terpecil. Pulau ini didiami oleh 2 kelompok, katakan sajakelompok bangsawan yang selalu berkata jujur dan kelompok awam yang selalu berkata bohong. Sang pilot memutuskan menuju kota untuk mencaribantuan tapi tidak tahu harus ke arah mana. Ketika sedang berjalan sendirisampai di suatu persimpangan (ada jalan ke kiri dan jalan ke kanan), danbertemu dua orang, katakan A dan B. Sang pilot bertanya pada A tentangjalan mana yang harus diambil agar sampai di kota. Si A menjawab sbb :“kota ada di gunung, atau jalan ke kanan menuju kota”. Berbeda dengan A, Si B memberikan statmen “kota ada di gunung, dan jalan ke kanan menujukota”. Sambil mengangkat bahu, si A mengatakan bahwa “si B pembohong”. Selanjutnya si B memberikan argumentasi dalam pernyataan berikut“jika kota ada di gunung maka jalan ke kanan menuju kota”. Dapatkahsang pilot mengambil jalan yang benar ? Bagaimana?

Penterjemahan bahasa IndonesiaKedalam bentuk Logika

Contoh 1: Anda dapat mengakses internet dari kampushanya jika anda jurusan informatika atau anda bukan mhs baru.

Penyelesaian : ada banyak cara untuk menyajikan klm inidalam bentuk logika, salah satunya sbb:Misalkan p : anda dapat mengakses internet dari kampus

q : anda mahasiswa jurusan informatikar : anda mahasiswa baru

Maka kalimat di atas dapat disajikan dalam simbol logika sbb :

q ( r ) p∨ ¬ →

Contoh 2 : Anda tidak diperbolehkan naik roller coaster jika tinggi andaKurang dari 120 cm, kecuali anda sudah berumur di atas 15 tahun.

Untuk latihan, coba ubah ke simbol logika.

Logika dan Operasi Bitpada sistem Komputer

• Bit berupa angka 1 dan 0. String merupakan barisan ataususunan beberapa bit. Komputer menggunakan sistembasis dua, yaitu ia menyajikan informasi dengan mengguna-kan bit 1 dan 0.

• Bit 1 digunakan untuk menyakjikan nilai benar (T), danbit 0 digunakan untuk menyajikan nilai salah (F).

• Operasi bit berupa konektivitas pada logika, yaitu :: “dan”, : “atau”, : ekslusif OR

• Dua string dapat dioperasikan jika mereka mempunyaipanjang yang sama.

∨∧ ⊕

Logika dan Operasi Bitpada sistem Komputer (Lanjutan)

CONTOH : Diberikan dua string x dan y sbb :x = 01 1011 0110 dan y = 11 0001 1101.

Tentukan hasil dari x y, x y dan x y.

PENYELESAIAN :x = 01 1011 0110 x = 01 1011 0110y = 11 0001 1101 y = 11 0001 1101x y = 01 0001 0100 x y = 11 1011 1111

∨∧ ⊕

∧ ∨

x = 01 1011 0110y = 11 0001 1101

x y = 10 1010 1011⊕

Konvers, invers dan kontraposisi

Diperhatikan implikasi p q :

• Konvers : q p

• Invers : p q

• Kontraposisi : q p

→

→

¬ →¬

¬ →¬

Coba buat tabel kebenaran untuk konjungsi, disjungsi, XOR, implikasi,konvers, invers dan kontraposisi. Selidikilah apa saja pasangan pro-posisi yang mempunyai nilai kebenaran yang sama.

EKUIVALENSI PROPOSISI

Tautologi dan KontradiksiGabungan dua proposisi yang selalu bernilai benar, tidakbergantung pada nilai kebenaran masing-masing propo-sisi disebut tautologi.

Gabungan dua proposisi yang selalu bernilai salah, tidakbergantung pada nilai kebenaran masing-masing propo-Sisi disebut kontradiksi.

Contoh : p p : Tautologi

p p : Kontradiksi

¬∨¬

Besok akan turun hujun atau tidak turun hujan tautologi

2 adalah bilangan genap dan bilangan ganjil kontradiksi

∧

DEFINISI :Dua proposisi m dan n dikatakan ekuivalen logis jikam n merupakan suatu tautologi.

Notasi m n : untuk menyatakan bahwa m dan nekuivalen secara logis.

¬ ∨ ¬

↔

⇔

EKUIVALEN LOGIS

CONTOH : 1. implikasi p q ekuivalen logis dengan kontraposisinya

2. (p q) p q

Bukti : Gunakan tabel kebenaran. Berikut untuk contoh 1, contoh 2 diberikan sebagai latihan.

→

⇔ ∧ ¬

¬ ¬ → ¬

TTTTFFTTFTTFFFTFFTTTFFTT

q pp qqpqp →¬

Dalam penerapannya, kebenaran proposisi yang berupa implikasikadangkala dibuktikan melalui kontraposisinya.

sama

BEBERAPA BENTUK EKUIVALENSI LOGIS

1. Hukum Identitas : p T p dan p F p

2. Hukum Dominasi : p T T dan p F F

3. Hukum Idempoten : p p p dan p p p

4. Hukum negasi ganda : ( p) p

5. Hukum Komutatif : p q q p dan p q q p

6. Hukum Asosiatif : (p q) r p (q r) (p q) r p (q r)

7. Hukum Distributif : p (q r) (p q) (p r)p (q r) (p q) (p r)

8. Hukum De Morgan : (p q) p q (p q) p q

∧ ⇔ ∨ ⇔

Misalkan T proposisi yang selalu bernilai benar dan F propoisiYang selalu bernilai salah.

∨ ⇔ ∧ ⇔∨ ⇔ ∧ ⇔¬ ¬ ⇔

∨ ⇔ ∨ ∧ ∧⇔∨ ∨ ∨ ∨⇔

⇔∧ ∧ ∧∨ ∧ ⇔ ∨ ∨∧

∨ ∨∧ ∧ ∧⇔¬ ∧ ⇔¬ ∨¬¬ ∨ ⇔¬ ¬∧

PREDIKAT dan FUNGSI PROPOSISIONAL

Diperhatikan kalimat yang memuat variabel “x < 2”.

Subjek : xPredikat : kurang dari 2

Pernyataan “x kurang dari 2” dinyatakan dengan P(x), dimanaP merujuk sifat “kurang dari 2” dan x variabel.

P disebut juga fungsi proposisional dimana P(x) adalah nilai fungsiP di x. Nilai P(x) hanya dua macam, yaitu benar (T) atau salah (F).

CONTOH :

1. Bila P(x) : x < 2 maka P(1) benar, P(2) salah, P(3/2) benar, dst2. Fungsi proposisional dengan beberapa varibel :

Q(x,y) : x^2 + y^2 = 25Q(3,4), Q(4,3) bernilai benar, Q(1,2), Q(5,3) salah, dst.

Misalkan perintah berikut : “ jika x > 0 maka x = x+1” dimasukkanpada suatu program.

Fungsi proposisi P(x): x >0.

Bila P(x) benar maka perintah x = x + 1 dieksekusi, tetapi bila P(x)salah maka nilai x yang dimasukkan tidak berubah.

x = 1 P(1) benar x = 1 + 1 = 2

x = 2 P(0) salah x = 2

Contoh penggunaan fungsi proposisionalpada program komputer

Misalkan P(x) suatu fungsi proposisional, x berasal dari suatu domainyang disebut semesta pembicaraan.

DEFINISI : Kuantifikasi universal adalah proposisi yang berbentukx, P(x).

dibaca: “untuk setiap x dalam semesta pembicaraan berlaku P(x) ”

Notasi disebut kuantor universal.

KUANTOR

∀

∀CONTOH : Nyatakan kalimat berikut dalam kuantifikasi universal“semua mhs di kelas ini mengambil kuliah kalkulus”

Penyelesaian : Misal P(x) : x mengambil kuliah kalkulus, x varibel mhs.Diperoleh

x, P(x).Bentuk lainnya : misalkan S(x): x yang ada di kelas ini, maka pernyataanDi atas dapat juga disajikan sebagai

x, [ S(x) P(x)]

∀

∀ →

DEFINISI : Kuantifikasi eksistensial adalah proposisi sbb :“terdapat (ada) x dalam semesta pembicaraan sehingga berlaku P(x)”ditulis

x, P(x).

Notasi disebut kuantor eksistensial.

KUANTOR (Lanjutan)

CONTOH : Diberikan pernyataan P(x): x^2 = 1. Tentukan nilai kebenaran

x, P(x).

Penyelesaian : Karena x = 1 dan x = -1 membuat persamaan x^2 = 1benar maka kuantifikasi eksistensial ini bernilai benar.

Bila Q(x,y) : x^2+y^2 < 0 maka kuantifikasi eksistensial (x,y), Q(x,y) benilai salah.

∃∃

Pengertian “terdapat” berarti paling tidak ada satu x dalam semestaPembicaraan sehingga P(x) benar.

∃

∃