EKUIVALENSI LOGIS
Dr. Julan HERNADI & (Asrul dan Enggar) Program Studi Pendidikan Matematika FKIP Unmuh Ponorogo
Pertemuan 3 FONDASI MATEMATIKA
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Variasi bentuk implikasi Berangkat dari implikasi p → q kita dapat membentuk tiga pernyataan implikasi relevan yang sering muncul, yaitu
1 q → p disebut konvers, 2 ¬q → ¬p disebut kontraposisi, 3 ¬p → ¬q disebut invers.
p
T T F F
q
T F T F
¬p
F F T T
¬q
F T F T
p→q
T F T T
q→p
T T F T
¬q → ¬p
T F T T
¬p → ¬q
T T F T
Diperhatikan bahwa implikasi dan kontraposisi mempunyai pola nilai kebenaran yang sama. Begitu juga dengan konvers dan invers. Selanjutnya, keadaan seperti ini disebut ekuivalen logis yaitu tidak serupa tapi sama makna.
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Tautologi dan Kontradiksi De nisi: Proposisi majemuk yang selalu bernilai benar tanpa terpengaruh oleh nilai kebenaran proposisi tunggal yang menyusunnya disebut tautologi. Sebaliknya, proposisi majemuk yang selalu bernilai salah tidak terpengaruh oleh nilai kebenaran proposisi yang menyusunnya disebut kontradiksi.
p ∨ ¬p adalah tautologi, p ∧ ¬p adalah kontradiksi. Periksa kebenaran ini dengan tabel kebenaran! De nisi: Pernyataan majemuk P dan Q dikatakan ekuivalen logis jika P ↔ Q sebuah tautologi. Selanjutnya, untuk P dan Q ekuialen logis ditulis P ≡ Q . Tautologi dan kontradiksi membicarakan sebuah pernyataan, sedangkan ekuivalensi logis membicarakan sifat dua pernyataan. Dua pernyataan ekuivalen dapat menggantikan satu sama lainnya. Dengan merujuk de nisi, dua pernyataan ekuivalen jika hanya jika tabel kebenarannya memiliki pola yang sama. Contoh: p → q ≡¬q → ¬p , yakni implikasi dan kontraposisi adalah ekuivalen logis. Juga dapat ditunjukkan bahwa invers dan konvers adalah ekuivalen logis. (lihat tabel).
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Bentuk Ekuivalensi Logis Dasar 1 2 3 4 5 6 7
Identitas : p ∧ T ≡ p dan p ∨ F ≡ p . dominasi : p ∨ T ≡ T dan p ∧ F ≡ F . idempoten : p ∨ p ≡ p dan p ∧ p ≡ p . negasi ganda : ¬(¬p ) ≡ p . komutatif : p ∨ q ≡ q ∨ p dan p ∧ q ≡ q ∧ p . asosiatif : (p ∨ q ) ∨ r ≡ p ∨ (q ∨ r ) dan (p ∧ q ) ∧ r ≡ p ∧ (q ∧ r ). distributif : p ∨ (q ∧ r ) ≡ (p ∨ q ) ∧ (p ∨ r ) dan p ∧ (q ∨ r ) ≡ (p ∧ q ) ∨ (p ∧ r ). 8 Hukum De Morgan : ¬(p ∨ q ) ≡ ¬p ∧ ¬q dan ¬(p ∧ q ) = ¬p ∨ ¬q . 9 Hukum absorpsi : p ∨ (p ∧ q ) ≡ p dan p ∧ (p ∨ q ) ≡ p . 10 Hukum negasi : p ∨ ¬p ≡ T dan p ∧ ¬p ≡ F . Hukum Hukum Hukum Hukum Hukum Hukum Hukum
di mana T pernyataan yang bernilai True dan F pernyataan yang bernilai False. Ada 2 metoda membuktikan ekuivalensi logis, yaitu Menggunakan tabel kebenaran Penjabaran dengan menggunakan bentuk dasar Semua bentuk ekuivalensi dasar di atas dapat dibuktikan.
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Bukti Hukum De Morgan dengan Tabel Membuktikan ¬(p ∨ q ) ≡ ¬p ∧ ¬q dengan tabel.
p
q
¬p
¬q
p∨q
¬(p ∨ q )
¬p ∧ ¬q
¬(p ∨ q )↔¬p ∧ ¬q
T T F F
T F T F
F F T T
F T F T
T T T F
F F F T
F F F T
T T T T
Untuk membuktikan ¬(p ∧ q ) = ¬p ∨ ¬q dapat dilakukan dengan cara yang sama atau menggunakan bentuk De Morgan pertama dan hukum negasi ganda. ¬p ∨ ¬ q
≡
¬(¬(¬p ) ∧ ¬(¬q ))
≡
¬ (p ∧ q .)
Perumuman hukum De Morgan: ¬(p1 ∨ p2 ∨ · · · ∨ pn ) ≡ ¬p1 ∧ ¬p2 ∧ · · · ∧ ¬pn dan ¬(p1 ∧ p2 ∧ · · · ∧ pn ) ≡ ¬p1 ∨ ¬p2 ∨ · · · ∨ ¬pn .
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Pembuktian dengan Tabel (Lanj...) Buktikan p → q dan ¬p ∨ q ekuivalen logis. Bukti. Bentuk tabel kebenaran kedua proposisi tsb
p
q
¬p
p→q
¬p ∨ q
T T F F
T F T F
F F T T
T F T T
T F T T
Karena nilai kebenaran dua kolom terakhir sama maka disimpulkan kedua proposisi majemuk ini ekuivalen logis. Pembuktian dengan tabel hanya efektif untuk proposisi dengan jumlah variabel (proposisi penyusunnya) sedikit. Untuk jumlah variabel banyak, misalnya 10 proposisi maka dibutuhkan tabel dengan 210 = 1024 baris sehingga tidak efektif. Dibutuhkan cara yang lebih praktis, yaitu penjabaran.
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Pembuktian dengan Penjabaran 1 Buktikan ¬(p → q ) dan p ∧ ¬q ekuivalen logis tanpa menggunakan Tabel Kebenaran. Bukti. Perhatikan penjabaran berikut ¬(p → q )
≡ ≡ ≡
¬(¬p ∨ q )
dengan contoh sebelumnya ¬(¬p ) ∧ ¬q Hukum De Morgan p ∧ ¬q Hukum negasi ganda
2 Buktikan (p ∧ q ) → (p ∨ q ) adalah tautologi.
Bukti. Berikan justi kasi aturan/hukum yang digunakan pada setiap langkah pembuktian berikut (p ∧ q ) → (p ∨ q )
≡
¬(p ∧ q ) ∨ (p ∨ q )
≡
(¬p ∨ ¬q ) ∨ (p ∨ q )
≡
(¬p ∨ p ) ∨ (¬q ∨ q )
≡
T ∨T T.
≡
Catatan: Tautologi harus ekuivalensi logis dengan T .
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
Tugas untuk Pekan Depan
Tugas Terstruktur (wajib dikumpul): Kerjakan 7 soal pada exercises hal 26-27 atau pilih dari Soal Latihan Bab 1 buku teks Pak Julan. Tugas Mandiri (tidak harus dikumpul): Buktikan kebenaran 10 bentuk ekuivalensi logis dasar dengan tabel kebenaran. Untuk pengembangan kemampuan logika dan bahasa Anda, selesaikan semua soal puzzle pada exercises hal 19 (No 40, 41, 42) dan hal 20 (No 56, 57, 58, 59, 60, 61). Sungguh kehebatan luar biasa jika Anda dapat menguasai soal-soal yang diberikan tersebut dengan baik.
Dr. Julan HERNADI & (Asrul dan Enggar)
EKUIVALENSI LOGIS
