Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 1.3 Aturan Logika

Subbagian Pratinjau Bagian

Selidiki!
Holmes selalu mengenakan salah satu dari dua rompi miliknya: satu berbahan wol kasar dan satu berwarna hijau mint. Ia selalu mengenakan rompi hijau atau sepatu merah. Setiap kali mengenakan kemeja ungu dan rompi hijau, ia memilih untuk tidak memakai dasi kupu-kupu. Ia tidak pernah mengenakan rompi hijau kecuali jika ia juga mengenakan kemeja ungu atau sepatu merah. Setiap kali mengenakan sepatu merah, ia juga mengenakan kemeja ungu. Hari ini, Holmes memakai dasi kupu-kupu. Apa lagi yang ia kenakan?
🔗
🔗

Cobalah 1.3.1.

Luangkan beberapa menit untuk memikirkan pertanyaan Selidiki! di atas. Dari enam pernyataan dalam teka-teki tersebut, hanya satu yang atomik. Gunakan pernyataan atomik ini dan satu pernyataan lain untuk menyimpulkan pernyataan baru tentang apa yang mungkin dikenakan (atau tidak dikenakan) Holmes. Jelaskan mengapa menurut Anda pernyataan baru tersebut benar.
🔗
Petunjuk.
Pernyataan atomiknya adalah, “Holmes memakai dasi kupu-kupu.” Hanya satu pernyataan majemuk yang memuat pernyataan ini sebagai salah satu atom-nya.
🔗
🔗
🔗
Logika mempelajari cara pernyataan-pernyataan saling berinteraksi. Lebih tepatnya, kita menelaah bagaimana bentuk logis pernyataan dapat saling berinteraksi. Kajian logika tidak mempersoalkan isi pernyataan atomik ataupun makna predikat. Sebagai contoh, klaim “Jika laba-laba memiliki enam kaki, maka Sam berjalan pincang,” dan “Jika bulan terbuat dari keju, maka cheddar adalah sejenis keju,” identik dari sudut pandang logika. Logika tidak mempersoalkan apakah Sam seekor laba-laba atau apa bahan penyusun bulan menurut ilmu kuliner. Kedua pernyataan memiliki bentuk yang sama: keduanya merupakan implikasi, \(P \imp Q\text{.}\)
🔗
Tentu saja, dalam matematika kita sering kali memang mengetahui hubungan di antara berbagai pernyataan atomik. Sebagai contoh, kita mengetahui hubungan antara sifat genap dan sifat kelipatan 10. Hubungan itu memungkinkan kita membuat klaim seperti, “Jika bilangan yang sedang saya pikirkan merupakan kelipatan 10, maka bilangan itu genap.” Misalkan saya juga memberi tahu Anda bahwa sekarang saya sedang memikirkan suatu bilangan yang tidak genap. Kita dapat menyimpulkan bahwa saya tidak sedang memikirkan kelipatan 10! Yang terpenting, jika kita menerima kebenaran pernyataan-pernyataan tersebut, kita dapat membuat deduksi ini tanpa memikirkan hakikat bilangan. Kemampuan memisahkan isi argumen dari bentuk logisnya dapat terasa sangat membebaskan dan memberi kejernihan yang amat dibutuhkan ketika kita mencoba memahami penalaran yang rumit.
🔗
Tujuan kita dalam bagian ini adalah menetapkan beberapa prosedur untuk menganalisis bagaimana kebenaran atau kesalahan pernyataan saling berinteraksi berdasarkan bentuk logisnya. Kita akan melihat bahwa beberapa pernyataan majemuk pasti benar tanpa bergantung pada benar atau salahnya bagian-bagian atomiknya, sedangkan beberapa pernyataan lain pasti selalu salah. Untuk pernyataan lainnya, dua pernyataan dapat selalu benar atau salah secara bersamaan, atau setiap kali satu pernyataan benar, pernyataan lain juga harus benar.
🔗
Metode utama untuk menetapkan hubungan-hubungan ini adalah tabel kebenaran. Ada prosedur yang sangat jelas untuk menyusun dan menganalisis tabel kebenaran, tetapi untuk argumen rumit yang memuat banyak pernyataan atomik, tabel kebenarannya menjadi sangat besar dan sukar ditangani. Karena itu, kita akan menggunakan tabel kebenaran untuk memahami beberapa ekuivalensi dan deduksi dasar yang dapat diterapkan dalam suatu rangkaian penalaran guna membangun argumen yang lebih besar.
🔗

Lembar Kerja Aktivitas Pratinjau

1.
Perhatikan pernyataan, “Setiap kali Holmes mengenakan kemeja ungu dan rompi hijau, ia memilih untuk tidak memakai dasi kupu-kupu.” Misalkan \(P\) adalah pernyataan “Holmes mengenakan kemeja ungu,” \(G\) adalah pernyataan “Holmes mengenakan rompi hijau,” dan \(B\) adalah pernyataan “Holmes memakai dasi kupu-kupu.” Manakah di antara pilihan berikut yang merupakan terjemahan terbaik pernyataan tersebut ke dalam logika proposisional?
🔗
  • \((P \wedge G) \imp \neg B \)
    🔗
  • \((P \wedge G) \imp B \)
    🔗
  • \((P \vee G) \imp \neg B \)
    🔗
  • \(P \wedge (G \imp B) \)
    🔗
🔗
2.
Perhatikan pernyataan, “Holmes tidak pernah mengenakan rompi hijau kecuali jika ia juga mengenakan kemeja ungu atau sepatu merah.” Dengan \(P\) dan \(G\) seperti pada pertanyaan sebelumnya, serta \(R\) sebagai pernyataan “Holmes mengenakan sepatu merah,” manakah di antara pilihan berikut yang merupakan terjemahan terbaik pernyataan tersebut ke dalam logika proposisional?
🔗
  • \(G \imp (P \vee R) \)
    🔗
  • \(\neg G \imp (P \vee R) \)
    🔗
  • Perhatikan kasus ketika Holmes mengenakan rompi hijau tetapi tidak mengenakan kemeja ungu maupun sepatu merah. Hal itu membuat \(\neg G\) salah dan \(P \vee R\) salah, sehingga implikasinya benar. Namun, dalam situasi ini, pernyataan semula salah.
  • \((P \vee R) \imp G \)
    🔗
  • Perhatikan kasus ketika Holmes tidak mengenakan kemeja ungu maupun sepatu merah, tetapi mengenakan rompi hijau. Hal itu membuat \(P \vee R\) salah dan \(G\) benar, sehingga implikasinya benar. Namun, dalam situasi ini, pernyataan semula salah.
  • \((P \vee R) \imp \neg G \)
    🔗
  • Perhatikan kasus ketika Holmes tidak mengenakan kemeja ungu maupun sepatu merah, tetapi mengenakan rompi hijau. Hal itu membuat \(P \vee R\) salah dan \(\neg G\) salah, sehingga implikasinya benar. Namun, dalam situasi ini, pernyataan semula salah.
🔗
3.
Perhatikan pernyataan “Jika Anda mengambil jurusan matematika, maka Anda akan mendapat pekerjaan bergaji tinggi,” dan pernyataan “Anda tidak mengambil jurusan matematika, atau Anda akan mendapat pekerjaan bergaji tinggi.” Dalam kasus manakah di antara pilihan berikut kedua pernyataan itu benar? Pilih semua yang sesuai.
🔗
  • Anda mengambil jurusan matematika dan mendapat pekerjaan bergaji tinggi.
    🔗
  • Anda mengambil jurusan matematika dan tidak mendapat pekerjaan bergaji tinggi.
    🔗
  • Faktanya, dalam kasus ini kedua pernyataan tersebut salah.
  • Anda tidak mengambil jurusan matematika dan mendapat pekerjaan bergaji tinggi.
    🔗
  • Hal ini membuat implikasinya benar karena bagian jika salah. Disjungsinya benar karena bagian pertama benar.
  • Anda tidak mengambil jurusan matematika dan tidak mendapat pekerjaan bergaji tinggi.
    🔗
🔗
🔗
🔗

Subbagian Tabel Kebenaran

Berikut sebuah pertanyaan tentang permainan Monopoli:
🔗
Jika Anda mendapat lebih banyak lemparan angka kembar daripada pemain lain, maka Anda akan kalah, atau jika Anda kalah, maka Anda pasti telah membeli properti terbanyak.
🔗
🔗
Benar atau salah? Kita akan menjawab pertanyaan ini tanpa perlu mengetahui apa pun tentang Monopoli. Sebagai gantinya, kita akan melihat bentuk logis pernyataan tersebut.
🔗
Kita perlu menentukan kapan pernyataan \((P \imp Q) \vee (Q \imp R)\) benar. Dengan menggunakan definisi konektif dalam Definisi 1.1.8, kita melihat bahwa agar pernyataan ini benar, \(P \imp Q\) harus benar atau \(Q \imp R\) harus benar (atau keduanya). Pernyataan-pernyataan itu benar jika \(P\) salah atau \(Q\) benar (pada kasus pertama), dan \(Q\) salah atau \(R\) benar (pada kasus kedua). Jadi—ya, ini menjadi agak rumit. Untungnya, kita dapat membuat bagan untuk mencatat semua kemungkinan dengan sebuah tabel kebenaran.
🔗
Gagasannya demikian: Pada setiap baris, kita mencantumkan satu kemungkinan kombinasi B dan S (Benar dan Salah) untuk setiap variabel proposisional, lalu menandai apakah pernyataan (majemuk) yang dibahas benar atau salah dalam kasus tersebut. Kita melakukan ini untuk setiap kemungkinan kombinasi B dan S. Dengan demikian, kita dapat melihat dengan jelas kasus-kasus ketika pernyataan itu benar atau salah. Untuk pernyataan yang rumit, pertama-tama kita akan mengisi nilai untuk setiap bagian pernyataan sebagai cara memecah tugas menjadi bagian-bagian yang lebih kecil dan lebih mudah ditangani.
🔗
Karena nilai kebenaran suatu pernyataan sepenuhnya ditentukan oleh nilai kebenaran bagian-bagiannya dan cara bagian-bagian itu dihubungkan, yang perlu Anda ketahui hanyalah tabel kebenaran untuk setiap konektif logis, yang telah kita lihat dalam Gambar 1.1.9
🔗
Semua tabel kebenaran yang kita bahas di sini dibangun dari tabel-tabel dasar dengan menerapkan aturan dasar beberapa kali.
🔗

Contoh 1.3.2.

Buatlah tabel kebenaran untuk pernyataan \(\neg P \vee Q\text{.}\)
🔗
Penyelesaian.
Perhatikan bahwa pernyataan ini bukan \(\neg(P \vee Q)\text{;}\) negasi hanya berlaku pada \(P\text{.}\) Konektif utama di sini adalah \(\vee\text{,}\) yang berarti kita akan menggunakan tabel kebenarannya terakhir. Pertama, kita menerapkan tabel kebenaran untuk \(\neg\text{,}\) lalu menerapkan tabel kebenaran untuk \(\vee\) dengan menggunakan “masukan” dari \(\neg P\) dan \(Q\text{.}\)
🔗
Karena terdapat dua variabel, ada empat kemungkinan kombinasi B dan S. Dengan menggabungkan semuanya, kita memperoleh tabel kebenaran berikut.
🔗
\(P\) \(Q\) \(\neg P\) \(\neg P \vee Q\)
B B S B
B S S S
S B B B
S S B B
Kita menambahkan kolom untuk \(\neg P\) agar pengisian kolom terakhir lebih mudah. Entri pada kolom \(\neg P\) ditentukan oleh entri pada kolom \(P\text{.}\) Kemudian, untuk mengisi kolom terakhir, perhatikan hanya kolom \(Q\) dan kolom \(\neg P\text{,}\) lalu gunakan aturan untuk \(\vee\text{.}\)
🔗
🔗
🔗
Sekarang mari kita jawab pertanyaan kita tentang Monopoli.
🔗

Contoh 1.3.3.

Analisislah pernyataan “Jika Anda mendapat lebih banyak lemparan angka kembar daripada pemain lain, maka Anda akan kalah, atau jika Anda kalah, maka Anda pasti telah membeli properti terbanyak,” dengan menggunakan tabel kebenaran.
🔗
Penyelesaian.
Nyatakan pernyataan tersebut dengan simbol sebagai \((P \imp Q) \vee (Q \imp R)\text{,}\) dengan \(P\) sebagai pernyataan “Anda mendapat lebih banyak lemparan angka kembar daripada pemain lain,” \(Q\) sebagai pernyataan “Anda akan kalah,” dan \(R\) sebagai pernyataan “Anda pasti telah membeli properti terbanyak.” Sekarang buatlah tabel kebenaran.
🔗
Tabel kebenaran harus memuat 8 baris untuk mencakup setiap kemungkinan kombinasi benar dan salah di antara ketiga pernyataan. Berikut tabel kebenaran lengkapnya:
🔗
\(P\) \(Q\) \(R\) \(P \imp Q\) \(Q \imp R\) \((P \imp Q) \vee (Q \imp R)\)
B B B B B B
B B S B S B
B S B S B B
B S S S B B
S B B B B B
S B S B S B
S S B B B B
S S S B B B
Tiga kolom pertama hanyalah daftar sistematis semua kemungkinan kombinasi B dan S untuk ketiga pernyataan (dapatkah Anda melihat bagaimana mencantumkan 16 kemungkinan kombinasi untuk empat pernyataan?). Dua kolom berikutnya ditentukan oleh nilai \(P\text{,}\) \(Q\text{,}\) dan \(R\) serta definisi implikasi. Kemudian, kolom terakhir ditentukan oleh nilai pada dua kolom sebelumnya dan definisi \(\vee\text{.}\) Kolom terakhir inilah yang kita perhatikan.
🔗
Perhatikan bahwa dalam masing-masing dari delapan kemungkinan kasus, pernyataan yang dibahas bernilai benar. Jadi, pernyataan kita tentang Monopoli benar (tanpa bergantung pada berapa banyak properti yang Anda miliki, berapa kali Anda melempar angka kembar, atau apakah Anda menang atau kalah).
🔗
🔗
🔗
Pernyataan tentang Monopoli adalah contoh tautologi, yaitu pernyataan yang niscaya benar semata-mata berdasarkan bentuk logisnya. Tautologi selalu benar, tetapi tidak banyak memberi tahu kita tentang dunia. Kita tidak memerlukan pengetahuan tentang Monopoli untuk menentukan bahwa pernyataan tersebut benar; jadi, mengetahui bahwa pernyataan itu benar tidak memberi tahu kita apa pun tentang Monopoli. Sama benarnya dengan pernyataan “jika bulan terbuat dari keju, maka Elvis masih hidup, atau jika Elvis masih hidup, maka unicorn memiliki 5 kaki.”
🔗
🔗

Subbagian Ekuivalensi Logis

Anda mungkin telah memperhatikan dalam Contoh 1.3.2 bahwa kolom terakhir pada tabel kebenaran untuk \(\neg P \vee Q\) identik dengan kolom terakhir pada tabel kebenaran untuk \(P \imp Q\text{:}\)
🔗
\(P\) \(Q\) \(P \imp Q\) \(\neg P \vee Q\)
B B B B
B S S S
S B B B
S S B B
Ini menunjukkan bahwa apa pun nilai \(P\) dan \(Q\text{,}\) pernyataan \(\neg P \vee Q\) dan \(P \imp Q\) selalu keduanya benar atau keduanya salah. Karena itu, kita mengatakan bahwa pernyataan-pernyataan tersebut ekuivalen secara logis.
🔗

Definisi 1.3.4. Ekuivalensi Logis.

Dua pernyataan (majemuk) \(P\) dan \(Q\) disebut ekuivalen secara logis jika \(P\) benar tepat ketika \(Q\) benar. Artinya, \(P\) dan \(Q\) memiliki nilai kebenaran yang sama untuk setiap pemberian nilai kebenaran pada bagian-bagian atomiknya.
🔗
Kita menuliskannya sebagai \(P \equiv Q\text{.}\)
🔗
🔗
Untuk memverifikasi bahwa dua pernyataan ekuivalen secara logis, Anda dapat membuat tabel kebenaran untuk masing-masing pernyataan dan memeriksa apakah kolom untuk kedua pernyataan tersebut identik.
🔗
Dalam Subbab 1.2 kita menyatakan bahwa setiap kali suatu implikasi benar, kontraposisinya juga benar. Sekarang kita dapat menyatakan klaim ini sebagai teorema berikut.
🔗

Bukti.

Kita cukup memeriksa tabel-tabel kebenarannya.
🔗
\(P\) \(Q\) \(P \imp Q\)
B B B
B S S
S B B
S S B
\(P\) \(Q\) \(\neg Q\) \(\neg P\) \(\neg Q \imp \neg P\)
B B S S B
B S B S S
S B S B B
S S B B B
(Perhatikan bahwa kombinasi nilai kebenaran dalam kedua tabel disusun dengan urutan yang sama, sehingga kita dapat dengan mudah melihat bahwa kolom terakhirnya identik.)
🔗
🔗
Mengenali dua pernyataan sebagai ekuivalen secara logis dapat sangat membantu. Merumuskan ulang suatu pernyataan matematika sering kali memberi wawasan tentang maknanya atau cara membuktikan maupun menyangkalnya. Dengan menggunakan tabel kebenaran, kita dapat memverifikasi secara sistematis bahwa dua pernyataan memang ekuivalen secara logis.
🔗

Contoh 1.3.6.

Apakah pernyataan “Tidak akan turun hujan atau salju,” dan “Tidak akan turun hujan dan tidak akan turun salju,” ekuivalen secara logis?
🔗
Penyelesaian.
Kita ingin mengetahui apakah \(\neg(P \vee Q)\) ekuivalen secara logis dengan \(\neg P \wedge \neg Q\text{.}\) Buatlah tabel kebenaran yang memuat kedua pernyataan:
🔗
\(P\) \(Q\) \(\neg(P \vee Q)\) \(\neg P \wedge \neg Q\)
B B S S
B S S S
S B S S
S S B B
Karena nilai kebenaran kedua pernyataan sama pada setiap baris, kedua pernyataan tersebut ekuivalen secara logis.
🔗
🔗
🔗
Perhatikan bahwa contoh ini memberi kita cara untuk “mendistribusikan” negasi terhadap disjungsi (“atau”). Kita memiliki aturan serupa untuk mendistribusikan negasi terhadap konjungsi (“dan”):
🔗
Hal ini menunjukkan bahwa mungkin ada semacam “aljabar” yang dapat diterapkan pada pernyataan (memang ada: disebut aljabar Boolean) untuk mengubah satu pernyataan menjadi pernyataan lain. Kita dapat mulai mengumpulkan contoh-contoh ekuivalensi logis yang berguna dan menerapkannya secara berturut-turut pada suatu pernyataan, alih-alih menuliskan tabel kebenaran yang rumit.
🔗
Hukum De Morgan tidak secara langsung membantu kita menangani implikasi, tetapi seperti yang kita lihat di atas, setiap implikasi dapat ditulis sebagai disjungsi:
🔗

Implikasi adalah Disjungsi.

\begin{equation*} P \imp Q \equiv \neg P \vee Q\text{.} \end{equation*}
🔗
Contoh: “Jika suatu bilangan merupakan kelipatan 4, maka bilangan itu genap” ekuivalen dengan “Suatu bilangan bukan kelipatan 4, atau (jika bukan demikian) bilangan itu genap.”
🔗
🔗
Dengan hasil ini dan hukum De Morgan, Anda dapat mengambil pernyataan apa pun dan menyederhanakannya hingga negasi hanya diterapkan pada proposisi atomik. Namun, mungkin saja beberapa negasi bertumpuk. Hal ini dapat ditangani dengan mudah:
🔗

Negasi Ganda.

\begin{equation*} \neg \neg P \equiv P\text{.} \end{equation*}
🔗
Contoh: “Tidak benar bahwa \(c\) tidak ganjil” berarti “\(c\) ganjil.”
🔗
🔗
Mari kita lihat bagaimana ekuivalensi-ekuivalensi yang telah kita jumpai dapat diterapkan.
🔗

Contoh 1.3.8.

Buktikan bahwa pernyataan \(\neg(P \imp Q)\) dan \(P\wedge \neg Q\) ekuivalen secara logis tanpa menggunakan tabel kebenaran.
🔗
Penyelesaian.
Kita akan memulai dengan salah satu pernyataan dan mengubahnya menjadi pernyataan yang lain melalui rangkaian pernyataan yang ekuivalen secara logis. Mulailah dengan \(\neg(P \imp Q)\text{.}\) Kita dapat menulis ulang implikasi sebagai disjungsi, sehingga pernyataan ini ekuivalen secara logis dengan
\begin{equation*} \neg(\neg P \vee Q)\text{.} \end{equation*}
Sekarang terapkan hukum De Morgan untuk memperoleh
\begin{equation*} \neg\neg P \wedge \neg Q\text{.} \end{equation*}
Terakhir, gunakan negasi ganda untuk memperoleh \(P \wedge \neg Q\)
🔗
🔗
🔗
Perhatikan bahwa contoh di atas menunjukkan bahwa negasi suatu implikasi BUKANLAH implikasi: negasi tersebut adalah konjungsi! Kita telah melihat ini sebelumnya dalam Subbab 1.1, tetapi hasil ini begitu penting dan berguna sehingga layak dinyatakan sebagai teorema.
🔗
Untuk memverifikasi bahwa dua pernyataan ekuivalen secara logis, Anda dapat menggunakan tabel kebenaran atau rangkaian penggantian yang ekuivalen secara logis. Metode tabel kebenaran, meskipun merepotkan, memiliki kelebihan karena dapat memverifikasi bahwa dua pernyataan TIDAK ekuivalen secara logis.
🔗

Contoh 1.3.10.

Apakah pernyataan \((P \vee Q) \imp R\) dan \((P \imp R) \vee (Q \imp R)\) ekuivalen secara logis?
🔗
Penyelesaian.
Perhatikan bahwa meskipun kita dapat mulai menulis ulang pernyataan-pernyataan ini dengan penggantian yang ekuivalen secara logis sambil berharap dapat mengubah yang satu menjadi yang lain, kita tidak akan pernah yakin apakah kegagalan kita disebabkan oleh tidak adanya ekuivalensi logis atau oleh kurangnya kreativitas kita. Karena itu, mari kita buat tabel kebenaran:
🔗
\(P\) \(Q\) \(R\) \((P\vee Q) \imp R\) \((P\imp R) \vee (Q \imp R)\)
B B B B B
B B S S S
B S B B B
B S S S B
S B B B B
S B S S B
S S B B B
S S S B B
Perhatikan baris keempat (atau keenam). Dalam kasus ini, \((P \imp R) \vee (Q \imp R)\) benar, tetapi \((P \vee Q) \imp R\) salah. Oleh karena itu, pernyataan-pernyataan tersebut tidak ekuivalen secara logis.
🔗
Meskipun tidak ada ekuivalensi logis, setiap kali \((P \vee Q) \imp R\) benar, \((P \imp R) \vee (Q \imp R)\) juga benar. Hal ini memberi tahu kita bahwa kita dapat mendeduksi \((P \imp R) \vee (Q \imp R)\) dari \((P \vee Q) \imp R\text{,}\) tetapi tidak dalam arah sebaliknya.
🔗
🔗
🔗
🔗

Subbagian Ekuivalensi untuk Pernyataan Berkuantor

Semua contoh yang telah kita bahas sejauh ini hanya melibatkan logika proposisional, dengan satuan dasar logika berupa pernyataan yang benar atau salah. Kita juga dapat mengatakan bahwa dua pernyataan yang melibatkan kuantor dan predikat ekuivalen secara logis.
🔗
Terkadang kuantor tidak berperan dalam ekuivalensi tersebut. Sebagai contoh,
\begin{equation*} \forall x (P(x) \imp Q(x)) \equiv \forall x (\neg P(x) \vee Q(x))\text{.} \end{equation*}
Begitu kita mengganti \(x\) dengan suatu konstanta, tersisa dua pernyataan yang ekuivalen secara logis berdasarkan bentuk proposisionalnya.
🔗
Pada kesempatan lain yang lebih menarik, justru logika kuantorlah yang membuat pernyataan-pernyataan itu ekuivalen secara logis. Yang sangat menarik di sini adalah bahwa kita tidak dapat menggunakan tabel kebenaran untuk memverifikasi ekuivalensi-ekuivalensi ini!
🔗
Sebagai gantinya, kita perlu menalar tentang semesta pembicaraan sebagai suatu himpunan. Sebagai contoh, mari kita perhatikan bagaimana negasi berinteraksi dengan kuantor.
🔗
Perhatikan klaim bahwa “semua bilangan ganjil adalah prima.” Kita dapat menyatakannya secara simbolis sebagai \(\forall x (O(x) \imp P(x))\text{.}\) Pernyataan itu jelas tidak benar, sehingga yang benar adalah “tidak semua bilangan ganjil adalah prima” (yaitu, \(\neg\forall x(O(x) \imp P(x))\)). Bagaimana kita mengetahuinya? Mudah: 9. Ya, 9 ganjil tetapi bukan prima. Namun, apakah cukup bahwa hanya satu bilangan ganjil bukan bilangan prima?
🔗
Untuk menyangkal klaim universal, Anda hanya memerlukan satu contoh penyangkal. Anda hanya perlu menunjukkan bahwa terdapat suatu bilangan yang membuat klaim tersebut salah. Dalam kasus kita, terdapat ekuivalensi
\begin{equation*} \neg\forall x (O(x) \imp P(x)) \equiv \exists x (O(x) \wedge \neg P(x))\text{.} \end{equation*}
Jika sejenak kita mengabaikan kuantornya, kita memperoleh
\begin{equation*} \neg(O \imp P) \equiv O \wedge \neg P \end{equation*}
yang tepat merupakan contoh dari Teorema 1.3.9. Bagian baru yang menarik adalah bahwa ketika kita menegasikan kuantor universal, kita memperoleh kuantor eksistensial.
🔗
Menegasikan kuantor eksistensial menghasilkan kuantor universal. Hal ini masuk akal. Jika tidak terdapat sesuatu yang memiliki suatu sifat, maka segala sesuatu tidak memiliki sifat tersebut.
🔗

Kuantor dan Negasi.

\(\neg \forall x P(x)\) ekuivalen dengan \(\exists x \neg P(x)\text{.}\)
🔗
\(\neg \exists x P(x)\) ekuivalen dengan \(\forall x \neg P(x) \text{.}\)
🔗
🔗
🔗
Secara simbolis, kita dapat memindahkan simbol negasi melewati suatu kuantor, tetapi hal itu menyebabkan jenis kuantornya berubah.
🔗
Cara lain untuk memahami mengapa hal ini masuk akal: Kuantor universal menyerupai konjungsi (yang mungkin tak hingga), sebab kuantor ini menyatakan bahwa sifat tersebut benar untuk benda ini, dan benda itu, dan benda lainnya,... semua benda. Kuantor eksistensial menyerupai disjungsi (yang mungkin tak hingga): Sifat tersebut benar untuk sedikitnya satu benda, mungkin benda ini, atau benda itu, atau benda lainnya, atau.... Hukum De Morgan memberi tahu kita bahwa ketika menegasikan konjungsi, kita memperoleh disjungsi, dan ketika menegasikan disjungsi, kita memperoleh konjungsi. Bukankah menyenangkan ketika semuanya berjalan sebagaimana mestinya?
🔗

Contoh 1.3.11.

Misalkan kita menyatakan bahwa tidak ada bilangan terkecil. Kita dapat menerjemahkan pernyataan ini ke dalam simbol sebagai
\begin{equation*} \neg \exists x \forall y (x \le y)\text{.} \end{equation*}
(“Tidak benar bahwa terdapat bilangan \(x\) sedemikian sehingga untuk setiap bilangan \(y\text{,}\) \(x\) kurang dari atau sama dengan \(y\text{.}\)”)
🔗
Namun, kita mengetahui bagaimana negasi berinteraksi dengan kuantor: Kita dapat memindahkan negasi melewati suatu kuantor dengan mengubah jenis kuantornya (antara universal dan eksistensial). Jadi, pernyataan di atas semestinya ekuivalen secara logis dengan
\begin{equation*} \forall x \exists y (y \lt x)\text{.} \end{equation*}
Perhatikan bahwa \(y \lt x\) adalah negasi dari \(x \le y\text{.}\) Pernyataan ini dibaca, “Untuk setiap bilangan \(x\text{,}\) terdapat bilangan \(y\) yang lebih kecil daripada \(x\text{.}\)” Kita melihat bahwa ini merupakan cara lain untuk menyatakan klaim semula.
🔗
🔗
Penting untuk menegaskan bahwa logika predikat memperluas logika proposisional (seperti mekanika kuantum memperluas mekanika klasik). Semua yang telah kita pelajari tentang ekuivalensi logis dan deduksi tetap berlaku. Namun, logika predikat memungkinkan kita menganalisis pernyataan dengan tingkat perincian yang lebih tinggi, hingga menelaah proposisi individual \(P\text{,}\) \(Q\text{,}\) dan seterusnya.
🔗
Untuk melakukannya, kita perlu memahami bagaimana kuantor dan konektif berinteraksi. Kita telah melihat sedikit tentang negasi dan kuantor. Bagaimana dengan konektif lainnya? Mari kita lihat sebuah contoh yang menyelidiki bagaimana kuantor universal dan disjungsi dapat (atau tidak dapat) bekerja bersama.
🔗

Contoh 1.3.12.

Perhatikan dua pernyataan berikut,
\begin{equation*} \forall x (P(x) \vee Q(x)) \qquad \qquad \forall x P(x) \vee \forall x Q(x)\text{.} \end{equation*}
Apakah keduanya ekuivalen secara logis?
🔗
Penyelesaian.
Pernyataan-pernyataan ini TIDAK ekuivalen secara logis. Secara intuitif, pernyataan di sebelah kiri menyatakan bahwa setiap objek merupakan objek-\(P\) atau objek-\(Q\text{.}\) Pernyataan di sebelah kanan menyatakan bahwa setiap objek merupakan objek-\(P\text{,}\) atau setiap objek merupakan objek-\(Q\text{.}\) Keduanya terasa berbeda.
🔗
Untuk memastikannya, kita ingin menentukan predikat \(P(x)\) dan \(Q(x)\) serta suatu semesta pembicaraan sedemikian sehingga salah satu pernyataan benar dan yang lain salah. Misalkan \(P(x)\) adalah “\(x\) genap” dan \(Q(x)\) adalah “\(x\) ganjil.” Semesta pembicaraan kita adalah semua bilangan bulat (karena pada himpunan bilangan inilah sifat genap dan ganjil bermakna).
🔗
Pernyataan di sebelah kiri benar! Setiap bilangan genap atau ganjil. Namun, apakah setiap bilangan genap? Tidak. Apakah setiap bilangan ganjil? Tidak. Jadi, pernyataan di sebelah kanan salah (pernyataan itu berbentuk salah atau salah).
🔗
Menariknya, pernyataan di sebelah kanan mengimplikasikan pernyataan di sebelah kiri. Artinya,
\begin{equation*} (\forall x P(x) \vee \forall x Q(x)) \imp \forall x (P(x) \vee Q(x)) \end{equation*}
selalu benar.
🔗
Hal ini mirip dengan tautologi, meskipun istilah itu kita khususkan untuk kebenaran niscaya dalam logika proposisional. Pernyataan dalam logika predikat yang niscaya benar mendapat sebutan yang lebih bergengsi, yaitu hukum logika (atau terkadang sahih secara logis, tetapi sebutan itu kurang menarik).
🔗
🔗
🔗
Kita juga dapat menelaah bagaimana kuantor saling berinteraksi.
🔗

Contoh 1.3.13.

Dapatkah Anda menukar urutan kuantor? Sebagai contoh, perhatikan dua pernyataan berikut:
\begin{equation*} \forall x \exists y P(x,y) \qquad \text{ dan } \qquad \exists y \forall x P(x,y)\text{.} \end{equation*}
Apakah keduanya ekuivalen secara logis?
🔗
Penyelesaian.
Pernyataan-pernyataan ini TIDAK ekuivalen secara logis. Untuk melihatnya, kita harus memberikan interpretasi atas predikat \(P(x,y)\) yang membuat salah satu pernyataan benar dan yang lain salah.
🔗
Misalkan \(P(x,y)\) adalah predikat \(x \lt y\text{.}\) Dalam bilangan asli, benar bahwa untuk setiap \(x\) terdapat suatu \(y\) yang lebih besar daripada \(x\) tersebut (karena terdapat tak hingga banyak bilangan). Namun, tidak ada bilangan asli \(y\) yang lebih besar daripada setiap bilangan \(x\text{.}\) Jadi, mungkin saja \(\forall x \exists y P(x,y)\) benar sedangkan \(\exists y \forall x P(x,y)\) salah.
🔗
Namun, arah sebaliknya tidak mungkin terjadi. Jika terdapat suatu \(y\) yang membuat setiap \(x\) memenuhi \(P(x,y)\text{,}\) maka tentu saja untuk setiap \(x\) terdapat suatu \(y\) yang memenuhi \(P(x,y)\text{.}\) Pernyataan pertama mengatakan bahwa kita dapat menemukan satu \(y\) yang berlaku untuk setiap \(x\text{.}\) Pernyataan kedua mengizinkan \(y\) yang berbeda berlaku untuk \(x\) yang berbeda, tetapi tidak ada yang menghalangi kita menggunakan \(y\) yang sama yang berlaku untuk setiap \(x\text{.}\) Dengan kata lain, meskipun kedua pernyataan tidak ekuivalen secara logis, kita memiliki aturan deduksi yang sahih:
🔗
\(\exists y \forall x P(x,y)\)
\(\therefore\) \(\forall x \exists y P(x,y)\)
Dengan ungkapan lain, hal ini mengatakan bahwa pernyataan tunggal
\begin{equation*} \exists y \forall x P(x,y) \imp \forall x \exists y P(x,y) \end{equation*}
selalu benar; pernyataan tersebut adalah hukum logika.
🔗
🔗
🔗
🔗

Subbagian Deduksi

Sebelumnya, kita menyatakan bahwa argumen berikut sahih:
🔗
Jika Edith memakan sayurannya, maka ia boleh mendapat kukis. Edith memakan sayurannya. Oleh karena itu, Edith mendapat kukis.
🔗
🔗
Bagaimana kita mengetahui bahwa argumen ini sahih? Mari kita lihat bentuk pernyataan-pernyataannya. Misalkan \(P\) menyatakan “Edith memakan sayurannya” dan \(Q\) menyatakan “Edith boleh mendapat kukis.” Dengan demikian, bentuk logis argumen tersebut adalah:
🔗
\(P \imp Q\)
\(P\)
\(\therefore\) \(Q\)
Ini adalah contoh aturan deduksi, yaitu bentuk argumen yang selalu sahih. Aturan ini sangat terkenal dan disebut modus ponens. Apakah Anda yakin bahwa ini merupakan aturan deduksi yang sahih? Jika belum, perhatikan tabel kebenaran berikut:
🔗
\(P\) \(Q\) \(P\imp Q\)
B B B
B S S
S B B
S S B
Ini hanyalah tabel kebenaran untuk \(P \imp Q\text{,}\) tetapi yang penting di sini adalah bahwa semua baris dalam aturan deduksi memiliki kolomnya sendiri pada tabel kebenaran. Ingat bahwa suatu argumen sahih jika kesimpulannya harus benar ketika premis-premisnya benar. Premis dalam kasus ini adalah \(P \imp Q\) dan \(P\text{.}\) Baris mana pada tabel kebenaran yang menunjukkan bahwa keduanya benar? \(P\) benar pada dua baris pertama, dan di antara keduanya, hanya baris pertama yang juga membuat \(P \imp Q\) benar. Dan ternyata, dalam satu-satunya kasus ini, \(Q\) juga benar. Jadi, jika \(P\imp Q\) dan \(P\) keduanya benar, kita melihat bahwa \(Q\) juga harus benar.
🔗
Anggaplah aturan deduksi sebagai semacam bentuk ekuivalensi logis satu arah. Dua pernyataan ekuivalen secara logis jika pada setiap baris tabel kebenaran ketika pernyataan pertama benar, pernyataan kedua juga benar, dan pada setiap baris ketika pernyataan kedua benar, pernyataan pertama juga benar. Suatu deduksi hanya mensyaratkan bagian pertama dari kedua bagian tersebut.
🔗
Berikut beberapa contoh lainnya.
🔗

Contoh 1.3.14.

Tunjukkan bahwa berikut ini merupakan aturan deduksi yang sahih.
🔗
\(P \imp Q\)
\(\neg P \imp Q\)
\(\therefore\) \(Q\)
Penyelesaian.
Kita membuat tabel kebenaran yang memuat semua baris bentuk argumen tersebut:
🔗
\(P\) \(Q\) \(P\imp Q\) \(\neg P\) \(\neg P \imp Q\)
B B B S B
B S S S B
S B B B B
S S B B S
(kita menyertakan kolom untuk \(\neg P\) sebagai langkah bantu untuk memperoleh kolom \(\neg P \imp Q\)).
🔗
Sekarang perhatikan semua baris yang membuat \(P \imp Q\) dan \(\neg P \imp Q\) keduanya benar. Hal ini hanya terjadi pada baris 1 dan 3. Lihat! Pada baris-baris tersebut \(Q\) juga benar, sehingga bentuk argumennya sahih (merupakan aturan deduksi yang sahih).
🔗
🔗
🔗

Contoh 1.3.15.

Tentukan apakah berikut ini merupakan aturan deduksi yang sahih.
🔗
\(P \imp R\)
\(Q \imp R\)
\(R\)
\(\therefore\) \(P \vee Q\)
Penyelesaian.
Mari kita buat tabel kebenaran yang memuat keempat pernyataan tersebut.
🔗
\(P\) \(Q\) \(R\) \(P \imp R\) \(Q \imp R\) \(P \vee Q\)
B B B B B B
B B S S S B
B S B B B B
B S S S B B
S B B B B B
S B S B S B
S S B B B S
S S S B B S
Perhatikan baris kedua dari bawah. Di sini ketiga premis argumen benar, tetapi kesimpulannya salah. Jadi, ini bukan aturan deduksi yang sahih.
🔗
Selagi tabel kebenaran ada di hadapan kita, perhatikan baris 1, 3, dan 5. Hanya pada baris-baris inilah semua pernyataan \(P \imp R\text{,}\) \(Q \imp R\text{,}\) dan \(P\vee Q\) benar. Ternyata \(R\) juga benar pada baris-baris tersebut. Jadi, kita telah menemukan aturan deduksi baru yang kita ketahui memang sahih:
🔗
\(P \imp R\)
\(Q \imp R\)
\(P \vee Q\)
\(\therefore\) \(R\)
🔗
🔗

Deduksi kuantor.

Ada pula aturan deduksi yang dapat kita tuliskan untuk kuantor. Sebagai contoh:
🔗
\(\forall x P(x)\)
\(\therefore\) \(\exists x P(x)\)
Jika setiap objek merupakan objek-\(P\text{,}\) maka pasti terdapat sesuatu yang merupakan objek-\(P\text{.}\) Aturan-aturan ini tidak dapat diverifikasi dengan tabel kebenaran, dan pembahasan lengkap tentang jenis logika predikat ini berada di luar cakupan buku ini.
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Untuk memeriksa apakah dua pernyataan ekuivalen secara logis, Anda dapat menggunakan tabel kebenaran. Jelaskan apa yang akan Anda cari dalam tabel kebenaran untuk menyimpulkan bahwa kedua pernyataan tersebut ekuivalen secara logis. Apa yang menunjukkan bahwa keduanya tidak ekuivalen secara logis?
🔗
🔗

2.

Untuk memeriksa apakah suatu aturan deduksi sahih, Anda dapat menggunakan tabel kebenaran. Jelaskan apa yang akan Anda cari dalam tabel kebenaran yang telah dilengkapi untuk menyatakan bahwa aturan deduksi tersebut sahih, dan apa yang menunjukkan bahwa aturan deduksi tersebut tidak sahih.
🔗
🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan sedikitnya satu pertanyaan tentang isi bagian ini yang ingin Anda ketahui jawabannya.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Buatlah tabel kebenaran untuk pernyataan \((P \wedge Q) \rightarrow (P \vee Q)\text{.}\)
🔗
\(P\) \(Q\) \(P \wedge Q\) \(P \vee Q\) \((P \wedge Q) \rightarrow (P \vee Q))\)
B B
B S
S B
S S
🔗

2.

Buatlah tabel kebenaran untuk pernyataan \(\neg Q \vee (Q \rightarrow P)\)
🔗
\(P\) \(Q\) \(\neg Q\) \(Q \rightarrow P\) \(\neg Q \vee (Q \rightarrow P)\)
B B
B S
S B
S S
Apa yang dapat Anda simpulkan tentang \(P\) dan \(Q\) jika diketahui bahwa pernyataan di atas salah?
🔗
  • \(P\) dan \(Q\) keduanya salah.
    🔗
    🔗
  • \(P\) benar dan \(Q\) salah.
    🔗
    🔗
  • \(P\) salah dan \(Q\) benar.
    🔗
    🔗
  • \(P\) dan \(Q\) keduanya benar.
    🔗
    🔗
  • Tidak satu pun jawaban di atas.
    🔗
    🔗
🔗
🔗

3.

Buatlah tabel kebenaran untuk pernyataan \(\neg P \wedge (Q \rightarrow R)\)
🔗
\(P\) \(Q\) \(R\) \(\neg P\) \(Q \rightarrow R\) \(\neg P \wedge (Q \rightarrow R)\)
B B B
B B S
B S B
B S S
S B B
S B S
S S B
S S S
🔗

4.

Tentukan apakah pernyataan \(P \rightarrow (Q \vee R)\) dan \((P \rightarrow Q) \vee (P\rightarrow R)\) ekuivalen secara logis.
🔗
Pertama, buatlah tabel kebenaran untuk kedua pernyataan tersebut. (Anda dapat melengkapi tabel kebenaran di atas kertas agar dapat membuat kolom untuk langkah-langkah antara; masukkan hanya kolom akhirnya di sini.)
🔗
\(P\) \(Q\) \(R\) \(P \rightarrow (Q \vee R)\) \((P \rightarrow Q) \vee (P\rightarrow R)\)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Apakah kedua pernyataan tersebut ekuivalen secara logis?
🔗
  • Tidak, karena kolom untuk kedua pernyataan tersebut tidak identik.
    🔗
    🔗
  • Ya, karena meskipun kolom-kolom tersebut tidak identik, ada beberapa baris yang nilainya identik.
    🔗
    🔗
  • Tidak, karena pernyataan-pernyataan tersebut tidak selalu benar.
    🔗
    🔗
  • Ya, karena kolom untuk kedua pernyataan tersebut identik.
    🔗
    🔗
  • Tidak mungkin ditentukan tanpa informasi lebih lanjut.
    🔗
    🔗
🔗
🔗

5.

Tentukan apakah aturan deduksi berikut sahih:
🔗
\(P \rightarrow Q\)
\(\neg Q\)
\(\therefore\) \(\neg P\)
Pertama, buatlah tabel kebenaran untuk pernyataan-pernyataan yang terkait. (Anda dapat melengkapi tabel kebenaran di atas kertas agar dapat membuat kolom untuk langkah-langkah antara; masukkan hanya kolom akhirnya di sini.)
🔗
\(P\) \(Q\) \(P \rightarrow Q\) \(\neg Q\) \(\neg P\)
T T
T F
F T
F F
Apakah aturan deduksi tersebut sahih?
🔗
  • Ya, pada setiap baris yang kedua premisnya benar, kesimpulannya juga benar.
    🔗
    🔗
  • Ya, karena ada satu baris yang kedua premisnya benar.
    🔗
    🔗
  • Tidak, karena kesimpulannya tidak selalu benar.
    🔗
    🔗
  • Tidak, karena kolom untuk kedua premis tersebut tidak identik.
    🔗
    🔗
  • Tidak mungkin ditentukan tanpa informasi lebih lanjut.
    🔗
    🔗
🔗
🔗

6.

Tentukan apakah aturan deduksi berikut sahih:
🔗
\(P \rightarrow (Q \vee R)\)
\(\neg(P \rightarrow Q)\)
\(\therefore\) \(R\)
Pertama, buatlah tabel kebenaran untuk pernyataan-pernyataan yang terkait. (Anda dapat melengkapi tabel kebenaran di atas kertas agar dapat membuat kolom untuk langkah-langkah antara; masukkan hanya kolom akhirnya di sini.)
🔗
\(P\) \(Q\) \(R\) \(P \rightarrow (Q \vee R)\) \(\neg(P \rightarrow Q)\)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Apakah aturan deduksi tersebut sahih?
🔗
  • Ya, karena ada satu baris yang kedua premisnya benar.
    🔗
    🔗
  • Ya, pada setiap baris yang kedua premisnya benar, kesimpulannya juga benar.
    🔗
    🔗
  • Tidak, karena kolom untuk kedua premis tersebut tidak identik.
    🔗
    🔗
  • Tidak, karena pernyataan-pernyataan tersebut tidak selalu benar.
    🔗
    🔗
  • Tidak mungkin ditentukan tanpa informasi lebih lanjut.
    🔗
    🔗
🔗
🔗

7.

Tentukan apakah aturan deduksi berikut sahih:
🔗
\((P \wedge Q) \rightarrow R\)
\(\neg P \vee \neg Q\)
\(\therefore\) \(\neg R\)
Pertama, buatlah tabel kebenaran untuk pernyataan-pernyataan yang terkait. (Anda dapat melengkapi tabel kebenaran di atas kertas agar dapat membuat kolom untuk langkah-langkah antara; masukkan hanya kolom akhirnya di sini.)
🔗
\(P\) \(Q\) \(R\) \((P \wedge Q) \rightarrow R\) \(\neg P \vee \neg Q\) \(\neg R\)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Apakah aturan deduksi tersebut sahih?
🔗
  • Tidak, karena kolom untuk kedua premis tersebut tidak identik.
    🔗
    🔗
  • Ya, karena ada satu baris yang kesimpulan dan kedua premisnya benar.
    🔗
    🔗
  • Tidak, karena ada satu baris yang kedua premisnya benar tetapi kesimpulannya salah.
    🔗
    🔗
  • Ya, karena pada setiap baris yang kesimpulannya benar, salah satu premisnya benar.
    🔗
    🔗
  • Tidak mungkin ditentukan tanpa informasi lebih lanjut.
    🔗
    🔗
🔗
🔗

8.

Tentukan apakah aturan deduksi berikut sahih:
🔗
\(P \rightarrow Q\)
\(P \wedge \neg Q\)
\(\therefore\) \(R\)
Pertama, buatlah tabel kebenaran untuk pernyataan-pernyataan yang terkait. (Anda dapat melengkapi tabel kebenaran di atas kertas agar dapat membuat kolom untuk langkah-langkah antara; masukkan hanya kolom akhirnya di sini.)
🔗
\(P\) \(Q\) \(R\) \(P \rightarrow Q\) \(P \wedge \neg Q\)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Apakah aturan deduksi tersebut sahih?
🔗
  • Ya, karena ada satu baris yang kedua premisnya benar.
    🔗
    🔗
  • Tidak, karena kolom untuk kedua premis tersebut tidak identik.
    🔗
    🔗
  • Ya, pada setiap baris yang kedua premisnya benar, kesimpulannya juga benar.
    🔗
    🔗
  • Tidak, karena kedua premis tidak pernah sama-sama benar pada baris yang sama.
    🔗
    🔗
  • Tidak mungkin ditentukan tanpa informasi lebih lanjut.
    🔗
    🔗
🔗
🔗

9.

Manakah di antara pernyataan berikut yang merupakan hukum logika? Artinya, manakah yang selalu benar, apa pun semesta pembicaraannya dan apa pun makna yang Anda berikan kepada predikat-predikatnya? Pilih semua jawaban yang benar.
🔗
  • \(\forall x (P(x) \vee \neg P(x))\text{.}\)
    🔗
  • \(\exists x P(x) \imp \forall x P(x)\text{.}\)
    🔗
  • \(\neg\forall x P(x) \imp \exists x P(x)\text{.}\)
    🔗
  • \(\forall x \exists y P(x,y) \iff \exists y \forall x P(x,y)\text{.}\)
    🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Anda menjumpai dua troll yang sedang bermain Stratego®. Mereka berkata kepada Anda:
🔗
Troll 1: Jika kami sepupu, maka kami berdua adalah penipu.
🔗
Troll 2: Kami sepupu, atau kami berdua adalah penipu.
🔗
🔗
Mungkinkah kedua troll tersebut adalah kesatria? Ingatlah bahwa setiap troll adalah kesatria yang selalu berkata benar atau penipu yang selalu berbohong. Jelaskan jawaban Anda dan bagaimana tabel kebenaran dapat digunakan untuk menemukannya.
🔗
Petunjuk.
Anda mungkin dapat menalar setiap kasus secara langsung, tetapi cobalah membuat tabel kebenaran. Gunakan dua pernyataan: \(P\) menyatakan “kami sepupu” dan \(Q\) menyatakan “kami berdua adalah penipu”.
🔗
🔗
🔗

2.

Selanjutnya, Anda menjumpai tiga troll yang mengenakan tanda nama. Mereka berkata:
Pat
🔗
Jika Quinn atau saya adalah kesatria, maka Ryan juga kesatria.
🔗
Quinn
🔗
Ryan adalah kesatria, dan jika Pat adalah kesatria, maka saya juga kesatria.
🔗
Ryan
🔗
Quinn adalah penipu, tetapi Pat dan saya sama-sama kesatria atau sama-sama penipu.
🔗
Buatlah tabel kebenaran yang memuat ketiga pernyataan tersebut. Kemudian gunakan tabel itu untuk menentukan jenis setiap troll.
🔗
🔗

3.

Perhatikan pernyataan tentang sebuah pesta, “Jika hari ini ulang tahun Anda atau akan ada kue, maka akan ada kue.”
  1. Nyatakan pernyataan di atas dengan simbol. Sebutkan dengan jelas pernyataan mana yang dilambangkan dengan \(P\) dan mana yang dilambangkan dengan \(Q\text{.}\)
    🔗
    🔗
  2. Buatlah tabel kebenaran untuk pernyataan tersebut.
    🔗
    🔗
  3. Dengan mengasumsikan pernyataan tersebut benar, apa (jika ada) yang dapat Anda simpulkan jika diketahui bahwa akan ada kue?
    🔗
    🔗
  4. Dengan mengasumsikan pernyataan tersebut benar, apa (jika ada) yang dapat Anda simpulkan jika diketahui bahwa tidak akan ada kue?
    🔗
    🔗
  5. Misalkan Anda mengetahui bahwa pernyataan tersebut bohong. Apa yang dapat Anda simpulkan?
    🔗
    🔗
🔗
🔗

4.

Geoff Poshingten sedang berada di restoran piza mewah dan memutuskan untuk memesan calzone. Ketika pramusaji menanyakan isian yang ia inginkan, Geoff menjawab, “Saya ingin pepperoni atau sosis. Selain itu, jika ada sosis, maka harus ada juga daging puyuh. Oh, dan jika ada pepperoni atau daging puyuh, maka harus ada juga keju ricotta.”
  1. Nyatakan pesanan Geoff dengan simbol logika.
    🔗
    🔗
  2. Pramusaji itu tahu bahwa Geoff adalah pembohong atau orang yang selalu berkata benar (jadi, semua yang ia katakan salah atau semuanya benar). Yang manakah Geoff?
    🔗
    🔗
  3. Apa, jika ada, yang dapat disimpulkan oleh pramusaji mengenai bahan-bahan calzone yang diinginkan Geoff?
    🔗
    🔗
🔗
Petunjuk.
Tuliskan tiga pernyataan menggunakan simbol \(P, Q, R, S\text{.}\) Jika Geoff adalah orang yang selalu berkata benar, ketiga pernyataan tersebut benar. Jika ia pembohong, ketiganya salah. Namun, dalam kedua kasus itu, kita belum mengetahui apakah keempat pernyataan atomik tersebut benar atau salah karena ia tidak mengucapkannya secara tersendiri.
🔗
Tabel kebenaran mungkin membantu, meskipun barangkali tidak mutlak diperlukan.
🔗
🔗
🔗

5.

Tentukan apakah kedua pernyataan berikut ekuivalen secara logis: \(\neg(P \imp Q)\) dan \(P \wedge \neg Q\text{.}\) Jelaskan bagaimana Anda mengetahui bahwa jawaban Anda benar.
🔗
🔗

6.

Sederhanakan pernyataan-pernyataan berikut (sehingga negasi hanya muncul tepat di depan variabel).
  1. \(\neg(P \imp \neg Q)\text{.}\)
    🔗
  2. \((\neg P \vee \neg Q) \imp \neg (\neg Q \wedge R)\text{.}\)
    🔗
  3. \(\neg((P \imp \neg Q) \vee \neg (R \wedge \neg R))\text{.}\)
    🔗
  4. Tidak benar bahwa jika Sam bukan laki-laki maka Chris adalah perempuan, dan bahwa Chris bukan perempuan.
    🔗
    🔗
🔗
🔗

7.

Gunakan hukum De Morgan dan fakta ekuivalensi logis lain yang Anda ketahui untuk menyederhanakan pernyataan-pernyataan berikut. Tunjukkan semua langkah Anda. Pada pernyataan akhir, negasi hanya boleh muncul tepat di sebelah variabel pernyataan atau predikat (\(P\text{,}\) \(Q\text{,}\) \(E(x)\text{,}\) dan sebagainya), dan tidak boleh ada negasi ganda. Sebaiknya gunakan hanya konjungsi, disjungsi, dan negasi.
  1. \(\neg((\neg P \wedge Q) \vee \neg(R \vee \neg S))\text{.}\)
    🔗
  2. \(\neg((\neg P \imp \neg Q) \wedge (\neg Q \imp R))\) (berhati-hatilah dengan implikasinya).
    🔗
  3. Untuk kedua bagian di atas, verifikasikan jawaban Anda menggunakan tabel kebenaran. Artinya, gunakan tabel kebenaran untuk memeriksa bahwa pernyataan yang diberikan dan bentuk penyederhanaan yang Anda usulkan memang ekuivalen secara logis.
    🔗
    🔗
🔗
🔗

8.

Perhatikan pernyataan, “Jika suatu bilangan merupakan bilangan segitiga atau bilangan kuadrat, maka bilangan itu bukan bilangan prima”
  1. Buatlah tabel kebenaran untuk pernyataan \((T \vee S) \imp \neg P\text{.}\)
    🔗
    🔗
  2. Jika Anda menganggap pernyataan tersebut salah, sifat apa saja yang harus dimiliki oleh suatu contoh penyangkal? Jelaskan dengan merujuk pada tabel kebenaran Anda.
    🔗
    🔗
  3. Jika pernyataan tersebut benar, apa yang dapat Anda simpulkan tentang bilangan 5657, yang sudah pasti merupakan bilangan prima? Sekali lagi, jelaskan menggunakan tabel kebenaran.
    🔗
    🔗
🔗
Petunjuk.
  1. Akan ada tiga baris yang pernyataannya bernilai salah.
    🔗
    🔗
  2. Perhatikan tiga baris yang bernilai salah, lalu nyatakan nilai kebenaran \(T\text{,}\) \(S\text{,}\) dan \(P\) pada baris-baris tersebut.
    🔗
    🔗
  3. Carilah baris tempat \(P\) bernilai benar dan seluruh pernyataan juga bernilai benar.
    🔗
    🔗
🔗
🔗
🔗

9.

Tommy Flanagan menceritakan kepada Anda apa yang ia santap kemarin sore. Ia berkata, “Saya makan berondong jagung atau kismis. Selain itu, jika saya makan roti lapis mentimun, maka saya minum soda. Namun, saya tidak minum soda ataupun teh.” Tentu saja, Anda tahu bahwa Tommy adalah pembohong terburuk di dunia dan semua yang ia katakan salah. Apa yang sebenarnya disantap Tommy?
🔗
Jelaskan alasan jawaban Anda dengan menuliskan semua pernyataan Tommy menggunakan variabel pernyataan (\(P, Q, R, S, T\)), mengambil negasinya, lalu menggunakannya untuk menyimpulkan apa yang sebenarnya disantap Tommy.
🔗
Petunjuk.
Tuliskan tiga pernyataan, lalu ambil negasi masing-masing (karena ia pembohong). Anda seharusnya menemukan bahwa Tommy makan satu jenis makanan dan minum satu jenis minuman. (\(Q\) menyatakan roti lapis mentimun.)
🔗
🔗
🔗

10.

Dapatkah Anda merangkai implikasi? Artinya, jika \(P \imp Q\) dan \(Q \imp R\text{,}\) apakah itu berarti \(P \imp R\text{?}\) Buktikan bahwa aturan deduksi berikut valid:
🔗
\(P \imp Q\)
\(Q \imp R\)
\(\therefore\) \(P \imp R\)
🔗

11.

Misalkan \(P\) dan \(Q\) adalah pernyataan proposisional (yang mungkin majemuk). Buktikan bahwa \(P\) dan \(Q\) ekuivalen secara logis jika dan hanya jika \(P \iff Q\) merupakan tautologi.
🔗
Petunjuk.
Apa arti konsep-konsep ini jika dinyatakan dalam tabel kebenaran?
🔗
🔗
🔗

12.

Misalkan \(P_1, P_2, \ldots, P_n\) dan \(Q\) adalah pernyataan proposisional (yang mungkin majemuk). Misalkan pula bahwa
🔗
\(P_1\)
\(P_2\)
\(\vdots\)
\(P_n\)
\(\therefore\) \(Q\)
merupakan aturan deduksi yang valid. Buktikan bahwa pernyataan
\begin{equation*} (P_1 \wedge P_2 \wedge \cdots \wedge P_n) \imp Q \end{equation*}
merupakan tautologi.
🔗
🔗

13.

Perhatikan pernyataan-pernyataan di bawah ini. Nyatakan masing-masing dengan simbol menggunakan predikat \(F(x,y)\) untuk “orang \(x\) dapat ditipu pada waktu \(y\text{.}\)” Tentukan apakah ada pernyataan yang ekuivalen satu sama lain, atau apakah ada yang mengimplikasikan pernyataan lain, dalam konteks ini maupun secara umum.
🔗
  1. Anda dapat menipu beberapa orang sepanjang waktu.
    🔗
    🔗
  2. Anda dapat menipu semua orang pada suatu waktu.
    🔗
    🔗
  3. Anda selalu dapat menipu beberapa orang.
    🔗
    🔗
  4. Kadang-kadang Anda dapat menipu semua orang.
    🔗
    🔗
🔗
🔗

14.

Misalkan \(P(x)\) adalah suatu predikat sehingga pernyataan \(\forall x P(x)\) benar. Apakah \(\exists x P(x)\) juga benar? Dengan kata lain, apakah pernyataan \(\forall x P(x) \imp \exists x P(x)\) selalu benar? Apakah konversnya selalu benar? Asumsikan semesta pembicaraannya tidak kosong.
🔗
Petunjuk.
Cobalah sebuah contoh. Bagaimana jika \(P(x)\) adalah predikat “\(x\) merupakan bilangan prima”? Bagaimana jika predikatnya adalah “Jika \(x\) habis dibagi 4, maka bilangan itu genap”? Tentu saja, contoh tidak cukup untuk membuktikan sesuatu secara umum, tetapi justru itulah inti pertanyaan ini.
🔗
🔗
🔗

15.

Menyederhanakan negasi akan sangat berguna ketika kita mencoba membuktikan suatu pernyataan dengan mempertimbangkan apa yang terjadi jika pernyataan itu salah. Untuk setiap pernyataan di bawah ini, tuliskan negasi-nya dalam bentuk sesederhana mungkin. Jangan hanya mengatakan, “Tidak benar bahwa …”
  1. Setiap bilangan merupakan bilangan genap atau ganjil.
    🔗
    🔗
  2. Ada suatu barisan yang sekaligus merupakan barisan aritmetika dan geometri.
    🔗
    🔗
  3. Untuk setiap bilangan \(n\text{,}\) jika \(n\) prima, maka \(n+3\) tidak prima.
    🔗
    🔗
🔗
Petunjuk.
Mungkin akan membantu jika pernyataan-pernyataan tersebut dinyatakan dengan simbol, lalu aturan-aturan formal digunakan untuk menyederhanakan negasi (yaitu aturan untuk kuantor dan hukum De Morgan). Setelah disederhanakan, untuk pernyataan pertama, misalnya, Anda seharusnya memperoleh \(\forall x(\neg E(x) \wedge \neg O(x))\text{.}\) Kemudian nyatakan kembali hasilnya dalam bahasa Indonesia.
🔗
🔗
🔗

16.

Kita dapat menyederhanakan pernyataan dalam logika predikat dengan menggunakan aturan untuk memindahkan negasi melewati kuantor sebelum menerapkan ekuivalensi logis pada bagian proposisional di “dalamnya”. Sederhanakan pernyataan-pernyataan di bawah ini (sehingga negasi hanya muncul tepat di sebelah predikat).
  1. \(\neg \exists x \forall y (\neg O(x) \vee E(y))\text{.}\)
    🔗
  2. \(\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))\text{.}\)
    🔗
  3. Ada suatu bilangan \(n\) sehingga tidak ada bilangan lain yang kurang dari atau sama dengan \(n\text{.}\)
    🔗
    🔗
  4. Tidak benar bahwa untuk setiap bilangan \(n\) terdapat dua bilangan lain yang mengapit \(n\text{.}\)
    🔗
    🔗
🔗
🔗

17.

Sederhanakan pernyataan-pernyataan di bawah ini hingga simbol negasi hanya muncul tepat di sebelah predikat.
  1. \(\neg \forall x \forall y (x \lt y \vee y \lt x)\text{.}\)
    🔗
    🔗
  2. \(\neg(\exists x P(x) \imp \forall y P(y))\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik