Logika Informatika : Sifat Kalimat, Pohon Semantik, dan Pengujian 2 Kalimat, beserta Contoh Soal
SIFAT KALIMAT
Kalimat F disebut kalimat valid atau tautologi bila bernilai true untuk setiap interpretasi yang mungkin bagi F
Kalimat F disebut dapat dipenuhi (satisfiable) bila ada interpretasi yang menciptakan F true
Kalimat F disebut tak sanggup dipenuhi (unsatisfiable/contradictory) bila bernilai false untuk semua interpretasi
Kalimat F mengimplikasikan G bila pada semua interpretasi bila F true maka G juga true
Kalimat F dan G ekivalen bila pada setiap interpretasi nilai kebenaran F dan G selalu sama
F1, F2,… konsisten bila 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 mengusut semua kemungkinan interpretasi. Tabel Kebenaran bersifat sederhana tetapi usang 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 sanggup menguji sifat valid, sanggup dipenuhi, atau tidak sanggup dipenuhi, secara langsung.
CONTOH
p Þ q Ú p
Pohon semantik dimulai dengan cabang tertinggi untuk proposisi pertama (p)
Cabang 1, bila p = T, maka q Ú p = T, sehingga (p Þ q Ú p) = T
Cabang 2, bila p = F, maka (p Þ q Ú p) = T.
Periksa nilai kebenaran tiap daun
Periksa nilai kebenaran tiap daun
KALIMAT VALID
Kalimat akan dikatakan valid bila 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 memakai 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 sanggup dipenuhi
Contoh :
Exercise 5
Tunjukkan dengan memakai pohon semantik :
Exercise 6
Tunjukkan apakah 2 kalimat berikut ekivalen atau tidak dengan memakai pohon semantik :
Exercise 7
Tunjukkan apakah kalimat-kalimat di bawah ini konsisten atau tidak dengan memakai pohon semantik :
IMPLIKASI DAN VALIDITAS
F mengimplikasikan G bila F Þ G valid. Jika F mengimplikasikan G maka bila 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 bila 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
EmoticonEmoticon