Pengantar Matematika Diskrit & Logika Proposisi

0Peta Belajar

Lihat gambaran besarnya dulu sebelum masuk ke detail

Modul ini disusun untuk belajar mandiri (BT dan BM) sekaligus pendamping tatap muka 3 × 50 menit. Total waktu belajar mandiri yang disarankan sekitar 180 menit, dibagi per bagian seperti di tabel berikut.

Cara memakai modul ini

Kamu akan menemukan lima jenis kotak di sepanjang modul. Kenali warnanya supaya belajarmu lebih cepat:

☆Tujuan Belajar

Apa yang bisa kamu lakukan setelah pertemuan ini

Setelah mempelajari modul ini, kamu mampu:

• Menjelaskan apa itu matematika diskrit dan perannya dalam Sistem Informasi.
• Membedakan proposisi dari kalimat yang bukan proposisi.
• Menerjemahkan kalimat sehari-hari atau kasus Sistem Informasi ke ekspresi logika memakai ¬, ∧, ∨, ⊕, →, dan ↔.
• Menyusun tabel kebenaran sampai tiga variabel dan menentukan nilai kebenaran proposisi majemuk.
• Mengenali tautologi, kontradiksi, kontingensi, dan ekuivalensi logis sederhana (pengayaan).
• Menghubungkan konsep proposisi dengan qadhiyyah dalam ilmu mantiq.

Alur pertemuan tatap muka (150 menit)

Kebiasaan belajar yang kita bawa

Mata kuliah ini mengajak kita menjadikan nilai-nilai Ahlussunnah wal Jama’ah An-Nahdliyah sebagai kebiasaan berpikir ilmiah, bukan sekadar hiasan. Di pertemuan pertama, wujudnya begini:

Lima nilai di atas dirumuskan di RPS mata kuliah ini. Di pertemuan 1 wujudnya adalah kebiasaan belajar, bukan komponen yang dinilai dalam kuis.

1Mengenal Matematika Diskrit

Matematika tentang hal-hal yang bisa dihitung satu per satu

Apa itu “diskrit”?

Kata diskrit berarti terpisah dan dapat dihitung. Matematika diskrit mempelajari objek-objek yang berdiri sendiri, seperti bilangan bulat, himpunan, pernyataan logika, graf, dan string. Lawannya adalah kontinu: besaran yang bisa bernilai berapa saja di antara dua titik, seperti tinggi badan atau suhu.

Kenapa mahasiswa Sistem Informasi perlu ini?

Karena hampir semua yang kamu bangun nanti, seperti basis data, aplikasi, jaringan, dan keamanan, berdiri di atas struktur diskrit. Setiap topik di mata kuliah ini punya “rumah” di dunia SI:

Berpikir komputasional

Capaian mata kuliah ini adalah berpikir komputasional: memecah masalah besar menjadi bagian kecil, mengenali pola, mengabstraksikan hal yang penting, lalu menyusun langkah penyelesaian. Logika proposisi adalah latihan pertamanya, karena kamu belajar mengubah kalimat yang kabur menjadi bentuk yang pasti dan bisa diperiksa.

Peta perjalanan 16 pertemuan

2Sekilas Sejarah Logika

Manusia sudah lama berusaha berpikir dengan tepat

Logika bukan barang baru. Berikut empat pos penting dalam perjalanannya, dari filsafat kuno sampai komputer modern.

Perhatikan bahwa dua tradisi, logika matematika modern dan mantiq klasik, sama-sama bertujuan menjaga kita dari kesalahan berpikir. Di bagian 8 kita akan membandingkan keduanya secara jujur: apa yang mirip dan apa yang tidak persis sama.

3Proposisi

Batu bata pertama dalam logika

Kata kuncinya ada dua: kalimatnya berbentuk pernyataan, dan kebenarannya pasti salah satu, tidak ganda dan tidak menggantung.

Mana yang proposisi?

Variabel proposisional

Supaya ringkas, kita mewakili proposisi dengan huruf kecil: p, q, r, s, dan seterusnya. Huruf-huruf ini disebut variabel proposisional, dan nilainya hanya T atau F.

Contoh. Misalkan:

• p: “Hari ini hujan.”
• q: “Saya membawa payung.”

Maka “Hari ini hujan dan saya membawa payung” ditulis p ∧ q. Dari dua proposisi atomik, kita mendapat satu proposisi majemuk. Cara menyambungnya akan kita pelajari di bagian berikutnya.

4Konektif Logika

Lem yang menyambung proposisi kecil menjadi proposisi besar

Ada lima konektif utama (ditambah satu varian). Untuk masing-masing, kita lihat arti, tabel kebenaran, contoh, dan jebakannya. Ingat: T = True (benar), F = False (salah).

4.1 Negasi ¬ p (“tidak”)

Negasi membalik nilai kebenaran. Jika p benar maka ¬ p salah, dan sebaliknya.

Contoh: p = “Server menyala”, maka ¬ p = “Server tidak menyala”.

4.2 Konjungsi p ∧ q (“dan”)

Konjungsi bernilai benar hanya jika keduanya benar. Cukup satu salah, hasilnya salah.

Dalam bahasa Indonesia, konjungsi bisa muncul sebagai dan, serta, tetapi, namun, meskipun. Secara logis semuanya sama: kedua bagian benar. “Hari ini tidak hujan, tetapi jalanan macet” berbentuk ¬ p ∧ q. Nuansa “tetapi” hilang di logika, yang tersisa hanya fakta bahwa keduanya benar.

4.3 Disjungsi p ∨ q (“atau”)

Disjungsi (inklusif) bernilai salah hanya jika keduanya salah. Cukup satu benar, hasilnya benar. Artinya “salah satu atau keduanya”.

Disjungsi eksklusif p ⊕ q (XOR)

Kadang “atau” berarti salah satu saja, tidak keduanya. Inilah XOR, yang benar jika p dan q berbeda nilai.

4.4 Implikasi p → q (“jika p maka q”)

Inilah konektif yang paling sering membuat bingung, jadi kita bahas pelan. Pada p → q, p disebut hipotesis (antesedens) dan q disebut konklusi (konsekuen).

Satu-satunya kasus salah adalah hipotesis benar tetapi konklusi salah. Mari pahami lewat analogi janji.

Jadi kalau p salah, janji tidak bisa dilanggar, sehingga implikasinya dianggap benar. Ini disebut benar secara hampa (vacuous truth).

Satu implikasi, banyak cara mengucapkannya

Semua bentuk berikut bermakna p → q:

Konvers, invers, dan kontraposisi

Dari satu implikasi p → q kita bisa membuat tiga “saudara”:

Buktikan lewat tabel kebenaran. Perhatikan bahwa kolom implikasi dan kolom kontraposisi identik (emas), begitu juga kolom konvers dan invers (biru):

4.5 Biimplikasi p ↔ q (“jika dan hanya jika”)

Biimplikasi bernilai benar jika p dan q bernilai sama, sama-sama T atau sama-sama F. Dibaca “p jika dan hanya jika q”, sering disingkat jhj (bahasa Inggris: iff), atau “p syarat perlu dan cukup bagi q”.

Contoh: “Sebuah bilangan bulat genap jika dan hanya jika habis dibagi 2.” Kalau genap maka habis dibagi 2, dan kalau habis dibagi 2 maka genap. Arahnya berlaku dua sisi.

4.6 Lembar rangkuman semua konektif

5Tabel Kebenaran

Alat untuk memeriksa proposisi majemuk tanpa menebak

5.1 Urutan pengerjaan (prioritas operator)

Seperti perkalian yang didahulukan dari penjumlahan, konektif logika juga punya urutan:

5.2 Berapa baris yang dibutuhkan?

Setiap variabel punya 2 kemungkinan nilai (T atau F). Dengan n variabel, jumlah baris adalah 2ⁿ.

5.3 Lima langkah menyusun tabel

1. 1Daftar variabel yang ada pada ekspresi (misalnya p, q, r).
2. 2Hitung jumlah baris: 2ⁿ.
3. 3Isi kombinasi T/F secara sistematis. Kolom paling kiri berganti paling lambat (separuh T, separuh F), kolom di sebelahnya berganti dua kali lebih cepat, dan seterusnya. Baris pertama semua T, baris terakhir semua F.
4. 4Buat kolom bantu untuk setiap bagian ekspresi, dari yang paling dalam (dalam kurung, negasi) ke luar.
5. 5Hitung kolom akhir dari kolom-kolom bantu.

5.4 Contoh 1: (p ∨ q) → ¬ r

Tiga variabel, jadi 8 baris. Kolom bantu: p ∨ q dan ¬ r. Kolom akhir ditandai emas.

Baca satu baris untuk memastikan: baris pertama p=T, q=T, r=T. Maka p ∨ q = T dan ¬ r = F, sehingga T → F = F. Cocok dengan kolom akhir.

5.5 Contoh 2 (kasus SI): aturan akses fitur

Sebuah sistem akademik memberi akses fitur “Ubah Nilai” dengan aturan: pengguna harus terautentikasi, dan perannya admin atau dosen. Misalkan a = terautentikasi, b = peran admin, c = peran dosen. Aturannya a ∧ (b ∨ c).

Dari tabel terlihat akses hanya diberikan pada baris saat a benar dan setidaknya salah satu dari b atau c benar. Perhatikan: pengguna yang tidak terautentikasi (a=F) tidak pernah mendapat akses, apa pun perannya. Beginilah tabel kebenaran dipakai untuk memeriksa aturan bisnis sebelum ditulis menjadi kode.

6Dari Kalimat ke Simbol

Keterampilan paling berguna: menerjemahkan bahasa manusia ke logika

6.1 Lima langkah menerjemahkan

1. 1Temukan pernyataan atomik (kalimat tunggal yang bisa benar atau salah).
2. 2Beri simbol (p, q, r, ...) dan tulis kamusnya: p = ...
3. 3Cari kata penghubung dan cocokkan dengan konektif.
4. 4Susun ekspresi dengan tanda kurung yang jelas.
5. 5Baca balik: ubah lagi ekspresimu ke kalimat. Kalau maknanya sama dengan aslinya, berarti benar.

6.2 Kamus kata kunci

6.3 Contoh terkerjakan

6.4 Sebaliknya: dari simbol ke kalimat

Diketahui p = “Kamu belajar rutin”, q = “Kamu lulus ujian”, r = “Kamu mengulang”. Terjemahkan (p ∧ ¬ q) → r.

Jawab: “Jika kamu belajar rutin dan tidak lulus ujian, maka kamu mengulang.”

7Tautologi, Kontradiksi, dan Ekuivalensi

Pengayaan: jembatan menuju pertemuan 2 dan Aljabar Boolean

7.1 Tiga jenis proposisi majemuk

Kolom 1 semuanya T, jadi p ∨ ¬ p adalah tautologi (“hujan atau tidak hujan” pasti benar). Kolom 2 semuanya F, jadi p ∧ ¬ p adalah kontradiksi (tidak mungkin hujan dan tidak hujan sekaligus). Kolom 3 campuran, jadi p ∧ q adalah kontingensi.

7.2 Ekuivalensi logis

Contoh penting yang sudah kamu temukan di Latihan cepat 3: implikasi dapat ditulis ulang tanpa tanda panah.

Kolomnya identik, jadi p → q ≡ ¬ p ∨ q. Jika tidak punya operator implikasi (misalnya di bahasa pemrograman), kamu menulisnya sebagai !p || q.

Hukum De Morgan

Hukum ini menjawab pertanyaan: bagaimana menegasikan “dan” dan “atau”?

Kolom 1 sama dengan kolom 2, dan kolom 3 sama dengan kolom 4. Maka ¬(p ∧ q) ≡ ¬ p ∨ ¬ q dan ¬(p ∨ q) ≡ ¬ p ∧ ¬ q. Dalam kata-kata: negasi dari “dan” adalah “atau” dengan masing-masing bagian dinegasikan, dan sebaliknya.

7.3 Hukum-hukum dasar ringkas

8Mantiq Corner

Proposisi dan qadhiyyah: dua tradisi, satu semangat berpikir tepat

Jika kamu pernah mengaji kitab mantiq di pesantren, misalnya as-Sullam al-Munawraq karya Abdurrahman al-Akhdhari, sebagian isi modul ini akan terasa seperti bertemu teman lama. Kitab itu memang dipakai luas sebagai pegangan dasar ilmu mantiq (logika) di pesantren dan perguruan tinggi Islam. Yang berbeda adalah “bahasa” dan simbolnya.

Qadhiyyah = proposisi

Jenis qadhiyyah dan padanan terdekatnya

Tulisan-tulisan mantiq membagi qadhiyyah, antara lain, menjadi hamliyyah, syarthiyyah muttashilah, dan syarthiyyah munfashilah (Hidayat dkk.; pembagian syarthiyyah menjadi muttashilah dan munfashilah juga dibahas dalam analisis Ibn Sina, lihat Chatti). Kita bandingkan dengan logika proposisi:

Tanaqudh dan negasi

Dalam mantiq dikenal tanaqudh (kontradiksi), yaitu hubungan dua proposisi yang saling menafikan secara mutlak (Hidayat dkk.). Intuisinya mirip pasangan p dan ¬ p: keduanya tidak mungkin sama-sama benar dan tidak mungkin sama-sama salah, sebagaimana kolom p ∧ ¬ p yang semuanya F di bagian 7.

Menyelami lebih jauh

• Untuk pembaca berbahasa Indonesia, syarah Belajar Mudah Ilmu Mantik karya Iman S. Muminin mengulas as-Sullam al-Munawraq, termasuk bab tentang proposisi dan hukum-hukumnya.
• Perbandingan lebih rinci akan sangat menarik menjadi bahan proyek integratif di minggu 15.

9Logika dalam Praktik SI

Dari simbol di kertas ke baris kode dan query

9.1 Operator logika di bahasa pemrograman dan SQL

Tidak ada operator implikasi bawaan di bahasa-bahasa tersebut. Itulah gunanya kesetaraan p → q ≡ ¬ p ∨ q dari bagian 7.

# Contoh Python: saldo cukup DAN PIN benar
if saldo >= harga and pin_benar:
    proses_transaksi()
else:
    tolak()

9.2 Prioritas operator di SQL: AND didahulukan dari OR

Prioritas yang kita pelajari di bagian 5 muncul nyata di SQL. Bandingkan dua query berikut:

-- Versi 1: (aktif AND semester 1) OR beasiswa
SELECT nama FROM mahasiswa
WHERE status = 'aktif' AND semester = 1 OR beasiswa = 'ya';

-- Versi 2: aktif AND (semester 1 OR beasiswa)
SELECT nama FROM mahasiswa
WHERE status = 'aktif' AND (semester = 1 OR beasiswa = 'ya');

Misalkan s = status aktif, m = semester 1, b = beasiswa. Versi 1 adalah (s ∧ m) ∨ b, sedangkan Versi 2 adalah s ∧ (m ∨ b). Perhatikan hasil pada empat mahasiswa contoh:

Budi tidak aktif tetapi punya beasiswa. Versi 1 mengikutsertakannya, Versi 2 tidak. Satu pasang tanda kurung mengubah hasil laporan. Ini alasan kuat kenapa tanda kurung wajib jadi kebiasaan.

10Rangkuman dan Latihan

Lembar contekan, soal latihan, dan tantangan kelompok

10.1 Lembar contekan satu halaman

Lima hal yang wajib diingat

• Proposisi = pernyataan yang pasti bernilai benar atau salah. Salah pun tetap proposisi.
• Urutan operator: ¬, ∧, ∨, →, ↔. Biasakan memakai tanda kurung.
• p → q salah hanya ketika p benar dan q salah.
• “hanya jika” berarti p → q, bukan q → p. Implikasi ekuivalen dengan kontraposisinya, bukan dengan konvers atau inversnya.
• Variabel n menghasilkan 2ⁿ baris. Susun tabel secara sistematis agar tidak ada yang terlewat.

10.2 Latihan A: pilihan ganda

Pilih satu jawaban yang paling tepat. Klik pilihanmu untuk langsung tahu benar atau salah. Pembahasan lengkap ada di bagian kunci.

Skor percobaan pertama: 0 dari 8

10.3 Latihan B: uraian

1. Tentukan mana yang proposisi, dan beri nilai kebenarannya:
   • (a) Indonesia merdeka pada tahun 1945.
   • (b) Mari belajar bersama!
   • (c) 3 + 4 = 8.
   • (d) 9 habis dibagi 3 dan 9 adalah bilangan genap.
2. Terjemahkan ke logika (tulis kamusnya):
   • (a) “Jika baterai habis atau layar rusak, maka ponsel tidak dapat digunakan.”
   • (b) “Dokumen dapat dicetak hanya jika printer terhubung.”
   • (c) “Tidak benar bahwa server aktif dan basis data terhubung.”
3. Susun tabel kebenaran (p → q) ∧ (q → p) dan bandingkan dengan p ↔ q.
4. Susun tabel kebenaran ¬ p ∨ (q ∧ r) (8 baris).
5. Tuliskan konvers, invers, dan kontraposisi dari “Jika sebuah bilangan habis dibagi 4, maka bilangan itu genap.” Mana yang benar dan mana yang salah? Berikan contoh penyangkal bila ada.
6. Periksa dengan tabel kebenaran apakah (p ∧ q) → (p ∨ q) adalah tautologi.

10.4 Latihan C: tantangan kelompok (tasyawur)

10.5 Cek diri

Ketuk kotak pada pernyataan yang sudah kamu kuasai. Pernyataan yang belum dicentang adalah bagian yang perlu kamu baca ulang atau tanyakan.

KKunci Jawaban dan Pembahasan

Cocokkan setelah kamu mencoba sendiri. Mengintip dulu tidak ikut belajar.

Latihan cepat 1 (bagian 3)

Latihan cepat 2 (bagian 4)

Latihan cepat 3 (bagian 5)

Kolom ¬ p ∨ q identik dengan p → q, jadi keduanya ekuivalen.

Latihan A: pilihan ganda

• 1. Hanya “7 adalah bilangan prima” yang berupa pernyataan dengan nilai pasti.
• 2. T → F = F, satu-satunya kasus salah pada implikasi.
• 3. “hanya jika” menempatkan p → q.
• 4. Konvers menukar hipotesis dan konklusi.
• 5. 2⁴ = 16.
• 6. Selalu benar, jadi tautologi.
• 7. ¬ q = T, p ∧ ¬ q = T, lalu T → F = F, jadi Salah.
• 8. De Morgan: ¬(p ∨ q) ≡ ¬ p ∧ ¬ q.

Latihan B: uraian

B1. (a) Proposisi, T. (b) Bukan (ajakan). (c) Proposisi, F. (d) Proposisi, F, karena 9 tidak genap (konjungsi dengan satu bagian salah).

B2. (a) b = baterai habis, l = layar rusak, d = ponsel dapat digunakan: (b ∨ l) → ¬ d. (b) c = dokumen dapat dicetak, t = printer terhubung: c → t. (c) a = server aktif, k = basis data terhubung: ¬(a ∧ k).

B3. Kolom (p → q) ∧ (q → p) identik dengan kolom p ↔ q:

B4.

B5. Implikasi asli: benar. Konvers: “Jika bilangan itu genap, maka habis dibagi 4” (salah, contoh penyangkal: 6). Invers: “Jika bilangan itu tidak habis dibagi 4, maka tidak genap” (salah, contoh penyangkal: 6). Kontraposisi: “Jika bilangan itu tidak genap (ganjil), maka tidak habis dibagi 4” (benar, ekuivalen dengan implikasi asli).

B6. Kolom akhir semuanya T, jadi tautologi:

Latihan C: tantangan kelompok

Kamus: a = terdaftar aktif, d = memiliki denda, s = punya surat izin pustakawan. Ekspresi: (a ∧ ¬ d) ∨ s.

Pembahasan diskusi: pada baris saat a = F dan s = T, aturan tetap membolehkan meminjam. Dengan kata lain, surat izin mengalahkan syarat keaktifan dan denda. Kelompok perlu menimbang apakah itu memang dikehendaki. Jika tidak, aturan bisa diubah menjadi a ∧ (¬ d ∨ s), yang tetap mewajibkan status aktif. Tidak ada jawaban tunggal: yang dinilai adalah ketepatan menerjemahkan, ketelitian tabel, dan kualitas musyawarah.

GGlosarium

Istilah penting di pertemuan 1

PDaftar Pustaka

Rujukan untuk belajar lebih jauh

Pustaka utama

Rosen, K.H. (2019). Discrete Mathematics and Its Applications (8th ed.). New York: McGraw-Hill Education. Bab 1 (The Foundations: Logic and Proofs), Subbab 1.1 Propositional Logic, 1.2 Applications of Propositional Logic, dan 1.3 Propositional Equivalences.

Munir, R. (2020). Matematika Diskrit (Edisi Revisi Ketujuh). Bandung: Informatika.

Epp, S.S. (2019). Discrete Mathematics with Applications (5th ed.). Cengage Learning.

Sejarah logika

Boole, G. (1854). An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities. London: Walton and Maberly.

Ilmu mantiq

Al-Akhdhari, ‘A. as-Sullam al-Munawraq fi ‘Ilm al-Mantiq (nazam tentang ilmu mantiq).

Muminin, I.S. Belajar Mudah Ilmu Mantik (syarah atas as-Sullam al-Munawraq).

Hidayat, D., dkk. Konsep Tanaqudh dalam Ilmu Mantiq sebagai Prinsip Penentuan Kebenaran Proposisi. Sindoro: Cendikia Pendidikan. https://cibinstitute.id/index.php/sindoro/article/view/5935

Chatti, S. (2022). On some ambiguities in Ibn Sīnā’s analysis of the quantified hypothetical propositions. Arabic Sciences and Philosophy. Cambridge University Press.