Logika Informatika : Sifat Kalimat, Pohon Semantik, dan Pengujian 2 Kalimat, beserta Contoh Soal
SIFAT KALIMAT
Kalimat F disebut kalimat valid atau tautologi jika bernilai true untuk setiap interpretasi yang mungkin bagi F
Kalimat F disebut dapat dipenuhi (satisfiable) jika ada interpretasi yang membuat F true
Kalimat F disebut tak dapat dipenuhi (unsatisfiable/contradictory) jika bernilai false untuk semua interpretasi
Kalimat F mengimplikasikan G jika pada semua interpretasi jika F true maka G juga true
Kalimat F dan G ekivalen jika pada setiap interpretasi nilai kebenaran F dan G selalu sama
F1, F2,… konsisten jika ada interpretasi di mana setiap F_i true
PENGUJIAN SIFAT KALIMAT
Terdapat beberapa cara pengujian sifat-sifat kalimat:
- Tabel kebenaran
- Pohon semantik
TABEL KEBENARAN
Harus memeriksa semua kemungkinan interpretasi. Tabel Kebenaran bersifat sederhana tetapi lama dalam waktu pengerjaan.
CONTOH TAUTOLOGI
p Þ q Ú p
Exercise 1
Tunjukan kalimat ini merupakan tautologi atau bukan :
CONTOH MENGIMPLIKASIKAN
F : (p Þ q) Λ (q Þ r)
G : p Þ r
Exercise 2
Exercise 3
POHON SEMANTIK
Berbentuk pohon biner. Setiap level merepresentasikan setiap variabel. Setiap daun berisi nilai kebenaran kalimat dimana Kiri = T, kanan = F. Pohon Semantik ini dapat menguji sifat valid, dapat dipenuhi, atau tidak dapat dipenuhi, secara langsung.
CONTOH
p Þ q Ú p
Pohon semantik dimulai dengan cabang tertinggi untuk proposisi pertama (p)
Cabang 1, jika p = T, maka q Ú p = T, sehingga (p Þ q Ú p) = T
Cabang 2, jika p = F, maka (p Þ q Ú p) = T.
Periksa nilai kebenaran tiap daun
Periksa nilai kebenaran tiap daun
KALIMAT VALID
Kalimat akan dikatakan valid jika seluruh daunnya bernilai T
Contoh :
KALIMAT SATISFIABLE
Kalimat yang setidaknya satu daun bernilai T ( minimal 1 )
Contoh :
KALIMAT UNSATISFIABLE
Kalimat yang seluruh daunnya bernilai F
Contoh :
Exercise 4
Tunjukan kalimat ini valid atau tidak dengan menggunakan pohon semantik :
PENGUJIAN 2 KALIMAT
Untuk menguji apakah F mengimplikasikan G dengan pohon semantik :
Uji apakah F Þ G valid
Contoh :
Contoh :
Untuk menguji apakah F dan G ekivalen dengan pohon semantik:
Uji apakah (F Þ G) Λ (G Þ F) valid
Contoh :
Untuk menguji apakah F1, F2, …, Fn konsisten dengan pohon semantik :
Uji apakah F1 Λ F2 Λ … Λ Fn dapat dipenuhi
Contoh :
Exercise 5
Tunjukkan dengan menggunakan pohon semantik :
Exercise 6
Tunjukkan apakah 2 kalimat berikut ekivalen atau tidak dengan menggunakan pohon semantik :
Exercise 7
Tunjukkan apakah kalimat-kalimat di bawah ini konsisten atau tidak dengan menggunakan pohon semantik :
IMPLIKASI DAN VALIDITAS
F mengimplikasikan G jika F Þ G valid. Jika F mengimplikasikan G maka jika F valid, G juga valid
EKIVALENSI DAN VALIDITAS
F dan G ekivalen jikka (F Þ G) Λ (G Þ F) valid. Jika F dan G ekivalen maka F valid jika G valid
RANTAI EKIVALENSI
Jika F dan G ekivalen dan G dan H juga ekivalen maka F dan H ekivalen
Exercises 8
Which of the following formulas are semantically equivalent to p Þ (q Ú r)
Exercises 9
Which of the following formulas are semantically equivalent to p Þ q
sangat bermanfaat
BalasHapusPosting Komentar