Discrete Math

Discrete mathematics forms the foundation of computer science and mathematical logic. This week we explore fundamental concepts including tautologies, contradictions, contingencies, logical equivalences, and their applications in truth tables. Understanding these concepts is crucial for logical reasoning and mathematical proofs.

Tautologi, Kontradiksi, dan Kontingen

Sebuah proposisi majemuk disebut Tautologi jika ia benar untuk semua kasus, sebaliknya disebut kontradiksi jika ia salah untuk semua kasus. Proposisi tautologi ditirikan pada kolom terakhir pada tabel kebenarannya hanya memuat T. Proposisi kontradiksi ditirikan dengan pada kolom terakhir pada label kebenarannya hanya memuat F. Jika kolom terakhir memuat kumpulan dari T dan F disebut kontingen. Contoh dari tautology dan kontradiksi ditunjukan pada tabel kebenaran berikut ini.

Contoh Tautologi: $p \vee \neg p$

Contoh Kontradiksi: $\neg[(p \rightarrow r) \wedge (p \rightarrow \neg q)] \vee r$

Ekuivalen Secara Logika

Dua proposisi dikatakan ekuivalen secara logika jika nilai kebenaran dari kedua pernyataan tersebut sama. Lambang untuk ekuivalen adalah " $\equiv$ ". Sebagai contoh, perhatikan label kebenaran dari proposisi $(p \vee q)$ dan $(p \Rightarrow q) \vee (q \Rightarrow p)$ berikut.

Karena nilai kebenaran dari kedua proposisi diatas sama (berdasar tabel kebenaran), maka

$(p \vee q) \equiv (p \Rightarrow q) \vee (q \Rightarrow p)$.

Hukum-Hukum Ekuivalensi Logika

Beberapa hukum ekuivalensi logika disajikan dalam daftar dibawah ini:

1. Hukum Komutatif

   • a. $p \vee q \equiv q \vee p$
   • b. $p \wedge q \equiv q \wedge p$

2. Hukum asosiatif

   • a. $(p \vee q) \vee r \equiv p \vee (q \vee r)$
   • b. $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$

3. Hukum distributive

   • a. $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
   • b. $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$

4. Hukum identitas

   • a. $p \vee T \equiv p$
   • b. $p \wedge F \equiv p$

5. Hukum ikatan

   • a. $p \vee F \equiv F$
   • b. $p \vee T \equiv T$

6. Hukum negasi

   • a. $p \vee \neg p \equiv T$
   • b. $p \wedge \neg p \equiv F$

7. Hukum negasi ganda

   • $\neg(\neg p) \equiv p$

8. Hukum idempotent

   • a. $p \vee p \equiv p$
   • b. $p \wedge p \equiv p$

9. Hukum De Morgan

   • a. $\neg(p \vee q) \equiv \neg p \wedge \neg q$
   • b. $\neg(p \wedge q) \equiv \neg p \vee \neg q$

10. Hukum Penyerapan

    • a. $p \vee (p \wedge q) \equiv p$
    • b. $p \wedge (p \vee q) \equiv p$

11. Negasi T dan F

    • a. $\neg T \equiv F$
    • b. $\neg F \equiv T$

Konvers, Invers, dan Kontraposisi

Terdapat beberapa implikasi lain yang berkaitan dengan proposisi $p \rightarrow q$, yaitu proposisi sederhana yang merupakan variasi dari implikasi. Perhatikan proposisi berikut:

Jika Amir mempunyai mobil, maka ia orang kaya.

Variasi dari proposisi diatas adalah sebagai berikut:

• a. Jika Amir orang kaya, maka ia mempunyai mobil.
• b. Jika Amir tidak mempunyai mobil, maka ia bukan orang kaya.
• c. Jika Amir bukan orang kaya, maka ia tidak mempunyai mobil.

Proposisi (a) disebut konvers, (b) disebut invers, dan (c) disebut kontraposisi. Tabel berikut ini memperlihatkan tabel kebenaran dari ketiga variasi proposisi $p \Rightarrow q$. Dari tabel tersebut terlihat bahwa proposisi $p \Rightarrow q$ ekuivalen secara logika dengan kontraposisinya $\neg q \Rightarrow \neg p$.

Latihan

1. Buatlah tabel kebenaran dari proposisi berikut:

   • a. $\neg p \wedge (q \vee \neg r)$
   • b. $(p \vee q) \vee \neg (r \vee s)$
   • c. $\neg (p \vee r) \wedge [(\neg p \vee \neg q) \rightarrow t]$

2. Periksalah menggunakan tabel kebenaran apakah proposisi berikut merupakan tautology, kontradiksi atau kontingen.

   • a. $p \vee [q \wedge (p \vee q)]$
   • b. $(p \Rightarrow \neg q) \Rightarrow (\neg q \Rightarrow p)$
   • c. $(r \vee p) \rightarrow [ (q \vee \neg p) \rightarrow (\neg q \rightarrow r)]$

3. Tentukan konvers, invers, dan kontraposisi dari proposisi berikut dan tentukan nilai kebenarannya.

   • a. Jika $x$, $y$ bilangan asli, maka $x - y$ adalah bilangan asli.
   • b. Jika $x$, $y$ bilangan ganjil, maka $x^2 + y^2$ adalah bilangan ganjil.
   • c. Jika $A = \varnothing$, maka $n(A) = 0$.

4. Tentukan pernyataan kondisional yang mempunyai:

   • a. Invers $p \rightarrow \neg q$
   • b. Kontraposisi $\neg p \Rightarrow q$
   • c. Konvers $(p \vee q) \Rightarrow \neg r$
   • d. Invers $(p \vee \neg q) \Rightarrow \neg(r \vee \neg s)$