• Logika adalah suatu system berbasis proposisi.

• Suatu proposisi adalah suatu pernyataan (statement) yang dapat bernilai Benar (true) atau Salah (false) dan tidak keduanya.

• Dikatakan bahwa nilai kebenaran daripada suatu proposisi adalah salah satu dari benar (true disajikan dengan T) atau salah (false disajikan dengan F).

• Dalam untaian digital (digital circuits) disajikan dengan 0 dan 1

Variabel-variabel tersebut diatas dihubungkan dengan menggunakan penghubung logis yang

disebut operator atau functor Sebagai contoh :

1) Saya mempunyai uang dan saya lapar

2) Jika balok mempunyai berat jenis lebih besar dari 1 maka ia akan tenggelam diair.

3) Ir. Sukarno presiden pertama RI dan ia proklamator negara RI

4) Saya berangkat naik becat atau naik angkot.

5) Lampu mobil mati karena plentongnya mati atau kabelnya putus

Perhatikan kalimat-kalimat sebagai berikut :

1) Tutuplah pintu itu

2) Dilarang merokok

3) Nilai daripada x terletak diantara nol dan satu

Kalimat-kalimat tersebut tidak dimasukkan dalam pembicaraan kita karena mereka tidak dapat bernilai benar ataupun salah sedang yang terakhir tidak dimasukkan disini tetapi masuk dalam logika predikat.

Bab 1

Logika

The Statement/Proposition Game

• “Gajah lebih besar daripada tikus.”

• Apakah ini suatu pernyataan? yes

• Apakah ini suatu proposisi? yes

• Apa nilai kebenaran daripada proposisi tersebut? True

The Statement/Proposition Game

• “520 < 111”• Apakah ini suatu pernyataan ? yes• Apakah ini suatu proposisi? yes• Apa nilai kebenaran daripada proposisi tersebut? False

Proposisi adalah kalimat deklaratif (atau pernyata an) yang memiliki hanya satu nilai kebenaran yaitu banar saja atau salah saja, akan tetapi tidak keduanya.Proposisi yang bukan hasil kombinasi dari proposisi-propo sisi disebut atom.

Jika atom-atom akan dikombinasikan untuk memperoleh proposisi baru maka diperlukan operator logika atau operator sambung yang dilambangkan dng simbol :

1). : “not”, atau “negasi”

2). : “and”, atau “konjungsi”

3). : “or” , atau “disjungsi” atau “inclusive or”

4). : “xor”, atau “exclusive or”

5). : “implies”, atau “Jika … maka…”, atau “implikasi kondisional”

6). : “jika dan hanya jika”, atau “bikondisional”

1) Negasi (not)

Jika p sembarang proposisi, pernyataan “not p” atau “negasi daripada p” akan bernilai F jika p bernilai T dan sebaliknya. Dan ditulis dengan

p

( “” disebut operator unary/monadika) dan akan digambarkan dengan tabel kebenaran sebagai berikut :

p ¬p

T F

F T

2) Konjungsi/conjunction (and)

Konjungsi adalah suatu operator binary atau diadika (diadic). Jika p dan q suatu proposisi, pernyataan p and q akan bernilai kebenaran T jika dan hanya jika kedua p dan q mempunyai nilai kebenaran T, dan ditulis dengan

p q

dimana operatornya terletak diantara kedua variable (operand) tersebut dan mempunyai tabel kebenaran.seperti terlihat dibawah ini :

P q p ˄ q T T T T F F F T F F F F

Tabel kebenaran juga dapat disajikan dengan suatu bentuk dua dimensi sebagai berikut :

p ˄ q T F q T T F F F F p

• Bentuk terakhir ini hanya dapat digunakan hanya untuk fungsi dua variabel

• Perhatikan bahwa untuk kalimat “Benda ini berwarna merah” dan “Benda ini berwarna putih” jika digandeng dengan “and” maka berbunyi “Benda ini berwarna merah “and” putih” yang artinya lain dengan “Benda ini berwarna merah and Benda ini berwarna putih”, jelaskan !!

• Sifatnya : 1) Komutatif ( p q = q p)

2) Asosiatif ( (pq)r = p(qr) )

• Operand daripada suatu kunjungsi juga disebut dengan conjunct.

3) Disjungsi (or)

Disjungsi yang juga ada yang menyebut dengan alternatif yang bersesuaian dengan bentuk

“ Salah satu dari … atau ….” (“Either.. Or..) . Pernyataan “p or q” bernilai T jika dan hanya jika salah satu p atau q (atau keduanya) bernilai T. Ditulis :

p q

dan mempunyai tabel kebenaran seperti di bawah ini:

p q p v q T T T T F T F T T F F F

Sifat :

1) Komutatif ( p q = q p )

2) Asosiatif ( (p q) r = p (q r) )

• Perhatikan bahwa terdapat dua pengertian or yaitu “inclusif or” dan “exclusive or”. Sebagai contoh :

• “Pintu rumah terbuka” or “jendela rumah terbuka”. Hal tersebut dapat keduanya

• “Suta pergi kekantor naik becak” or “Suta pergi kekantor naik angkot”. Hal tersebut tidak mungkin keduanya.

• Contoh pertama “or inclusive” dan disimbolkan dengan

• Contoh kedua “or exclusive” atau “non-equivalen” dan disimbolkan dengan ( atau XOR atau )

4) Implikasi (Implication)

Arti daripada pernyataan “If p then q” atau “p implies q” atau “q if p” atau “p hanya jika q” atau “q sarat perlu untuk p” atau “p sarat cukup untuk q” adalah T jika salah satu dari p bernilai T dan q bernilai T atau jika p bernilai F. Jika tidak demikian, yaitu p bernilai T dan q bernilai F, maka nilai F. Ditulis

p q

dan tabel kebenarannya seperti berikut (ada yang menggunakan simbol )

p q p → qT T TT F FF T TF F T

Untuk penjelasan ini maka perhatikan kalimat :

“Jika Anita pergi keluar negeri maka ia mempunyai passport”

Penjelasannya adalah sebagai berikut :

1)Jika Anita keluar negeri ( T ) dan Ia mempunyai passport (T), maka legal (T)

2) Jika Anita keluar negeri (T) dan Ia tidak mempu nyai passport (F), maka illegal (F)

3) Jika Anita tidak keluar negeri (F) dan ia mempu nyai passport (T), maka legal (T)

4) Jika Anita tidak keluar negeri (F) dan ia tidak mempunyai passport (F), maka legal (T)

kondisionalp → q

konversiq→p

inversi¬p → ¬q

kontrapositif¬q → ¬pp q

T T T T T TT F F T T FF T T F F TF F T T T T

• Perhatikan bahwa : pernyataan p q selalu mempunyai tabel kebenaran (p) q dan juga dengan (pq), (buat tabel kebenarannya)

5) Ekuivalensi

Pernyataan “ p ekuivalen dengan q” mempunyai nilai kebenaran T jika dan hanya jika p dan q mempunyai nilai kebenaran yang sama ditulis dengan simbol :

p q

dan tabel kebenarannya seperti berikut ( ada yang menggunakan simbol )

p q p ↔ qT T TT F FF T FF F T

Sifat :

1) Komutatif ; ( p q = q p)

2) Asosiatif ; ( (p q) r = p (q r) )

3) Pernyataan (p q) mempunyai tabel kebenaran yang sama dengan pernyataan p q

• Perhatikan bahwa ia juga dapat dipikirkan sebagai pernyataan “ p jika dan hanya jika q”

• Pernyataan p q disebut juga dengan bikondisional daripada p dan q, sebab ia selalu mempunyai tabel kebenaran sama-dng (p q ) (q p) atau (pq) (pq)

• Ditulis dengan p q =T (p q) (p q)

• Prioritas Operator

• Terkuat monadika ()

• Untuk diadika terkuat (), kemudian () dan berikutnya () dan yang lainnya berikutnya lagi seperti misalnya ()

• Contoh :

“Saya lapar saya sedih saya bahagia saya telah kekenyangan” berarti

“(Saya lapar saya sedih) (saya bahagia saya telah kekenyangan)”

Mana yang pernyataan dan mana yang bukan

1. Ngawi adalah ibukota propinsi Jawa Timur.(P)

2. Dilarang merokok(B)

3. 119 adalah bilangan bulat(P)

4. Buka pintu(B)

5. Logika informatika adalah mudah(P)

6. Yogya kota pelajar(P)

7. Makanlah yang banyak(B)

8. Sesama cabup tak boleh saling mendahului(B)

9. Buatlah daftar pernyataan sebanyak 50 buah(B)

Tuliskan kalimat dibawah ini dengan simbol logika

a. Saya akan berlibur ke Bali hanya jika saya lulus ujian

b. Sarat perlu agar 273 habis dibagi 3 adalah 273 merupakan bilangan prima

c. Saya akan memberi anda uang apabila saya lulus ujian atau saya mendapat hadiah TTS

Jawab

a. P = saya berlibur ke Bali, Q = Saya lulus ujian Kalimatnya menjadi : P Q

b. P = 273 habis dibagi 3, Q = 273 merupakan bilangan primaKalimatnya menjadi :

P Q

c. P = Saya memberi Anda uang, Q = Saya lulus ujian, dan R = saya mendapat hadiah TTS .Kalimatnya menjadi : P Q R

Tentukan nilai kebenaran pernyataan-pernyataan dibawah ini :

a. Jika Jakarta bukan ibukota RI, maka 9 juga bukan bilangan prima

b. 2+2 = 2x2 hanya bila 2 =0

c. 2<3 merupakan syarat cukup untuk 2x2 < 3x3

a. Benar, karena anteseden salah (Jakarta bukan ibu kota RI)

b. Salah, karena anteseden (2+2 = 2x2) benar sedangkan konsekuennya (2 = 0 ) salah

c. Benar, karena konsekuennya (2x2 <3x3) benar

3. Tentukan nilai kebenaran daripada :

a. Syarat perlu dan cukup agar 7 merupakan bilangan prima adalah Kebumen berada di Jawa

Timur B ↔ S =S

b. Apabila 12 habis dibagi 4 ekuivalen dengan 12 bilangan bilangan genap maka

(a+b)^2 = a^2 + 2ab +b^2 B → B = B

4. Tuliskan dengan simbol logika kalimat-kalimat dibawah ini :

a. Matahari sangat verah dan kelembabannya tidak tinggi p ^ q

b. Jika saya dapat menyelesaikan koreksi saya sebelum makan malam dan tidak hujan, maka

saya akan pergi nonton tonil (p ^ q) → r

c. Jika Anda tidak menjumpai saya besok, berarti saya sudah pergi ke Bandung.¬ p →q

d. Syarat perlu dan cukup agar bilangan a merupakan bilangan prima adalah a merupakan

bilangan gasal atau sama dengan 2 p ↔ (q ˅ r)

Buatlah table kebenaran

1.(p ^ ¬ q) v r

p q r p ˄ ¬q (p ˄ ¬q) ˅ rT T T F TT T F F FT F T T TT F F T TF T T F TF T F F FF F T F TF F F F F

2. .(p ˅ ¬ q) ˄ (¬ p v q )

p q r p v ¬q ¬p v q (p v ¬q) ˄ (¬p v q )T T T T T TT T F T T TT F T T F FT F F T F FF T T F T FF T F F T FF F T T T TF F F T T T

3.(p → q) ˄ r

p q r p → q (p → q) ˄ rT T T T TT T F T FT F T F FT F F F FF T T T TF T F T FF F T T TF F F T F

4.(¬ q→ ¬ p) ˄ r

p q r (¬q → ¬p) (¬q →¬ p) ˄ rT T T T TT T F T F

T F T F FT F F F FF T T T TF T F T FF F T T TF F F T F

Contoh :

1. Notasi Polandia : Epq

Disajikan dalam notasi yang lain.

a. p q b. p q c. p q

2. Notasi Polandia : CKpqr

Disajikan dalam notasi yang lain.

C(p&q)r = (p&q) r

3.Notasi Polandia : CpCpr

Disajikan dalam notasi yang lain.

Cp (p r) = p (p r)

Contoh

( ( p q ) r ) ( ( p r ) q

( K p q ) r ) ( ( p r ) q

C ( K p q ) r ( ( p r ) q

C ( K p q ) r ( ( ( p ( N r ) ) q )

C ( K p q ) r ( K p ( N r ) q )

C ( K p q ) r ( K p ( N r ) ( N q ) )

C ( K p q ) r ( C ( K p ( N r ) ( N q ) )

E ( C ( K p q ) r ( C ( K p ( N r ) ( N q ) ) )

E C Kpq r C Kp N r N q

Prioritas dengan Operator.

Seperti pada ungkapan dalam ilmu hitung, maka didalam operator logika pun terdapat prioritas sebagai berikut :

1). Operator mempunyai prioritastertinggi

2). Operator berprioritas berikutnya

3). Operator berprioritas berikutnya

4). Operator berprioritas berikunya

5). Dan seterusnya operator yang lain termasuk dan seterusnya.

Contoh

1). p q r s dapat diinterpretasikan sebagai (p q) (r s)

2). p q akan diinterpretasikan dengan (p) q

3). “Saya lapar” dan “saya malas” atau “Saya bahagia” dan

“Saya telah makan enak” diartikan sebagai ????

Tabel kebenaran untuk bentuk yang komplek

1.( ¬ p ˄ q) ↔ r

¬ P ˄ q ↔ r2 1 3 1 4 1F T F T F TF T F T T FF T F F F TF T F F T FT F T T T TT F T T F FT F F F F TT F F F T F

2.¬ ( p v q ) ^ (¬ p v ¬r)

¬ p v q ^ ¬ P v ¬ r4 1 3 1 5 2 1 3 2 1F T T T F F T F F TF T T T F F T T T F

T T T F F F T F F TF T T F F F T T T FF F T T T T F F F TF F T T T T F T T FT F T F T T F F F TT F F F T T F T T F

3.p → q → ¬ r

p → q → ¬ r1 3 1 4 2 1T T T F F TT T T T T FT F F T F TT F F T T FF T T F F TF T T T T FF F F F F TF F F F T F

4.¬ p ˄ ¬q v q ˄ ¬r

¬ p ˄ ¬ q v q ^ ¬ r2 1 3 2 1 4 1 3 2 1F T F F T F T F F TF T F T T T T T T FT T F F F F F F F TF T F T F F F F T FF F T F T F T F F TF F T T T T T T T FT F T F F T F F F TT F T T F T F F T F

Aljabar Proposisi Aljabar proposisi adalah hukum-hukum aljabar yang dapat digunakan dalam proposisi.

Hukum-hukum tersebut adalah:

1. Idempoten 3. Distributif

p p p p (q r) (p q) (p r)

q q q p (q r) (p q) (p r)

2. Assosiatif 4. Komutatif

(p q) r p (q r) p q q p

(p q) r p (q r) p q q p

5. Identitas 7. Komplemen

p f p p ~p t

p t t p ~p f

p f f ~t f

p t p ~f t

6. Involution 8. De Morgan’s

~~p p ~(p q) ~p ~q

~(p q) ~p ~q

Contoh pemakaian hukum aljabar proposisi Sederhanakan proposisi berikut ini:

1.p (p q)

p (p q) (p f) (p q) …( hk.identitas )

p (f q) …( hk.distribusi )

p f …( hk.identitas )

p …( hk.identitas )

2. p (p q)

p (p q) T (p ^ T) v (p ^ q) …..(hk.identitas)

T P ^ (t v q)……………(hk.distributif)

T p ^ t ………………… (hk.identitas)

T p………………………….(hk.identitas)

INTERPRETASI

Andaikan S suatu himpunan formula proposisi, suatu interpretasi disebut model S jika setiap anggota S bernilai TRUE untuk interpretasi tersebut.

Contoh : Andaikan S adalah himpunan formula proposisi :

{ p q , q r , r s }

dan interpretasi :

I1 : {p=T,q=F,r=T,s=T} ; I2 : { p=T, q=T,s =T , r=T} ;

I3 : {p=T,q=T,r=F,s=F} ; I4 : { p=T, q=T,r =T, s=F} ;

Interpretasi yang mana yang merupakan model S ? Gambarkan tabel kebenarannya.

p q r s (p ^ q) (q v ¬ r) (r → s)I1 T F T T F F TI2 T T T T T T TI3 T T F F T T TI4 T T T F T T F

Dari tabel diatas maka interpretasi yang merupakan S adalah I2 dan I3.Perhatikan karena I1 sudah memberikan nilai kebenaran F untuk p q maka dua yang lain tak perlu di evaluasi, karena jelas bahwa I1 bukan model.

TAUTOLOGI

• Sebarang formula yang selalu bernilai TRUE, tak tergantung pada nilai kebenaran dari pada variabel-variabel proposisinya, disebut tautologi, dan dikatakan sebagai tautologis atau valid.

• Suatu tautologi adalah suatu formula proposisional yang mengambil nilai T untuk setiap interpretasi yang mungkin. Semua entri dalam kolom pada tabel kebenaran yang merupakan kolom nilai formula tersebut bernilai kebenaran T.

Contoh :

p p adalah Tautologi karena untuk I1 : p = T, maka p p = T

I2 : p = F, maka p p = T dan tak ada lagi interpretasi lain. Untuk menyatakan bahwa suatu formula adalah suatu tautologi/valid maka dituliskan dengan menggunakan metasimbol ╞ , maka contoh diatas menjadi :

╞ (p p)

Tabel dari kebenaran p p adalah :

p ¬p ¬p v pT F TF T T

Tabel dari kebenaran p (p (q p)) adalah :

P ↔ ( ¬ P v (q ^ ¬ p1 5 2 1 4 1 3 2 1T F F T F T F F TT F F F F F F F TF F T T T T T T FF F T F T F F T F

Perhatikan hubungan antara metasimbol =T dng ╞ Yang dapat dilihat pada contoh dibawah ini :

Menggunakan ╞ menggunakan =T

╞ p (p) p =T (p)

╞ (p q) (q p) p q =T q p

╞ (p q) (p)(q) (p q) =T (p) (q)

╞ ((p q )) ((p) (q)) ((p q)) =T (( p) (q))

Baris pertama kiri dibaca : p (p) adalah suatu tautologi, kanan :Formula p mempunyai tabel kebenaran sama dengan formula (p)

Dikatakan bahwa dua formula P dan Q adalah Ekuivalen Logis jika ekuivalen logisnya

‘ P Q’adalah suatu tautologi ( yang dapat dikatakan juga dengan bahwa mereka mempunyai tabel ke benaran yang sama)Dikatakan bahwa suatu formula P implai logis

suatu formula Q jika implikasi logis mereka‘ P Q’ adalah tautologi.

Absurditi/Kontradiksi

Sebarang formula yang selalu bernilai kebenaran F, tak tergantung pada nilai kebenaran dari

pada variabel-variabel proposisinya, disebut Absurditi atau Kontradiksi atau Unsatisfiable

dan dikatakan sbg Absurditi atau Invalid.

Suatu Absurditi adalah suatu formula proposisional yang ber nilai F untuk setiap interpretasi

yang mungkin. Semua entri dalam kolom pada tabel kebenaran yang merupakan kolom nilai

formula tersebut bernilai kebenaran F.

Contoh :

(p p) dan (p p)

adalah absurditi/kontradiksi karena untuk :

I1 : p = T, maka (p p) = F

I2 : p = F, maka (p p) = F

dan tak ada lagi interpretasi lain.Perhatikan bahwa suatu formula proposisional P

yang adalah suatu absurditi, maka formula P adalah suatu Tautologi, begitu pula sebaliknya.Jika sebarang formula P adalah suatu absurditi, maka ditulis :

╞ P

FORMULA CAMPUR

• Sebarang formula yang, tergantung pada nilai kebenaran daripada variabel-variabelnya, dapat bernilai baik nilai T maupun nilai F disebut suatu formula campur, atau ada yang menyebut contingent.

Contoh :

• Tentukan mana yang merupakan tautologi, absurditi, atau formula campur :

a) p (q p) ;

b) p (p (q p) ;

c) p (p (q p)).

P ↔ ( ¬ q → p1 4 2 1 3 1T T F T T TT T T F T TF F F T T FF T T F F F

P ↔ ( ¬ V (q ^ ¬ P

1 5 2 4 1 3 2 1T F F F T F F TT F F F F F F TF F T T T T T FF F T T F T T F

¬ P ↔ (¬ P ^ (q → ¬ P)2 1 5 2 1 4 1 3 2 1F T T F T F T F F TF T T F T F F T F TT F T T F T T T T FT F T T F T F T T F

Valid , Tautology, Satisfiable, dan Contradictory

Suatu formula P dikatakan valid/benar jika ia true/benar untuk setiap interpretasi (I) daripada P. Formula- formula valid daripada logika proposional disebut Tautologi.

Suatu formula P dikatakan Satisfiable/Dapat-puas/Memuaskan jika ia true dibawah suatu interpretasi (I) daripada P.

Suatu formula P dikatakan kontradiksi/ contradictory ( unsatis fiable/ tak terpenuhi) jika ia false dibawah setiap/ semua inter pretasi (I) daripada P.

Catatan : pada bukunya Zohar Manna and Richard Waldinger formula ditulis dengan sentence/closed formula.

Implies, Equivalent, dan Consistent

Suatu kalimat P implies suatu kalimat Q jika, untuk sebarang Interpretasi (I) daripada P dan Q, jika P true untuk I maka Q true untuk I.

Dua kalimat P dan G ekuivalen/ equivalent jika setiap interpre tasi (I) untuk P dan G , P mempunyai nilai kebenaran yang sama dengan nilai kebenarannya G.

Seperangkat kalimat P1,P2,P3,…. Dikatakan konsisten jika terdapat suatu interpretasi untuk P1,P2,P3,…. dibawah setiap Pi bernilai true.

Fungsi Kebenaran/Truth Functions

Fungsi Kebenaran (kadang disebut suatu operator logis) adalah suatu fungsi yang mengambil nilai-kebenaran sebagai argumen dan selalu menghasilkan salah satu dari nilai T atau nilai F. Suatu fungsi kebenaran dapat mempunyai sejumlah operand (kadang-kadang disebut argument Suatu fungsi dengan satu operand disebut suatu fungsi kebenaran monadika ( ).Jika mempunyai dua operand disebut dengan fungsi kebenaran diadika (, , , ),jika tiga triadika ( If… then … else … ) .

Bentuk-bentuk dasar menarik kesimpulan

1. Conjunction 2. Addition 5. Modus Tollens

p p p q

q p q ~ q

p q ~ p

3. Construction Dilemma 4. Modus Ponens 6. Hypothetical syllogism

p q p q p q

p ~ q q r

q ~ p p r

7. Simplification 8. Disjunctive syllogism

p q p q

p ~ p

q

9. Destructive Dilemma 10. Absorption

( p q ) ( r s ) p q

~ q ~ s

~ p ~ r p (p q)

Contoh pemanfaatan:

Buatlah kesimpulan dari argumen di bawah ini sehingga argumen tersebut valid

1. Jika hasilnya akurat maka sistemnya digital

2. Jika sistem digital maka menggunakan bil. Biner

3. Hasilnya akurat

Jawab

Premis 1 : p q

Premis 2 : q r

Premis 3 : p

Dengan hypothetical syllogism

p q

q r

p r

Sehingga argumentasi dapat ditulis kembali:

p r

p

?

Dengan Modus Ponen, konklusinya adalah r

p r

p

r

Adalah valid

p q r p →q q → pT T T T TT T F T FT F T F TT F F F TF T T T TF T F T FF F T T TF F F T T

PEMBUKTIAN VALIDITAS KALIMAT LOGIKA

ASUMSI SALAH

ᴑ Perlu pembuktian nilai True untuk semua interpretasi (2n)

ᴑMembutuhkan langkah pembuktian yang panjang

ᴑ Akan lebih mudah membuktikan bahwa ada 1 interpretasi yang menyebabkan nilai kalimat salah Tidak valid

ᴑAsumsi salah tidak mungkin terjadi Valid

Contoh Soal 2.1

Buktikan validitas kalimat A : if ((not x) or (not y)) then (not(x and y))

Jawab :

Bentuk kalimat implikasi A : A1 A2 (¬ x ¬ y) ¬ (x y)

Misalkan A diasumsikan salah yang berarti :

Antesenden/premis/hipotesis A1 benar (¬ x ¬ y) = T

konklusi/konsekuen A2 salah ¬(x y) = F

Ada dua cara pembuktian valid/tidak valid A : (¬ x ¬ y) ¬ (x y)

a.) Dimulai dari konklusi dulu (A2 = F) periksa apakah hipotesisnya (A1 = T) ?

b). Dimulai dari hipotesisnya dulu (A1 = T) periksa apakah konklusinya (A2 = F) ?

a). Konklusi A2 : ¬ (x y) = F (x y) = T x = T dan y =T

Periksa hipotesis A1 : (¬ x ¬ y) = F F = F seharusnya A1 = T

Asumsi A = F tidak pernah terjadi kalimat A valid

b) Hipotesis A1 = (¬ x ¬ y) = T, ada beberapa kemungkinan:

Hipotesis A1 Akibatnya pada konklusi A2

Kondisi A2 yang diperoleh dari asumsi salah

Kontradiksi ?

(¬ x ¬ y) = T ¬ (x y) Ya/tidak

x = F dan y = F T F Ya

x = F dan y = T T F Ya

x = T dan y = F T F Ya

Asumsi A = F tidak pernah terjadi kalimat A valid

Contoh Soal 2.2

Buktikan validitas kalimat B : (if x then y) if and only if ((not x) or y)

Jawab :

Bentuk kalimat biimplikasi B: B1 B2 (x y) (¬x y)

Misalkan B diasumsikan salah, maka ada 2 kemungkinan :

a). hipotesis B1 benar (x y) = T dan konklusi B2 salah (¬x y) = F

b). hipotesis B1 salah (x y) = F dan konklusi B2 benar (¬x y) = T

a1). Dimulai dari hipotesis dulu (x y) = T dan (¬x y) = F

Hipotesis B1

(x y) = T

Akibatnya pada konklusi B2

(¬x y) = F

Kondisi yang diperoleh dari asumsi salah

Kontradiksi ?

Ya/tidak

x = T dan y = T T F Ya

x = F dan y = T T F Ya

x = F dan y = F T F Ya

a2). Dimulai dari konklusi dulu (x y) = T dan (¬x y) = F

Konklusi B2

(~x y) = F

Akibatnya pada hipotesis B1

(x y)

Kondisi yang diperoleh dari asumsi salah

Kontradiksi ?

Ya/tidak

x = T dan y = F F T Ya

b1). Dimulai dari hipotesis dulu (x y) = F dan (¬x y) = T

Hipotesis B1

(x y) = F

Akibatnya pada konklusi B2

(¬x y) = F

Kondisi B2 yang diperoleh dari asumsi salah

Kontradiksi ?

Ya/tidak

x = T dan y = F F T Ya

b2). Dimulai dari konklusi dulu (x y) = F dan (¬x y) = T

Konklusi B2

(¬x y) = T

Akibatnya pada hipotesis B1

(x y)

Kondisi B1 yang diperoleh dari asumsi salah

Kontradiksi ?

Ya/tidak

x = F dan y = T T F Ya

x = T dan y = T T F Ya

x = F dan y = F T F Ya

Jadi asumsi B = F tidak pernah terjadi kalimat B valid

Contoh Soal 2.3

Buktikan validitas kalimat C : if (if x then y) then (if (not x) then (not y))

Bentuk kalimat implikasi C : C1 C2 (x y) (¬x ¬y)

Misalkan C diasumsikan salah yang berarti :

hipotesis C1 benar (x y) = T

konklusi C2 salah (¬x ¬ y) = F

Dimulai dari hipotesis dulu : (x y) = T dan (¬x ¬ y) = F

Hipotesis C1

(x y) = T

Akibatnya pada konklusi C2

(~x ¬ y)

Kondisi C2 yang diperoleh dari asumsi salah

Kontradiksi ?

Ya/tidak

x = T dan y = T T F Ya

x = F dan y = T F F Tidak

x = F dan y = F T F Ya

Dimulai dari konklusi dulu : (x y) = T dan (¬x ¬y) = F

Konklusi C2(¬x ¬y) = F

Akibatnya pada hipotesis C1 (x y)

Kondisi C2 yang diperoleh dari asumsi salah

Kontradiksi ?

Ya/tidak

x = F dan

y = T

T F Ya

Jadi asumsi C = F dapat terjadi kalimat C tidak valid

Cara Langsung

Contoh 1:

Buktikan validitas kalimat A : if ((not x) or (not y)) then (not(x and y))

Dibentuk notasi: A : (¬ x ¬ y) ¬ (x y)

(¬ X ¬ y) ¬ (x y)

2 1 3 2 1 5 4 1 3 1

F T F F T T F T T T

F T T T F T T T F F

T F T F T T T F F T

T F T T F T T F F F

Karena A bernilai T untuk masing-masing kasus, maka A Valid

1.Buktikan validitas kalimat B : (if x then y) if and only if ((not x) or y)

(x → y) ↔ ((¬ x) v y)1 3 1 4 2 1 3 1T T T T F T T TT F F T F T F FF T T T T F T TF T F T T F T F

Karena A bernilai T masing-masing kasus, maka A Valid

2. if (if x then y) then (if (not x) then (not y))

(x → y) → ((¬ x) → ¬ y1 3 1 4 2 1 3 2 1T T T T F T T F TT F F T F T T T FF T T F T F F F TF T F T T F T T F

3.Buktikan validitas kalimat D : if(if(not x) then y) then if(not y) then x) and (x or y)

D : ( x y) ( ( y x) (x y))

(¬ x → y) → ((¬ y v x) ˄ (x v y))2 1 3 1 5 2 1 3 1 4 1 3 1F T T T T F T T T T T T TF T T F T T F T T T T T FT F T T T F T T F T F T TT F F F T T F T F F F F F

4. Tentukan validitas kalimat (p q) ( p r) (q r) dengan menggunakan asumsi salah

(p q) ( p r) ( q r)

T2 T1 F F1

T3 F3 T4 F4 F2 F2

T T2

F5

F

Pohon Semantik

Metode lain yang digunakan untuk pengujian validitas suatu kalimat adalah dengan teknik pohon semantik (semantic tree technique)

Misalkan suatu kalimat logika A terdiri dari 3 proposisi p, q dan r

Pohon semantik dimulai dengan cabang tertinggi untuk proposisi pertama (p)

Cabang tertinggi ini terdiri cabang kiri (T) dan cabang kanan (F)

p = F

p = T

3F

p = F

p = T

p = T 1

3

2

Perhatikan cabang kiri No. 2 :

• Bila dengan p = T nilai kebenaran dari A sudah dapat ditentukan (bernilai benar atau salah), maka cabang No. 2 ini tidak bercabang, misalkan nilainya salah

• Bila belum dapat ditentukan, maka cabang ini akan bercabang lagi, yaitu cabang kiri (T) dan cabang kanan (F) untuk proposisi kedua q

Perhatikan cabang kiri No. 4 :

• Bila dengan p = T dan q = T nilai kebenaran dari A sudah dapat ditentukan (bernilai benar atau salah), maka cabang No. 4 ini tidak bercabang, misalkan nilainya benar

• Bila belum dapat ditentukan, maka cabang ini akan bercabang lagi, yaitu cabang kiri (T) dan cabang kanan (F) untuk proposisi ketiga r

Langkah-langkah tersebut di atas diulangi lagi untuk cabang-cabang lain

3p = F

p = T

q = Fq = T

5 3

4p = F

q = T5

Kalimat logika dikatakan valid bila semua cabangnya bernilai benar, bila ada cabangnya yang bernilai salah, maka kalimat tsb dikatakan tidak valid

Bila semua cabang bercabang lagi, maka pohon semantiknya menjadi :

7

6r = F

r = T

q = F

q = T53T

p = Fp = T

q = F

Contoh Soal 2.4

Tentukan validitas kalimat G : if (if x then y) then (if (not x) then (not y))

Jawab :

Bentuk kalimat implikasi G :G1 G2

G : (p q) ( p q)

Periksa cabang No. 2 :

Bila p = T, maka p = F

G2 : ( p q) = T apapun nilai q

Bila ( p q) = T,

maka G = T apapun nilai G1 : (p q)

Nilai G sudah dapat ditentukan, yaitu bernilai T

Bentuk kalimat G implikasi :G1 G2

G : (p q) ( p q)

Periksa cabang No. 3 :

Bila p = F, maka G1: (p q) = T apapun nilai q

p = T, nilai G2 : ( p q) tergantung pada nilai q

Bila q = T, maka G2 = T dan bila q = F, maka G2 = F

Bila G2 = T, maka G = T dan bila G2 = F, maka G = F

Jadi nilai G belum sudah dapat ditentukan, cabang No. 3 bercabang lagi

T p = T

T r = F

r = TT

r = F

r = T T

F T