Sistem Digital : Sum of Product ( SOP ) dan Product of Sum ( POS )

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

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 :

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

Sumber

Slide Logika Informatika : Sifat Kalimat dan Phon Semantik

http://informatika.unpar.ac.id/