Bab 4. Logika (Backup 2)

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

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

Contoh 4.1.1
Semua kalimat di bawah ini adalah proposisi.

1. DKI Jakarta adalah ibukota dari Indonesia.
2. Tokyo adalah ibukota Korea Selatan.
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. Sebagai contoh,

$p$ : Jakarta adalah ibukota Indonesia.

$q$ : 3 + 5 = 8.

$r$ : 8 adalah bilangan genap.

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.

//
Bagian bidang logika yang mempelajari proposisi dinamakan kalkulus proposisi.
//

4.2. Mengkombinasikan Proposisi

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. Sedangkan proposisi yang bukan merupakan kombinasi proposisi lain disebut dengan proposisi atomik.

Operator Logika Dasar

Operator logika dasar yang dapat digunakan untuk mengkombinasikan proposisi antara lain operator negasi, operator konjungsi, dan operator disjungsi.

A. Negasi

DEFINISI 4.2
Misal

$p$ adalah proposisi. Negasi dari

$p$ dinotasikan dengan

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

$p$.

Catatan: Beberapa buku menggunakan simbol

$\sim$ untuk menyatakan negasi.

Cara yang praktis untuk menampilkan hubungan nilai kebenaran antara proposisi majemuk dengan nilai kebenaran dari proposisi atomiknya adalah melalui tabel kebenaran. Tabel 4.1 berikut adalah tabel kebenaran untuk operasi negasi

$\mathrm{\neg }p$.

Tabel 4.1. Tabel Kebenaran Operasi Negasi.

Tabel kebenaran dari operasi negasi di atas mempunyai baris untuk setiap dua kemungkinan nilai kebenaran dari proposisi

$p$. Baris pertama menunjukkan jika nilai kebenaran dari

$p$ adalah benar ( T ), maka nilai kebenaran dari

$\mathrm{\neg }p$ adalah salah ( F ). Baris kedua menunjukkan jika nilai kebenaran dari

$p$ adalah salah ( F ), maka nilai kebenaran dari

$\mathrm{\neg }p$ adalah benar ( T ).

Contoh 4.2.1
Cari negasi dari proposisi

$$ "Hari ini hujan."

Solusi:
Negasi dari "Hari ini hujan" adalah

$$"Tidak benar hari ini hujan."

atau lebih sederhananya dapat diekspresikan dengan

$$"Hari ini tidak hujan."

B. Konjungsi

DEFINISI 4.3
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.2 di bawah adalah tabel kebenaran (truth table) untuk

$p\wedge q$.

Tabel 4.2. Tabel Kebenaran Operasi Konjungsi.

Tabel kebenaran dari operasi konjungsi di atas mempunyai baris untuk setiap empat kemungkinan kombinasi dari nilai kebenaran dari

$p$ dan

$q$. Keempat baris ini terdiri dari kombinasi TT, TF, FT, dan FF, dimana nilai kebenaran pertama dari kombinasi tersebut adalah nilai kebenaran dari

$p$ dan nilai kebenaran kedua dari kombinasi tersebut adalah nilai kebenaran dari

$q$.

Contoh 4.2.2
Diketahui proposisi-proposisi berikut:

$p$ : "Hari ini hujan."

$q$ : "Murid-murid diliburkan dari sekolah."

Maka, konjungsi dari

$p$ dan

$q$ adalah

$p\wedge q$ : "Hari ini hujan dan murid-murid diliburkan dari sekolah."

Untuk konjungsi ini bernilai benar, kedua proposisi harus bernilai benar. Konjungsi ini bernilai salah ketika satu atau kedua proposisi bernilai salah.

Perlu dicatat bahwa dalam bahasa sehari-hari, kata "tapi" terkadang digunakan menggantikan kata "dan". Sebagai contoh, pernyataan "Hari ini hujan tapi matahari bersinar" adalah cara lain untuk mengatakan "Hari ini hujan dan matahari bersinar. "

C. Disjungsi

DEFINISI 4.4
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.3 di bawah adalah tabel kebenaran untuk operasi disjungsi

$p\vee q$.

Tabel 4.3. Tabel Kebenaran Operasi Disjungsi.

Contoh 4.2.3
Diketahui proposisi-proposisi berikut:

$p$ : "Hari ini hujan."

$q$ : "Murid-murid diliburkan dari sekolah."

Maka, disjungsi dari

$p$ dan

$q$ adalah

$p\vee q$ : "Hari ini hujan atau atau murid-murid diliburkan dari sekolah."

Disjungsi ini bernilai benar jika salah satu atau kedua proposisi bernilai benar yaitu ketika "Hari ini hujan" adalah benar, ketika "Murid-murid diliburkan dari sekolah" adalah benar, dan ketika keduanya benar. Disjungi ini bernilai salah jika kedua proposisi bernilai salah.

Disjungsi Eksklusif (Exclusive OR)

Kata "atau" dalam operasi logika (begitu juga dalam bahasa sehari-hari) dapat digunakan dalam dua cara. Cara pertama kata "atau" digunakan secara inklusif yaitu pernyataan "

$p$ atau

$q$" berarti
"

$p$ atau

$q$ atau keduanya". Operasi disjungsi yang kita bahas sebelumnya adalah penggunaan kata "atau" secara inklusif. Pada penggunaan "atau" inklusif ini proposisi majemuk bernilai benar jika salah satu atau kedua proposisi atomik pembentuknya bernilai benar. Sebagai contoh, pernyataan

$$"Programmer yang dibutuhkan adalah yang menguasai Bahasa Python atau Bahasa Java"

diartikan programmer yang dibutuhkan adalah yang menguasai Bahasa Python dan Bahasa Java dan juga yang hanya menguasai salah satu dari kedua bahasa tersebut.

Cara kedua kata "atau" digunakan secara eksklusif. Ketika "atau" digunakan secara eksklusif, pernyataan "

$p$ atau

$q$ berarti "

$p$ atau

$q$ tetapi tidak keduanya". Pernyataan berikut adalah contoh penggunaan kata "atau" secara eksklusif

$$"Hadiah utama dari pertandingan ini adalah sebuah mobil atau uang tunai."

Pernyataan di atas berarti hadiah utama adalah salah satu dari mobil atau uang tunai tetapi tidak keduanya.

Operator logika yang digunakan untuk menyatakan "atau" secara eksklusif dinamakan operator disjungsi eksklusif (exclusive or).

DEFINISI 4.5
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.4 adalah tabel kebenaran untuk operasi disjungsi eksklusif

$p\oplus q$.

Tabel 4.4. Tabel Kebenaran Operasi Disjungsi Eksklusif.

Perhatikan pada Tabel 4.4, operasi disjungsi ekslusif bernilai benar hanya ketika salah satu proposisi bernilai benar.

Proposisi Majemuk

Proposisi yang kita bahas sebelumnya adalah proposisi majemuk yang hanya melibatkan paling banyak 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.

Saat menuliskan proposisi majemuk dengan lebih dari satu operator, umumnya kita menggunakan tanda kurung untuk menyatakan urutan penerapan operator logika. Sebagai contoh, kita dapat membentuk proposisi majemuk

$(p\wedge q)\vee (\mathrm{\neg }q\wedge r)$ yang merupakan disjungsi dari proposisi

$p\wedge q$ dan proposisi

$\mathrm{\neg }q\wedge r$.

Tabel kebenaran juga dapat digunakan untuk menentukan nilai-nilai kebenaran dari proposisi majemuk dengan lebih dari satu operasi seperti

$(p\wedge q)\vee (\mathrm{\neg }q\wedge r)$, dimana diperlihatkan pada Contoh x.x.x berikut.

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

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

Solusi:
Untuk membentuk tabel kebenaran dari proposisi majemuk yang melibatkan tiga proposisi atomik kita membutuhkan 2 x 2 x 2 = 8 baris. Masing

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.

Kita menggunakan kolom terpisah untuk mendapatkan nilai kebenaran dari setiap proposisi majemuk yang membentuk proposisi mejemuk kompleks ini.

Keutamaan Operator Logika

Saat menuliskan proposisi majemuk dengan lebih dari satu operator, umumnya kita menggunakan tanda kurung untuk menyatakan urutan penerapan operator logika. Sebagai contoh,

$(p\vee q)\wedge (\mathrm{\neg }r)$ adalah konjungsi dari

$p\vee q$ dan

$\mathrm{\neg }r$. Jika kita tidak menuliskan tanda kurung, urutan operasi-operasi mengacu pada aturan keutamaan operator. Misalkan,

$\mathrm{\neg }p\wedge q$ berarti konjungsi dari

$\mathrm{\neg }p$ dan

$q$, bukan negasi dari

$p\wedge q$. Ini karena operator negasi mempunyai keutamaan tertinggi dibandingkan operator konjungsi. Tabel 4.7 menunjukkan keutamaan operator logika.

Tabel 4.7. Tabel Keutamaan Operator Logika.

Hal yang perlu diingat pada keutamaan operator di atas adalah operator negasi adalah operator yang paling diutamakan. Kita akan tetap menggunakan tanda kurung pada proposisi-proposisi yang melibatkan operator-operator selain negasi.

Menggunakan Tabel Kebenaran untuk Proposisi Majemuk

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

4.2.1. Tautologi, Kontradiksi, dan Kontigensi

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

DEFINISI 4.9
Berikut adalah definisi tautologi, kontrakdiksi, dan kontigensi:

• Proposisi majemuk yang selalu bernilai benar (true), apapun nilai-nilai kebenaran dari variabel proposi yang membentuk disebut dengan tautologi.
• Proposisi majemuk yang selalu bernilai salah (false) 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.2. Ekuivalensi Secara Logika

Satu langkah penting yang digunakan dalam sebuah argumen matematika adalah penggantian dari sebuah proposisi ke proposisi lain dengan nilai kebenaran yang sama. Proposisi-proposisi yang mempunyai nilai kebenaran yang sama untuk semua kemungkinan nilai-nilai kebenaran proposisi atomiknya disebut sebagai proposisi yang ekuivalen secara logika.

Ekuivalen Secara Logika

Dua proposisi majemuk yang mempunyai nilai kebenaran yang sama untuk semua kemungkinan nilai-nilai kebenaran proposisi atomiknya disebut ekuivalen secara logika.

DEFINISI 4.x
Dua proposisi majemuk

$p$ dan

$q$ disebut ekuivalen secara logika jika dan hanya jika kedua proposisi tersebut mempunyai nilai kebenaran yang identik untuk setiap kemungkinan nilai kebenaran dari proposisi atomiknya.
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 sebuah pernyataan bahwa

$p$ dan

$q$ adalah ekuivalen secara logika.

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

Contoh x.x.x
Buktikan bahwa proposisi

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

$p\to q$ adalah ekuivalen secara logika.

Solusi:
Tabel kebenaran dari proposisi

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

$p\to q$

Dari tabel di atas dapat dilihat bahwa untuk setiap kombinasi nilai

$p$ dan

$q$, proposisi

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

$p\to q$ mempunyai nilai kebenaran yang sama.

Contoh x.x.x
Tunjukkan bahwa

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

$\mathrm{\neg }p\vee \mathrm{\neg }q$ adalah ekuivalen secara logika.

Solusi:
Tabel kebenaran dari kedua proposisi majemuk ini adalah sebagai berikut:

Karena nilai kebenaran dari proposisi majemuk

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

$\mathrm{\neg }p\vee \mathrm{\neg }q$ sama untuk setiap kemungkinan nilai kebenaran

$p$ dan

$q$, maka kedua proposisi majemuk tersebut adalah ekuivalen secara logika atau

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

Contoh x.x.x
Tunjukkan bahwa

$p\to q$ ekuivalen secara logika dengan

$\mathrm{\neg }p\vee q$.

Solusi:
Tabel berikut adalah tabel kebenaran untuk proposisi

$p\to q$ dan

$\mathrm{\neg }p\vee q$.

Dapat dilihat pada tabel di atas

$p\to q$ dan

$\mathrm{\neg }p\vee q$ mempunyai nilai kebenaran yang identik untuk setiap kemungkinan nilai kebenaran

$p$ dan

$q$. Ini berarti

$p\to q\equiv \mathrm{\neg }p\vee q$.

Hukum-hukum Ekuivalensi Logika

Menggunakan tabel kebenaran untuk membuktikan bahwa dua proposisi majemuk adalah ekuivalen secara logika dapat menjadi langkah yang melelahkan, terutama ketika proposisi-proposisi majemuk tersebut menggunakan lebih dari dua variabel proposisi. Seperti yang telah kita lihat pada contoh sebelumnya,…

Misalkan proposisi majemuk yang melibatkan tiga variabel proposisi

$p$,

$q$, dan

$r$, jika kita ingin menggunakan tabel kebenaran untuk membuktikan ekuivalensi logika maka kita akan membutuhkan delapan kombinasi nilai kebenaran dari

$p$,

$q$, dan

$r$. Ini akan menjadi cara yang melelahkan. Tabel kebenaran berikut adalah tabel kebenaran yang dibutuhkan untuk membuktikan bahwa

$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$.

Cara lain untuk membuktikan ekuivalensi secara logika dari dua proposisi majemuk adalah dengan aljabar proposisi. Dalam pembuktian dengan aljabar proposisi, kita menggunakan 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.

Tabel 4.x. Tabel Hukum-hukum Ekuivalensi Logika.

Contoh 4.3.x
Buktikan bahwa

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

Solusi:

$$\begin{array}{rl}p\vee (q\wedge r)& \equiv \end{array}$$

Contoh 4.3.x
Buktikan bahwa

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

Solusi:

$$\begin{array}{lll}p\vee \mathrm{\neg }(p\vee q)& \equiv p\vee (\mathrm{\neg }p\wedge \mathrm{\neg }q)& \text{(dengan hukum De Morgan)}\\ & \equiv (p\vee \mathrm{\neg }q)\wedge (p\vee \mathrm{\neg }q)& \text{(dengan hukum distributif)}\\ & \equiv \mathbf{\text{T}}\wedge (p\vee \mathrm{\neg }q)& \text{(dengan hukum negasi)}\\ & \equiv p\vee \mathrm{\neg }q& \text{(dengan hukum identitas)}\end{array}$$

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.

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)} \
&

$$

4.3. Implikasi (Kondisional)

Selain dihubungkan dengan operator-operator logika yang telah dibahas sebelumnya, dua proposisi dapat juga dihubungkan dengan bentuk "jika

$p$, maka

$q$", seperti pada contoh-contoh berikut:

• Jika saya lapar, maka saya akan makan.
• Jika Anda menang, maka Anda mendapatkan hadiah.
• Jika 4686 habis dibagi 6, maka 4686 habis dibagi 3.

Pernyataan berbentuk "jika

$p$, maka

$q$" ini dinamakan dengan proposisi kondisional (proposisi bersyarat) atau implikasi.

DEFINISI 4.6
Misal

$p$ dan

$q$ adalah proposisi. Implikasi atau proposisi kondisional

$p\to q$ adalah proposisi yang dibaca "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.5 adalah tabel kebenaran dari implikasi

$p\to q$.

Tabel 4.5. Tabel Kebenaran Implikasi.

Perhatikan pada tabel kebenaran di atas, pernyataan

$p\to q$ bernilai benar ketika

$p$ dan

$q$ keduanya bernilai benar dan ketika

$p$ bernilai salah (apapun nilai kebenaran dari

$q$).

Salah satu cara untuk memahami nilai kebenaran dari implikasi adalah dengan memandangnya sebagai sebuah janji atau kontrak. Sebagai contoh, misalkan dosen Anda memberikan pernyataan seperti berikut:

$$"Jika Anda mendapatkan nilai 100 pada ujian akhir, maka Anda mendapatkan nilai A."

Dalam keadaan apa Anda dapat mengatakan dosen Anda memberikan pernyataan yang benar atau tidak benar? Tentu saja jika Anda mendapatkan nilai 100 pada ujian akhir, dan pada akhirnya Anda mendapatkan nilai A, maka pernyataan dosen Anda adalah benar. Anda dapat mengatakan pernyataan dosen Anda tidak benar ketika Anda mendapatkan nilai 100 pada ujian akhir, tetapi Anda tidak mendapatkan nilai A. Bagaimana jika Anda tidak mendapatkan nilai 100 pada ujian akhir? Pada keadaan ini Anda bisa mendapatkan nilai A atau bisa tidak mendapatkan nilai A. Anda tidak bisa mengatakan pernyataan dosen Anda salah, karena pernyataan dosen Anda tidak mengatakan apa yang akan terjadi jika Anda tidak mendapatkan nilai 100.

Terdapat sejumlah cara untuk mengekspresikan implikasi

$p\to q$ dalam bahasa antara lain:

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

Contoh 4.2.x //ganti contoh
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"

Konverse, Kontrapositif, dan Inverse dari Implikasi

Kita dapat membentuk proposisi bersyarat baru dari

$p\to q$. Terdapat tiga proposisi yang terkait implikasi yang sering digunakan sehingga ketiganya diberikan nama.

DEFINISI 4.7
Diberikan prososisi kondisional

$p\to q$.

1. Konverse dari
   $p\to q$ adalah
   $q\to p$.
2. Kontrapositif dari
   $p\to q$ adalah
   $\mathrm{\neg }q\to \mathrm{\neg }p$.
3. Inverse dari
   $p\to q$ adalah
   $\mathrm{\neg }p\to \mathrm{\neg }q$.

Contoh x.x.x
Tentukan konvers, kontrapositif, dan invers dari pernyataan:

$$ "Jika Budi mempunyai mobil, maka ia orang kaya."

Solusi:
Misal

$p$ : "Budi mempunyai mobil." dan

$q$ : "Budi orang kaya." Maka,

• Konvers dari pernyataan (
  $q\to p$ ): "Jika Budi orang kaya, maka ia mempunyai mobil."
• Kontrapositif dari pernyataan (
  $\mathrm{\neg }q\to \mathrm{\neg }p$ ): "Jika Budi bukan orang kaya, maka ia tidak mempunyai mobil."
• Inverse dari pernyataan (
  $\mathrm{\neg }p\to \mathrm{\neg }q$): "Jika Budi tidak mempunyai mobil, maka ia bukan orang kaya."

Bikondisional/Bi-implikasi

Bentuk kombinasi dua proposisi lainnya yang tak kalah penting adalah bentuk "

$p$ jika dan hanya jika

$q$". Bentuk ini disebut proposisi bikondisional.

DEFINISI 4.8
Misal

$p$ dan

$q$ adalah proposisi. Proposisi bikondisional

$p\leftrightarrow q$ adalah proposisi yang dibaca "

$p$ jika dan hanya jika

$q$". Proposisi bikondisional

$p\leftrightarrow q$ adalah benar ketika

$p$ dan

$q$ mempunyai nilai kebenaran yang sama, dan bernilai salah selain itu.

Tabel 4.6 adalah tabel kebenaran dari bikondisional

$p\leftrightarrow q$.

Tabel 4.6. Tabel Kebenaran Bikondisional/Bi-implikasi.

Perhatikan bahwa pernyataan

$p\leftrightarrow q$ bernilai benar ketika

$p$ dan

$q$ keduanya bernilai benar atau ketika keduanya bernilai salah.

Terdapat sejumlah cara untuk mengekspresikan bikondisional

$p\leftrightarrow q$, antara lain:

• $p$ jika dan hanya jika
  $q$.
• $p$ adalah syarat perlu dan cukup untuk
  $q$.
• Jika
  $p$ maka
  $q$, dan sebaliknya.

Contoh x.x.x
Proposisi-proposisi majemuk berikut adalah bi-implikasi:

• $1+1=2$ jika dan hanya jika
  $2+2=4$.
• Syarat cukup dan syarat perlu agar hari ini hujan adalah kelembaban udara tinggi.
• Jika Anda orang kaya, maka Anda mempunyai banyak uang, dan sebaliknya.

Contoh x.x.x
Misal

$p$ adalah pernyataan "Anda dapat naik ke kereta." dan

$p$ adalah pernyataan "Anda membeli tiket.". Maka

$p\leftrightarrow q$ adalah pernyataan:

$$ "Anda dapat naik ke kereta jika dan hanya jika Anda membeli tiket."

Pernyataan ini benar jika

$p$ dan

$q$ keduanya benar atau keduanya salah.

4.4. Inferensi (Penarikan Kesimpulan)

//Argumen adalah rangkaian pernyataan-pernyataan yang ditujukan untuk menunjukkan kebenaran dari sebuah p//

Pembuktian dalam matematika adalah pengkonstruksian argumen valid yang membentuk kebenaran dari pernyataan matematika. Argumen dalam matematika dan logika berbeda dengan arti argumen dalam bahasa sehari-hari yang berarti bantahan. Argumen dalam matematika berarti rangkaian pernyataan-pernyataan (proposisi-proposisi) yang disebut premis dan diakhiri dengan sebuah pernyataan yang disebut kesimpulan. Sebuah argumen disebut valid apabila kesimpulan atau pernyataan akhir dari argumen mengikuti kebenaran premis-premisnya.

DEFINISI x.x
Argumen adalah rangkaian proposisi-proposisi yang disebut sebagai premis dan diikuti oleh sebuah proposisi yang disebut sebagai kesimpulan.

DEFINISI x.x
Sebuah argumen disebut valid jika dan hanya jika dalam semua kasus dimana semua premis dari argumen tersebut bernilai benar, kesimpulan dari argumen bernilai benar.

Dari definisi ke-valid-an argumen (DEFINISI x.x), kita dapat melihat bahwa bentuk argumen dengan premis

$p1,p2,...,p_n$ dan kesimpulan

$q$ adalah valid, jika

$(p_1\wedge p_2\wedge ...\wedge p_n)\to q$ adalah sebuah tautologi.

Berikut adalah contoh sebuah argumen:

$$ "Jika Anda memiliki password, maka Anda dapat login ke internet."

$$ "Anda memiliki password."

$$ Jadi,

$$ "Anda dapat login ke internet."

Kita ingin menentukan apakah argumen di atas adalah valid. Ini berarti, kita ingin menentukan apakah kesimpulan "Anda dapat login ke internet" bernilai benar ketika premis "Jika Anda memiliki password, maka Anda dapat login ke internet." dan premis "Anda memiliki password." keduanya bernilai benar.

Sebelum kita membahas ke-valid-an dari argumen di atas, kita akan melihat bentuk argumen tersebut terlebih dahulu. Misalkan

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

$q$ adalah pernyataan "Anda dapat login ke internet.". Maka, argumen di atas mempunyai bentuk:

$$\begin{array}{rl}& p\to q\\ & p\\ \therefore & q\end{array}$$

atau jika diuraikan:

$$\begin{array}{llrl}\text{Premis 1: }& \text{"Jika Anda memiliki password, maka Anda dapat login ke internet."}& & p\to q\\ \text{Premis 2: }& \text{"Anda memiliki password."}& & p\\ \text{Kesimpulan: }& \mathbf{\text{Jadi, }}\text{"Anda dapat login ke internet."}& \therefore & q\end{array}$$

Simbol

$\therefore$ adalah simbol yang menyatakan "Jadi". Kevalidan dari argumen di atas ditunjukkan oleh Contoh x.x.x.

Contoh x.x.x
Tunjukkan bahwa argumen berbentuk:

$$\begin{array}{rl}& p\to q\\ & p\\ \therefore & q\end{array}$$

Solusi:
Kita dapat membuat tabel kebenaran yang berisi semua baris dari argumen:

Tunjukkan argumen berikut:

$$\begin{array}{rl}& p\to q\\ & \mathrm{\neg }p\to q\\ \therefore & q\end{array}$$

adalah valid.

Solusi:

4.5.1. Kaidah-kaidah Inferensi

Kita dapat selalu menggunakan tabel kebenaran untuk menunjukkan bahwa sebuah bentuk argumen adalah valid. Kita melakukan ini dengan menunjukkan bahwa kapanpun premis-premis bernilai benar, kesimpulan juga harus bernilai benar. Namun, cara seperti ini dapat menjadi pendekatan yang melelahkan. Sebagai contoh, ketika sebuah bentuk argumen melibatkan 10 variabel proposional berbeda, untuk menggunakan tabel kebenaran untuk menunjukkan bahwa bentuk argumen tersebut valid membutuhkan

$2^{10}$ =

$1024$ baris. Untungnya terdapat cara lain selain dengan tabel kebenaran. Kita dapat menggunakan kaidah-kaidah inferensi sebagai balok bangun untuk mengkonstruksi bentuk argumen valid yang kompleks.

A. Modus Ponen

Modus Ponen adalah bahasa Latin yang berarti "metode penegasan". Dinamakan seperti itu karena kesimpulan dari aturan ini adalah penegasan. Modus ponen mempunyai bentuk argumen:

$\begin{array}{rl}& p\to q\\ & p\\ \therefore & q\end{array}$

Dasar dari aturan modus ponen adalah tautologi

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

Contoh x.x.x
Misalkan pernyataan bersyarat "Jika hari ini hujan, maka saya memerlukan payung" dan pernyataan "Hari ini hujan." adalah premis-premis dari sebuah argumen. Apa kesimpulan dari argumen tersebut?

Solusi:
Anggap:

• $p$ adalah proposisi "Hari ini hujan"
• $q$ adalah proposisi "Saya memerlukan payung"

Maka, dengan modus ponen kita mempunyai bentuk argumen:

$$\begin{array}{rl}& p\to q\\ & p\\ \therefore & q\end{array}$$

Argumen ini mempunyai kesimpulan pernyataan

$q$ yaitu "Saya memerlukan payung".

Secara lengkap bentuk argumen ini adalah

$$\begin{array}{ll}\text{Premis 1: }& \text{"Jika hari ini hujan, maka saya memerlukan payung."}\\ \text{Premis 2: }& \text{"Hari ini hujan."}\\ \therefore \text{Kesimpulan: }& \mathbf{\text{Jadi, }}\text{"Saya memerlukan payung."}\end{array}$$

B. Modus Tollens

Modus Tollens adalah bahasa Latin yang berarti "metode penyangkalan". Dinamakan seperti itu karena kesimpulan dari aturan ini adalah penyangkalan. Modus tollens mempunyai bentuk argumen:

$\begin{array}{rl}& p\to q\\ & \sim q\\ \therefore & \sim p\end{array}$

Dasar dari aturan modus tollens adalah tautologi

$((p\to q)\wedge \sim q)\to \sim p$

Contoh x.x.x

C. Transitivitas (Silogisme Hipotesis)

Transitivitas atau dikenal juga sebagai silogisme hipotesis mempunyai bentuk argumen:

$\begin{array}{rl}& p\to q\\ & q\to r\\ \therefore & p\to r\end{array}$

Dasar dari aturan silogisme hipotesis adalah tautologi

$((p\to q)\wedge (q\to r))\to (p\to r)$

Contoh x.x.x
Misalkan:

$p$ : "

$n$ habis dibagi

$18$"

$q$ : "

$n$ habis dibagi

$9$"

$r$ : "Jumlah digit dari

$n$ habis dibagi

$9$."

Maka dengan bentuk transitivitas kita dapat membangun argumen berikut:

$$\begin{array}{rl}& \text{"Jika }n\text{ habis dibagi }18\text{, maka }n\text{ habis dibagi }9\text{."}\\ & \text{"Jika }n\text{ habis dibagi }9\text{, maka jumlah digit dari }n\text{ habis dibagi }9\text{."}\\ \therefore & \mathbf{\text{Jadi, }}\text{"Jika }n\text{ habis dibagi }18\text{, maka jumlah digit dari }n\text{ habis dibagi }9\text{."}\end{array}$$

Contoh x.x.x
Aturan inferensi mana yang menjadi basis dari argumen berikut: "Hari ini hujan. Jadi, hari ini hujan atau berawan." ?

Solusi:
Anggap:

• $p$ adalah proposisi "Hari ini hujan"
• $q$ adalah proposisi "Hari ini berawan"

Maka, argumen ini mempunyai bentuk:

$$\begin{array}{rl}& p\\ \therefore & p\vee q\end{array}$$

Argumen ini menggunakan aturan penambahan.

D. Eliminasi (Silogisme Disjungtif)

Eliminasi atau dikenal juga sebagai silogisme disjungtif mempunyai bentuk argumen:

$\begin{array}{rl}& p\vee q\\ & \sim p\\ \therefore & q\end{array}$

yang didasarkan oleh tautologi

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

Bentuk lain dari eliminasi:

$\begin{array}{rl}& p\vee q\\ & \sim q\\ \therefore & p\end{array}$

yang didasarkan oleh tautologi

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

Contoh x.x.x
Misalkan terdapat premis-premis berikut:

Premis 1: "Suhu hari ini lebih dari 38 derajat atau polusi udara sangat tinggi."
Premis 2: "Suhu hari ini tidak lebih dari 38 derajat."

Kesimpulan apa yang dapat digunakan umum membentuk sebuah argumen yang valid?

Solusi:

Misalkan:

$p$ : "Suhu hari ini lebih dari 38 derajat."

$q$ : "Polusi udara hari ini sangat tinggi"

Dengan aturan eliminasi kita dapat membentuk argumen:

$$\begin{array}{rl}& \text{"Suhu hari ini lebih dari 38 derajat atau polusi udara sangat tinggi."}\\ & \text{"Suhu hari ini tidak lebih dari 38 derajat."}\\ \therefore & \mathbf{\text{Jadi, }}\text{"Polusi udara hari ini sangat tinggi."}\end{array}$$

E. Generalisasi (Penambahan)

Aturan generalisasi atau penambahan mempunyai bentuk argumen berikut:

$\begin{array}{rl}& p\\ \therefore & p\vee q\end{array}$

yang berdasarkan tautologi

$p\to (p\vee q)$ dan bentuk argumen berikut:

$\begin{array}{rl}& q\\ \therefore & p\vee q\end{array}$

yang berdasarkan tautologi

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

Contoh x.x.x
Argumen: "Hari ini hujan. Jadi, hari ini hujan atau berawan." adalah contoh dari penerapan aturan generalisasi.
Ini dapat ditunjukkan dengan memisalkan:

$p$ : "Hari ini hujan."

$q$ : "Hari ini berawan."

Maka berdasarkan aturan generalisasi:

$$\begin{array}{llrl}\text{Premis: }& \text{"Hari ini hujan."}& & p\\ \text{Kesimpulan: }& \mathbf{\text{Jadi, }}\text{"Hari ini hujan atau berawan"}& \therefore & p\vee q\end{array}$$

F. Spesialisasi (Penyederhanaan)

Aturan spesialisasi atau penyederhanaan mempunyai bentuk argumen:

$\begin{array}{rl}& p\wedge q\\ \therefore & p\end{array}$

yang berdasarkan tautologi

$(p\wedge q)\to p$ dan bentuk argumen berikut:

$\begin{array}{rl}& p\wedge q\\ \therefore & q\end{array}$

yang berdasarkan tautologi

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

Contoh x.x.x
Argumen: "Hari ini hujan dan berawan. Jadi, hari ini hujan." adalah contoh dari penerapan aturan spesialisasi atau penyerdahanaan.
Ini dapat ditunjukkan dengan memisalkan:

$p$ : "Hari ini hujan."

$q$ : "Hari ini berawan."

Maka berdasarkan aturan spesialisasi:

$$\begin{array}{llrl}\text{Premis: }& \text{"Hari ini hujan dan berawan."}& & p\wedge q\\ \text{Kesimpulan: }& \mathbf{\text{Jadi, }}\text{"Hari ini hujan."}& \therefore & p\end{array}$$

G. Konjungsi

Aturan konjungsi mempunyai bentuk argumen:

$\begin{array}{rl}& p\\ & q\\ \therefore & p\wedge q\end{array}$

yang berdasarkan tautologi

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

H. Resolusi

Aturan resolusi mempunyai bentuk argumen:

$\begin{array}{rl}& p\vee q\\ & \sim p\vee r\\ \therefore & q\vee r\end{array}$

yang berdasarkan tautologi

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

Contoh x.x.x
//ganti
Misalkan hipotesa "Budi bermain futsal atau hari ini hujan." dan "Hari ini tidak hujan atau Andi berenang.". Apa kesimpulan yang bisa diambil?

Kita dapat memisalkan:

$p$ : "Hari ini hujan."

$q$ : "Budi bermain futsal."

$r$ : "Andi berenang."

Maka, kesimpulan yang bisa diambil, berdasarkan resolusi adalah

$q\vee r$ : "Budi bermain futsal atau Andi berenang."

Tabel x berikut meringkas kaidah-kaidah inferensi yang umum beserta namanya.

4.4.x Fallacy

Fallacy adalah kesalahan penalaran yang menghasilkan sebuah argumen tidak valid. Tiga fallacy yang umum adalah menggunakan premis ambigu,

Kesalahan Converse

Kesalahan Inverse

/////

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

$(p\vee \mathrm{\neg }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.

//////