Matematika Diskrit : Logic Puzzles

📋 Daftar Isi

CASE 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 (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

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.

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.

Masalah ini dapat juga diselesaikan dengan meninjau kasus untuk si B:

Kasus I_B: B adalah seorang satria yang selalu jujur, atau q bernilai true

Kasus II_B: B adalah seorang penipu yang selalu berbohong, atau q bernilai false

Untuk kasus I_B:

(I_B.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

(I_B.2) (p ∧ ¬q) ∨ (¬p ∧ q) dan (I_B.2) harus bernilai true

Perhatikan nilai kebenaran dari (I_B.2) dalam keadaan (I_B.1):

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

≡ false ∨ (¬p ∧ true)

Karena (I_B.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 (I_B.1). Jadi, kasus I_B tidak mungkin terjadi.

Untuk kasus II_B:

(II_B.1) q bernilai false

berarti pernyataan B, yaitu salah satu dari A dan B adalah satria, sedangkan satu lagi adalah penipu adalah false. Hal ini berarti

(II_B.2) (p ∧ ¬q) ∨ (¬p ∧ q)

harus bernilai false. Dalam keadaan (II_B.1), nilai kebenaran (II_B.2) adalah

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

≡ (p ∧ true) ∨ false.

Karena (II_B.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 (II_B.1), yaitu q bernilai false, atau B adalah penipu.

∴ Kesimpulannya: A dan B kedua-duanya adalah penipu.

CASE 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.

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?”

untuk yang pertama kali dan yang kedua kali.

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.