Matematika SMA/MA/SMK/MAK
Kontradiksi, Tautologi, dan Pernyataan Majemuk yang Ekuivalen
A. Tautologi
Pengertian Tautologi
Tautologi adalah pernyataan majemuk yang selalu bernilai benar (B) untuk setiap kemungkinan nilai kebenaran dari pernyataan-pernyataan penyusunnya.
Dengan kata lain, pada tabel kebenaran suatu tautologi, kolom terakhir (hasil) seluruhnya bernilai B (Benar), tidak ada yang bernilai S (Salah).
Perhatikan pernyataan berikut:
“Hari ini hujan atau hari ini tidak hujan”
Dalam simbol logika: p ∨ ~p
Apapun keadaannya, pernyataan ini selalu benar. Inilah yang disebut tautologi.
Bagaimana cara membuktikan suatu pernyataan majemuk adalah tautologi? Apakah cukup dengan contoh, atau harus dibuktikan untuk semua kemungkinan?
Untuk membuktikan tautologi, kita harus memeriksa semua kemungkinan nilai kebenaran menggunakan tabel kebenaran. Jika semua baris menghasilkan nilai B, maka terbukti tautologi.
Pembuktian dengan Tabel Kebenaran
Buktikan bahwa p ∨ ~p adalah tautologi:
| p | ~p | p ∨ ~p |
|---|---|---|
| B | S | B |
| S | B | B |
✓ Semua hasil bernilai B, maka p ∨ ~p adalah tautologi.
Buktikan bahwa p → (p ∨ q) adalah tautologi dengan membuat tabel kebenaran lengkap.
Contoh-contoh Tautologi yang Penting
- p ∨ ~p (Hukum Eksklusi Tengah)
- ~(p ∧ ~p) (Hukum Non-Kontradiksi)
- p → p
- (p ∧ q) → p
- p → (p ∨ q)
- (p → q) ↔ (~q → ~p) (Kontraposisi)
Tautologi dilambangkan dengan t atau T. Jika suatu pernyataan majemuk P adalah tautologi, kita tulis P ≡ T atau cukup menyebut P adalah tautologi.
Contoh Soal Tautologi
● Tingkat Mudah
Buktikan bahwa p → p adalah tautologi!
Pembahasan:
| p | p → p |
|---|---|
| B | B |
| S | B |
Ingat: implikasi p → q bernilai S hanya jika p = B dan q = S. Karena p → p berarti anteseden dan konsekuen sama, maka tidak mungkin p = B dan p = S sekaligus. Semua baris bernilai B, terbukti tautologi. ✓
Buktikan bahwa ~(p ∧ ~p) adalah tautologi!
Pembahasan:
| p | ~p | p ∧ ~p | ~(p ∧ ~p) |
|---|---|---|---|
| B | S | S | B |
| S | B | S | B |
p dan ~p selalu berlawanan, sehingga konjungsinya selalu S. Negasi dari S selalu B. Terbukti tautologi. ✓
Buktikan bahwa (p ∧ q) → p adalah tautologi!
Pembahasan:
| p | q | p ∧ q | (p ∧ q) → p |
|---|---|---|---|
| B | B | B | B |
| B | S | S | B |
| S | B | S | B |
| S | S | S | B |
Ketika p ∧ q = B, pasti p = B, sehingga implikasi B → B = B. Ketika p ∧ q = S, implikasi S → apapun = B. Terbukti tautologi. ✓
Buktikan bahwa p → (p ∨ q) adalah tautologi!
Pembahasan:
| p | q | p ∨ q | p → (p ∨ q) |
|---|---|---|---|
| B | B | B | B |
| B | S | B | B |
| S | B | B | B |
| S | S | S | B |
Jika p = B, maka p ∨ q pasti B (karena salah satu sudah B), sehingga B → B = B. Jika p = S, maka S → apapun = B. Terbukti tautologi. ✓
Tentukan apakah p ∨ q merupakan tautologi atau bukan!
Pembahasan:
| p | q | p ∨ q |
|---|---|---|
| B | B | B |
| B | S | B |
| S | B | B |
| S | S | S |
Ada baris yang bernilai S (baris terakhir), maka p ∨ q bukan tautologi. ✓
● Tingkat Sedang
Buktikan bahwa (p → q) ∨ (q → p) adalah tautologi!
Pembahasan:
| p | q | p → q | q → p | (p→q) ∨ (q→p) |
|---|---|---|---|---|
| B | B | B | B | B |
| B | S | S | B | B |
| S | B | B | S | B |
| S | S | B | B | B |
Semua baris bernilai B. Ini karena jika p → q bernilai S (p=B, q=S), maka q → p bernilai B (S → B = B), dan sebaliknya. Terbukti tautologi. ✓
Buktikan bahwa [(p → q) ∧ p] → q adalah tautologi! (Modus Ponens)
Pembahasan:
| p | q | p → q | (p→q) ∧ p | [(p→q) ∧ p] → q |
|---|---|---|---|---|
| B | B | B | B | B |
| B | S | S | S | B |
| S | B | B | S | B |
| S | S | B | S | B |
Ini adalah hukum Modus Ponens: jika kita tahu p → q benar dan p benar, maka q pasti benar. Semua baris bernilai B, terbukti tautologi. ✓
Buktikan bahwa [(p → q) ∧ ~q] → ~p adalah tautologi! (Modus Tollens)
Pembahasan:
| p | q | ~p | ~q | p→q | (p→q)∧~q | [(p→q)∧~q]→~p |
|---|---|---|---|---|---|---|
| B | B | S | S | B | S | B |
| B | S | S | B | S | S | B |
| S | B | B | S | B | S | B |
| S | S | B | B | B | B | B |
Modus Tollens: jika p → q dan ~q, maka ~p. Satu-satunya baris di mana (p→q)∧~q = B adalah baris terakhir, dan di situ ~p = B, sehingga implikasinya B → B = B. Baris lain memiliki anteseden S. Terbukti tautologi. ✓
Buktikan bahwa (p ∧ (p → q)) → q adalah tautologi!
Pembahasan:
| p | q | p → q | p ∧ (p→q) | [p∧(p→q)]→q |
|---|---|---|---|---|
| B | B | B | B | B |
| B | S | S | S | B |
| S | B | B | S | B |
| S | S | B | S | B |
Semua bernilai B. Terbukti tautologi. ✓
Buktikan bahwa [(p → q) ∧ (q → r)] → (p → r) adalah tautologi! (Silogisme Hipotetis)
Pembahasan:
| p | q | r | p→q | q→r | (p→q)∧(q→r) | p→r | Hasil |
|---|---|---|---|---|---|---|---|
| B | B | B | B | B | B | B | B |
| B | B | S | B | S | S | S | B |
| B | S | B | S | B | S | B | B |
| B | S | S | S | B | S | S | B |
| S | B | B | B | B | B | B | B |
| S | B | S | B | S | S | B | B |
| S | S | B | B | B | B | B | B |
| S | S | S | B | B | B | B | B |
Kolom “Hasil” = [(p→q)∧(q→r)] → (p→r). Semua bernilai B. Ini adalah Silogisme Hipotetis: jika p menyebabkan q dan q menyebabkan r, maka p menyebabkan r. Terbukti tautologi. ✓
● Tingkat Sulit
Buktikan bahwa [(p → q) ∧ (r → s) ∧ (p ∨ r)] → (q ∨ s) adalah tautologi! (Silogisme Destruktif)
Pembahasan:
Kita gunakan penalaran logis:
- Misalkan anteseden bernilai B, artinya: p→q = B, r→s = B, dan p∨r = B
- Dari p∨r = B, setidaknya salah satu dari p atau r bernilai B
- Kasus 1: p = B. Karena p→q = B dan p = B, maka q = B. Sehingga q∨s = B ✓
- Kasus 2: r = B. Karena r→s = B dan r = B, maka s = B. Sehingga q∨s = B ✓
- Jadi jika anteseden = B, konsekuen pasti B. Implikasi selalu B.
- Jika anteseden = S, implikasi otomatis B.
Dengan demikian semua kemungkinan menghasilkan B. Terbukti tautologi. ✓
Buktikan bahwa [~(p ∧ q)] ↔ (~p ∨ ~q) adalah tautologi! (Hukum De Morgan)
Pembahasan:
| p | q | p∧q | ~(p∧q) | ~p | ~q | ~p∨~q | Biimplikasi |
|---|---|---|---|---|---|---|---|
| B | B | B | S | S | S | S | B |
| B | S | S | B | S | B | B | B |
| S | B | S | B | B | S | B | B |
| S | S | S | B | B | B | B | B |
Biimplikasi bernilai B jika kedua sisi sama nilainya. Kolom ~(p∧q) dan ~p∨~q selalu sama. Terbukti tautologi. ✓
Buktikan bahwa [(p → q) ∧ (p → r)] ↔ [p → (q ∧ r)] adalah tautologi!
Pembahasan:
| p | q | r | p→q | p→r | (p→q)∧(p→r) | q∧r | p→(q∧r) | ↔ |
|---|---|---|---|---|---|---|---|---|
| B | B | B | B | B | B | B | B | B |
| B | B | S | B | S | S | S | S | B |
| B | S | B | S | B | S | S | S | B |
| B | S | S | S | S | S | S | S | B |
| S | B | B | B | B | B | B | B | B |
| S | B | S | B | B | B | S | B | B |
| S | S | B | B | B | B | S | B | B |
| S | S | S | B | B | B | S | B | B |
Kolom biimplikasi selalu B. Terbukti tautologi. ✓
Buktikan bahwa [(p ∨ q) ∧ ~p] → q adalah tautologi! (Silogisme Disjungtif)
Pembahasan:
| p | q | p∨q | ~p | (p∨q)∧~p | [(p∨q)∧~p]→q |
|---|---|---|---|---|---|
| B | B | B | S | S | B |
| B | S | B | S | S | B |
| S | B | B | B | B | B |
| S | S | S | B | S | B |
Satu-satunya baris di mana anteseden B adalah baris 3 (p=S, q=B), dan di situ q=B sehingga implikasinya B→B=B. Baris lain memiliki anteseden S. Terbukti tautologi. ✓
Buktikan bahwa [(p → q) ∧ (q → r) ∧ ~r] → ~p adalah tautologi!
Pembahasan:
Penalaran logis:
- Misalkan anteseden bernilai B: p→q = B, q→r = B, ~r = B (artinya r = S)
- Dari q→r = B dan r = S: agar implikasi tetap B, harus q = S (karena B→S = S, tidak cocok)
- Dari p→q = B dan q = S: agar implikasi tetap B, harus p = S (karena B→S = S, tidak cocok)
- Jadi p = S, artinya ~p = B
- Maka implikasi keseluruhan: B → B = B ✓
- Jika anteseden = S, maka implikasi otomatis B ✓
Semua kemungkinan menghasilkan B. Ini merupakan gabungan Modus Tollens berantai. Terbukti tautologi. ✓
Latihan Soal Tautologi
Kerjakan soal-soal berikut dengan membuat tabel kebenaran!
● Mudah
- Buktikan bahwa p → (q → p) adalah tautologi!
- Buktikan bahwa (p ∧ q) → (p ∨ q) adalah tautologi!
- Buktikan bahwa ~p → (p → q) adalah tautologi!
- Tentukan apakah p → (p ∧ q) merupakan tautologi atau bukan!
- Buktikan bahwa (p → q) ∨ p bukan tautologi! (Tunjukkan baris bernilai S)
● Sedang
- Buktikan bahwa [(p → q) ∧ (r → q)] → [(p ∨ r) → q] adalah tautologi!
- Buktikan bahwa (p → q) ↔ (~p ∨ q) adalah tautologi!
- Buktikan bahwa [p → (q → r)] ↔ [(p ∧ q) → r] adalah tautologi!
- Buktikan bahwa (p ↔ q) → (p → q) adalah tautologi!
- Buktikan bahwa [(p ∨ q) ∧ (~p ∨ r)] → (q ∨ r) adalah tautologi!
● Sulit
- Buktikan bahwa [(p → q) ∧ (~p → r) ∧ (q → s) ∧ (r → s)] → s adalah tautologi!
- Buktikan bahwa {[(p ∨ q) → r] ∧ ~r} → (~p ∧ ~q) adalah tautologi!
- Buktikan bahwa [(p ↔ q) ∧ (q ↔ r)] → (p ↔ r) adalah tautologi!
- Buktikan bahwa ~[(p → q) → p] → ~p adalah tautologi!
- Buktikan bahwa [(p → q) ∨ (p → r)] ↔ [p → (q ∨ r)] adalah tautologi!
B. Kontradiksi
Pengertian Kontradiksi
Kontradiksi adalah pernyataan majemuk yang selalu bernilai salah (S) untuk setiap kemungkinan nilai kebenaran dari pernyataan-pernyataan penyusunnya.
Pada tabel kebenaran suatu kontradiksi, kolom terakhir (hasil) seluruhnya bernilai S (Salah).
Kontradiksi merupakan kebalikan dari tautologi. Jika P adalah tautologi, maka ~P adalah kontradiksi, dan sebaliknya.
Perhatikan pernyataan berikut:
“Hari ini hujan dan hari ini tidak hujan”
Dalam simbol logika: p ∧ ~p
Tidak mungkin hujan dan tidak hujan terjadi bersamaan. Pernyataan ini selalu salah. Inilah yang disebut kontradiksi.
Apa hubungan antara tautologi dan kontradiksi? Bagaimana jika suatu pernyataan bukan tautologi maupun kontradiksi?
Hubungan tautologi dan kontradiksi:
- Jika P adalah tautologi, maka ~P adalah kontradiksi
- Jika P adalah kontradiksi, maka ~P adalah tautologi
- Jika P bukan tautologi dan bukan kontradiksi, maka P disebut kontingensi (kadang B, kadang S)
Pembuktian dengan Tabel Kebenaran
Buktikan bahwa p ∧ ~p adalah kontradiksi:
| p | ~p | p ∧ ~p |
|---|---|---|
| B | S | S |
| S | B | S |
✓ Semua hasil bernilai S, maka p ∧ ~p adalah kontradiksi.
Buktikan bahwa (p ∧ q) ∧ (~p ∨ ~q) ∧ (p ∨ q) bukan kontradiksi dengan menemukan baris yang bernilai S dan B.
Kontradiksi dilambangkan dengan f atau F. Jika suatu pernyataan majemuk P adalah kontradiksi, kita tulis P ≡ F. Sifat penting: negasi kontradiksi adalah tautologi, yaitu ~F ≡ T.
Contoh-contoh Kontradiksi yang Penting
- p ∧ ~p
- (p → q) ∧ p ∧ ~q
- (p ↔ q) ∧ (p ∧ ~q)
- ~(p → p)
Contoh Soal Kontradiksi
● Tingkat Mudah
Buktikan bahwa ~(p → p) adalah kontradiksi!
Pembahasan:
| p | p → p | ~(p → p) |
|---|---|---|
| B | B | S |
| S | B | S |
p → p adalah tautologi (selalu B), maka negasinya selalu S. Terbukti kontradiksi. ✓
Buktikan bahwa (p ∨ ~p) ∧ ~(p ∨ ~p) adalah kontradiksi!
Pembahasan:
Misalkan A = p ∨ ~p (yang merupakan tautologi, selalu B).
Maka pernyataan menjadi: A ∧ ~A, yang berbentuk X ∧ ~X = kontradiksi.
| p | p∨~p | ~(p∨~p) | (p∨~p) ∧ ~(p∨~p) |
|---|---|---|---|
| B | B | S | S |
| S | B | S | S |
Terbukti kontradiksi. ✓
Tentukan apakah p ∧ ~q merupakan kontradiksi atau bukan!
Pembahasan:
| p | q | ~q | p ∧ ~q |
|---|---|---|---|
| B | B | S | S |
| B | S | B | B |
| S | B | S | S |
| S | S | B | S |
Ada baris yang bernilai B (baris 2), maka p ∧ ~q bukan kontradiksi (ini adalah kontingensi). ✓
Buktikan bahwa ~(p ∨ ~p) adalah kontradiksi!
Pembahasan:
| p | ~p | p ∨ ~p | ~(p ∨ ~p) |
|---|---|---|---|
| B | S | B | S |
| S | B | B | S |
p ∨ ~p selalu B (tautologi), negasinya selalu S. Terbukti kontradiksi. ✓
Buktikan bahwa (p → q) ∧ (p ∧ ~q) adalah kontradiksi!
Pembahasan:
| p | q | ~q | p→q | p∧~q | (p→q)∧(p∧~q) |
|---|---|---|---|---|---|
| B | B | S | B | S | S |
| B | S | B | S | B | S |
| S | B | S | B | S | S |
| S | S | B | B | S | S |
Semua baris bernilai S. Logikanya: p→q berarti “jika p maka q”, sedangkan p∧~q berarti “p benar dan q salah”. Keduanya tidak bisa benar bersamaan. Terbukti kontradiksi. ✓
● Tingkat Sedang
Buktikan bahwa (p ↔ q) ∧ (p ∧ ~q) adalah kontradiksi!
Pembahasan:
| p | q | p↔q | ~q | p∧~q | (p↔q)∧(p∧~q) |
|---|---|---|---|---|---|
| B | B | B | S | S | S |
| B | S | S | B | B | S |
| S | B | S | S | S | S |
| S | S | B | B | S | S |
p↔q berarti p dan q bernilai sama. p∧~q berarti p=B dan q=S (berbeda). Keduanya tidak bisa sekaligus benar. Terbukti kontradiksi. ✓
Buktikan bahwa (p → q) ∧ (p → ~q) ∧ p adalah kontradiksi!
Pembahasan:
| p | q | p→q | p→~q | (p→q)∧(p→~q)∧p |
|---|---|---|---|---|
| B | B | B | S | S |
| B | S | S | B | S |
| S | B | B | B | S |
| S | S | B | B | S |
Jika p=B: p→q mengharuskan q=B, tetapi p→~q mengharuskan q=S. Kontradiksi! Jika p=S: konjungsi dengan p=S menghasilkan S. Terbukti kontradiksi. ✓
Buktikan bahwa [(p ∨ q) ∧ ~p ∧ ~q] adalah kontradiksi!
Pembahasan:
| p | q | p∨q | ~p | ~q | (p∨q)∧~p∧~q |
|---|---|---|---|---|---|
| B | B | B | S | S | S |
| B | S | B | S | B | S |
| S | B | B | B | S | S |
| S | S | S | B | B | S |
p∨q mengharuskan setidaknya salah satu B, tetapi ~p∧~q mengharuskan keduanya S. Kontradiksi! ✓
Buktikan bahwa (p ↔ ~p) adalah kontradiksi!
Pembahasan:
| p | ~p | p ↔ ~p |
|---|---|---|
| B | S | S |
| S | B | S |
Biimplikasi bernilai B hanya jika kedua sisi sama. Tetapi p dan ~p selalu berbeda. Selalu S. Terbukti kontradiksi. ✓
Buktikan bahwa ~[(p → q) ∨ (q → p)] adalah kontradiksi!
Pembahasan:
Kita sudah buktikan sebelumnya bahwa (p→q) ∨ (q→p) adalah tautologi (selalu B).
Maka negasinya selalu S.
| p | q | (p→q)∨(q→p) | ~[(p→q)∨(q→p)] |
|---|---|---|---|
| B | B | B | S |
| B | S | B | S |
| S | B | B | S |
| S | S | B | S |
Terbukti kontradiksi. ✓
● Tingkat Sulit
Buktikan bahwa (p → q) ∧ (q → r) ∧ p ∧ ~r adalah kontradiksi!
Pembahasan:
Penalaran logis:
- Misalkan seluruh konjungsi = B. Maka setiap komponen harus B.
- p = B (dari komponen p)
- ~r = B, berarti r = S
- p→q = B dan p = B, maka q = B
- q→r = B dan q = B, maka r = B
- Kontradiksi! r = S dan r = B tidak bisa bersamaan.
Tidak ada kemungkinan yang membuat seluruhnya B. Maka selalu S. Terbukti kontradiksi. ✓
Buktikan bahwa [(p ↔ q) ∧ (q ↔ r) ∧ p ∧ ~r] adalah kontradiksi!
Pembahasan:
- Misalkan seluruh konjungsi = B.
- p = B dan ~r = B (artinya r = S)
- p↔q = B dan p = B, maka q = B
- q↔r = B dan q = B, maka r = B
- Kontradiksi! r = S dan r = B bersamaan.
Tidak ada kemungkinan yang memenuhi. Terbukti kontradiksi. ✓
Buktikan bahwa ~{[(p ∧ q) → p] ∨ [p → (p ∨ q)]} adalah kontradiksi!
Pembahasan:
Kita tahu:
- (p∧q)→p adalah tautologi (selalu B)
- p→(p∨q) adalah tautologi (selalu B)
- Disjungsi dua tautologi = tautologi (B∨B = B)
- Negasi tautologi = kontradiksi (selalu S)
Terbukti kontradiksi. ✓
Buktikan bahwa [(p → q) ∧ (~p → q) ∧ ~q] adalah kontradiksi!
Pembahasan:
- Misalkan seluruh konjungsi = B. Maka ~q = B, artinya q = S.
- p→q = B dan q = S, maka p harus S (agar tidak B→S).
- ~p→q = B. Karena p = S, maka ~p = B. Maka B→q = B→S = S. Kontradiksi!
Tidak ada kemungkinan yang membuat semuanya B. Terbukti kontradiksi. ✓
Buktikan bahwa [(p ∨ q) ∧ (p → r) ∧ (q → r) ∧ ~r] adalah kontradiksi!
Pembahasan:
- Misalkan seluruh konjungsi = B. Maka ~r = B, artinya r = S.
- p→r = B dan r = S, maka p = S (agar tidak B→S).
- q→r = B dan r = S, maka q = S (agar tidak B→S).
- p∨q = S∨S = S. Kontradiksi dengan p∨q harus B!
Tidak ada kombinasi yang memenuhi. Terbukti kontradiksi. ✓
Latihan Soal Kontradiksi
● Mudah
- Buktikan bahwa q ∧ ~q adalah kontradiksi!
- Buktikan bahwa ~(q → q) adalah kontradiksi!
- Tentukan apakah p → ~p merupakan kontradiksi atau bukan!
- Buktikan bahwa (p ∧ q) ∧ ~(p ∧ q) adalah kontradiksi!
- Buktikan bahwa ~[(p ∧ q) → (p ∨ q)] adalah kontradiksi!
● Sedang
- Buktikan bahwa (p → q) ∧ p ∧ ~q adalah kontradiksi!
- Buktikan bahwa (p ↔ q) ∧ (~p ↔ q) adalah kontradiksi!
- Buktikan bahwa ~[(p → q) ↔ (~q → ~p)] adalah kontradiksi!
- Buktikan bahwa (p ∧ ~p) ∨ (q ∧ ~q) adalah kontradiksi!
- Buktikan bahwa [(p → q) ∧ (p → ~q)] ∧ p adalah kontradiksi!
● Sulit
- Buktikan bahwa [(p ∨ q) ∧ (~p) ∧ (~q)] adalah kontradiksi!
- Buktikan bahwa [(p → q) ∧ (q → r) ∧ p ∧ ~r] adalah kontradiksi!
- Buktikan bahwa ~{[(p → q) ∧ ~q] → ~p} adalah kontradiksi!
- Buktikan bahwa [(p ↔ q) ∧ (q ↔ r) ∧ ~(p ↔ r)] adalah kontradiksi!
- Buktikan bahwa [(p → q) ∧ (~p → r) ∧ ~q ∧ ~r] adalah kontradiksi!
C. Pernyataan Majemuk yang Ekuivalen
Pengertian Ekuivalensi Logis
Dua pernyataan majemuk P dan Q dikatakan ekuivalen secara logis (dilambangkan P ≡ Q) jika keduanya memiliki nilai kebenaran yang sama untuk setiap kemungkinan nilai kebenaran pernyataan-pernyataan penyusunnya.
Dengan kata lain, P ≡ Q jika dan hanya jika P ↔ Q adalah tautologi.
Perhatikan dua pernyataan berikut:
- P: “Jika hujan, maka jalan basah” → p → q
- Q: “Jika jalan tidak basah, maka tidak hujan” → ~q → ~p
Kedua pernyataan ini memiliki makna logis yang sama. Kita katakan p → q ≡ ~q → ~p
Bagaimana cara membuktikan dua pernyataan majemuk ekuivalen? Apakah “ekuivalen” sama dengan “biimplikasi”?
Cara membuktikan ekuivalensi:
- Buat tabel kebenaran untuk P dan Q
- Bandingkan kolom hasil P dan Q
- Jika seluruh baris memiliki nilai yang sama, maka P ≡ Q
Perbedaan ≡ dan ↔:
- ↔ (biimplikasi) adalah operator/konektivitas logika yang menghasilkan pernyataan majemuk baru
- ≡ (ekuivalensi logis) adalah relasi antara dua pernyataan yang menunjukkan keduanya selalu bernilai sama
- P ≡ Q berarti P ↔ Q adalah tautologi
Buktikan bahwa p → q ≡ ~p ∨ q dengan tabel kebenaran!
Hukum-Hukum Ekuivalensi Logis yang Penting
| Nama Hukum | Ekuivalensi |
|---|---|
| Negasi Ganda | ~(~p) ≡ p |
| Komutatif (∧) | p ∧ q ≡ q ∧ p |
| Komutatif (∨) | p ∨ q ≡ q ∨ p |
| Asosiatif (∧) | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
| Asosiatif (∨) | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) |
| Distributif | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| Distributif | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| De Morgan | ~(p ∧ q) ≡ ~p ∨ ~q |
| De Morgan | ~(p ∨ q) ≡ ~p ∧ ~q |
| Implikasi | p → q ≡ ~p ∨ q |
| Kontraposisi | p → q ≡ ~q → ~p |
| Biimplikasi | p ↔ q ≡ (p → q) ∧ (q → p) |
| Identitas (∧) | p ∧ T ≡ p |
| Identitas (∨) | p ∨ F ≡ p |
| Dominasi (∧) | p ∧ F ≡ F |
| Dominasi (∨) | p ∨ T ≡ T |
| Idempoten (∧) | p ∧ p ≡ p |
| Idempoten (∨) | p ∨ p ≡ p |
| Absorpsi | p ∨ (p ∧ q) ≡ p |
| Absorpsi | p ∧ (p ∨ q) ≡ p |
Ekuivalensi logis sangat berguna untuk menyederhanakan pernyataan majemuk yang rumit menjadi bentuk yang lebih sederhana namun memiliki makna logis yang sama. Hukum-hukum di atas dapat digunakan secara berantai untuk penyederhanaan.
Contoh Soal Pernyataan Majemuk Ekuivalen
● Tingkat Mudah
Buktikan bahwa p → q ≡ ~p ∨ q!
Pembahasan:
| p | q | ~p | p → q | ~p ∨ q |
|---|---|---|---|---|
| B | B | S | B | B |
| B | S | S | S | S |
| S | B | B | B | B |
| S | S | B | B | B |
Kolom p→q dan ~p∨q selalu sama nilainya. Terbukti p → q ≡ ~p ∨ q. ✓
Buktikan bahwa ~(~p) ≡ p!
Pembahasan:
| p | ~p | ~(~p) |
|---|---|---|
| B | S | B |
| S | B | S |
Kolom p dan ~(~p) selalu sama. Negasi ganda mengembalikan nilai asal. Terbukti. ✓
Buktikan bahwa p ∧ q ≡ q ∧ p (Hukum Komutatif)!
Pembahasan:
| p | q | p ∧ q | q ∧ p |
|---|---|---|---|
| B | B | B | B |
| B | S | S | S |
| S | B | S | S |
| S | S | S | S |
Kedua kolom selalu sama. Urutan dalam konjungsi tidak mempengaruhi hasil. Terbukti. ✓
Buktikan bahwa p → q ≡ ~q → ~p (Kontraposisi)!
Pembahasan:
| p | q | ~p | ~q | p → q | ~q → ~p |
|---|---|---|---|---|---|
| B | B | S | S | B | B |
| B | S | S | B | S | S |
| S | B | B | S | B | B |
| S | S | B | B | B | B |
Kedua kolom identik. Kontraposisi selalu ekuivalen dengan implikasi aslinya. Terbukti. ✓
Tentukan apakah p → q ≡ q → p?
Pembahasan:
| p | q | p → q | q → p |
|---|---|---|---|
| B | B | B | B |
| B | S | S | B |
| S | B | B | S |
| S | S | B | B |
Baris 2 dan 3 berbeda. Maka p → q TIDAK ekuivalen dengan q → p. (q → p disebut konvers, bukan kontraposisi). ✓
● Tingkat Sedang
Buktikan bahwa ~(p ∧ q) ≡ ~p ∨ ~q (Hukum De Morgan)!
Pembahasan:
| p | q | p∧q | ~(p∧q) | ~p | ~q | ~p∨~q |
|---|---|---|---|---|---|---|
| B | B | B | S | S | S | S |
| B | S | S | B | S | B | B |
| S | B | S | B | B | S | B |
| S | S | S | B | B | B | B |
Kolom ~(p∧q) dan ~p∨~q selalu sama. Terbukti ekuivalen. ✓
Buktikan bahwa ~(p ∨ q) ≡ ~p ∧ ~q (Hukum De Morgan)!
Pembahasan:
| p | q | p∨q | ~(p∨q) | ~p | ~q | ~p∧~q |
|---|---|---|---|---|---|---|
| B | B | B | S | S | S | S |
| B | S | B | S | S | B | S |
| S | B | B | S | B | S | S |
| S | S | S | B | B | B | B |
Kedua kolom identik. Terbukti ekuivalen. ✓
Buktikan bahwa p ↔ q ≡ (p → q) ∧ (q → p)!
Pembahasan:
| p | q | p↔q | p→q | q→p | (p→q)∧(q→p) |
|---|---|---|---|---|---|
| B | B | B | B | B | B |
| B | S | S | S | B | S |
| S | B | S | B | S | S |
| S | S | B | B | B | B |
Kolom p↔q dan (p→q)∧(q→p) identik. Biimplikasi = konjungsi dua implikasi. Terbukti. ✓
Sederhanakan ~(p → q) menggunakan hukum ekuivalensi!
Pembahasan:
Langkah penyederhanaan:
- ~(p → q)
- ≡ ~(~p ∨ q) (karena p→q ≡ ~p∨q)
- ≡ ~(~p) ∧ ~q (Hukum De Morgan)
- ≡ p ∧ ~q (Negasi ganda)
Jadi ~(p → q) ≡ p ∧ ~q
Verifikasi: Negasi “jika hujan maka jalan basah” = “hujan DAN jalan tidak basah”. Logis! ✓
Buktikan bahwa p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (Distributif)!
Pembahasan:
| p | q | r | q∨r | p∧(q∨r) | p∧q | p∧r | (p∧q)∨(p∧r) |
|---|---|---|---|---|---|---|---|
| B | B | B | B | B | B | B | B |
| B | B | S | B | B | B | S | B |
| B | S | B | B | B | S | B | B |
| B | S | S | S | S | S | S | S |
| S | B | B | B | S | S | S | S |
| S | B | S | B | S | S | S | S |
| S | S | B | B | S | S | S | S |
| S | S | S | S | S | S | S | S |
Kolom p∧(q∨r) dan (p∧q)∨(p∧r) identik di semua 8 baris. Terbukti ekuivalen. ✓
● Tingkat Sulit
Sederhanakan ~(p → q) ∨ (~p ∧ q) menggunakan hukum ekuivalensi!
Pembahasan:
- ~(p → q) ∨ (~p ∧ q)
- ≡ (p ∧ ~q) ∨ (~p ∧ q) (karena ~(p→q) ≡ p∧~q)
Ini adalah bentuk XOR (exclusive or): tepat salah satu dari p,q yang benar.
Verifikasi dengan tabel:
| p | q | (p∧~q)∨(~p∧q) |
|---|---|---|
| B | B | S |
| B | S | B |
| S | B | B |
| S | S | S |
Jadi ~(p → q) ∨ (~p ∧ q) ≡ (p ∧ ~q) ∨ (~p ∧ q) ≡ p ⊕ q (XOR). ✓
Buktikan bahwa p → (q → r) ≡ (p ∧ q) → r (Hukum Ekspor-Impor)!
Pembahasan:
Menggunakan hukum ekuivalensi:
- p → (q → r)
- ≡ p → (~q ∨ r) (implikasi)
- ≡ ~p ∨ (~q ∨ r) (implikasi)
- ≡ (~p ∨ ~q) ∨ r (asosiatif)
- ≡ ~(p ∧ q) ∨ r (De Morgan terbalik)
- ≡ (p ∧ q) → r (implikasi terbalik)
Terbukti ekuivalen melalui rantai ekuivalensi. ✓
Sederhanakan (p → q) ∧ (p → ~q)!
Pembahasan:
- (p → q) ∧ (p → ~q)
- ≡ (~p ∨ q) ∧ (~p ∨ ~q) (implikasi)
- ≡ ~p ∨ (q ∧ ~q) (distributif terbalik: faktorisasi ~p)
- ≡ ~p ∨ F (q ∧ ~q adalah kontradiksi)
- ≡ ~p (identitas disjungsi)
Jadi (p → q) ∧ (p → ~q) ≡ ~p
Maknanya: jika dari p bisa disimpulkan q sekaligus ~q, maka p pasti salah. ✓
Buktikan bahwa p ↔ q ≡ (p ∧ q) ∨ (~p ∧ ~q)!
Pembahasan:
- p ↔ q ≡ (p → q) ∧ (q → p)
- ≡ (~p ∨ q) ∧ (~q ∨ p)
Distribusikan:
- ≡ [(~p ∨ q) ∧ ~q] ∨ [(~p ∨ q) ∧ p]
Lebih mudah dengan tabel kebenaran:
| p | q | p↔q | (p∧q)∨(~p∧~q) |
|---|---|---|---|
| B | B | B | B |
| B | S | S | S |
| S | B | S | S |
| S | S | B | B |
Identik. Biimplikasi benar jika keduanya benar atau keduanya salah. Terbukti. ✓
Sederhanakan [(p → q) ∧ ~q] → ~p dan tunjukkan bahwa hasilnya adalah tautologi!
Pembahasan:
- [(p → q) ∧ ~q] → ~p
- ≡ [(~p ∨ q) ∧ ~q] → ~p (implikasi)
- ≡ [(~p ∧ ~q) ∨ (q ∧ ~q)] → ~p (distributif)
- ≡ [(~p ∧ ~q) ∨ F] → ~p (q∧~q = F)
- ≡ (~p ∧ ~q) → ~p (identitas)
- ≡ ~(~p ∧ ~q) ∨ ~p (implikasi)
- ≡ (p ∨ q) ∨ ~p (De Morgan)
- ≡ (p ∨ ~p) ∨ q (komutatif & asosiatif)
- ≡ T ∨ q (p∨~p = T)
- ≡ T (dominasi)
Terbukti bahwa pernyataan tersebut ekuivalen dengan T (tautologi). ✓
Ini adalah Modus Tollens yang memang merupakan tautologi.
Latihan Soal Pernyataan Majemuk Ekuivalen
● Mudah
- Buktikan bahwa p ∨ q ≡ q ∨ p dengan tabel kebenaran!
- Buktikan bahwa p ∨ p ≡ p (Idempoten)!
- Buktikan bahwa p ∧ (p ∨ q) ≡ p (Absorpsi)!
- Tentukan apakah p ∧ q ≡ p ∨ q! Jika tidak, tunjukkan baris yang berbeda.
- Buktikan bahwa ~(~p) ∧ q ≡ p ∧ q!
● Sedang
- Sederhanakan ~(~p ∨ q) menggunakan hukum ekuivalensi!
- Buktikan bahwa (p → q) ∧ (p → r) ≡ p → (q ∧ r)!
- Sederhanakan (p ∨ q) ∧ (p ∨ ~q)!
- Buktikan bahwa ~(p ↔ q) ≡ (p ∧ ~q) ∨ (~p ∧ q)!
- Sederhanakan (p → q) ∨ (p → ~q)!
● Sulit
- Sederhanakan [(p → q) ∧ (~p → r)] ∧ ~q menggunakan hukum ekuivalensi!
- Buktikan bahwa (p → q) ∨ (q → r) adalah tautologi menggunakan penyederhanaan ekuivalensi!
- Sederhanakan ~[(p ∧ q) → (p ∨ r)]!
- Buktikan bahwa (p ↔ q) ↔ [(p ∧ q) ∨ (~p ∧ ~q)] adalah tautologi!
- Sederhanakan [(p → q) ∧ (r → q)] → [(p ∨ r) → q] dan buktikan hasilnya tautologi!
Ringkasan
| Jenis | Definisi | Tabel Kebenaran | Simbol |
|---|---|---|---|
| Tautologi | Selalu bernilai benar | Semua baris = B | T atau t |
| Kontradiksi | Selalu bernilai salah | Semua baris = S | F atau f |
| Kontingensi | Kadang benar, kadang salah | Ada B dan ada S | – |
| Ekuivalen | Dua pernyataan selalu bernilai sama | Kolom hasil identik | ≡ |
Hubungan Penting:
- P adalah tautologi ⟺ ~P adalah kontradiksi
- P ≡ Q ⟺ P ↔ Q adalah tautologi
- P adalah tautologi ⟺ P ≡ T
- P adalah kontradiksi ⟺ P ≡ F