Logika Matematika
& Himpunan
Oleh : Rohmad Wahid Rhomdani
Dari kalimat sehari-hari sampai simbol $\forall$ dan $\exists$ — pelajari bagaimana matematika menjamin sebuah kesimpulan benar, bukan sekadar meyakinkan. Lengkap dengan mesin-mesin logika yang bisa kamu jalankan sendiri.
Tiga pemberhentian, satu perjalanan logika.
Kita mulai dari unit terkecil (proposisi), merakitnya menjadi mesin (operasi logika), mengujinya di atas kertas (tabel kebenaran), lalu menskalakannya ke seluruh himpunan (kuantor).
Proposisi & Operasi Logika
Apa itu proposisi, lalu empat mesin dasar: NOT, AND, OR, dan sang Juara — implikasi $p \to q$.
Tabel Kebenaran & Ekuivalensi
Membangun tabel dari nol, mengenali tautologi, dan memakai hukum-hukum ekuivalensi seperti De Morgan.
Kuantor ∀ dan ∃
Berbicara tentang semua dan ada: kuantor universal & eksistensial, negasinya, dan urutannya.
PROLOG · Kenapa repot belajar logika?
Karena logika adalah satu-satunya alat yang bisa mengubah “sepertinya benar” menjadi “pasti benar”. Selama premis benar dan penalaran sah, kesimpulan terjamin — tidak bisa dibantah.
Modul ini menuntunmu dari nol: setiap rumus akan kita bedah asal-usulnya, bukan sekadar dihafal. Setiap mesin interaktif — tekan tombol Jalankan-nya!
Proposisi & Operasi Logika
Semua cerita logika dimulai dari kalimat paling sederhana yang bisa dinilai benar-salah. Dari bahan dasar itu, kita rakit mesin-mesin: $\neg$, $\land$, $\lor$, dan $\rightarrow$.
1.1.1 · Apa itu Proposisi?
Sebuah proposisi adalah kalimat deklaratif yang nilai kebenarannya pasti dan tunggal — benar saja atau salah saja, tidak boleh keduanya, tidak boleh ragu.
Dalam komputer, $B$ ditulis $1$ dan $S$ ditulis $0$.
“7 adalah bilangan prima.”
Faktual dan pasti benar. ✓
“Matahari terbit dari timur.”
Fakta alam, bernilai $B$. ✓
“7 adalah bilangan genap.”
Masih proposisi — walau nilainya $S$. Penting: salah bukan berarti bukan proposisi.
“Berapakah akar dari 16?”
Kalimat tanya — tidak bisa dinilai benar/salah.
“Tutuplah jendelanya!”
Kalimat perintah — tidak memiliki nilai kebenaran.
“$x + 1 > 5$”
Kalimat terbuka: nilainya tergantung $x$. ($x=1$ salah, $x=10$ benar). Nanti kita tangani ini dengan kuantor di Subbab 1.3 →
$4-7=-3$ adalah pernyataan faktual yang benar.
Ini kalimat terbuka — nilai kebenarannya bergantung pada $n$. Ia baru menjadi proposisi setelah $n$ diberi nilai, misalnya “$7$ adalah bilangan prima”.
Kalimat ajakan/seruan tidak bisa dinilai benar atau salah.
Juni punya 30 hari — tunggu, itu benar! Cek kalender: Juni memang 30 hari, jadi nilainya $B$. Kalimatnya “Juni memiliki 30 hari” = BENAR. Kalau kalimatnya “Februari memiliki 30 hari” barulah $S$. Kuncinya: proposisi salah tetap proposisi.
Contoh Pegangan Kita
dipakai konsisten sepanjang modulKenapa pasangan ini? Sederhana, faktual, dan pas satu benar–satu salah — bahan uji ideal untuk semua mesin logika di bawah.
1.1.2 · Operasi Logika: Mesin Pengolah Kebenaran
Operasi logika ibarat mesin: proporsi masuk, proposisi baru keluar. Nilai keluaran sepenuhnya ditentukan oleh nilai masukan — inilah sifat fungsi kebenaran.
Negasi membalik nilai kebenaran. Dibaca “tidak benar bahwa …”. Secara bahasa: tambahkan “tidak”, atau keluarkan “bukan”.
Konjungsi benar hanya jika keduanya benar — aturan “serba harus lolos”. Bahasa: “dan”.
Disjungsi benar bila minimal satu benar — disebut atau inklusif. Bahasa: “atau”.
Dibaca “$p$ jika dan hanya jika $q$”. Benar tepat ketika kedua nilai kembar (sama-sama $B$ atau sama-sama $S$).
“dan” dalam logika sama sekali tidak peduli nada emosional. “Dia pintar dan sombong” nilainya $B$ hanya jika kedua bagiannya $B$ — persis sama dengan “dia pintar dan rajin”.
“atau” eksklusif: “Pilih naik mobil atau motor” berarti salah satu saja ($\oplus$, xor). Tapi “bayar via QRIS atau transfer” mengizinkan keduanya → itu $\lor$ inklusif. Konteks menentukan!
Membalik dua kali pulang ke awal: “Tidak benar bahwa 7 bukan prima” = 7 prima.
1.1.3 · Implikasi: Sang “Jika–Maka”
Implikasi $p \rightarrow q$ punya dua bagian: $p$ = hipotesis (syaratnya) dan $q$ = konsekuen (akibatnya). Asal-usul aturannya dari janji dan aturan: “Jika hujan, maka tanah basah”, “Jika skormu ≥ 60, maka kamu lulus”.
Perhatikan tiga baris pertama bernilai $B$ — implikasi jauh lebih “pemaaf” daripada kelihatannya.
Skenario: Bapak berjanji — “Jika kamu belajar sungguh-sungguh ($p$), maka kamu boleh ikut perkhemahan ($q$).” Pilih salah satu keadaan dunia, lalu lihat apakah janji diingkari:
Pilih salah satu skenario di atas untuk mengetes janji Bapak.
Ketika hipotesis $p$ salah dari awal, implikasi otomatis $B$ — sebab janji tidak mungkin dilanggar (syaratnya tak pernah terjadi). Ini disebut implikasi kosong (vacuous truth).
“Jika $2+2=5$, maka aku burung unta.” — Dalam logika pernyataan ini BENAR! Bukan karena aku burung unta, melainkan karena premisnya mustahil, janjinya tak akan pernah teruji.
Contoh pegangan · Implikasi dua arah pada $p$, $q$
Balik sakelar $p$ / $q$, lalu tekan Jalankan: sinyal akan menyapu kelima mesin keluaran.
Ringkasan 1.1 · Lima Mesin Dasar
| Mesin | Simbol | Dibaca | Bernilai B ketika… |
|---|---|---|---|
| Negasi | ¬p | “tidak p” | $p$ salah |
| Konjungsi | p ∧ q | “p dan q” | keduanya benar |
| Disjungsi | p ∨ q | “p atau q” | minimal satu benar |
| Implikasi | p → q | “jika p maka q” | tidak terjadi ($p$ benar, $q$ salah) |
| Biimplikasi | p ↔ q | “p jika dan hanya jika q” | keduanya bernilai sama |
Tabel Kebenaran & Ekuivalensi Logis
Tabel kebenaran adalah peta semua kemungkinan dunia: satu baris untuk satu kombinasi nilai. Jika dua kalimat punya peta yang identis baris demi baris — mereka ekuivalen.
1.2.1 · Berapa baris yang dibutuhkan?
Dari mana asalnya $2^n$? Setiap variabel punya 2 pilihan ($B$ atau $S$). Dengan kaidah perkalian, $n$ variabel menghasilkan $2 \times 2 \times \cdots \times 2 = 2^n$ kombinasi. Satu variabel → 2 baris; dua → 4; tiga → 8.
n = 3 variabel → 23 = 8 baris
Kotak-kotak oker = satu baris tabel = satu “kemungkinan dunia”.
Pilih ekspresi, lalu tekan Jalankan — tabel terisi baris demi baris, dan mesin men-tampel verdictnya di akhir.
Tekan Lanjut untuk menambah kolom satu per satu — saksikan sebuah ekuivalensi terbukti sendiri di depan mata.
1.2.2 · Tiga Watak Kalimat
Selalu $B$ di semua baris.
“Hujan atau tidak hujan” — mustahil salah.
Selalu $S$ di semua baris.
“Hujan dan tidak hujan” — mustahil benar.
Campuran — kadang $B$, kadang $S$.
Nilainya bergantung pada dunia mana yang kita jalani.
1.2.3 · Ekuivalensi Logis: Sidik Jari Kebenaran
Dua kalimat $\alpha$ dan $\beta$ disebut ekuivalen logis, ditulis $\alpha \equiv \beta$, jika tabel kebenarannya identis di semua baris — atau secara setara: $\alpha \leftrightarrow \beta$ adalah tautologi.
$\leftrightarrow$ adalah mesin: menghubungkan dua proposisi menghasilkan proposisi baru yang bisa bernilai $B$ atau $S$. Sedangkan $\equiv$ adalah klaim di luar logika (meta-simbol): pernyataan bahwa dua kalimat tak terbedakan nilainya. $\equiv$ selalu “benar atau keliru” sebagai klaim, bukan bagian dari rumus.
1.2.4 · Daftar Hukum Ekuivalensi
Semua hukum ini bisa dibuktikan dengan tabel kebenaran — coba verifikasi sendiri lewat Pembangkit Tabel di atas. Arahkan kursor pada baris untuk menyorot.
| Nama Hukum | Rumus | Intuisi |
|---|---|---|
| Involusi | $\neg(\neg p) \equiv p$ | Dibalik dua kali → kembali ke awal |
| Idempoten | $p \land p \equiv p$ ; $p \lor p \equiv p$ | Mengulang tak mengubah apa pun |
| Komutatif | $p \land q \equiv q \land p$ ; $p \lor q \equiv q \lor p$ | Urutan bebas |
| Asosiatif | $(p \land q) \land r \equiv p \land (q \land r)$ | Pengelompokan bebas |
| Distributif | $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ | Sama seperti distributif di aritmetika |
| Identitas | $p \land B \equiv p$ ; $p \lor S \equiv p$ | $B$/$S$ elemen netral |
| Dominasi | $p \land S \equiv S$ ; $p \lor B \equiv B$ | Konstanta “menang” |
| Komplemen | $p \land \neg p \equiv S$ ; $p \lor \neg p \equiv p \lor \neg p \equiv B$ | Sumber kontradiksi & tautologi |
| De Morgan | $\neg(p \land q) \equiv \neg p \lor \neg q$ ; $\neg(p \lor q) \equiv \neg p \land \neg q$ | Negasi menyebar, $\land \leftrightarrow \lor$ bertukar |
| Implikasi | $p \rightarrow q \equiv \neg p \lor q$ | Implikasi tanpa panah |
| Kontraposisi | $p \rightarrow q \equiv \neg q \rightarrow \neg p$ | Ekuivalensi terpenting untuk pembuktian |
| Negasi Implikasi | $\neg(p \rightarrow q) \equiv p \land \neg q$ | Cara menyangkal sebuah janji |
| Biimplikasi | $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ | Dua arah sekaligus |
Dari mana asalnya? · $p \rightarrow q \equiv \neg p \lor q$, diturunkan langkah demi langkah
p benar & q salah salah $\iff p \land \neg q$ benar $\iff \neg(p \land \neg q)$ DE MORGAN $ \neg p \lor \neg(\neg q) \equiv \neg p \lor q$ ∎
Mesin ini menguji $ \neg(p \land q)$ terhadap dua kandidat: $\neg p \lor \neg q$ (klaim De Morgan) dan $\neg p \land \neg q$ (kesalahan umum). Tekan Jalankan.
| p | q | p ∧ q | ¬(p ∧ q) | ¬p ∨ ¬q | ¬p ∧ ¬q |
|---|---|---|---|---|---|
| · | · | · | · | · | · |
| · | · | · | · | · | · |
| · | · | · | · | · | · |
| · | · | · | · | · | · |
1.2.5 · Konvers, Invers, Kontraposisi — Tiga Kembar yang Beda Nasib
Balik arah panah. Tidak ekuivalen dengan $p \to q$.
Negasi keduanya. Juga tidak ekuivalen (tapi ekuivalen dengan konvers!).
Balik arah + negasi keduanya. Ekuivalen dengan $p \to q$ — senjata utama pembuktian.
| p | q | p → q | q → p (konvers) | ¬q → ¬p (kontraposisi) |
|---|---|---|---|---|
| B | B | B | B | B |
| B | S | S | B | S |
| S | B | B | S | B |
| S | S | B | B | B |
Lihat: kolom $p \to q$ dan $\neg q \to \neg p$ identis ($\equiv$), sedangkan kolom konvers berbeda di dua baris.
$p \to q$ : “Jika seekor hewan ikan, maka ia hidup di air.” — BENAR.
Konversnya: “Jika ia hidup di air, maka ia ikan.” — SALAH! Paus hidup di air tapi bukan ikan. Pausingit inilah yang menjadikan konvers tak dapat dipakai sebagai kesimpulan. Sementara kontraposisinya, “Jika tidak hidup di air, maka bukan ikan” — selalu benar selama kalimat aslinya benar.
Ini persis hukum De Morgan kedua. Negasi menyebar ke masing-masing dan $\lor$ berubah menjadi $\land$.
Itu justru konvers! Tabel di atas menunjukkan keduanya berbeda pada baris $(B,S)$ dan $(S,B)$. Yang ekuivalen dengan $p \to q$ adalah kontraposisi $\neg q \to \neg p$.
Menyangkal “jika p maka q” berarti menemukan janji yang ingkar: p-nya terjadi ($p$) tapi q-nya batal ($\neg q$). Cek dengan Pembangkit Tabel: kolom $\neg(p \to q)$ hanya $B$ di baris $(B,S)$ — sama seperti $p \land \neg q$.
Hukum distributif versi $\lor$ atas $\land$. Sama seperti $2 \times (3+4) = (2 \times 3) + (2 \times 4)$ — hanya beda “kali”nya ganti $\lor$.
Kuantor Universal & Eksistensial
Proposisi bicara tentang satu hal. Tapi matematika sering bicara tentang semua bilangan, atau ada solusi. Untuk itulah ada $\forall$ dan $\exists$ — mesin pengikat variabel.
1.3.1 · Predikat & Semesta (Domain)
Predikat $P(x)$ adalah kalimat terbuka yang mengandung variabel $x$; ia belum punya nilai kebenaran. Ia baru menjadi proposisi setelah $x$ diberi nilai ($P(4)$), atau diikat oleh kuantor ($\forall x\, P(x)$).
Klaim: setiap elemen domain memenuhi $P$. Simbolnya huruf A terbalik dari All.
Cara membuktikan $B$: argumen umum yang mencakup semua elemen (mengecek satu per satu mustahil untuk domain tak hingga).
Cara membuktikan $S$: cukup satu penyangkal!
Klaim: minimal satu elemen domain memenuhi $P$. Simbolnya huruf E terbalik dari Exist.
Cara membuktikan $B$: cukup satu saksi!
Cara membuktikan $S$: tunjukkan tak ada satu pun — butuh argumen umum.
Kartu Kunci: Siapa yang Harus Lembur?
| Klaim | Untuk membuktikan BENAR | Untuk membuktikan SALAH |
|---|---|---|
| ∀x P(x) | cek semua elemen (argumen umum) | cukup 1 penyangkal |
| ∃x P(x) | cukup 1 saksi | cek semua (tak ada yang lolos) |
Lihat simetrinya: $\neg$ menukar $\forall \leftrightarrow \exists$ dan menukar “semua” ↔ “satu”. Inilah benih hukum negasi kuantor di bawah.
Domain D = {1, 2, …, 8}
1.3.2 · Negasi Kuantor: De Morgan Versi Himpunan
Dari mana asalnya? Murni dari parafrase bahasa. “Tidak benar bahwa semua angsa putih” artinya persis “ada angsa yang tidak putih”. Negasi menembus kuantor, menukarkan $\forall \leftrightarrow \exists$, lalu menempel pada predikat:
$\neg\exists x\, P(x) \;\equiv\; \forall x\, \neg P(x)$
| Kalimat | Negasinya | Hukum |
|---|---|---|
| “Semua angsa putih.” | “Ada angsa yang tidak putih.” | ¬∀ ≡ ∃¬ |
| “Tidak ada siswa yang terlambat.” | “Semua siswa tidak terlambat.” | ¬∃ ≡ ∀¬ |
| “Semua mahasiswa lulus.” | “Ada mahasiswa yang tidak lulus.” | ¬∀ ≡ ∃¬ |
Negasikan “Ada bilangan prima yang genap” → “Semua bilangan prima ganjil”… padahal $2$ adalah prima genap! Negasi $\exists$ memang $\forall\neg$ — dan justru $2$ membuktikan kedua klaim itu salah. Logika tidak menjebak; yang menjebak adalah lupa datanya.
Diagram · Satu Penyangkal Menggugurkan ∀
¬∀x Terbang(x) ≡ ∃x ¬Terbang(x) — tanda silang merah berkedip di atas penguin adalah penyangkal, cukup satu untuk menggugurkan klaim “semua”.
1.3.3 · Menerjemahkan Bahasa ↔ Simbol
| Frasa dalam Bahasa Indonesia | Simbol | Contoh |
|---|---|---|
| semua, tiap, setiap, berapa pun | ∀ | “Semua prima > 1” → $\forall x\,(P(x) \to x>1)$ |
| ada, terdapat, beberapa, minimal satu | ∃ | “Ada prima genap” → $\exists x\,(P(x) \land G(x))$ |
| tidak ada / tidak satu pun | ¬∃ | “Tidak ada prima < 2” → $\neg\exists x\,(P(x) \land x<2)$ |
| tidak semua | ¬∀ | “Tidak semua genap prima” → $\neg\forall x\,(G(x) \to P(x))$ |
Mengapa $\to$? Karena klaimnya hanya berlaku bila $x$ anggota $A$; untuk yang bukan $A$, klaimnya diam (implikasi kosong). Ini membuat pola aman untuk semua elemen di luar $A$.
Mengapa $\land$? Karena kita menuntut satu benda yang sekaligus memenuhi keduanya: anggota $A$ dan memenuhi $B$.
Salah 1: $\forall x\,(A(x) \land B(x))$ — ini mengklaim semua benda di domain adalah $A$ sekaligus $B$. Klaim yang jauh terlalu kuat.
Salah 2: $\exists x\,(A(x) \to B(x))$ — ini nyaris selalu $B$ secara murahan! Contoh: $\exists x\,(\text{Prima}(x) \to \text{Genap}(x))$ sudah benar hanya karena $x=4$: Prima$(4)$ salah, sehingga implikasinya kosong → benar. Padahal maksud kita “ada prima genap” = $x=2$. Pola yang keliru menghasilkan kalimat yang berbeda makna.
1.3.4 · Urutan Kuantor: Giliran Memilih Itu Penting
Baca kuantor seperti giliran bermain kartu: dari kiri ke kanan. $\forall x \exists y$ berarti “lawan mengumumkan $x$ dulu, baru kamu membalas dengan $y$”. Sedangkan $\exists y \forall x$ memaksa kamu menunjukkan $y$ dulu — satu kartu untuk semua lawan.
Tantangan apa pun $x$, balas dengan $y = x+1$. Selalu bisa → $B$.
Harus menunjuk satu $y$ ajaib yang lebih besar dari semua bilangan. Tapi $y > y$ itu mustahil → $S$. Tidak ada “bilangan terbesar”.
Lawan memilih dulu: ambil $x = 0$. Inversnya $y = 1/0$ tidak ada. Satu penyangkal menggugurkan $\forall$. (Di $\mathbb{R}\setminus\{0\}$ barulah benar.)
Kita memilih dulu, dan kita boleh pilih dengan cerdas: $y = 1$. Kartu tunggal itu melayani semua $x$. Inilah elemen identitas perkalian.
Kartu Hafalan — rumus inti Bab 1.
Delapan lembar kertas di atas meja gelap. Kalau kamu hanya bisa menyimpan satu halaman dari modul ini — simpan halaman ini.
Dibalik dua kali → pulang
$\neg(p \lor q) \equiv \neg p \land \neg q$
Negasi menyebar, ∧↔∨ bertukar
Janji tanpa panah
Ekuivalen — konvers TIDAK!
Bukti janji diingkari
Benar saat nilainya kembar
$\neg\exists x P(x) \equiv \forall x \neg P(x)$
∀↔∃ bertukar, ¬ menempel
$\forall x (A(x) \to B(x))$
Ada A yang B:
$\exists x (A(x) \land B(x))$
Jangan tukar pasangannya!
Mesin Penilai QZ-05.
Lima pertanyaan lintas subbab. Pilih jawaban, tekan Periksa, dan terima stempel skormu.