Лицарі та Шахраї
Лицарі та Шахраї — тип логічних загадок винайдений Реймондом Смалліаном.
На вигаданому острові, всі мешканці якого або лицарі, які завжди кажуть правду, або шахраї, які завжди брешуть. Загадки включають відвідувача острова, який зустрічається з маленькими групами мешканців. Зазвичай метою відвідувача є визначити типи остров'ян через їхні твердження, хоча деякі загадки потребують виведення інших фактів. Також завданням може бути визначити запитання на так/ні, яке відвідувач може запитувати з метою розкрити те, що йому потрібно знати.
Ранній приклад загадок цього типу включав трьох мешканців на яких посилались як на A, B і C. Відвідувач запитує в A до якого типу він відноситься, але не чує його відповідь. Тоді B каже "A сказав, що він брехун" і C каже "не вір B: він бреше!" Для розв'язання цієї загадки зауважте, що жоден мешканець не може сказати, що він шахрай. Тож твердження B є неправдивим, тобто він брехун, що робить твердження C правдою, тобто він лицар. Звідси відповідь A однозначно була "Я лицар", і за допомогою наданих даних неможливо визначити лицар A чи ні.
В деяких різновидах, мешканці дають почергово правдиві та брехливі відповіді, або звичайні люди, які кажуть те, що забажають (Як у випадку загадки Лицар/Шахрай/Шпигун). Подальше ускладнення полягає в надання мешканцям можливості давати відповіді на рідній мові, і відвідувач знає, що «бел» і «де» значать «так» і «ні», але не знає яке саме «так», а яке «ні». Ці типи загадок головно вплинули на те, що ми знаємо як «найскладніша логічна задача».
Декілька прикладів загадок типу «Лицарі та Шахраї»[ред. | ред. код]
Великий клас простих логічних загадок може бути розв'язаним із використанням законів Булевої алгебри і таблиць істинності. Знайомство з булевою алгеброю і її процесом спрощення допоможе в розумінні наступних прикладів.
Василь і Григір є постійними мешканцями острова лицарів і шахраїв.
Питання 1[ред. | ред. код]
Василь каже: Ми обидва шахраї.
Хто є хто?
Питання 2[ред. | ред. код]
Тут подається, мабуть, найвідоміша з цього типу загадок:
Василь і Григір стоять на розгалуженні дороги. Відомо, що один з них лицар, а другий шахрай, але невідомо хто саме. Також відомо, що одна дорога веде до смерті, друга до свободи. Чи можете ви визначити з допомогою одного запитання яка дорога веде до свободи?
Розв'язок для питання 1[ред. | ред. код]
Василь шахрай, а Григір лицар.
Василь твердить, що "Василь і Григір шахраї."
Якщо Василь лицар, він не зміг би сказати, що він шахрай бо він не може брехати. Те що Василь шахрай робить його твердження брехнею. Тоді хтось з них лицар, або обидва вони лицарі. Ми вже знаємо, що Василь не може бути лицарем, тоді Григір має бути лицарем.
Розв'язок для питання 2[ред. | ред. код]
Існує декілька шляхів для розв'язання. Один з них наступне запитання: "Чи скаже мені другий, що твій шлях веде до свободи?"
Зауважимо, що попередній розв'язок вимагає знання кожного про тип другого. Другий розв'язок полягає в запитанні кожного з них, "Якою буде твоя відповідь, якщо я запитаю тебе чи веде твій шлях до свободи?"
Іще одним варіантом є запитання: "Чи вірне одне з наступних запитань? Ти Лицар і одночасно цей шлях веде до свободи; або ти шахрай і це не шлях до свободи". Додаткові різновиди запитань можна знайти за допомогою булевої алгебри.
Література[ред. | ред. код]
- George Boolos, John P. Burgess, Richard C. Jeffrey, Logic, logic, and logic (Harvard University Press, 1999).
Посилання[ред. | ред. код]
- Автоматизований генератор загадок типу Лицарі та Шахраї (англ.)
- Зауваження на деякі філософські підтексти загадки Лицарів і Шахраїв для концепції можливості пізнання (англ.)
- Повний список і аналіз загадок Лицар, Шахрай і Шпигун, де шпигун може брехати або казати правду. [Архівовано 18 вересня 2009 у Wayback Machine.] (англ.)