Bab 4. Logika (Backup)

Aturan logika menjelaskan arti dari pernyataan matematika. Sebagai contoh, aturan logika membantu kita untuk memahami dan menalar pernyataan-pernyataan seperti "Terdapat sebuah bilangan bulat yang bukan jumlah dari dua kuadrat" dan "Untuk setiap bilangan bulat positif n, jumlah dari bilangan posisitf yang tidak melebihi

$n$ adalah

$n(n+1)/2$". Logika adalah dasar dari semua penalaran matematika dan untuk semua penalaran. Aplikasi dari penalaran antra lain untuk mendesain mesin komputer, spesifikasi sistem, artificial intelligence, pemrograman komputer, bahasa pemrograman, dan area lainnya dalam ilmu komputer, dan juga banyak bidang lainnya.

4.1. Proposisi

Proposisi adalah sebuah kalimat pernyataan (yaitu kalimat yang menyatakan sebuah fakta) yang bernilai benar (true) atau salah (false), tetapi tidak keduanya.

Contoh 4.1.1
Semua kalimat pernyataan di bawah ini adalah proposisi.

1. DKI Jakarta adalah ibukota dari Indonesia.
2. Tokyo adalah ibukota dari Jepang.
3. $1+1=2$.
4. $2+2=3$.

Nilai kebenaran dari proposisi 1 dan 3 adalah benar, sedangkan nilai kebenaran dari proposisi 2 dan 4 adalah salah.

Contoh 4.1.2
Perhatikan kalimat-kalimat berikut:

1. Jam berapa sekarang?
2. Baca ini secara teliti.
3. $x+1=2$.
4. $x+y=z$.

Kalimat 1 dan 2 bukan proposisi karena keduanya bukan kalimat pernyataan. Kalimat 3 dan 4 bukan proposisi karena tidak bernilai benar maupun salah. Perhatikan bawah kalimat 3 dan 4 dapat menjadi proposisi jika kita memberikan nilai-nilai ke variabel-variabelnya.

Kita menggunakan huruf kecil untuk menotasikan variabel yang mewakili sebuah proposisi. Huruf-huruf yang umum digunakan sebagai variabel proposisi antara lain

$p$,

$q$,

$r$,

$s$, dan sebagainya. Setiap proposisi memiliki nilai kebenaran. Nilai kebenaran ini bernilai benar (true) dan dinotasikan dengan T jika prososisi tersebut adalah benar, dan bernilai salah (false) dan dinotasikan dengan F jika proposisi tersebut adalah salah.

4.2. Operasi Logika

Banyak pernyataan matematika dikonstruksi dengan mengkombinasi satu atau lebih proposisi. Proposisi-proposisi dikombinasikan menggunakan operator-operator logika dan hasil kombinasi dari proposisi-proposisi ini disebut dengan proposisi majemuk.

4.2.1. Operasi Logika Dasar

Terdapat sejumlah operator-operator logika antara lain:

• Konjungsi
• Disjungsi
• Negasi
• Implikasi
• Biimplikasi

4.2.1. Konjungsi

DEFINISI 4.1
Misal

$p$ dan

$q$ adalah proposisi. Konjungsi dari

$p$ dan

$q$ yang dinotasikan dengan:

$$p\wedge q$$

adalah proposisi "

$p$ dan

$q$". Konjungsi

$p\wedge q$ bernilai benar jika kedua

$p$ dan

$q$ bernilai benar dan bernilai salah jika sebaliknya.

Tabel 4.1 di bawah adalah tabel kebenaran (truth table) untuk

$p\wedge q$. Tabel kebenaran digunakan untuk memperlihatkan hubungan diantara nilai-nilai kebenaran variabel proposisi dan nilai kebenaran operasi proposisi.

$p$	$q$	$p\wedge q$
T	T	T
T	F	F
F	T	F
T	F	F

// ganti tabel di atas dengan gambar.

4.2.2. Disjungsi

DEFINISI 4.1
Misal

$p$ dan

$q$ adalah proposisi. Disjungsi dari

$p$ dan

$q$ yang dinotasikan dengan:

$$p\vee q$$

adalah proposisi "

$p$ atau

$q$". Konjungsi

$p\vee q$ bernilai salah jika kedua

$p$ dan

$q$ bernilai salah, dan bernilai benar jika sebaliknya.

Tabel 4.2 di bawah adalah tabel kebenaran (truth table) untuk

$p\vee q$.

$p$	$q$	$p\vee q$
T	T	T
T	F	T
F	T	T
T	F	F

// ganti tabel di atas dengan gambar.

4.2.1. Negasi

DEFINISI 4.1
Misal

$p$ adalah proposisi. Negasi dari

$p$ dinotasikan dengan

$\mathrm{\neg }p$ mempunyai nilai kebenaran kebalikan dari nilai kebenaran

$p$.

Tabel 4.1 berikut adalah tabel kebenaran untuk negasi dari proposisi

$p$.

$p$	$\mathrm{\neg }p$
T	F
F	T

Contoh 4.2.x
Cari negasi dari proposisi "PC punya Andi bersistem operasi Linux".

Solusi:
Negasinya adalah "Tidaklah benar bahwa PC punya Andi bersistem operasi Linux." atau dapat juga diekspresikan dengan "PC punyai Anda tidak bersistem operasi Linux."

4.2.4. Disjungsi Eksklusif (Exclusive OR)

DEFINISI 4.1
Misal

$p$ dan

$q$ adalah proposisi. Disjungsi Eksklusif (Exclusive OR) dari

$p$ dan

$q$ yang dinotasikan dengan:

$$p\oplus q$$

adalah proposisi yang bernilai benar jika salah satu dari

$p$ atau

$q$ bernilai benar dan bernilai salah jika sebaliknya.

Tabel 4.x adalah tabel kebenaran dari disjungsi eksklusif

$p\oplus q$.

$p$	$q$	$p\oplus q$
T	T	F
T	F	T
F	T	T
T	F	F

4.2.4. Implikasi/Kondisional

DEFINISI 4.1
Misal

$p$ dan

$q$ adalah proposisi. Implikasi atau kondisional

$p\to q$ adalah proposisi "jika

$p$, maka

$q$". Kita menyebut:

• $p$ sebagai hipotesa (anteseden atau premis)
• $q$ sebagai kesimpulan (konsekuensi)

Implikasi

$p\to q$ bernilai salah jika

$p$ benar dan

$q$ salah, dan bernilai benar untuk kombinasi nilai

$p$ dan

$q$ lainnya.

Tabel 4.x adalah tabel kebenaran dari implikasi

$p\to q$.

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
T	F	T

Terdapat sejumlah cara untuk mengekspresikan implikasi

$p\to q$:

• Jika
  $p$, maka
  $q$.
• Jika
  $p$,
  $q$.
• $p$ mengakibatkan
  $q$ (
  $p$ implies
  $q$)
• $q$ jika
  $p$
• $p$ hanya jika
  $q$
• $p$ syarat cukup untuk
  $q$
• $q$ syarat perlu utnuk
  $p$
• $q$ bilamana
  $p$

// ubah atas ke tabel.

Contoh 4.2.x
Misal

$p$ adalah proposisi "Beni belajar matematika diskrit" dan

$q$ adalah proposisi "Beni akan mendapatkan pekerjaan bagus." Ekspresikan implikasi

$p\to q$.

Solusi:
Implikasi

$p\to q$ dapat diekspresikan dengan:
"Jika Beni belajar matematika diskrit, maka dia akan mendapatkan pekerjaan bagus"

Perhatikan bahwa dalam implikasi yang dipentingkan adalah nilai kebenaran dari hipotesa dan kesimpulan, bukan hubungan sebab dan akibat diantara keduanya. Sebagai contoh, dua implikasi di bawah adalah valid meskipun secara bahasa tidak mempunyai makna:

• "Jika
  $1+1=2$, maka Bangkok ibukota Thailand"
• "Jika
  $n$ bilangan bulat maka hari ini hujan"

4.2.5. Bikondisional

4.3. Proposisi Majemuk Kompleks

Proposisi yang kita bahas sebelumnya adalah proposisi majemuk yang hanya melibatkan dua variabel proposisi dan sebuah operator logika. Kita dapat menggunakan operator-operator yang kita bahas pada bagian sebelumnya untuk membentuk proposisi mejemuk yang lebih kompleks dengan berapapun variabel proposisi.

// penggunaan tanda kurung untuk m

Kita dapat menggunakan tabel kebenaran untuk menentukan nilai-nilai kebenaran dari porosisi majemuk yang kompleks seperti yang dicontohkan pada Contoh x.x.x berikut. Kita menggunkan kolom terpisah untuk menjadi nilai kebenaran dari setiap proposisi majemuk yang membentuk proposisi mejemuk kompleks ini.

Contoh x.x.x
Buat tabel kebenaran dari proposisi majemuk

$(p\vee q)\to (p\wedge q)$.

Solusi:

Karena proposisi ini menggunakan dua variabel proposisi

$p$ dan

$q$ maka terdapat empat baris dalam tabel kebenaran, masing-masing untuk pasangan nilai kebenaran TT, TF, FT, dan FF. Dua kolom pertama digunakan untuk nilai-nilai kebenaran untuk

$p$ dan

$q$. Pada kolom ketiga kita mencari nilai kebenaran untuk

$\mathrm{\neg }q$ yang diperlukan untuk mencari nilai kebenaran

$p\vee \mathrm{\neg }q$ yang ditampilkan pada kolom keempat. Kolom kelima memberikan nilai kebebaran dari

$p\wedge q$. Terakhir, nilai kebenaran dari

$(p\vee q)\to (p\wedge q)$ didapatkan pada kolom terakhir.

4.3.1. Keutamaan Operator Logika

Dalam menuliskan proposisi majemuk kita menggunakan tanda kurung untuk menyatakan bahwa proposisi majemuk yang berada di dalam kurung dicari nilainya terlebih dahulu. Sebgai contoh

4.4. Ekuivalensi Proposisional

Satu langkah penting yang digunakan dalam sebuah argumen matematika adalah penggantian dari sebuah statement ke statement lain dengan nilai kebenaran yang sama. Karena ini, metode-metode yang menghasilkan proposisi lain dengan nilai kebenaran yang sama dengan proposisi yang diberikan sering digunakan untuk membangun argumen-argumen matematika.

4.4.1. Tautologi, Kontradiksi, dan Kontigensi

Proposisi majemuk diklasifikasikan berdasarkan kemungkinan nilai kebenarannya menjadi tiga: tautologi, kontradiksi, dan kontigensi.

DEFINISI 4.x
Berikut adalah definisi tautologi, kontrakdiksi, dan kontigensi:

• Proposisi majemuk yang selalu bernilai true (benar), apapun nilai-nilai kebenaran dari variabel proposi yang membentuk disebut dengan tautologi.
• Proposisi majemuk yang selalu bernilai false (salah) disebut dengan kontradiksi.
• Proposisi majemuk yang tidak tautologi maupun kontradiksi disebut dengan kontigensi.

Contoh 4.4.x.
Pandang proposisi majemuk

$p\vee \mathrm{\neg }p$ dan

$p\wedge \mathrm{\neg }p$, maka:

• $p\vee \mathrm{\neg }p$ adalah tautologi. Ini dapat dilihat pada tabel kebenaran berikut:
  

• $p\wedge \mathrm{\neg }p$ adalah kontrakdiksi. Ini dapat dilihat pada tabel kebenaran berikut:
  

4.4.2. Logika Ekuivalen

DEFINISI 4.x
Proposisi majemuk

$p$ dan

$q$ disebut ekuivalen secara logika jika

$p\leftrightarrow q$ adalah suatu tautologi.
Notasi

$p\equiv q$ menyatakan bahwa

$p$ dan

$q$ ekuivalen secara logika.

Catatan:
Simbol

$\equiv$ bukanlah operator logika, dan

$p\equiv q$ bukanlah proposisi majemuk, melainkan simbol tersebut adalah pernyataan bahwa

$p$ dan

$q$ adalah tautologi.

Salah satu cara untuk menunjukkan dua proposisi adalah ekuivalen adalah dengan menggunakan tabel kebenaran.

4.4.3. Hukum-hukum Ekuivalensi Logika

Tabel x di bawah mendaftar ekuivalensi-ekuivalensi logika yang penting. Dalam ekuivalensi-ekuivalensi ini, T menandakan proposisi majemuk yang selalu benar dan F menandakan proposisi majemuk yang selalu salah.

Contoh 4.3.x
Tunjukkan bahwa

$\mathrm{\neg }(p\to q)$ dan

$p\wedge \mathrm{\neg }q$ adalah ekuivalensi logika!

Solusi:
$$
\neg(p \land q) \equiv \neg(\neg p \lor q) \qquad \text{(dengan Hukum De Morgan)} \
&

$$

Selain hukum-hukum di atas, tabel x di bawah mendaftar ekuivalnsi untuk proposisi majemuk yang melibatkan pernyataan kondisional dan tabel x di bawah mendaftar ekuivalnsi untuk proposisi majemuk yang melibatkan pernyataan bikondisional.

4.4.x. Pengaplikasian Hukum De Morgan

Dua ekuivalensi logika dari hukum De Morgan sangatlah penting. Hukum ini menjelaskan bagaimana menegasi konjungsi dan bagaimana menegasi disjungsi. Ekuivalensi

$\mathrm{\neg }(p\vee q)\equiv \mathrm{\neg }p\wedge \mathrm{\neg }q$

Hukum De Morgan dapat diperluas menjadi:

$\mathrm{\neg }(p_1\vee p_2\vee ...\vee p_n)\equiv (\mathrm{\neg }{p}_1\wedge \mathrm{\neg }{p}_2\wedge ...\wedge \mathrm{\neg }{p}_3)$

dan

$\mathrm{\neg }(p_1\vee p_2\vee ...\vee p_n)\equiv (\mathrm{\neg }{p}_1\wedge \mathrm{\neg }{p}_2\wedge ...\wedge \mathrm{\neg }{p}_3)$

4.5. Kaidah Inferensi (Rules of Inference)

Pembuktian dalam matematika adalah pengkonstruksian argumen valid yang membentuk kebenaran dari pernyataan matematika. Argumen berarti rangkaian pernyataan-pernyataan yang berakhir dengan sebuah kesimpulan. Valid berarti bahwa kesimpulan atau pernyataan akhir dari argumen mengikuti kebenaran dari pernyataan-pernyataan yang mendahuluinya, atau premise.

Berikut adalah contoh sebuah argumen:

Misalkan

$p$ adalah pernyataan "Jika Anda memiliki password" dan

$q$ adalah pernyataan "Anda dapat login ke internet".