Logika Matematika
Logika Matematika
[email protected] Jurusan Informatika FMIPA Unsyiah
September 26, 2012
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Tabel Kebenaran Cara menentukan nilai kebenaran pernyataan majemuk dengan menggunakan tabel kebenaran, yaitu dengan membagi beberapa bagian (kolom). Nilai kebenarannya terletak pada kolom yang terdapat operasi logika yang terakhir dan akan diberi tanda *. Banyaknya baris yang tersedia tergantung banyaknya pernyataan yang ada dengan menggunakan rumus 2n , dimana n adalah banyaknya pernyataan tunggal yang menyusun pernyataan majemuk tersebut. Pernyataan yang pertama diisi dengan setengah B dan setengah S. Pernyataan kedua diisi dengan seperempat B dan berselang-seling dengan seperempat S dan seterusnya.
[email protected]
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Logika Matematika
Contoh Tentukan nilai kebenaran dari pernyataan ((p ∧ q) → ¬p) ∨ ¬q. Jawab : Karena ada 2 pernyataan yaitu p dan q maka terdapat 22 = 4 baris. Tabel kebenarannya : ((p B B S S
∧ B S S S
q) B S B S
[email protected]
→ S B B B
¬p) S S B B
∨ S B B B
¬q S B S B
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Pernyataan yang Ekuivalen
Dua pernyataan majemuk p dan q dikatakan ekuivalen dan ditulis p ≡ q jika dan hanya jika p dan q mempunyai nilai kebenaran yang sama. Untuk itu membuktikannya dengan menggunakan tabel kebenaran.
[email protected]
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Logika Matematika
Contoh Tunjukkan dengan tabel kebenaran bahwa (p → (q → r)) = ((p ∧ q) → r) (p B B B B S S S S
→ B S B B B B B B
(q B B S S B B S S
→ B S B B B S B B
r)) B S B S B S B S
=
((p B B B B S S S S
∧ B B S S S S S S
q) B B S S B B S S
→ B S B B B B B B
r) B S B S B S B S
Karena nilai kebenaran ruas kiri dan kanan sama yaitu BSBBBBBB maka keduanya ekuivalen.
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Konvers, invers dan kontraposisi dari suatu implikasi mempunyai ketentuan sebagai berikut : Jika suatu implikasi p → q maka : Konversnya : q → p Inversnya : ¬p → ¬q Kontraposisinya : ¬q → ¬p Catatan: Implikasi ekuivalen dengan kontraposisi Konvers ekuivalen dengan invers.
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Contoh
Tentukan konvers, invers dan kontraposisi dari implikasi ”Jika hari libur maka anak-anak tidak masuk sekolah” Jawab: Konversnya : Jika anak-anak tidak masuk sekolah maka hari libur Inversnya : Jika hari tidak libur maka anak-anak masuk sekolah Kontraposisinya : Jika anak-anak masuk sekolah maka hari tidak libur
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Definisi Tautologi adalah suatu pernyataan majemuk yang bernilai benar untuk setiap kemungkinan. Kontradiksi adalah suatu pernyataan majemuk yang bernilai salah untuk setiap kemungkinan. Kontingensi adalah suatu pernyataan majemuk yang bukan termasuk tautologi dan bukan juga kontradiksi. Tautologi, kontradiksi dan kontigensi dapat dibuktikan menggunakan tabel kebenaran ataupun sifat-sifat logika. Contoh: 1 2 3
[(p → q) ∧ ¬q] → ¬p (tautologi) p ∧ ¬p (kontradiksi) p ∨ q (kontigensi)
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Penarikan kesimpulan Ada tiga metode atau cara yang digunakan dalam penarikan kesimpulan, yaitu: Modus Ponens Modus Tollens Silogisme. Penarikan kesimpulan dilakukan dari beberapa pernyataan yang diketahui nilai kebenarannya yang disebut premis. Kemudian, dengan menggunakan prinsip-prinsip logika diperoleh pemyataan baru yang disebut kesimpulan / konklusi yang diturunkan dari premis yang ada. Penarikan kesimpulan seperti itu sering juga disebut argumentasi.
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Penarikan kesimpulan Prinsip-prinsip logika yang dipakai dalam penarikan kesimpulan adalah sebagai berikut. 1
Argumentasi dikatakan sah : Konjungsi dari premis-premis yang diketahui diimplikasikan dengan konklusi hasilnya tautologi
2
Argumentasi dikatakan tidak sah: Konjungsi dari premis-premis yang diketahui diimplikasikan dengan konklusi hasilnya bukan tautologi
Jadi suatu argumentasi dikatakan sah jika premis-premisnya benar maka konklusinya juga benar.
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Modus Ponens
Jika diketahui premis-premisnya p → q dan p maka dapat diambil konklusi q. Penarikan kesimpulan seperti itu disebut Modus Ponens atau Kaidah Pengasingan. Modus Ponens disajikan dalam susunan sebagai berikut. premis 1: p → q premis 2: p konklusi : ∴ q
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Modus Tollens
Jika diketahui premis-premisnya p → q dan ¬q maka dapat diambil konklusi ¬p. Penarikan kesimpulan seperti itu disebut Modus Tollens atau Kaidah Penolakan. Modus Tollens disajikan dalam susunan sebagai berikut. premis 1: p → q premis 2: ¬q konklusi : ∴ ¬p
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Silogisme
Jika diketahui premis-premisnya p → q dan q → r maka dapat diambil konklusi p → r. Penarikan kesimpulan seperti itu disebut Silogisme. Silogisme menggunakan sifat menghantar atau transitif dari pemyataan implikasi. Silogisme disajikan dalam susunan sebagai berikut. premis 1: p → q premis 2: q → r konklusi : ∴ p → r
[email protected]
Logika Matematika
Logika Matematika
Tabel Kebenaran Pernyataan yang Ekuivalen Konvers, invers dan kontraposisi Tautologi Penarikan kesimpulan
Contoh Modus tollens
premis 1: Jika seseorang sudah berumur 17 tahun maka ia boleh me premis 2: Ali belum mempunyai KTP (B) konklusi : Ali belum berumur 17 tahun (B) Silogisme premis 1: Jika rajin belajar maka ia naik kelas (B) premis 2: Jika naik kelas maka ia dibelikan sepeda (B)) konklusi : Jika rajin belajar maka ia dibelikan sepeda (B)
[email protected]
Logika Matematika
Kuantor
Misalkan p(x) adalah pernyataan yang menyangkut variabel x dan D adalah sebuah himpunan, maka p adalah fungsi proposisi jika untuk setiap x ∈ D berlaku p(x) adalah sebuah proposisi.
[email protected]
INF-104 Matematika Diskrit
Kuantor
Contoh 1 Misalkan p(x) adalah pernyataan dengan x adalah sebuah bilangan genap bulat. Misalkan D adalah himpunan bilangan bulat positif. Maka fungsi proposisi p(x) dapat ditulis: Jika x = 1 maka proposisinya 1 adalah bilangan bulat genap (F) Jika x = 2 maka proposisinya 2 adalah bilangan bulat genap (T) dan seterusnya. Jadi dapat kita lihat ada sejumlah (kuantitas) proposisi yang benar. Untuk menyatakan kuantitas suatu objek dalam proposisi tersebut digunakan notasi-notasi yang disebut kuantor.
[email protected]
INF-104 Matematika Diskrit
Kuantor
Jenis-jenis kuantor
Jenis-jenis kuantor yang sering digunakan dalam proposisi: 1
Untuk setiap x, p(x) disebut kuantor universal dan simbol yang digunakan ∀.
2
Untuk beberapa (paling sedikit satu) x, p(x) disebut kuantor existensial simbol yang digunakan ∃.
[email protected]
INF-104 Matematika Diskrit
Kuantor
Contoh 2 Misalkan x himpunan warga negara Indonesia, p predikat membayar pajak, r predikat membeli printer, maka 1
∀xp(x) artinya: Semua warga negara membayar pajak.
2
∃xr(x)p(x) artinya: Ada beberapa warga negara pembeli printer membayar pajak.
3
∀xr(x) → p(x) artinya: Setiap warga negara jika membeli printer maka membayar pajak.
4
∃xr(x) ∧ ¬p(x) artinya: Ada warga negara membeli printer dan tidak membayar pajak.
[email protected]
INF-104 Matematika Diskrit
Kuantor
Negasi Kuantor
¬∀x = ∃x ¬∃x = ∀x maka 1
¬(∀xp(x)) = ∃x(¬p(x))
2
¬(∃xp(x)) = ∀x(¬p(x))
3
¬(∀xp(x) → q(x)) = ∃x¬(p(x) → q(x)) = ∃x(p(x)∧(¬q(x)))
4
¬(∃xp(x) → q(x)) = ∀x¬(p(x) → q(x)) = ∀x¬(p(x)∧¬q(x))
[email protected]
INF-104 Matematika Diskrit