Logika Informatika-arti kalimat,interpretasi

LOGIKA INFORMATIKA

ARTI KALIMAT

•          Arti kalimat = nilai kebenaran

•          Setiap kalimat pada logika proposisi memiliki salah satu dari nilai {true, false}

•          Arti kalimat kompleks yang terdiri atas n variabel merupakan fungsi dari nilai kebenaran n variabel tersebut

•          Perlu tahu nilai kebenaran masing-masing variabel

•          Perlu aturan untuk menghitung fungsi tersebut

•          Logika hanya berhubungan dengan bentuk (form) logis dari argumen-argumen, serta penarikan kesimpulan tentang validitas dari argumen tersebut

•          Contoh 1:

–         Badu seorang manusia

–         Setiap manusia memiliki 2 mata

–         Maka Badu memiliki 2 mata

•          Contoh 2:

–         Hewan meiliki 2 mata

–         Manusia memiliki 2 mata

–         Maka hewan sama dengan manusia

INTERPRETASI

•          Interpretasi pada logika proposisi = pemberian nilai kebenaran pada semua variabel

•          Contoh : P Ú ØQ

•          I1 : P true dan Q true

•          I2 : P true dan Q false

•          I3 : P false dan Q false

•          I4 : P false dan Q true

Aturan Semantik

•          kalimat true bernilai true untuk semua interpretasi

•          kalimat false bernilai false untuk semua interpretasi

•          kalimat P,Q,R,… bernilai sesuai interpretasinya

•          not F bernilai true jika F false dan bernilai false jika F true

•          F Ù G bernilai true jika F dan G keduanya true dan bernilai false jika tidak demikian

•          F Ú G bernilai false jika F dan G keduanya false dan bernilai true jika tidak demikian

•          F Þ G bernilai false jika F true dan G false dan bernilai true jika tidak demikian

Tabel Kebenaran

•          Dengan aturan semantik dapat ditentukan nilai kebenaran suatu kalimat kompleks untuk semua interpretasi yang mungkin

•          Biasanya ditabelkan dan disebut tabel kebenaran

•          Jika terdapat n variabel, maka terdapat 2ⁿ baris tabel kebenaran

Operator / Logical Connectives

•          Sebuah operator atau penghubung menggabungkan satu atau lebih ekspresi operand ke dalam ekspresi yang lebih besar.  (seperti tanda “+” di ekspresi numerik.)

•          Operator Uner bekerja pada satu operand (contoh  −3); Operator biner bekerja pada 2 operand (contoh  3 ´ 4).

•          Operator Proposisi atau Boolean bekerja pada proposisi-proposisi atau nilai kebenaran, bukan pada suatu angka

Operator / Boolean Umum

Nama Resmi

Istilah

Arity

Simbol

Operator Negasi

NOT

Unary

¬

Operator  Konjungsi

AND

Binary

Ù

Operator Disjungsi

OR

Binary

Ú

Operator Exclusive-OR

XOR

Binary

Å

Operator Implikasi

IMPLIES (jika-maka)

Binary

®

Operator Biimplikasi  (Biconditional)

IFF (jika dan hanya jika)

Binary

↔

Operator Negasi

•          Operator negasi uner “¬” (NOT) mengubah suatu proposisi menjadi proposisi lain yang bertolak belakang nilai kebenarannya

•          Contoh: Jika  p = Hari ini hujan

•                                  maka ¬p = Tidak benar hari ini hujan

•           Tabel kebenaran untuk  NOT:

p	¬p
T	F
F	T

 T = True; F = False

º Diartikan “didefinisikan sebagai”

Operator Konjungsi

•         Operator konjungsi biner “Ù” (AND) menggabungkan dua proposisi untuk membentuk logika konjungsinya

•         Cth:   p = Badu menabrak pagar rumah                                    

    q = Badu menginjak-injak pagar rumah

•                     pÙq = Badu menabrak pagar rumah dan

                                    menginjak-injaknya

Tabel Kebenaran Konjungsi

•         Perhatikan bahwa

 Konjungsi p1 Ù p2 Ù … Ù pn  dari n proposisi akan memiliki 2ⁿ baris
pada tabelnya

•         Operasi ¬ dan Ù saja cukup untuk mengekspresikan semua tabel kebenaran Boolean

p	q	pÙq
F	F	F
F	T	F
T	F	F
T	T	T

Operator Disjungsi

Operator biner disjungsi “Ú” (OR) menggabungkan dua proposisi untuk membentuk logika disjungsinya

p=“Saya memilih pizza untuk dinner”

q=“Saya memilih fried chicken untuk dinner”

pÚq=“Saya memilih pizza atau fried chicken untuk dinner.”

Tabel Kebenaran Disjungsi

•         Perhatikan bahwa pÚq                      
berarti p benar, atau q
benar, atau keduanya benar!

•         Jadi, operasi ini juga disebut

            inclusive or, karena mencakup
kemungkinan bahwa  both p

    dan q keduanya benar.

•         “¬” dan “Ú” keduanya membentuk opearator universal.

p	q	pVq
F	F	F
F	T	T
T	F	T
T	T	T

Proposi Bertingkat

•         Gunakan tanda kurung untuk mengelompokkan  sub-ekspresi:
“Saya baru saja bertemu teman lama, dan anaknya sudah dua atau tiga.” = f Ù (g Ú s)

–          (f Ù g) Ú s   artinya akan berbeda

–          f Ù g Ú s     artinya akan ambigu

•         Menurut perjanjian, “¬” presedensinya lebih tinggi dari “Ù” dan “Ú”.

–          ¬s Ù f   artinya   (¬s) Ù f  ,   bukan   ¬ (s Ù f)

CONTOH:

Misalkan  p=“Tadi malam hujan”,
            q=“Tukang siram tanaman datang tadi malam,”
            r=“Pagi ini kebunnya basah.”

Terjemahkan proposisi berikut dalam bahasa Indonesia:

¬p              = “Tadi malam tidak hujan.”

r Ù ¬p         = “Pagi ini kebunnya basah dan tadi malam tidak hujan.”

“Pagi ini kebun tidak basah, atau tadi malam hujan, atau tukang siram tanaman datang tadi malam.”

Operator Exclusive OR

Operator biner exclusive-or “Å” (XOR) menggabungkan dua proposisi untuk membentuk logika “exclusive or”-nya

p = “Saya akan mendapat nilai A di kuliah ini,”

q = “Saya akan drop kuliah ini,”

p Å q = “Saya akan mendapat nilai A atau saya       akan drop kuliah ini (tapi tidak dua-duanya!)”

Tabel Kebenaran Exclusive OR

•         Perhatikan bahwa pÅq
berarti p benar, atau q

      benar tapi tidak dua-

      duanya benar!

•         Disebut exclusive or,
karena tidak memungkinkan

      p dan q keduanya benar

•         “¬” dan “Å” tidak membentuk operator universal

p	q	pÅq
F	F	F
F	T	T
T	F	T
T	F	T
T	T	F

Bahasa Alami sering Ambigu

•         Perhatikan bahwa kata “atau” dapat bermakna

            ambigu berkenaan dengan kasus keduanya benar.

•         “Tia adalah penulis atau

            Tia adalah aktris.” -

•         “Tia perempuan atau
Tia laki-laki” –

•         Perlu diketahui konteks pembicaraannya!

p	q	p "or" q
F	F	F
F	T	T
T	F	T
T	T	?

Operator Implikasi

•         Implikasi p ® q menyatakan bahwa p mengimplikasikan q.

•         p disebut antecedent dan q disebut consequent

•         Jika p benar, maka q benar; tapi jika p tidak benar,  maka q bisa benar - bisa tidak benar

•         Contoh :

            p = Nilai ujian akhir anda 80 atau lebih

            q = Anda mendapat nilai A

            p ® q = “Jika nilai ujian akhir anda 80 atau lebih, maka anda mendapat nilai A”

Implikasi p ® q

(a) Jika p, maka q                    (if p, then q)

(b) Jika p, q                              (if p, q)

(c) p mengakibatkan q                     (p implies q)

(d) q jika p                                        (q if p)

(e) p hanya jika q                    (p only if q)

(f) p syarat cukup agar q        (p is sufficient for q)

(g) q syarat perlu bagi p         (q is necessary for p)

(i) q bilamana p                               (q whenever p)

Tabel Kebenaran Implikasi

•         p ® q salah  hanya jika
p benar tapi q tidak benar

•         p ® q   tidak mengatakan

   bahwa hanya p yang menye-

   babkan q!

•         p ® q   tidak mensyaratkan

            bahwa p atau q harus benar!

•         Cth. “(1=0) ® kucing bisa terbang” BENAR!

p	q	p®q
F	F	T
F	T	T
T	F	F
T	T	T

Contoh Implikasi

•         “Jika saya rajin kuliah hari ini, matahari akan bersinar esok hari” True / False?

•         “Jika hari ini Kamis, maka saya adalah seekor pinguin.” True / False?

•         “Jika 1+1=6, maka SBY adalah presiden.” True / False?

•         “Jika bulan dibuat dari keju, maka saya lebih kaya dari Bill Gates.” True or False?

Converse, Inverse & Contrapositive

Beberapa terminologi dalam implikasi p ® q:

•         Converse-nya adalah:             q ® p.

•         Inverse-nya adalah:                ¬p ® ¬q.

•         Contrapositive-nya adalah:     ¬q ® ¬ p.

•         Salah satu dari ketiga terminologi di atas memiliki makna yang sama (memiliki tabel kebenaran yang sama) dengan p ® q. Bisa Anda sebutkan yang mana?

Bagaimana Menunjukkannya?

Membuktikan eqivalensi antara p ® q dan contrapositive-nya dengan tabel kebenaran:

p	q	Øq	Øp	p®q	Øq ®Øp
F	F	T	T	T	T
F	T	F	T	T	T
T	F	T	F	F	F
T	T	F	F	T	T

Operator Biimplikasi

•         Operator biimplikasi p « q menyatakan bahwa p benar jika dan hanya jika (jikka) q benar

•         p = “SBY menang pada pemilu 2004”

•         q = “SBY akan menjadi presiden mulai tahun 2004.”

•         p « q = “Jika dan hanya jika SBY menang pada pemilu 2004 maka dia akan menjadi presiden mulai tahun 2004.”

Biimplikasi p ↔ q

(a) p jika dan hanya jika q.

            (p if and only if q)

(b) p adalah syarat perlu dan cukup untuk q. (p is necessary and sufficient for q)

(c) Jika p maka q, dan sebaliknya.

            (if p then q, and conversely)

(d) p jikka q

            (p iff q)

Tabel Kebenaran Biimplikasi

•         p « q benar jika p dan q
memiliki nilai kebenaran

   yang sama.

•         Perhatikan bahwa tabelnya

   adalah kebalikan dari tabel

   exclusive or Å!

–        p « q artinya  ¬(p Å q)

p	q	p « q
F	F	T
F	T	F
T	F	F
T	T	T

Perhatikan

Nyatakan pernyataan berikut dalam ekspresi logika :

            “Anda tidak dapat terdaftar sebagai pemilih dalam Pemilu jika anda berusia di bawah 17 tahun kecuali kalau anda sudah menikah”

Misalkan :

p : Anda berusia di bawah 17 tahun.

q : Anda sudah menikah.

r : Anda dapat terdaftar sebagai pemilih dalam Pemilu.

maka pernyataan di atas dapat ditulis sebagai

(p Λ ~ q) ® ~ r

Ringkasan

p	q	Øp	pÙq	pÚq	pÅq	p®q	p«q
F	F	T	F	F	F	T	T
F	T	T	F	T	T	T	F
T	F	F	F	T	T	F	F
T	T	F	T	T	F	T	T