Bab I. Logika Proposisi Logika Proposisi atau Kalkulus Proposisi dikembangkan oleh ahli filsafat Yunani Aristotle 2300 tahun lebih. Definisi 1. Suatu proposisi (proposition) adalah suatu pernyataan (statement) yang memiliki nilai kebenaran true (benar, T) atau false (salah, F) tetapi tidak kedua-duanya pada saat dinyatakannya. Contoh 1. Pernyataan berikut adalah proposisi: (a) Jakarta adalah ibu kota Indonesia. (b) Penang adalah ibu kota Malaysia. (c) 5 + 6 = 11. (d) 25 + 2 = 26. Proposisi (a) dan proposisi (c) bernilai true, sedangkan proposisi (b) dan proposisi (d) bernilai false. 1

Contoh 2. Pernyataan berikut bukan proposisi : (a) Jam berapa sekarang ? (b) Bacalah dengan teliti. (c) x + 1 = 2. (d) x + y = z. Kalimat (a) dan kalimat (b) masing-masing bukan pernyataan, jadi bukan proposisi. Kalimat (c) merupakan pernyataan tetapi bukan suatu proposisi, karena variabel x dalam kalimat tersebut belum ada nilainya, jadi masih dapat bernilai true (bila x bernilai 1) juga dapat bernilai false (bila x ≠ 1). Begitu pula dengan kalimat (d).

2

Proposisi yang bernilai tetap pada setiap saat disebut konstanta proposisi. Dikenal dua buah konstanta proposisi:

• Proposisi true atau T, yang selalu bernilai true • Proposisi false atau F, yang selalu bernilai false.

Proposisi lainnya, yang nilainya bisa true atau false pada saat yang berbeda disebut juga sebagai variabel proposisi, dapat dinyatakan oleh sebuah huruf. Misalnya, p, q, r, s, ……, p1, p2, ……, q1, q2, ……, r1, r2, ……, s1, s2, ……

3

Operator Logika atau Penghubung Logika (Logical Connectives) Dari proposisi-proposisi yang ada dapat dibentuk proposisi baru dengan menggunakan penghubung atau operator logika. Yang dikenal ada 6 operator logika, yaitu

negasi ¬, konjungsi ∧, disjungsi ∨, exclusive or ⊕, implikasi →, dan bi-implikasi (biconditional) ↔,

masing-masing didefinisikan sebagai berikut:

4

1. Operator negasi ¬ Definisi 2. Jika p adalah sebuah proposisi, maka ¬p (atau p) adalah sebuah proposisi pula. ¬p disebut negasi (negation) dari p, atau tidak p (not p). Nilai kebenaran dari ¬p adalah true bila p bernilai false, dan bernilai false bila p bernilai true. Hubungan antara nilai kebenaran dari p dan negasinya ¬p dapat pula dinyatakan dalam suatu tabel yang disebut Tabel Kebenaran sebagai berikut:

Tabel Kebenaran untuk Negasi dari pp ¬p T F F T

5

Contoh 3. (a) Negasi proposisi “Jakarta adalah ibu kota Indonesia” adalah “Jakarta bukan ibu kota Indonesia” atau

“Tidak benar bahwa Jakarta bukan ibu kota Indonesia”. (b) Jika p mewakili proposisi

“Luas ruang kuliah ini lebih dari 16 m2”, maka ¬p mewakili proposisi

“Luas ruang kuliah ini kurang dari atau sama dengan 16 m2” atau “Tak benar bahwa luas ruang kuliah ini lebih dari 16 m2”.

6

2. Operator Konjungsi ∧ Definisi 3. Jika p dan q adalah proposisi maka “p dan q” atau p ∧ q adalah sebuah proposisi pula, yang disebut sebagai konjungsi (conjunction) dari p dan q. Dan nilai kebenaran dari p ∧ q adalah true pada saat p dan q kedua-duanya bernilai true, dan false bila salah satu atau kedua-duanya dari p dan q bernilai false. Dan dapat ditunjukkan oleh tabel kebenaran berikut:

Tabel Kebenaran untuk Konjungsi dari p dan qp q p ∧ q T T TT F FF T FF F F

7

Contoh 4. Jika p : Hari ini adalah hari Selasa.

q : Hari ini hujan. maka p ∧ q : Hari ini adalah hari Selasa dan hari ini hujan atau Hari ini adalah hari Selasa dan hujan p ∧ q bernilai T hanya pada hari Selasa yang hujan, dan bernilai F pada hari lainnya atau pada hari Selasa yang tidak hujan.

8

3. Operator Disjungsi ∨ Definisi 4. Jika p dan q adalah proposisi maka “p atau q” atau p ∨ q adalah sebuah proposisi pula, yang disebut sebagai disjungsi (disjunction) dari p dan q. Dan nilai kebenaran dari p ∨ q adalah false pada saat p dan q kedua-duanya bernilai false, dan true bila salah satu atau kedua-duanya dari p dan q bernilai true. Dan dapat ditunjukkan oleh tabel kebenaran berikut:

Tabel Kebenaran untuk Disjungsi dari p dan q p q p ∨ q T T TT F TF T TF F F

9

Contoh 5. Jika p : Hari ini adalah hari Selasa

q : Hari ini hujan maka p ∨ q : Hari ini adalah hari Selasa atau hari ini hujan p ∨ q bernilai F apabila harinya bukan hari Selasa dan pada hari itu tidak hujan, dan bernilai T apabila harinya adalah hari Selasa atau apabila harinya hujan.

10

4. Operator Exclusive Or ⊕ Definisi 5. Jika p dan q adalah proposisi maka exclusive or dari p dan q atau p ⊕ q adalah sebuah proposisi pula. Dan nilai kebenaran dari p ⊕ q adalah true pada saat p dan q memiliki nilai kebenaran yang berbeda, dan false bila p dan q memiliki nilai kebenaran yang sama. Dan dapat ditunjukkan oleh tabel kebenaran berikut:

Tabel Kebenaran untuk Exclusive or dari p dan qp q p ⊕ q T T FT F TF T TF F F

11

Contoh 6. Jika p : Hari ini adalah hari Selasa

q : Hari ini hujan maka p ⊕ q : Hari ini adalah hari Selasa yang tidak hujan atau hari ini bukan hari

Selasa tetapi hujan. p ⊕ q bernilai F pada setiap hari Selasa yang hujan atau pada hari-hari bukan hari Selasa yang tidak hujan, dan bernilai T pada hari Selasa yang tidak hujan atau pada hari lainnya yang hujan.

12

5. Operator Implikasi → Definisi 6. Jika p dan q adalah proposisi maka Implikasi (Implication) p → q, dibaca “Jika p maka q“, adalah sebuah proposisi pula. p disebut hipotesa atau antecedent atau premise, q disebut konklusi (conclusion) atau konsekuensi (consequence). Dan nilai kebenaran dari p → q adalah false hanya pada saat p bernilai true dan q bernilai false, selainnya p → q akan bernilai true. Dan dapat ditunjukkan oleh tabel kebenaran berikut:

Tabel Kebenaran untuk Implikasi dari p ke q p q p → q T T TT F FF T TF F T

13

Contoh 7. Jika p : Hari ini adalah hari Selasa

q : Hari ini hujan maka p → q : Jika hari ini adalah hari Selasa maka hari ini hujan. p → q bernilai F hanya pada hari Selasa yang tidak hujan, dan bernilai T pada hari Selasa yang hujan atau pada hari yang bukan hari Selasa. “Jika p maka q“ dapat pula dikatakan sebagai

“p mengakibatkan q” Atau “p hanya jika q” atau “p adalah syarat cukup untuk q” atau “q jika p” atau “q apabila p” atau “q adalah syarat perlu untuk p”. 14

6. Operator Bi-implikasi (Biconditional) ↔ Definisi 7. Jika p dan q adalah proposisi maka biconditional p ↔ q juga sebuah proposisi, dibaca “p jika dan hanya jika q“, atau “p adalah syarat perlu dan cukup untuk q”. Dan nilai kebenaran dari p ↔ q adalah true pada saat p dan q memiliki nilai kebenaran yang sama, dan false bila p dan q memiliki nilai kebenaran yang berbeda. Dan dapat ditunjukkan oleh tabel kebenaran berikut:

Tabel Kebenaran untuk Bi-implikasi dari p dan q p q p ↔ q T T TT F FF T FF F T

15

Contoh 8. Jika p : Hari ini adalah hari Selasa q : Hari ini hujan maka p ↔ q : Hari ini adalah hari Selasa jika dan hanya jika hari ini hujan, atau

Hari ini adalah hari Selasa adalah syarat perlu dan cukup agar hari ini hujan.

p ↔ q bernilai F hanya pada hari Selasa yang tidak hujan atau hari lain yang

hujan, dan bernilai T pada hari Selasa yang hujan atau pada hari lain yang tidak hujan.

16

Kalimat Logika Proposisi Definisi 8. Kalimat (Formula) Logika Proposisi dibentuk dari - konstanta proposisi : T (true), F (false) - variabel proposisi : p, p1, p2, …, q, q1, q2, …, r, r1, r2, …, s, s1, s2, … dengan menggunakan penghubung proposisi berikut: - negasi ¬ ( tidak ) - konjungsi ∧ (dan) - disjungsi ∨ ( atau ) - exclusive or ⊕ (atau eksklusif ) - implikasi → ( jika … maka …) - biconditional ↔ (jika dan hanya jika) dan mengikuti aturan-aturan berikut: (a) Setiap proposisi merupakan sebuah kalimat logika proposisi (KLP) (b) Jika F dan G merupakan sebuah KLP maka ¬ F, F ∧ G, F ∨ G, F ⊕ G, F → G, dan F ↔ G masing-masing juga merupakan sebuah KLP. KLP F dan G yang dipakai untuk membentuk KLP H yang lebih kompleks dengan aturan (b) tadi disebut komponen dari KLP yang bersangkutan dan disebut sebagai anak kalimat dari H. H juga merupakan anak kalimat dari H. Anak kalimat dari H yang bukan H disebut anak kalimat sejati dari H. 17

Contoh 9. KLP H: ( p ⊕ q ) ∨ ( p ⊕ ¬q ) memiliki anak kalimat : G: p ⊕ q K: p ⊕ ¬q dan H sendiri. G memiliki anak kalimat p dan q dan G. K memiliki anak kalimat p dan K1: ¬q dan K. K1 memiliki anak kalimat q dan K1. Nilai kebenaran dari sebuah KLP (selanjutnya nilai kebenaran disingkat oleh nilai saja) ditentukan dari nilai anak kalimatnya berdasarkan Definisi 2 s/d 7. Jadi nilai KLP H pada Contoh 9 ditentukan oleh nilai KLP G dan K. Nilai KLP G ditentukan oleh nilai proposisi p dan q. Nilai KLP K ditentukan oleh nilai proposisi p dan KLP K1. Nilai KLP K1 ditentukan oleh nilai proposisi q. Jadi nilai KLP H pada Contoh 9 ditentukan oleh nilai variabel proposisi p dan q yang ada di H. 18

Interpretasi dan Tabel Kebenaran Definisi 9. Suatu interpretasi (interpretation) I adalah suatu pemberian nilai T atau F pada setiap proposisi yang terpakai. Interpretas I disebut interpretasi kosong (empty interpretation) apabila I tidak memberi nilai pada proposisi apapun. Interpretasi I disebut interpretasi untuk sebuah KLP H bila I memberi nilai pada setiap variabel proposisi yang ada pada H.

19

Contoh 10. Interpretasi untuk KLP H pada Contoh 9 ada 4 buah, yaitu

1 : p bernilai T, q bernilai T 2 : p bernilai T, q bernilai F 3 : p bernilai F, q bernilai T 4 : p bernilai F, q bernilai F Jadi nilai H terhadap masing-masing interpretasi dapat ditentukan melalui sebuah tabel yang disebut

Tabel Kebenaran untuk H seperti berikut: Interpretasi G1: ¬q F: p ⊕ q G: p ⊕ G1 H: F ∨ G

1: p(T), q(T) F F T T2: p(T), q(F) T T F T 3: p(F), q(T) F T F T4: p(F), q(F) T F T T

Jadi KLP H bernilai true terhadap setiap interpretasi untuknya. 20

Contoh 11. Tentukan semua nilai yang mungkin dari KLP H: (p ∨ q) ∧ (¬p ∧ ¬q). Interpretasi untuk KLP H adalah 1 : p bernilai T, q bernilai T 2 : p bernilai T, q bernilai F 3 : p bernilai F, q bernilai T 4 : p bernilai F, q bernilai F Semua nilai yang mungkin dari KLP H diberikan pada tabel kebenaran berikut:

Interpretasi ¬p ¬q p ∨ q ¬p ∧ ¬q H: (p ∨ q) ∧ (¬p ∧ ¬q) 1: p(T), q(T) F F T F F 2: p(T), q(F) F T T F F 3: p(F), q(T) T F T F F4: p(F), q(F) T T F T F

Jadi KLP H bernilai false terhadap setiap interpretasi untuknya.

21

Contoh 12. Tentukan semua nilai yang mungkin dari KLP H: (p ∨ q) ∧ ¬r. Interpretasi untuk KLP H adalah 1 : p bernilai T, q bernilai T, r bernilai T 2 : p bernilai T, q bernilai T, r bernilai F 3 : p bernilai T, q bernilai F, r bernilai T 4 : p bernilai T, q bernilai F, r bernilai F 5 : p bernilai F, q bernilai T, r bernilai T 6 : p bernilai F, q bernilai T, r bernilai F 7 : p bernilai F, q bernilai F, r bernilai T 8 : p bernilai F, q bernilai F, r bernilai F Semua nilai yang mungkin dari KLP H diberikan pada tabel kebenaran berikut:

22

Interpretasi ¬r p ∨ q H: ( p ∨ q ) ∧ ¬r

1: p(T), q(T), r(T) F T F 2: p(T), q(T), r(F) T T T3: p(T), q(F), r(T) F T F4: p(T), q(F), r(F) T T T5: p(F), q(T), r(T) F T F6: p(F), q(T), r(F) T T T7: p(F), q(F), r(T) F F F8: p(F), q(F), r(F) T F T

Jadi KLP H tidak bernilai true terhadap setiap interpretasi untuknya. Tetapi terdapat interpretasi terhadapnya H bernilai true. Dari Contoh 10, 11 dan 12 terlihat bahwa KLP-KLP dapat diklasifikasikan menjadi tiga jenis.

23

Definisi 10. Sebuah KLP H disebut absah (valid) bila H bernilai true terhadap setiap interpretasi I untuk H. H disebut juga suatu tautologi (tautology). Sebuah KLP H disebut terpenuhi (satisfiable) bila terdapat interpretasi I untuk H sehingga H bernilai true terhadap I itu. Sebuah KLP H disebut kontradiksi (contradictory/unsatisfiable) bila H bernilai false terhadap setiap interpretasi I untuk H. KLP H pada Contoh 10 adalah suatu KLP yang valid, KLP pada Contoh 11 adalah suatu KLP yang contradictory, dan KLP pada Contoh 12 adalah KLP yang satisfiable.

24

Skema Kalimat dan Kesetaraan Dapat dibuktikan bahwa masing-masing kalimat berikut adalah valid. (i) p ∨ ¬p (ii) q ∨ ¬q (iii) (p ∧ q) ∨ ¬(p ∧ q) Terlihat bahwa ketiga kalimat di atas memiliki bentuk yang ‘serupa’. Agar tidak perlu tiga kali membuktikan keabsahan tiga kalimat tersebut, dapat dipakai Skema Kalimat (Sentence Schema) berikut (*) H ∨ ¬H dengan H sebagai kalimat variabel. Pada (i) diambil p sebagai F, pada (ii) diambil q sebagai H, pada (iii) diambil (p ∧ q) sebagai H. Kalimat (i), (ii) dan (iii), yaitu kalimat yang diperoleh dari (*) dengan mengganti kalimat variabel H dengan sebuah kalimat tertentu disebut sebagai kalimat nyata (instance) dari skema kalimat (*). Jika skema kalimat (*) telah terbukti valid, maka setiap kalimat nyata dari (*) juga valid. 25

Untuk membuktikan keabsahan sebuah skema kalimat dapat dipakai cara yang sama untuk membuktikan keabsahan sebuah kalimat biasa. Definisi 11. Dua kalimat H dan K disebut setara (logically equivalent) jika kalimat H ↔ K valid (tautologi). Ditulis H ≡ K. atau H ⇔ K.

26

Skema Kalimat Absah berdasarkan Definisi F ≡ ¬T ( Definisi dari False ) ( H ↔ K ) ≡ (H ∧ K ) ∨ (¬H ∧ ¬K ) ( Definisi dari ↔ ) ( H ¬↔ K ) ≡ ¬(H ↔ K ) ( Definisi dari ¬↔ ) ( H → K ) ≡ (¬ H ∨ K ) ( Definisi dari → ) ( H → K ) ≡ (H ∧ K ) ↔ H ( Definisi dari → ) ( H → K ) ≡ (H ∨ K ) ↔ K ( Definisi dari → ) Skema Kalimat Absah berdasarkan Sifat Identitas ( H ∨ F ) ≡ H ( Identitas dari ∨ adalah F) ( H ∧ T ) ≡ H ( Identitas dari ∧ adalah T) T ≡ H ↔ H ( Identitas dari ↔ ) T → H ≡ H ( Identitas kiri dari → adalah T)

27

Skema Kalimat Absah berdasarkan Sifat Dominasi H ∨ T ≡ T ( Dominasi dari ∨ ) H ∧ F ≡ F ( Dominasi dari ∧) H → T ≡ T ( Dominasi kanan dari → ) Skema Kalimat Absah berdasarkan Sifat Idempoten H ∨ H ≡ H ( Idempoten dari ∨ ) H ∧ H ≡ H ( Idempoten dari ∧ ) Skema Kalimat Absah berdasarkan Sifat Refleksif H ≡ H ( Refleksif dari ↔) H → H ≡ T ( Refleksif dari →)

28

Skema Kalimat Absah berdasarkan Sifat Komutatif / Simetri ( H ∧ K ) ≡ ( K ∧ H ) ( Simetri dari ∧ ) ( H ∨ K ) ≡ ( K ∨ H ) ( Simetri dari ∨ ) ( H ↔ K ) ≡ ( K ↔ H ) ( Simetri dari ↔ ) ( H ¬↔ K ) ≡ ( K ¬↔ H ) ( Simetri dari ¬↔ ) Skema Kalimat Absah berdasarkan Sifat Asosiatif [ ( H ∧ K ) ∧ L ] ≡ [ H ∧ ( K ∧ L ) ] [ ( H ∨ K ) ∨ L ] ≡ [ H ∨ ( K ∨ L ) ] [ ( H ↔ K ) ↔ L ] ≡ [ H ↔ ( K ↔ L ) ] [ ( H ¬↔ K ) ¬↔ L ] ≡ [ H ¬↔ ( K ¬↔ L ) ]

29

Skema Kalimat Absah berdasarkan Sifat Transitif [ ( H → K ) ∧ ( K → L ) ] → ( H → L ) [ ( H ↔ K ) ∧ ( K ↔ L ) ] → ( H ↔ L )

Skema Kalimat Absah berdasarkan Sifat Kontrapositif ( H → K ) ≡ ( ¬ K → ¬ H ) (¬ H → K ) ≡ ( ¬ K → H ) ( H ↔ K ) ≡ ( ¬ K ↔ ¬ H )

Skema Kalimat Absah berdasarkan Sifat Distributif [ H ∧ ( K ∧ L ) ] ≡ [ ( H ∧ K ) ∧ ( H ∧ L ) ] ( Distributif ∧ terhadap ∧ ) [ H ∨ ( K ∨ L ) ] ≡ [ ( H ∨ K ) ∨ ( H ∨ L ) ] ( Distributif ∨ terhadap ∨ ) [ H ∧ ( K ∨ L ) ] ≡ [ ( H ∧ K ) ∨ ( H ∧ L ) ] ( Distributif ∧ terhadap ∨ ) [ H ∨ ( K ∧ L ) ] ≡ [ ( H ∨ K ) ∧ ( H ∨ L ) ] ( Distributif ∨ terhadap ∧ ) [ H ∨ ( K ↔ L ) ] ≡ [ ( H ∨ K ) ↔ ( H ∨ L ) ] ( Distributif ∨ terhadap ↔) [ H → ( K ↔ L ) ] ≡ [ ( H → K ) ↔ ( H → L ) ] (Distributif → terhadap ↔) ¬( H ↔ K ) ≡ ( H ↔ ¬K ) ( Distributif ¬ terhadap ↔)

30

Skema Kalimat Absah berdasarkan De Morgan ¬ ( H ∧ K ) ≡ (¬ H ∨ ¬ K ) ¬ ( H ∨ K ) ≡ (¬ H ∧ ¬ K ) Skema Kalimat Absah berdasarkan Dobel Negasi ¬(¬H ) ≡ H Skema Kalimat Absah berdasarkan Excluded Middle H ∨ ¬H ≡ T Skema Kalimat Absah berdasarkan Golden Rule H ∧ K ↔ H ≡ K ↔ H ∨ K Skema Kalimat Absah berdasarkan Kontradiksi ( H ∧ ¬H ) ≡ F

31

32

Skema Kalimat Absah berdasarkan Modus Ponens H ∧ ( H → K ) → H Skema Kalimat Absah berdasarkan Absorption H ∧ ( H ∨ K ) ≡ H H ∨ ( H ∧ K ) ≡ H H ∧ (¬H ∨ K ) ≡ H ∧ K H ∨ (¬H ∧ K ) ≡ H ∨ K Skema Kalimat Absah berdasarkan Weakening / Strengthening H ∧ K → H H ∧ K → H ∨ K H → ( H ∨ K ) H ∧ K → H ∧ ( K ∨ L ) H ∨ ( K ∧ L ) → H ∨ K Untuk membuktikan bahwa dua kalimat adalah setara dapat menggunakan kesetaraan kalimat-kalimat yang telah dibuktikan kesetaraannya.

Contoh 19. Buktikan bahwa H : ¬( p ∨ (¬p ∧ q)) setara dengan K : (¬p ∧ ¬q). Bukti: ¬( p ∨ (¬ p ∧ q )) ≡ ¬p ∧ ¬(¬p ∧ q ) ≡ ¬p ∧ (¬(¬p) ∨ ¬q ) ≡ ¬p ∧ ( p ∨ ¬q ) ≡ (¬p ∧ p ) ∨ (¬p ∧ ¬q ) ≡ F ∨ (¬p ∧ ¬q ) ≡ (¬p ∧ ¬q )

33

Contoh 20. Buktikan bahwa H : ( p ∧ q ) → ( p ∨ q ) adalah valid Bukti. ( p ∧ q ) → ( p ∨ q ) ≡ ¬( p ∧ q ) ∨ ( p ∨ q ) ≡ ( ¬p ∨ ¬q ) ∨ ( p ∨ q ) ≡ ( ¬p ∨ p) ∨ (¬q ∨ q )

≡ T ∨ T ≡ T

34

Logic Puzzles I. Two opposite kinds of inhabitants of an island An island that has two kinds of inhabitants:

knights (satria), who always tell the truth knaves (bangsat, penipu), who always lie.

You encounter two people A and B. If A says “B is a knight” and B says “The two of us are opposite type”, then can you tell what type are A and B? Solusi: Misalkan p := A adalah seorang satria yang selalu jujur

q := B adalah seorang satria yang selalu jujur

berarti ¬p := A adalah seorang penipu yang selalu berbohong

¬q := B adalah seorang penipu yang selalu berbohong 35

Kasus I: A adalah seorang satria yang selalu jujur, atau p bernilai true Kasus II: A adalah seorang penipu yang selalu berbohong, atau p bernilai false Untuk kasus I: (I.1) p bernilai true berarti pernyataan A benar, yaitu B adalah seorang satria yang selalu jujur. Berarti (I.2) q bernilai true, hal ini mengakibatkan pernyataan B benar, yaitu salah satu dari A dan B adalah satria, sedangkan yang satu lagi adalah penipu. Kenyataan ini dapat dinyatakan sebagai

(p ∧ ¬q) ∨ (¬p ∧ q) yang harus bernilai true. Sedangkan dalam keadaan (I.1) dan (I.2),

(p ∧ ¬q) ∨ (¬p ∧ q) ≡ (true ∧ ¬true) ∨ (¬true ∧ true) ≡ false. Terjadi kontradiksi, berarti kasus I tidak mungkin terjadi. 36

Untuk kasus II: (II.1) p bernilai false berarti pernyataan A tidak benar, yaitu B adalah seorang satria yang selalu jujur adalah tidak benar. Jadi haruslah (II.2) q bernilai false, hal ini mengakibatkan pernyataan B juga tidak benar, yaitu salah satu dari A dan B adalah satria, sedangkan yang satu lagi adalah penipu tidak benar. Berarti pernyataan

(p ∧ ¬q) ∨ (¬p ∧ q) yang harus bernilai false. Dan dalam keadaan (II.1) dan (II.2),

(p ∧ ¬q) ∨ (¬p ∧ q) ≡ (false ∧ ¬false) ∨ (¬false ∧ false) ≡ false. Tidak terjadi kontradiksi, berarti kasus II yang terjadi. Kesimpulannya: A dan B kedua-duanya adalah penipu.

37

Masalah ini dapat juga diselesaikan dengan meninjau kasus untuk si B: Kasus IB: B adalah seorang satria yang selalu jujur, atau q bernilai true Kasus IIB: B adalah seorang penipu yang selalu berbohong, atau q bernilai false Untuk kasus IB: (IB.1) q bernilai true berarti pernyataan B benar, yaitu salah satu dari A dan B adalah satria, sedangkan yang satu lagi adalah penipu. Kenyataan ini dapat dinyatakan sebagai (IB.2) (p ∧ ¬q) ∨ (¬p ∧ q) dan (IB.2) harus bernilai true. Perhatikan nilai kebenaran dari (IB.2) dalam keadaan (IB.1):

(p ∧ ¬q) ∨ (¬p ∧ q) ≡ (p ∧ ¬true) ∨ (¬p ∧ true)

≡ false ∨ (¬p ∧ true)

38

Karena (IB.2) harus bernilai true, jadi ¬p harus bernilai true. Dengan demikian p harus bernilai false. p bernilai false, memberi arti bahwa A adalah penipu, jadi pernyataan A, yaitu B adalah seorang satria adalah tidak benar, atau q bernilai false. Hal ini bertentangan dengan (IB.1). Jadi kasus IB tidak mungkin terjadi. Untuk kasus IIB: (IIB.1) q bernilai false berarti pernyataan B, yaitu salah satu dari A dan B adalah satria, sedangkan yang satu lagi adalah penipu adalah false. Hal ini berarti (IIB.2) (p ∧ ¬q) ∨ (¬p ∧ q) harus bernilai false. Dalam keadaan (IIB.1), nilai kebenaran (IIB.2) adalah

(p ∧ ¬q) ∨ (¬p ∧ q) ≡ (p ∧ ¬false) ∨ (¬p ∧ false)

≡ (p ∧ true) ∨ false.

39

Karena (IIB.2) harus bernilai false, jadi p harus bernilai false, atau A adalah penipu. Karena A adalah penipu, maka pernyataan A, yaitu B adalah seorang satria adalah tidak benar, hal ini tidak bertentangan dengan (IIB.1), yaitu q bernilai false, atau B adalah penipu. Kesimpulannya: A dan B kedua-duanya adalah penipu. II. Muddy children puzzle A father tells his two children, a boy and a girl, to play in their backyard without getting dirty. However, while playing, both children get mud on their foreheads. When the children stop playing, the father says

“At least one of you has a muddy forehead”, and then asks the children to answer “yes” or “no” to the question:

“Do you know whether you have a muddy forehead?” Assume that both children are honest and that each child can see whether his or her sibling has a muddy forehead, but cannot see his or her own forehead.

40

If the father asks the above question twice and the children should answer each question simultaneously, then what will the children answer each time the question asked? Solusi: Misalkan s := dahi si putra kotor

d := dahi si putri kotor Diketahui faktanya adalah s bernilai true, dan d juga bernilai true. Pernyataan si ayah kepada putra dan putrinya adalah

“At least one of you has a muddy forehead”, yang berarti bahwa proposisi

p := s ∨ d bernilai true. Dipertanyakan jawaban serentak apa yang diberikan oleh putra dan putrinya terhadap pertanyaan yang sama: “Do you know whether you have a muddy forehead?” 41

untuk yang pertama kali dan yang kedua kali.

42

Jawaban serentak si putra dan si putri untuk pertanyaan pertama kali: Si putra melihat dahi si putri kotor, berarti

d bernilai true, yang mengakibatkan p juga bernilai true. Jadi, si putra tidak dapat memastikan dahinya kotor atau tidak, maka ia akan menjawab ‘no’. Begitu pula dengan si putri, ia melihat dahi si putra kotor berarti

s bernilai true, yang mengakibatkan p juga bernilai true. Jadi, si putri tidak dapat memastikan dahinya kotor atau tidak, maka ia akan menjawab ‘no’. Jawaban serentak si putra dan si putri untuk pertanyaan kedua kali: Setelah si putra mengetahui jawaban ‘no’ dari si putri, berarti si putri mengetahui bahwa s bernilai true, maka si putra akan menjawab ‘yes’ untuk pertanyaan yang sama untuk yang kedua-kalinya. Begitu juga dengan si putri, ia akan menjawab ‘yes’ pula.

43