1. Operator Logika.docx

MATEMATIKA DISKRIT Deskripsi Mata Kuliah: Ilmu dasar dalam pembelajaran informatika. Matematika Diskrit memberikan landasar matematis untuk mata kuliah algoritma, struktur data, jaringan komputer dan seterusnya. Capaian Pembelajaran: Mampu berpikir secara logika sehingga dapat mengidentifikasi (P2) data diskrit yang diberikan, merumuskan permasalahan secara sederhana, dan membuktikan (A5) secara matematis untuk siap menjadi masukan dan proses dalam pemrograman komputer untuk memecahkan (C3) masalah umum yang bersifat diskrit Materi yang Disampaikan: 1. Dasar logika (pernyataan tunggal dan pernyataan majemuk) 2. Operator logika -

Konjungsi

-

Disjungsi

-

Ingkaran

-

Implikasi (konvers, invers, kontraposisi)

-

Biimplikasi

3. Aljabar proposisi 4. Penarikan kesimpulan -

Modus ponen

-

Modus tollen

-

Dst

5. Kalimat berkuantor 6. Induksi matematika

1 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Buku Referensi: Lipscutz, S., & Lipson, M. (2008). Matematika Diskret Edisi Ketiga. Jakarta: Erlangga. Jong Jek Siang, (2009). Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: Penerbit ANDI Yogyakarta. Rinaldi Munir, (2012). Matematika Diskrit. Bandung: Penerbit Informatika.

2 Matematika Diskrit – Nalsa Cintya Resti, M.Si

PERTEMUAN 1 Dasar Dasar Logika Logika adalah cara berpikir manusia dengan mengembangkan sesuatu berdasarkan akal pikiran dan bukan pada perasaan ataupun pengalaman. Logika dikaitkan dengan hubungan antar pernyataan, dimana pernyataan dapat memberikan nilai benar atau salah. Aplikasi logika dalam bidang komputer sangat luas, salah satunya adalah dalam bidang pemrograman, rancang komputer, analisa algoritma, dan seterusnya. 1.

Kalimat pernyataan (proposisi) Kalimat pernyataan memiliki perbedaan dengan kalimat biasa yang digunakan sehari-hari. Kalimat biasa sering dipilih kata-kata kiasan, ungkapan, bahasa gaul serta kadang bermakna ganda. Berbeda dengan kalimat biasa, kalimat pernyataan atau disingkat dengan pernyataan harus memiliki struktur yang lengkap, tidak kabur dan jelas. Sebuah pernyataan merupakan kalimat yang hanya memiliki nilai benar (true) atau salah (false) tetapi tidak memiliki nilai keduanya. Kalimat perintah, kalimat Tanya tidak termasuk dalam pernyataan karena tidak dapat ditentukan nilai kebenarannya. Contoh kalimat pernyataan: a. Surabaya adalah ibukota NKRI b. Singa pemakan daging c. Matahari terbit dari timur d. Jika 𝑥 = 2, maka 3𝑥 = 6 e. Setiap bilangan prima adalah ganjil f. Jika 𝑥 = 𝑦 maka 𝑦 = 𝑥 Contoh bukan kalimat pernyataan: a. Tolong ambilkan buku di almari 3 Matematika Diskrit – Nalsa Cintya Resti, M.Si

b. Jangan nyalakan lampunya! c. 𝑥 + 𝑦 = 5 d. 𝑎 + 𝑏 > 9 e. 𝑥 2 + 2𝑥 − 9 = 0 f. Jangan mengambil uang itu! Istilah lain untuk pernyataan adalah kalimat tertutup, kalimat deklaratif, statement atau proposisi. Sedangkan istilah lain untuk kalimat bukan pernyataan adalah kalimat terbuka. 2.

Kalimat pernyataan tunggal dan majemuk Suatu kalimat dapat dibedakan atas pernyataan tunggal dan pernyataan majemuk. Pernyataan tunggal atau pernyataan sederhana adalah pernyataan yang tidak memuat pernyataan lain sebagai bagiannya. Pernyataan majemuk adalah pernyataan yang memuat beberapa pernyataan lain atau merupakan penggabungan dari beberapa pernyataan tunggal. Contoh pernyataan tunggal: 

Pernyataan “2 merupakan bilangan prima” dilambangkan dengan huruf "𝑥" Ditulis: 𝑥 = "2 merupakan bilangan prima"



Pernyataan "matahari terbit dari timur" dilambangkan dengan huruf "𝑞" Ditulis: 𝑞 = matahari terbit dari timur Dua pernyataan tunggal atau lebih dapat digabungkan menjadi

sebuah kalimat baru, yang disebut kalimat majemuk. Tiap pernyataan bagian dari pernyataan majemuk disebut sebagai komponen-komponen pernyataan majemuk. 4 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Untuk

menggabung

pernyataan-pernyataan

tunggal

menjadi

pernyataan majemuk dapat digunakan kata hubung atau kata sambung yang disebut operasi-operasi logika matematika. Adapun operasi yang dapat membentuk pernyataan tunggal menjadi pernyataan majemuk adalah: 

Negasi atau ingkaran, dengan kata perangkai “tidak benar bahwa”



Konjungsi, dengan kata perangkai “dan”



Disjungsi, dengan kata perangkai “atau”



Implikasi, dengan kata perangkai “jika … maka …”



Biimplikasi, dengan kata perangkai “… jika dan hanya jika …” Contoh pernyataan majemuk:

1. ikan hidup di air dan kucing hidup di darat 2. Cuaca hujan atau cuaca mendung 3. Jika 𝑥 = 3 maka 𝑥 3 = 27 4. Tidak benar bahwa matahari terbit dari barat 5. Rudi berangkat ke sekolah jika dan hanya jika hari cerah Contoh 1 adalah pernyataan majemuk yaitu suatu konjungsi, karena pernyatan “ikan hidup di air dan kucing hidup di darat” terdiri dari dua komponen pernyataan tunggal yaitu: “ikan hidup di air” dan “kucing hidup di darat” Contoh 2 adalah pernyataan majemuk yaitu suatu disjungsi.

3.

Nilai Kebenaran Pernyataan Seperti yang telah dibahas sebelumnya bahwa pernyataan memiliki nilai benar atau salah. Untuk pernyataan yang memiliki nilai benar diberi tanda B sedangkan untuk pernyataan yang salah diberi tanda S.

5 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Ucapan nilai kebenaran dilambangkan dengan"𝜏". Nilai kebenaran dari pernyataan q ditulis 𝜏(𝑞). Jika pernyataan itu benar maka ditulis 𝜏(𝑞) = 𝐵, sedangkan jika salah maka ditulis 𝜏(𝑞) = 𝑆. Contoh: 1.

jika 𝑞: “kambing berkaki empat”, maka 𝜏(𝑞) = 𝐵

2.

jika 𝑚: “semua bilangan prima adalah ganjil”, maka 𝜏(𝑚) = 𝑆.

6 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Operator-Operator Logika 1) Operator Negasi Operator negasi atau bisa juga disebut penyangkalan adalah operator yang dikenakan pada sebuah pernyataan. Lambang dari operator negasi adalah "~". Jika terdapat r sebuah pernyataan tunggal maka ~𝑟 merupakan negasi dari 𝑟 atau dibaca tidak 𝑟 atau bukan 𝑟. Contoh: 

Jika 𝑝

∶ Hari ini hujan deras

Maka ~𝑝: Hari ini tidak hujan deras 

Jika 𝑞

∶ Mahasiswa adalah agent of change

Maka ~𝑞: Tidak benar bahwa mahasiswa adalah agent of change 

Jika 𝑟

∶ 3 + 8 = 11

Maka ~𝑟: 3 + 8 ≠ 11 

Jika 𝑥

∶ semua bilangan prima adalah bilangan ganjil

Maka ~𝑥: tidak benar bahwa semua bilangan prima adalah bilangan ganjil Dari penjelasan contoh diatas, dapat ditarik kesimpulan bahwa negasi dari sebuah pernyataan yang benar adalah salah dan negasi dari sebuah pernyataan salah adalah benar. Tabel Kebenaran Negasi: 𝒑

~𝒑

𝐵

𝑆

𝑆

𝐵

7 Matematika Diskrit – Nalsa Cintya Resti, M.Si

2) Operator Konjungsi Suatu pernyataan yang dibentuk dengan menggabungkan dua pernyataan tunggal dengan menggunakan kata hubung dan disebut konjungsi. Operasi konjungsi berfungsi sebagai kata penghubung dua kalimat tunggal menjadi kalimat majemuk. Operasi tersebut dinotasikan dengan tanda " ∧ ". a. Jika Dan

𝑎: 7 adalah bilangan prima 𝑏: Indonesia adalah negara tropis

Maka 𝑎 ∧ 𝑏: 7 adalah bilangan prima dan Indonesia adalah negara tropis b. Jika Dan

𝑥: Mahasiswa harus rajin belajar 𝑦: Kopi mengandung kafein

Maka 𝑎 ∧ 𝑏: Mahasiswa harus rajin belajar dan kopi mengandung kafein c. Jika Dan

𝑝: 3 + 6 = 10 𝑞: 4 adalah bilangan prima

Maka 𝑝 ∧ 𝑞: 3 + 6 = 10 dan 4 adalah bilangan prima

Dalam

membuat

kalimat

majemuk

tidak

diharuskan

menggunakan kalimat tunggal yang saling berkaitan dan memiliki arti. Sebagai contoh pada soal b diatas, antara pernyataan tunggal yang satu dengan yang lain tidak memiliki arti. Definisi: sebuah konjungsi bernilai benar jika komponenkomponennya benar, tetapi bernilai salah jika salah satu komponennya salah atau keduanya salah.

8 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Tabel Kebenaran Konjungsi: 𝒑

𝒒

𝒑∧𝒒

𝐵

𝐵

𝐵

𝐵

𝑆

𝑆

𝑆

𝐵

𝑆

𝑆

𝑆

𝑆

a. Jika Dan

𝑎: 7 adalah bilangan prima, 𝜏(𝑎) = 𝐵 𝑏: Indonesia adalah negara tropis, 𝜏(𝑏) = 𝐵

Maka 𝑎 ∧ 𝑏: 7 adalah bilangan prima dan Indonesia adalah negara tropis, 𝜏(𝑎 ∧ 𝑏) = 𝐵 b. Jika Dan

𝑥: 52 < 42 , 𝜏(𝑥) = 𝑆 𝑦: Kopi mengandung kafein, 𝜏(𝑦) = 𝐵

Maka 𝑎 ∧ 𝑏: 52 < 42 dan kopi mengandung kafein, 𝜏(𝑥 ∧ 𝑦) = 𝑆 c. Jika Dan

𝑝: 3 + 6 = 10, 𝜏(𝑝) = 𝑆 𝑞: 4 adalah bilangan prima, 𝜏(𝑞) = 𝑆

Maka 𝑝 ∧ 𝑞: 3 + 6 = 10 dan 4 adalah bilangan prima, 𝜏(𝑝 ∧ 𝑞) = 𝑆

3) Operator Disjungsi Jika terdapat dua pernyataan tunggal yang digabungkan dengan kata perangkai atau, maka pernyataan majemuk yang diperoleh disebut disjungsi. Disjungsi dinotasikan dengan tanda "⋁". Definisi:

sebuah

disjungsi

bernilai

benar

jika

komponennya benar, paling sedikit satu komponennya benar.

9 Matematika Diskrit – Nalsa Cintya Resti, M.Si

kedua

Tabel Kebenaran Disjungsi 𝒑

𝒒

𝒑⋁𝒒

𝐵

𝐵

𝐵

𝐵

𝑆

𝐵

𝑆

𝐵

𝐵

𝑆

𝑆

𝑆

𝑎: 7 + 5 = 9 , 𝜏(𝑎) = 𝑆

a. Jika

𝑏: Indonesia adalah negara tropis, 𝜏(𝑏) = 𝐵

Dan

Maka 𝑎⋁𝑏 ∶ 7 + 5 = 9 atau Indonesia adalah negara tropis, 𝜏(𝑎⋁𝑏) = 𝐵 𝑥: 52 > 42 , 𝜏(𝑥) = 𝐵

b. Jika

𝑦: Kopi mengandung kafein, 𝜏(𝑦) = 𝐵

Dan

Maka 𝑥⋁𝑦: 52 > 42 , r atau kopi mengandung kafein, 𝜏(𝑥⋁𝑦) = 𝐵 c. Jika Dan

𝑝: 3 + 6 = 10, 𝜏(𝑝) = 𝑆 𝑞: 4 adalah bilangan prima, 𝜏(𝑞) = 𝑆

Maka 𝑝⋁𝑞: 3 + 6 = 10 dan 4 adalah bilangan prima, 𝜏(𝑝⋁𝑞) = 𝑆 LATIHAN: Jika 𝑝, 𝑞, 𝑟 adalah proposisi, bentuklah tabel kebenaran dari ekspresi logika berikut: 1. (𝑝 ⋀ ~𝑞)⋁𝑝 2 (𝑝 ⋀ ~𝑞)⋁(𝑝 ⋀ 𝑞) 3. (𝑝⋀𝑞)⋁(~𝑞 ⋀ ~𝑟)

10 Matematika Diskrit – Nalsa Cintya Resti, M.Si

4) Operator Implikasi Dalam matematika sering ditemui pernyataan dalam bentuk “jika … maka…”. Pernyataan dalam bentuk tersebut diperoleh dari penggabungan dua pernyataan tertentu, misalnya dari pernyataan tunggal 𝑝 dan pernyataan tunggal 𝑞. Pernyataan “jika 𝑝 maka 𝑞” dinotasikan "𝑝 → 𝑞". Perhatikan contoh berikut: Contoh: Jika

𝑝: Segitiga ABC samasisi

Dan

𝑞: Segitiga ABC memiliki tiga sudut yang sama besarnya

Maka 𝑝 → 𝑞: jika segitiga ABC samasisi maka segitiga ABC memiliki tiga sudut yang sama besarnya. Dalam pernyataan implikasi tersebut, komponen yang terletak diantara “jika …maka” yaitu bagian kalimat yang lebih dulu menjadi

syarat

pernyataan

disebut

yang

ditulis

“anteseden”, kemudian,

sedangkan yaitu

komponen

bagian

belakang

merupakan akibatnya atau yang mengikutinya disebut “konsekuen”. Dari contoh diatas dapat diketahui anteseden adalah kalimat 𝑝: “segitiga ABC samasisi”, dan konsekuen adalah kalimat 𝑞: “segitiga ABC memiliki tiga sudut yang sama besarnya.” Definisi:

suatu

pernyataan

implikasi

hanya

salah

jika

antisedennya benar dan konsekuennya salah, dalam kemungkinan lainnya pernyataan implikasi itu adalah benar.

11 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Tabel Kebenaran Implikasi: 𝒑

𝒒

𝒑→𝒒

𝐵

𝐵

𝐵

𝐵

𝑆

𝑆

𝑆

𝐵

𝐵

𝑆

𝑆

𝐵

Contoh: 𝑝: Segitiga ABC samasisi, 𝜏(𝑝) = 𝐵

Jika

𝑞: Segitiga ABC memiliki tiga sudut yang sama besarnya,

Dan 𝜏(𝑞) = 𝐵

Maka 𝑝 → 𝑞: jika segitiga ABC samasisi maka segitiga ABC memiliki tiga sudut yang sama besarnya, 𝜏(𝑝 → 𝑞) = 𝐵. Jika diketahui 𝑝 → 𝑞 maka didapatkan konvers, invers dan kontraposisi yang dinyatakan sebagai berikut: Konvers/kebalikan : 𝑞 → 𝑝 Invers

: ~𝑝 → ~𝑞

Kontraposisi

: ~𝑞 → ~𝑝

Tabel kebenaran untuk proposisi bersyarat dapat disajikan pada tabel dibawah ini. Tabel kebenaran konvers, invers, dan kontraposisi 𝑝

𝑞

~𝑝

~𝑞

𝑝→𝑞

𝑞→𝑝

~𝑝 → ~𝑞

~𝑞 → ~𝑝

𝐵

𝐵

𝑆

𝑆

𝐵

𝐵

𝐵

𝐵

𝐵

𝑆

𝑆

𝐵

𝑆

𝐵

𝐵

𝑆

𝑆

𝐵

𝐵

𝑆

𝐵

𝑆

𝑆

𝐵

𝑆

𝑆

𝐵

𝐵

𝐵

𝐵

𝐵

𝐵

12 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Contoh: Tentukan konvers, invers, dan kontraposisi dari pernyataan bersyarat berikut: “ jika anda mengirim saya list tugas lewat email maka saya akan menyelesaikan tugas dalam seminggu ini”  Konvers: jika saya menyelesaikan tugas dalam seminggu ini maka anda mengirim list tugas lewat email.  Invers: jika anda tidak mengirim list tugas lewat email maka saya tidak akan menyelesaikan tugas dalam seminggu ini.  Kontraposisi: jika saya tidak menyelesaikan tugas dalam seminggu ini maka anda tidak mengirim list tugas lewat email. Latihan: Tentukan konvers, invers dan kontraposisi dari pernyataan bersyarat berikut: a. “jika manusia tidak memelihara lingkungan dengan baik maka akan

terjadi

kerusakan-kerusakan

bumi

yang

merugikan

manusia”. b. Jika 𝑎2 + 𝑏 2 = 𝑐 2 maka 𝑎, 𝑏, 𝑐 adalah sisi-sisi segitiga siku-siku c. Jika 𝑛 habis dibagi 8 maka 𝑛 habis dibagi 2 d. Jika 𝑝 adalah bujur sangkar maka 𝑝 adalah empat persegi panjang

5) Operator Biimplikasi Operasi biimplikasi disebut juga operasi bikondisional, operasi dua arah, operasi ekuivalensi. Operasi biimplikasi dinotasikan dengan " ↔ " atau “jika dan hanya jika”. 13 Matematika Diskrit – Nalsa Cintya Resti, M.Si

Untuk membentuk pernyataan majemuk biimplikasi diperlukan dua pernyataan 𝑝 dan 𝑞. Untuk operator biimplikasi maka pernyataan majemuknya menjadi “𝑝 jika dan hanya jika 𝑞" atau "𝑝 ekivalen dengan 𝑞" yang dinotasikan dengan "𝑝 ↔ 𝑞". Hal tersebut memiliki arti "𝑝 → 𝑞" dan "𝑞 → 𝑝". Definisi: Suatu biimplikasi 𝑝 ↔ 𝑞 bernilai benar jika nilai kebenaran 𝑝 sama dengan nilai kebenaran 𝑞. Biimplikasi 𝑝 ↔ 𝑞 bernilai salah jika nilai kebenaran 𝑝 tidak sama dengan nilai kebenaran 𝑞. Tabel Kebenaran Biimplikasi: 𝒑

𝒒

𝒑↔𝒒

𝐵

𝐵

𝐵

𝐵

𝑆

𝑆

𝑆

𝐵

𝑆

𝑆

𝑆

𝐵

Contoh: Jika Dan

𝑝: Segitiga ABC samakaki, 𝜏(𝑝) = 𝐵 𝑞: Segitiga ABC memiliki dua sudut yang sama besarnya,

𝜏(𝑞) = 𝐵 Maka 𝑝 ↔ 𝑞: segitiga ABC samakaki jika dan hanya jika memiliki dua sudut yang sama besarnya, 𝜏(𝑝 ↔ 𝑞) = 𝐵.

Latihan Soal: a. (𝑝⋀(~𝑝⋁𝑞)) → 𝑟 b. (𝑝 → 𝑞) ↔ ~(𝑞⋁𝑝) c. (~𝑝⋀(~𝑞⋀𝑟)) ↔ (𝑝⋀𝑟) 14 Matematika Diskrit – Nalsa Cintya Resti, M.Si

15 Matematika Diskrit – Nalsa Cintya Resti, M.Si