Logik proposisi & pembuktian: soalan latihan dengan penyelesaian langkah demi langkah
Soalan latihan Logik proposisi & pembuktian percuma dengan rajah, petunjuk dan penyelesaian lengkap. Nilai baharu setiap kali, pada tiga tahap: jadual kebenaran, kesetaraan dan kaedah pembuktian, pengkuantiti dan hujah.
Soalan latihan percumaMudah
Lengkapkan jadual kebenaran (1 = benar, 0 = palsu). Dalam berapa baris N adakah (p → r) ↔ (r ∨ q) benar?
Proposisi ialah pernyataan yang sama ada benar atau palsu, seperti “7 ialah nombor perdana”. Kita menulisnya dengan huruf, p atau q, dan nilai kebenarannya sebagai 1 (benar) atau 0 (palsu).
Penghubung membina formula yang lebih besar daripada yang lebih kecil:
¬p (bukan p) menyongsangkan nilai.
p ∧ q (dan) ialah 1 hanya apabila kedua-duanya 1.
p ∨ q (atau) ialah 0 hanya apabila kedua-duanya 0. Ia ialah atau inklusif: kedua-duanya boleh benar.
p → q (jika p maka q) ialah 0 hanya apabila p = 1 dan q = 0.
p ↔ q (jika dan hanya jika) ialah 1 apabila p dan q mempunyai nilai yang sama.
Implikasi mengejutkan ramai pelajar: apabila p palsu, p → q benar walau apa pun q. Janji “jika hujan, saya bawa payung” hanya dimungkiri pada hari hujan tanpa payung.
Semakan kendiri p = 0 dan q = 1. Apakah nilai p → q?
0
1
Bergantung pada konteks
Tidak ditakrifkan
Jawapan: 1. Implikasi hanya palsu apabila syarat dipenuhi dan kesimpulan gagal (p = 1, q = 0). Dengan p = 0 ia benar, walau apa pun q.
2Jadual kebenaran
Jadual kebenaran menyenaraikan setiap gabungan nilai kebenaran pemboleh ubah. Dengan n pemboleh ubah berbeza terdapat 2ⁿ baris: 4 untuk dua pemboleh ubah, 8 untuk tiga, 16 untuk empat. Pemboleh ubah yang muncul dua kali tetap dikira sekali.
Bekerja dari dalam ke luar. Beri setiap subformula lajurnya sendiri, supaya setiap lajur baharu hanya memerlukan satu penghubung dikenakan pada lajur yang sudah anda ada.
Senaraikan pemboleh ubah dan tulis semua 2ⁿ gabungan, bermula dengan semua 1.
Tambah satu lajur untuk setiap subformula, yang paling dalam dahulu.
Isi setiap lajur menggunakan peraturan penghubung utamanya.
Baca jawapan daripada lajur terakhir: kira 1, atau cari baris yang diminta.
Semakan kendiri Berapa banyak baris yang ada pada jadual kebenaran (p ∧ q) → (r ∨ p)?
16
4
6
8
Jawapan: 8. Formula itu mempunyai tiga pemboleh ubah berbeza, p, q dan r, maka 2³ = 8 baris. p muncul dua kali tetapi ialah satu pemboleh ubah; 16 ialah 2⁴ untuk empat kemunculan.
3Contoh terselesai
Ikuti setiap langkah. Cuba ramalkan langkah seterusnya sebelum anda membukanya.
Contoh terselesai
Dalam berapa baris jadual kebenarannya (p → q) ∧ ¬q benar?
1
Pemboleh ubah dan baris
Dua pemboleh ubah, p dan q, maka 4 baris: (1, 1), (1, 0), (0, 1), (0, 0).
2
Lajur p → q
Ia 0 hanya dalam baris p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Lajur ¬q
¬q: 0, 1, 0, 1
4
Konjungsi
Kedua-dua lajur mestilah 1. Itu hanya berlaku dalam baris terakhir, p = 0 dan q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Jawapan
Formula itu benar dalam 1 baris, iaitu baris p = 0, q = 0. Inilah sebabnya p → q dan ¬q bersama-sama memberi ¬p (modus tollens).
4Kesetaraan dan kaedah pembuktian
Dua formula adalah setara (≡) apabila lajur jadual kebenaran keduanya serupa. Tautologi ialah 1 dalam setiap baris, percanggahan ialah 0 dalam setiap baris, dan kontingensi bukan kedua-duanya.
Hukum yang paling kerap anda gunakan:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Hukum-hukum ini ialah asas kaedah pembuktian. Pembuktian secara kontrapositif bagi p → q membuktikan ¬q → ¬p sebagai gantinya, yang setara. Pembuktian secara percanggahan mengandaikan p ∧ ¬q, satu-satunya cara implikasi itu boleh gagal, dan menghasilkan sesuatu yang mustahil.
Berhati-hati: akas q → p dan songsangan ¬p → ¬q tidak setara dengan p → q.
Semakan kendiri Formula manakah yang setara dengan ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Jawapan: ¬p ∨ ¬q. Menurut De Morgan, ∧ menjadi ∨ dan kedua-dua bahagian dinafikan. ¬p ∧ ¬q ialah penafian p ∨ q, pernyataan yang berbeza: ia palsu apabila tepat satu daripada p dan q benar, sedangkan ¬(p ∧ q) benar.
5Pengkuantiti dan hujah yang sah
Dengan pemboleh ubah pada suatu domain, ∀x P(x) bermaksud “P benar untuk setiap x” dan ∃x P(x) bermaksud “P benar untuk sekurang-kurangnya satu x”. Penafian menukar pengkuantiti:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Alihkan penafian ke dalam satu langkah pada satu masa; di dalamnya, gunakan hukum proposisi. Contohnya ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): “bukan setiap P ialah Q” bermaksud “ada P yang bukan Q”.
Hujah adalah sah apabila kesimpulan ialah 1 dalam setiap baris yang semua premisnya 1. Bentuk sah yang klasik ialah modus ponens (p → q, p, maka q), modus tollens (p → q, ¬q, maka ¬p) dan silogisme hipotesis (p → q, q → r, maka p → r).
Baris yang semua premisnya 1 dan kesimpulannya 0 ialah contoh penyangkal. Mengesahkan akibat (p → q, q, maka p) adalah tidak sah: baris p = 0, q = 1 ialah contoh penyangkal.
Semakan kendiri Apakah penafian bagi “setiap pelajar lulus”, ∀x P(x)?
¬P(x) untuk seorang pelajar x yang tertentu
∀x ¬P(x): tiada pelajar yang lulus
∃x P(x): ada pelajar yang lulus
∃x ¬P(x): ada pelajar yang tidak lulus
Jawapan: ∃x ¬P(x): ada pelajar yang tidak lulus. Seorang pelajar yang gagal sudah memadai untuk menjadikan “setiap pelajar lulus” palsu. “Tiada pelajar yang lulus” jauh lebih kuat daripada penafian.
6Kesilapan lazim
Menganggap p → q palsu apabila p palsu. Ia hanya palsu apabila p = 1 dan q = 0.
Mengira pemboleh ubah yang berulang dua kali semasa mencari bilangan baris.
Mengelirukan kontrapositif ¬q → ¬p dengan akas q → p atau songsangan ¬p → ¬q.
Menafikan ∀x P(x) sebagai ∀x ¬P(x): pengkuantiti mesti bertukar kepada ∃.
Menulis ¬(p ∧ q) sebagai ¬p ∧ ¬q: De Morgan juga menukar penghubung.
Semakan kendiri Pernyataan manakah kontrapositif bagi “jika n² genap, maka n genap”?
Jika n ganjil, maka n² ganjil
Jika n genap, maka n² genap
Jika n² ganjil, maka n ganjil
n² genap dan n ganjil
Jawapan: Jika n ganjil, maka n² ganjil. Tukar kedudukan kedua-dua bahagian dan nafikan kedua-duanya: bukan (n genap) → bukan (n² genap). “Jika n genap, maka n² genap” ialah akas; pilihan terakhir ialah apa yang diandaikan dalam pembuktian secara percanggahan.
7Rupa soalan peperiksaan
Mudah: jadual kebenaran. Anda mencari bilangan baris, mengira baris yang formulanya benar, atau mengklik satu baris yang menjadikan formula benar atau palsu.
Sederhana: kesetaraan dan kaedah pembuktian. Anda menentukan sama ada formula ialah tautologi, percanggahan atau kontingensi, memilih formula yang setara, atau pernyataan yang hendak dibuktikan dalam pembuktian secara kontrapositif atau percanggahan.
Sukar: pengkuantiti dan hujah. Anda menafikan pernyataan berpengkuantiti, memilih kesimpulan yang terhasil daripada premis, mengklik baris contoh penyangkal bagi hujah yang tidak sah, atau mengira baris benar dalam jadual empat pemboleh ubah.
Tepat satu baris jadual kebenaran menjadikan ¬(p ∨ q) → q palsu. Klik baris itu.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Tunjukkan petunjuk
a → b ialah 0 hanya apabila a = 1 dan b = 0. ¬a menyongsangkan nilai. a ∨ b ialah 0 hanya apabila kedua-duanya 0.
Cari penghubung utama dahulu: apakah yang mesti menjadi kedua-dua belahnya supaya keseluruhan formula ialah 0?
Beri setiap bahagian lajurnya sendiri: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Tunjukkan jawapan dan penerangan
Jadual kebenaran: formula dengan n pemboleh ubah berbeza mempunyai 2ⁿ baris, satu untuk setiap gabungan nilai kebenaran (1 = benar, 0 = palsu). Bekerja dari dalam ke luar dan beri setiap subformula lajurnya sendiri. ¬a menyongsangkan nilai; a ∧ b ialah 1 hanya apabila kedua-duanya 1; a ∨ b ialah 0 hanya apabila kedua-duanya 0; a → b ialah 0 hanya apabila a = 1 dan b = 0; a ↔ b ialah 1 apabila kedua-dua belah sama.
Formula manakah yang setara secara logik dengan (b ∧ c) → a? Klik formula itu.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Tunjukkan petunjuk
Formula yang setara bersetuju dalam setiap baris jadual kebenaran. Satu baris yang keduanya berbeza menyingkirkan sesuatu pilihan.
Cuba baris yang menjadikan (b ∧ c) → a 0 dan semak pilihan mana yang juga 0 di situ.
Eksportasi: (a ∧ b) → c ≡ a → (b → c). Kedua-duanya 0 hanya apabila a = 1, b = 1 dan c = 0.
Tunjukkan jawapan dan penerangan
Kesetaraan logik: dua formula adalah setara (≡) apabila ia mempunyai nilai yang sama dalam setiap baris jadual kebenaran. Tautologi ialah 1 dalam setiap baris, percanggahan ialah 0 dalam setiap baris, dan kontingensi bukan kedua-duanya. Hukum yang berguna: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b dan ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (kontrapositif); ¬(a → b) ≡ a ∧ ¬b; dan hukum agihan, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Hukum
Eksportasi: (a ∧ b) → c ≡ a → (b → c). Kedua-duanya 0 hanya apabila a = 1, b = 1 dan c = 0.
(b ∧ c) → a ≡ b → (c → a)
Semak dengan jadual kebenaran
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Jawapan
b → (c → a)
Lajur selepas palang ialah pilihan mengikut susunan yang ditunjukkan.
Contoh 3Sukar
Premis (q ∧ p) → r; q; ¬r diberikan. Kesimpulan manakah yang terhasil daripadanya? Klik kesimpulan itu.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Tunjukkan petunjuk
Sesuatu kesimpulan terhasil apabila ia 1 dalam setiap baris yang semua premisnya 1.
Cari baris yang menjadikan semua premis 1, kemudian uji setiap pilihan dalam baris itu.
Ini ialah peraturan piawai: modus tollens dengan konjungsi.
Tunjukkan jawapan dan penerangan
Pengkuantiti dan hujah: ¬∀x P(x) ≡ ∃x ¬P(x) dan ¬∃x P(x) ≡ ∀x ¬P(x). Alihkan penafian ke dalam, tukar setiap pengkuantiti yang dilaluinya, dan nafikan formula di dalam dengan hukum proposisi, seperti ¬(a → b) ≡ a ∧ ¬b. Hujah adalah sah apabila kesimpulan ialah 1 dalam setiap baris yang semua premisnya 1. Satu baris dengan premis benar dan kesimpulan palsu ialah contoh penyangkal dan menunjukkan hujah itu tidak sah.
Baris dengan semua premis benar
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Kesimpulan
¬p (modus tollens dengan konjungsi)
Jawapan
¬p
Soalan dan jawapan
Apakah Logik proposisi & pembuktian?
Penghubung membina formula yang lebih besar daripada yang lebih kecil:
Implikasi mengejutkan ramai pelajar: apabila p palsu, p → q benar walau apa pun q. Janji “jika hujan, saya bawa payung” hanya dimungkiri pada hari hujan tanpa payung.
Kira bilangan pemboleh ubah yang berbeza: jadual kebenaran mempunyai 2ⁿ baris, bermula dengan kesemuanya 1.
Beri setiap subformula lajurnya sendiri dan isi lajur-lajur itu dari dalam ke luar.
Gunakan peraturan setiap penghubung: → hanya 0 bagi 1 → 0, ↔ ialah 1 apabila kedua-dua belah sepadan.
Untuk kesetaraan, bandingkan lajur akhir baris demi baris; untuk hujah, lihat hanya baris yang setiap premisnya 1.
Untuk menafikan pernyataan berpengkuantiti, alihkan ¬ ke dalam, tukar ∀ dan ∃, dan nafikan formula di dalamnya.
Apakah kesilapan lazim dalam Logik proposisi & pembuktian?
Menganggap p → q palsu apabila p palsu.
Mengira pemboleh ubah yang berulang dua kali semasa mencari bilangan baris.
Mengelirukan kontrapositif ¬q → ¬p dengan akas q → p.
Menafikan ∀x P(x) sebagai ∀x ¬P(x) dan bukan ∃x ¬P(x).
Menggunakan De Morgan tanpa menukar ∧ dan ∨.
Apakah yang diliputi oleh latihan Logik proposisi & pembuktian?
Mudah: jadual kebenaran
Sederhana: kesetaraan dan kaedah pembuktian
Sukar: pengkuantiti dan hujah
Setiap soalan mempunyai nilai baharu, jadi anda mempelajari kaedah dan bukannya jawapan. Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.
Cara latihan berfungsi
Setiap soalan mempunyai nilai baharu, jadi anda mempelajari kaedah dan bukannya jawapan.
Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.
Kemajuan, kesilapan dan soalan tersimpan anda dikekalkan, jadi anda boleh menyemak sebelum peperiksaan.