creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
the hardest logic puzzle ever

ปริศนาตรรกะที่ยากที่สุดตลอดกาล[1]
โดย george boolos[2]



หลายปีก่อน raymond smullyan นักตรรกศาสตร์-นักแก้ปริศนา ได้ประดิษฐ์โจทย์ปัญหาด้านตรรกะที่ยอดเยี่ยมที่สุดไว้ข้อหนึ่งในนาม The Hardest Logic Puzzle Ever บทความนี้เราจะได้ดูและวิเคราะห์แง่มุมที่น่าสนใจกัน

ปริศนามีอยู่ว่า: มีพระเจ้าสามองค์คือ A B และ C มีหนึ่งองค์พูดจริงเสมอ มีหนึ่งองค์พูดเท็จเสมอ ส่วนอีกองค์ที่เหลือพูดจริงบ้างเท็จบ้างอย่างสุ่ม (random) คุณมีสิทธิ์ถามคำถามประเภทใช่หรือไม่ จำนวนสามคำถาม ถามองค์ใดก็ได้ เพื่อนำคำตอบมาใช้ระบุว่าพระเจ้าองค์ใด (A B C) คือ องค์ที่พูดจริง พูดเท็จ และพูดสุ่ม พระเจ้าทั้งสามองค์เข้าใจภาษาไทย (ภาษาอังกฤษ หรือภาษาอื่นใดที่มนุษย์ใช้กัน) ดังนั้นพระเจ้าเข้าใจคำถามที่คุณถาม แต่เวลาตอบ พระเจ้าจะตอบด้วยภาษาเทพ ซึ่งภาษาเทพสองคำคือคำว่า “ดา” กับ “หยา” มีคำใดคำหนึ่งแปลว่า “ใช่” ส่วนอีกคำหนึ่งแปลว่า “ไม่ใช่” คุณไม่รู้ว่าคำไหนแปลว่าอะไร คุณจะตั้งคำถามสามข้อนี้ว่าอะไรบ้าง

ก่อนอื่นเรามาทำความกระจ่างเกี่ยวกับโจทย์ข้อนี้กันอีกสักนิด

1. มีพระเจ้าบางองค์อาจถูกถามได้มากกว่าหนึ่งคำถาม นั่นคือมีพระเจ้าบางองค์ที่อาจไม่ถูกถามเลยก็ได้
2. คำถามที่สองที่เราถาม (ถามว่าอะไร และถามพระเจ้าองค์ใด) อาจขึ้นอยู่กับคำตอบจากคำถามแรก และในกรณีคำถามที่สามก็เช่นเดียวกัน อาจขึ้นอยู่กับคำตอบจากคำถามที่สอง
3. คำตอบของพระเจ้าองค์สุ่ม ไม่ว่าจะจริงหรือเท็จ ให้เรานึกภาพว่าพระเจ้าโยนเหรียญหัว-ก้อยในสมองก่อนตอบคำถาม เช่นถ้าเหรียญออกหัว พูดจริง ถ้าเหรียญออกก้อย พูดเท็จ
4. โอกาสที่พระเจ้าองค์สุ่มจะตอบว่า “ดา” หรือ “หยา” มีเท่ากัน ไม่ว่าคำถามนั้นจะเป็นคำถามใด

เพื่อเป็นแนวทางในการแก้โจทย์ปัญหาข้อนี้ เราลองมาพิจารณาโจทย์ย่อยสามข้อที่ง่ายกว่ากันก่อน แล้วนำแนวคิดของโจทย์ย่อยทั้งสามประมวลเพื่อตอบคำถามปริศนาหลัก สำหรับโจทย์ย่อยทั้งสามข้อนี้ สองข้อหลังผู้อ่านอาจเคยพบเห็นมาก่อน แต่โจทย์ข้อแรกคงไม่คุ้นเคยนัก (อันที่จริงผู้เขียนได้สร้างมันขึ้นมาระหว่างแก้ปริศนาข้อนี้เอง)

โจทย์ย่อยข้อที่ 1: มีไพ่ A สองใบ และ J หนึ่งใบ ผมเป็นคนคว่ำหน้าไพ่แล้วเรียงเป็นแถวอยู่บนโต๊ะ คุณไม่รู้ว่าไพ่ใบอะไรอยู่ตำแหน่งไหน คุณมีสิทธิ์ตั้งคำถามใช่หรือไม่หนึ่งคำถาม เพื่อหาว่าไพ่ใบไหนคือ A โดยก่อนถามให้คุณชี้ที่ไพ่ใบหนึ่ง ถ้าไพ่ใบนั้นเป็น A ผมจะพูดจริง แต่ถ้าไพ่ใบนั้นเป็น J ผมจะพูดจริงหรือเท็จอย่างสุ่ม

โจทย์ย่อยข้อที่ 2: สมมติว่าคุณกำลังคุยอยู่กับพระเจ้าที่พูดจริงเสมอ หรือพระเจ้าที่พูดเท็จเสมอ ซึ่งคุณไม่รู้ว่าเป็นองค์ไหน และพระเจ้าที่คุณคุยด้วยก็ยินดีตอบคำถามของคุณเป็นภาษาไทย ถ้าคุณอยากรู้ว่าเมือง Dushanbe อยู่ในประเทศ Kirghizia ใช่หรือไม่ คุณต้องตั้งคำถามว่าอะไร

โจทย์ย่อยข้อที่ 3: ถ้าคุณกำลังพูดอยู่กับพระเจ้าที่พูดจริงเสมอ แต่พระเจ้าไม่ยอมตอบคำถามของคุณด้วยภาษาที่คุณเข้าใจ ท่านจะใช้ภาษาเทพของท่านคือ “ดา” กับ “หยา” คุณจะตั้งคำถามใช่หรือไม่ เพียงคำถามเดียวว่าอะไร เพื่อให้รู้ว่าเมือง Dushanbe อยู่ในประเทศ Kirghizia รึเปล่า

เฉลยโจทย์ย่อยข้อที่ 1: ให้ชี้ที่ไพ่ใบกลางแล้วถามว่า “ไพ่ใบทางซ้ายคือ A ใช่มั้ย?” ถ้าผมตอบว่า “ใช่” ก็ให้คุณเลือกไพ่ใบซ้าย แต่ถ้าผมตอบว่า “ไม่” คุณก็เลือกไพ่ใบขวา ไม่ว่าไพ่ใบที่คุณชี้เป็นอะไรก็ตาม ถ้าได้ยินคำว่า “ใช่” เลือกไพ่ด้านซ้าย ได้ยินคำว่า “ไม่” เลือกไพ่ด้านขวา เหตุผลคือ ถ้าไพ่ใบกลางที่คุณชี้เป็น A ผม

พูดจริง คุณก็เลือกตามที่ผมพูด ถ้าไพ่ใบกลางที่คุณชี้คือ J ไม่ว่าผมจะตอบอย่างไรไพ่ทั้งซ้ายและขวาย่อมเป็น A ทั้งคู่เสมอ

การแก้ปัญหาโจทย์ย่อยข้อที่สองและสามเราจำเป็นต้องใช้ตัวเชื่อมประพจน์[3] “ก็ต่อเมื่อ” (iff[4]) เข้ามาช่วย คุณสมบัติที่น่าสนใจของตัวเชื่อมประพจน์ “ก็ต่อเมื่อ” คือ เมื่อเรานำมันไปแทรกระหว่างสองประพจน์ที่มีค่าความจริงเหมือนกัน มันจะให้ผลลัพธ์ออกมาเป็นจริง แต่ถ้าเรานำไปแทรกระหว่างสองประพจน์ที่มีค่าความจริงต่างกัน จะให้ผลลัพธ์ออกมาเป็นเท็จ เช่น “พระจันทร์สร้างจากชีส (Gorgonzola[5]) ก็ต่อเมื่อ โรมอยู่ในรัสเซีย” ประโยคนี้มีค่าความจริงเป็นจริง เพราะ พระจันทร์ไม่ได้สร้างจากชีส และโรมไม่ได้อยู่ในรัสเซีย แต่ประโยค “พระจันทร์สร้างจากชีส ก็ต่อเมื่อ โรมอยู่ในอิตาลี” และ “บนพระจันทร์ไม่มีอากาศหายใจ ก็ต่อเมื่อ โรมอยู่ในรัสเซีย” มีค่าความจริงเป็นเท็จ เพราะ โรมอยู่ในอิตาลี และบนพระจันทร์ไม่มีอากาศหายใจ ดังนั้นประโยค “บนพระจันทร์ไม่มีอากาศหายใจ ก็ต่อเมื่อ โรมอยู่ในอิตาลี” มีค่าความจริงเป็นจริง

เฉลยโจทย์ย่อยข้อที่ 2: เราไม่สามารถถามพระเจ้าตรงๆว่า “Dushanbe อยู่ใน Kirghizia ใช่หรือไม่?” ได้ แต่เราต้องตั้งคำถามให้ซับซ้อนขึ้นว่า “ท่านคือพระเจ้าที่พูดจริงเสมอ ก็ต่อเมื่อ เมือง Dushanbe อยู่ในประเทศ Kirghizia ใช่หรือไม่?” คำถามนี้มีกรณีคำตอบที่เป็นไปได้สี่แบบ

1. พระเจ้าพูดจริงเสมอ และ D. อยู่ใน K. พระเจ้าจะตอบคุณว่า “ใช่”
2. พระเจ้าพูดจริงเสมอ แต่ D. ไม่อยู่ใน K. พระเจ้าจะตอบคุณว่า “ไม่ใช่”
3. พระเจ้าพูดเท็จเสมอ แต่ D. อยู่ใน K. พระเจ้าจะตอบคุณว่า “ใช่” เพราะ 2 ประพจน์มีค่าความจริงต่างกัน ดังนั้นผลลัพธ์เป็นเท็จ แต่พระเจ้าพูดเท็จ จึงตอบคุณว่า “ใช่”
4. พระเจ้าพูดเท็จเสมอ และ D. ไม่อยู่ใน K. พระเจ้าจะตอบคุณว่า “ไม่ใช่” เพราะ 2 ประพจน์มีค่าความจริงเหมือนกัน ดังนั้นผลลัพธ์เป็นจริง แต่พระเจ้าพูดเท็จ จึงตอบคุณว่า “ไม่”

คำตอบที่คุณได้รับจากสี่กรณีนี้ไม่ว่าพระเจ้าพูดจริงหรือพระเจ้าพูดเท็จเป็นผู้ตอบ คือ “ใช่” ถ้าเมือง D. อยู่ในประเทศ K. และ “ไม่ใช่” ถ้าเมือง D. ไม่ได้อยู่ในประเทศ K.

มีข้อสังเกต ถ้าคุณถามพระเจ้าไม่ว่าจะเป็นพระเจ้าพูดจริงหรือพระเจ้าพูดเท็จว่า “ท่านคือพระเจ้าพูดจริงเสมอ ก็ต่อเมื่อ X ใช่หรือไม่?” และได้รับคำตอบกลับมาด้วยภาษาที่คุณเข้าใจ คำตอบที่คุณได้รับคือ “ใช่” ถ้า X เป็น “จริง” และ “ไม่ใช่” ถ้า X เป็น “เท็จ” โดยไม่ขึ้นกับพระเจ้าที่คุณพูดด้วยว่าพูดจริงหรือพูดเท็จ

เฉลยโจทย์ย่อยข้อที่ 3: คล้ายกันกับโจทย์ย่อยข้อที่ 2 เราจะถามตรงๆว่า “เมือง Dushanbe อยู่ในประเทศ Kirghizia ใช่มั้ย?” ไม่ได้ แต่ต้องถามว่า “ดา แปลว่า ใช่ ก็ต่อเมื่อ เมือง D. อยู่ในประเทศ K. ใช่หรือไม่?” กรณีของคำตอบเป็นไปได้ 4 แบบเช่นเดียวกัน

1. ดา แปลว่า ใช่ และ D. อยู่ใน K. พระเจ้าจะตอบคุณว่า “ดา”
2. ดา แปลว่า ใช่ แต่ D. ไม่อยู่ใน K. พระเจ้าจะตอบคุณว่า “หยา” (แปลว่า ไม่)
3. ดา แปลว่า ไม่ แต่ D. อยู่ใน K. พระเจ้าจะตอบคุณว่า “ดา” (แปลว่า ไม่)
4. ดา แปลว่า ไม่ และ D. ไม่อยู่ใน K. พระเจ้าจะตอบคุณว่า “หยา” เพราะประพจน์ทั้งสองเป็นเท็จ ประโยคที่เชื่อมสองประพจน์ด้วยก็ต่อเมื่อจึงเป็นจริง

สังเกตคำตอบที่คุณได้รับคือ “ดา” ถ้า D. อยู่ใน K. และ “หยา” ถ้า D. ไม่อยู่ใน K. ไม่ว่าดาหรือหยาจะมีความหมายว่าใช่หรือไม่ใช่ก็ตาม

จุดที่น่าสนใจคือ ถ้าคุณถามพระเจ้าพูดจริงเสมอด้วยคำถามว่า “ดาแปลว่าใช่ ก็ต่อเมื่อ Y ใช่หรือไม่?” ถ้า Y เป็น “จริง” คุณจะได้รับคำตอบว่า “ดา” แต่ถ้า Y เป็น “เท็จ” คุณจะได้รับคำตอบว่า “หยา” โดยไม่จำเป็นต้องรู้ความหมายของคำว่าดาและหยา

คราวนี้เราลองรวมแนวคิดจากคำตอบของโจทย์ย่อยข้อที่สองและสาม เพื่อนำมาตั้งคำถามถามพระเจ้าที่อาจจะพูดจริงเสมอหรือพูดเท็จเสมอ (พระเจ้าตอบด้วยภาษาเทพ คือ ดากับหยา) “ดาแปลว่าใช่ ก็ต่อเมื่อ ท่านคือพระเจ้าพูดจริงเสมอ ก็ต่อเมื่อ X” คุณจะได้รับคำตอบว่า “ดา” ถ้า X เป็น “จริง” และ “หยา” ถ้า X เป็น “เท็จ” ไม่ว่าพระเจ้าองค์นั้นจะพูดจริงเสมอ หรือพูดเท็จเสมอ และไม่ขึ้นกับความหมายที่แท้จริงของคำว่าดาและหยา ถ้าคุณเข้าใจความรู้เรื่องนี้คุณก็พร้อมแล้วสำหรับการแก้ปริศนาตรรกะข้อนี้

ขั้นแรกคุณต้องตั้งคำถามเพื่อหาพระเจ้าที่ไม่ใช่องค์สุ่มออกมาให้ได้

คำถามที่ 1: ให้คุณถามพระเจ้า A ว่า “ดาแปลว่าใช่ ก็ต่อเมื่อ ท่านคือพระเจ้าที่พูดจริงเสมอ ก็ต่อเมื่อ B คือพระเจ้าสุ่ม ใช่หรือไม่?” ไม่ว่าพระเจ้า A จะเป็นองค์พูดจริง หรือองค์พูดเท็จ (A ไม่เป็นพระเจ้าสุ่ม) ถ้า B คือพระเจ้าสุ่ม จะได้รับคำตอบว่า “ดา” เสมอ ดังนั้นพระเจ้า C คือองค์ที่ไม่ใช่พระเจ้าสุ่ม (อาจจะเป็นพระเจ้าพูดจริงหรือพระเจ้าพูดเท็จก็ได้) แต่ถ้าคุณได้รับคำตอบว่า “หยา” จากพระเจ้า A กรณีที่พระเจ้า A คือพระเจ้าไม่สุ่ม ดังนั้น B ไม่ใช่พระเจ้าสุ่ม

ถ้าพระเจ้า A เป็นพระเจ้าสุ่มล่ะ? นั่นก็หมายความว่า B กับ C ไม่ใช่พระเจ้าสุ่ม ดังนั้นไม่ว่า A จะเป็นพระเจ้าใดก็ตาม ถ้าตอบ “ดา” เราสรุปได้ว่า C ไม่ใช่พระเจ้าสุ่ม และถ้าตอบ “หยา” เราสรุปได้ว่า B ไม่ใช่พระเจ้าสุ่ม

คำถามที่ 2: ให้คุณถามพระเจ้าไม่สุ่ม อาจจะเป็นพระเจ้า B หรือ C ขึ้นอยู่กับคำตอบของ A จากคำถามแรก สมมติว่าคือพระเจ้า B “ดาแปลว่าใช่ ก็ต่อเมื่อ โรมอยู่ในอิตาลี ใช่หรือไม่?” พระเจ้าพูดจริงจะตอบว่า “ดา” ส่วนพระเจ้าพูดเท็จจะตอบว่า “หยา” เพียง 2 คำถามนี้คุณก็สามารถระบุได้แล้วว่า B คือพระเจ้าพูดจริงเสมอหรือพระเจ้าพูดเท็จเสมอ

คำถามที่ 3: สำหรับคำถามสุดท้ายให้คุณถาม B อีกครั้งว่า “ดาแปลว่าใช่ ก็ต่อเมื่อ A คือพระเจ้าสุ่ม ใช่หรือไม่?”

ถ้า B คือพระเจ้าพูดจริง คุณจะได้รับคำตอบว่า “ดา” ถ้า A คือพระเจ้าสุ่ม (A=พระเจ้าสุ่ม B=พระเจ้าพูดจริง C=พระเจ้าพูดเท็จ) และได้รับคำตอบว่า “หยา” ถ้า A ไม่ใช่พระเจ้าสุ่ม (A=พระเจ้าพูดเท็จ B=พระเจ้าพูดจริง C=พระเจ้าสุ่ม)

ถ้า B คือพระเจ้าพูดเท็จ ตอบว่า “ดา” ดังนั้น A จึงไม่ใช่พระเจ้าสุ่ม (A=พระเจ้าพูดจริง B=พระเจ้าพูดเท็จ C=พระเจ้าสุ่ม) แต่ถ้าได้รับคำตอบว่า “หยา” สรุปได้ว่า A เป็นพระเจ้าสุ่ม (A=พระเจ้าสุ่ม B=พระเจ้าพูดเท็จ C=พระเจ้าพูดจริง) จบ

ผมไม่ได้พูดเท็จหรือพูดสุ่มตอนที่ผมบอกว่าปริศนาข้อนี้ยาก เห็นด้วยมั้ยครับ?

ก่อนจาก Dushanbe[6] เป็นเมืองหลวงของ Tajikistan[7] ไม่ใช่ Kirghizia[9]!









[1] บทความเผยแพร่ปีพุทธศักราช 2539 ฤดูใบไม้ผลิ โดยนิตยสาร The Harvard Review of Philosophy

[2] George Boolos รั้งตำแหน่งศาสตราจารย์ด้านปรัชญาแห่ง MIT เขาเป็นหนึ่งในผู้บุกเบิกศาสตร์แขนง “Provability Logic” เป็นเจ้าของผลงานตำรา The Logic of Provability (Cambridge, 2536) และ Computability and Logic (Cambridge, 2517) ร่วมกับ Richard Jeffrey

[3] ประพจน์คือข้อความที่มีค่าความจริงเป็นจริงหรือเท็จอย่างใดอย่างหนึ่งเท่านั้น เช่น 1+1 = 3 เป็นประพจน์ที่มีค่าความจริงเป็นเท็จ

[4] iff เป็นตัวย่อของวลี “if, and only if” ตำราคณิตศาสตร์ชั้นมัธยมของประเทศไทยเราเทียบกับศัพท์คำว่า “ก็ต่อเมื่อ” เมื่อใช้เชื่อมประพจน์สองประพจน์ ค่าความจริงของประพจน์ใหม่ที่เกิดจากการเชื่อม ขึ้นอยู่กับค่าความจริงของแต่ละประพจน์ที่นำมาเชื่อม

[5] ชีสอิตาเลียนทำจากนมวัว ชื่อ Gorgonzola เรียกตามชื่อเมืองเล็กๆใกล้มิลาน ซึ่งเป็นสถานที่แห่งแรกที่ผลิตชีสชนิดนี้

[6] ชื่อ Dushanbe มาจากคำภาษาเปอร์เซีย du=two + shanbe=day หรือ “day two” ซึ่งหมายถึงวันจันทร์

[7] เป็นประเทศสาธารณรัฐในเอเชียกลาง มีชายแดนทางภาคเหนือติด Afghanistan ภาคใต้ติด Kyrgyzstan ภาคตะวันออกติดจีน ตะวันตกติด Uzbekistan

[8] Kirghizia หรือ Kyrgyzstan





บทความนี้ตีพิมพ์ใน MY MATHS, APRIL 2007, VOL. 3 NO. 3 ISSUE 27




Create Date : 29 มกราคม 2550
Last Update : 16 ตุลาคม 2553 13:49:07 น. 2 comments
Counter : 2240 Pageviews.

 
ชอบอ่านครับ แต่ความสามารถห่างไกลจากการหาคำตอบ

วันนี้ได้ประโยคนี้
"ดาแปลว่าใช่ ก็ต่อเมื่อ ท่านคือพระเจ้าที่พูดจริงเสมอ ก็ต่อเมื่อ B คือพระเจ้าสุ่ม ใช่หรือไม่?"
กลับไปคิดและหาประโยชน์ต่อครับ


โดย: อะไรคือสิ่งหายาก แต่ไม่มีค่า วันที่: 29 มกราคม 2550 เวลา:22:34:00 น.  

 
เยี่ยมไปเลย


โดย: Thales of Miletus วันที่: 16 มีนาคม 2551 เวลา:0:57:26 น.  

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.