Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 47
Мне кажется, главный цинизм вашего решения — использование отбойного молотка для забивания гвоздей. Я имею ввиду, что использовать реляционные базы данных и SQL для решения логических задач не совсем уместно.
И статья значительно выиграет, если вы добавите в нее математические формулы вместо не очень внятных словесных описаний систем уравнений.
И статья значительно выиграет, если вы добавите в нее математические формулы вместо не очень внятных словесных описаний систем уравнений.
В прикладном плане у сочетания РБД и SQL есть новое качество. Формулы там записываются в виде реляционных таблиц и диалоговых форм для обзора и редактирования реляционных запросов. А это новое более ориентированное на человека по сравнению с текстами представление формул.
С отрицательными вопросами богам совсем запутано стало.
Пример:
— Не является ли небо синим?
— Нет
Что мы получили в ответ? Нет, не является (сейчас ночь), или «выражение 'не является небо синим' ложно» (и небо таки синее)?
Пример:
— Не является ли небо синим?
— Нет
Что мы получили в ответ? Нет, не является (сейчас ночь), или «выражение 'не является небо синим' ложно» (и небо таки синее)?
>Формально эти вопросы могут быть записаны в виде системы из 6 логических неравенств, решением которой будет единственный ответ: А – бог истины, В – бог лжи, а С – бог случая.
С каких пор вопросы определяют реальность? Как было 6 возможных вариантов, так и осталось.
С каких пор вопросы определяют реальность? Как было 6 возможных вариантов, так и осталось.
Сколько не перечитывал решение, так и не понял вот этой магии:
PS зачем нужна приписка «EQV TRUE» в конце условия?
Отметим, что ответы богов — «da» или «ja» для решения задачи не нужны.Каким образом мы, просто задав вопрос богу, и проигнорировав его ответ, решили задачу?
PS зачем нужна приписка «EQV TRUE» в конце условия?
Ответы богов зафиксированы в виде логических констант TRUE и FALSE (см. дополнение), а их тарабарские обозначения не интересны.
Феномен магии вопросов объясняется очень просто. Не нужны нам вопросы. Нам нужна система логических уравнений и неравенств.
Приписка «EQV TRUE» возникла из методических соображений. В условии логической задачи нам интересны данные о причинно-следственных связях (A IMP B) и об эквиваленциях. A EQV B это данные о двух причинно-следственных связях (A IMP B) AND (B IMP F)
Феномен магии вопросов объясняется очень просто. Не нужны нам вопросы. Нам нужна система логических уравнений и неравенств.
Приписка «EQV TRUE» возникла из методических соображений. В условии логической задачи нам интересны данные о причинно-следственных связях (A IMP B) и об эквиваленциях. A EQV B это данные о двух причинно-следственных связях (A IMP B) AND (B IMP F)
Если кто-то хочет решить задачу нормально, то у меня есть
хак против неопределенности языка богов
Достаточно добавить в конец каждого вопроса «XOR da означает да» — и ответ на этот вопрос, данный богом, перестанет зависеть от языка, на котором этот бог говорит.
Если кому-то не нравится использование операции XOR — можно использовать формулировку «Верно ли, что из следующих двух высказываний ровно одно истинно: ...»
Если кому-то не нравится использование операции XOR — можно использовать формулировку «Верно ли, что из следующих двух высказываний ровно одно истинно: ...»
А вот и решение
Решения не существует: боги сообщают нам всего 2 бита информации, а нам нужно больше.
Строгое доказательство: предположим, что решение этой задачи существует. Тогда представим его в виде функции f(x,y,z), которая принимает на вход три ответа от первого, второго и третьего богов соответственно — а на выходе дает классификацию всех трех богов.
Рассмотрим любую тройку значений x0, y0, z0 и узнаем, какой из богов является богом случая. Пусть, для определенности, бог случая — третий. Обозначим через z1 ответ бога, противоположный ответу z0. Тогда, f(x0, y0, z0) = f(x0, y0, z1), ведь бог случая может ответить на вопрос как угодно.
Из этих рассуждений следует, что любое значение функции должно повторяться как минимум для двух различных троек входов. Но при числе различных троек входов 8 — и числе различных значений на выходе 6 это невозможно. Следовательно, решения не существует.
Строгое доказательство: предположим, что решение этой задачи существует. Тогда представим его в виде функции f(x,y,z), которая принимает на вход три ответа от первого, второго и третьего богов соответственно — а на выходе дает классификацию всех трех богов.
Рассмотрим любую тройку значений x0, y0, z0 и узнаем, какой из богов является богом случая. Пусть, для определенности, бог случая — третий. Обозначим через z1 ответ бога, противоположный ответу z0. Тогда, f(x0, y0, z0) = f(x0, y0, z1), ведь бог случая может ответить на вопрос как угодно.
Из этих рассуждений следует, что любое значение функции должно повторяться как минимум для двух различных троек входов. Но при числе различных троек входов 8 — и числе различных значений на выходе 6 это невозможно. Следовательно, решения не существует.
Не могу согласиться с вашими уравнениями:
будет истинным только если бог А ответил утвердительно, все эти уравнения строятся именно на этом предположении, т.е. вообще без реальных данных.
А.СТАТУС = ИСТИНА IMP С.СТАТУС = СЛУЧАЙбудет истинным только если бог А ответил утвердительно, все эти уравнения строятся именно на этом предположении, т.е. вообще без реальных данных.
Возможно, я что-то упускаю, но по-моему, ваше решение не всегда может дать однозначный ответ, кто есть кто. Это следует из следующих простых соображений.
1. Имеется ровно шесть вариантов того, кто есть кто (они записаны у вас в таблице)
2. Задавая вопросы, можно получить ровно восемь наборов ответов (три вопроса, два варианта ответа на каждый), но поскольку ’da’ и ’ja’ для нас принципиально неразличимы, то принципиально различных ответов в два раза меньше — ровно четыре.
3. Очевидно, что если шести вариантам решения отвечают только четыре варианта полученных ответов, то однозначный вывод, по крайней мере, в случае одного варианта ответов, сделать невозможно.
Чтобы внести асимметрию в варианты ответов с ’da’ и ’ja’, необходимы включать их в вопросы (например, «если бы я вас спросил, является ли бог С богом случая, ответили бы вы ’da’?»
1. Имеется ровно шесть вариантов того, кто есть кто (они записаны у вас в таблице)
2. Задавая вопросы, можно получить ровно восемь наборов ответов (три вопроса, два варианта ответа на каждый), но поскольку ’da’ и ’ja’ для нас принципиально неразличимы, то принципиально различных ответов в два раза меньше — ровно четыре.
3. Очевидно, что если шести вариантам решения отвечают только четыре варианта полученных ответов, то однозначный вывод, по крайней мере, в случае одного варианта ответов, сделать невозможно.
Чтобы внести асимметрию в варианты ответов с ’da’ и ’ja’, необходимы включать их в вопросы (например, «если бы я вас спросил, является ли бог С богом случая, ответили бы вы ’da’?»
Ваши рассуждения частично верны, но не совсем. Принципиально различных ответов в два раза меньше не из-за языка (вы сами написали, как этот язык обходится), а из-за того, что бог Случая не сообщает нам никакой информации.
«Решение» же автора заключается в том, что мы задаем вопросы, на которые можно дать всего один ответ (якобы). Поэтому ему вообще не требуются ответы на вопросы — но как в таких условиях он собрался получать информацию, мне не ясно.
«Решение» же автора заключается в том, что мы задаем вопросы, на которые можно дать всего один ответ (якобы). Поэтому ему вообще не требуются ответы на вопросы — но как в таких условиях он собрался получать информацию, мне не ясно.
Задача решена. Из 27 возможных комплектов значений переменных системе уравнений и неравенств удовлетворяет один комплект значений переменных.
Мне нравится формулировка этой задачи в реалиях Walking Dead: есть остров, где половина жителей зомби (они постоянно лгут и жрут людей), а другая половина — люди (они постоянно говорят правду и выясняют отношения в лесу или на заброшенном складе). Ситуацию усложняет факт, что жители острова прекрасно нас понимают, но древнее табу (вирус) запрещает им использовать неродные слова. Поэтому они используют ответы «bal» или «da», которые означают «да» и «нет», причём неясно, какое из них что обозначает (взято из википедии)…
Что касается статьи, то сложность такого решения определяется сложностью ее представления в формализме языка запросов. На сколько это было нужно, ведь решение можно построить классической первопорядковой логике?
Мне кажется что такой циничный подход не сработает для логических задач которые требуют итеративность для получения решения.
Что касается статьи, то сложность такого решения определяется сложностью ее представления в формализме языка запросов. На сколько это было нужно, ведь решение можно построить классической первопорядковой логике?
Мне кажется что такой циничный подход не сработает для логических задач которые требуют итеративность для получения решения.
В ситуации, когда нет никакого Случая, решение простейшее, это не интересно :)
Скрытый текст
Верно ли, что 'da' на вашем языке означает 'да'? Человек ответит 'da', зомби ответит 'bal', независимо от того, что эти слова означают.
С тезисом о первопорядковой логике согласен. В прикладном плане у сочетания РБД и SQL есть новое качество. Формулы там записываются в виде реляционных таблиц и диалоговых форм для обзора и редактирования реляционных запросов. А это новое более ориентированное на человека по сравнению с текстами представление формул.
Для логических задач, которые требуют итеративности при построении решения, есть рекурсивные запросы.
Для логических задач, которые требуют итеративности при построении решения, есть рекурсивные запросы.
> Формулы там записываются в виде реляционных таблиц
Афтар жжот
Афтар жжот
Это не я жгу, а Э.Кодд (E.Codd). В конце 60, начале 70 обосновывая языки запросов к РБД, Кодд доказал, что выражения реляционной алгебры редуцируемы к формулам исчисления отношений. Там же доказано, формулы определённого вида редуцируемы к выражениям реляционной алгебры. См., например, Codd E.F. Relational completeness of data base sublanguages. IBM Research Laboratory, San Jose, California. КО 987 (#170041), March 6, 1972, Computer Sciences.
>> Богу А: «Не является ли бог С богом случая?». Богу В: «Не является ли бог А богом лжи?». Богу С: «Не является ли он богом случая?»
А если они скажут ja ja ja.
А если они скажут ja ja ja.
Роли богов
A — бог случая, Б — бог лжи, С — бог правды
В вашем случае боги B и C должны дать разные ответы, пример некорректный. Впрочем, можете не пытаться его уточнять — автору уже 5 критических комментариев выше накидали, а он еще ни на один не ответил.
Вопросы серьезные, требуют внимательного рассмотрения и вдумчивого отношения.
На комментарии обязательно будут даны ответы и разъяснения, но позже. Надеюсь на понимание.
На комментарии обязательно будут даны ответы и разъяснения, но позже. Надеюсь на понимание.
Точно, но все равно не отгадать эти роли с таким вопросами.
Уточняю: не отгадать ни с какими вопросами. Это легко доказывается.
Отгадать возможно. Ваше доказательство основано на том, что вопросы односложные, однако они могут быть и составными.
Мое доказательство основано на том, что мы обязаны задать по вопросу каждому из богов. Составные вопросы я в своем доказательстве учитывал…
> Адресуя наши вопросы богам в другом порядке, например, первый вопрос богу В, а второй – богу А, можно получить любой другой ответ из числа возможных решений логического уравнения, приведенных на первом рисунке.
Любой ответ — это НЕ правильный ответ.
Вы пытались проделать то, что пишете? Давайте я за вас.
Итак, пусть бог А — истины, В — лжи, С — случая (как у вас в решении, для наглядности)
da = нет
Упрощу ваши вопрос, убрав негативность:
1 вопрос — является ли бог С богом случая? — богу В (лжи) — ответ нет (da)
2 вопрос — является ли бог А богом лжи? — богу А (истины) — ответ нет (da)
3 вопрос — является ли он богом случая? — богу С (случая) — ответ да (ja)
Интерпретировать da можно в обе стороны (ограничения нет):
Предположим, что da = да
A.Статус = истина, значит с.статус = случай
В.статус = истина, значит а.статус = ложь
с.статус = ложь, с.статус случай (противоречие с первой строкой)
Предположим, что da = нет
A.Статус = ложь, значит с.статус != случай
В.статус = ложь, значит а.статус != ложь
с.статус = истина, с.статус = случай (противоречие с первой строкой)
Любой ответ — это НЕ правильный ответ.
Вы пытались проделать то, что пишете? Давайте я за вас.
Итак, пусть бог А — истины, В — лжи, С — случая (как у вас в решении, для наглядности)
da = нет
Упрощу ваши вопрос, убрав негативность:
1 вопрос — является ли бог С богом случая? — богу В (лжи) — ответ нет (da)
2 вопрос — является ли бог А богом лжи? — богу А (истины) — ответ нет (da)
3 вопрос — является ли он богом случая? — богу С (случая) — ответ да (ja)
Интерпретировать da можно в обе стороны (ограничения нет):
Предположим, что da = да
A.Статус = истина, значит с.статус = случай
В.статус = истина, значит а.статус = ложь
с.статус = ложь, с.статус случай (противоречие с первой строкой)
Предположим, что da = нет
A.Статус = ложь, значит с.статус != случай
В.статус = ложь, значит а.статус != ложь
с.статус = истина, с.статус = случай (противоречие с первой строкой)
Думаю, что в дополнении ответ на этот комментарий есть.
Нет, этого там нет. Там сплошные глупости, уж простите.
Допустим, Бог А — случая. Допустим, что он сказал «да». По-вашему, получается что Богом случая автоматически становится С. Противоречие.
> Уравнению и всем 6 неравенствам удовлетворяет один комплект значений переменных, соответствующий случаю, когда А – бог истины, В – бог лжи, а С – бог случая.
Ваше «решение» берёт за основу вариант, когда А – бог истины, В – бог лжи, а С – бог случая и подбирает под это красивые слова и формулы. Таким образом можно попытаться запутать преподавателя в школе, понядеявшись, что ему лень будет разбираться с фразами типа «импликация с тождественно ложной посылкой тождественна, а тождественный множитель в конъюнкции несущественен» и прочим бредом.
> Из формулировки самой сложной логической задачи мы извлекли одно уравнение. Решив его, мы получили 6 возможных решений. Любое из них это ответ на вопрос задачи.
Это находится (как я писал ниже) банально факториалом. Вы ничего не решили, потому что НЕ любое из них, а ОДНО из них — ответ на вопрос задачи.
Как итог, вы даже не поняли смысла задачи, не то что не решили её.
Допустим, Бог А — случая. Допустим, что он сказал «да». По-вашему, получается что Богом случая автоматически становится С. Противоречие.
> Уравнению и всем 6 неравенствам удовлетворяет один комплект значений переменных, соответствующий случаю, когда А – бог истины, В – бог лжи, а С – бог случая.
Ваше «решение» берёт за основу вариант, когда А – бог истины, В – бог лжи, а С – бог случая и подбирает под это красивые слова и формулы. Таким образом можно попытаться запутать преподавателя в школе, понядеявшись, что ему лень будет разбираться с фразами типа «импликация с тождественно ложной посылкой тождественна, а тождественный множитель в конъюнкции несущественен» и прочим бредом.
> Из формулировки самой сложной логической задачи мы извлекли одно уравнение. Решив его, мы получили 6 возможных решений. Любое из них это ответ на вопрос задачи.
Это находится (как я писал ниже) банально факториалом. Вы ничего не решили, потому что НЕ любое из них, а ОДНО из них — ответ на вопрос задачи.
Как итог, вы даже не поняли смысла задачи, не то что не решили её.
Позволю себе заметить, что употреблять в обсуждении слова: «бред», «глупости» и т.п. некорректно. Это хамство. Даже, если, Вы, не согласны с точкой зрения автора.
Позволю себе заметить, что вещи надо называть своими именами. И если написан полный бред — то так и следует говорить.
В общем случае, вы были бы правы. А если бы вы сразу сказали «простите-извините, ошибся, хотел показаться сведущим, но не потянул», то есть сохранили лицо, я бы ни за что не стал использовать упомянутые слова.
Однако вместо этого вы решили попробовать запудрить мозги людям ещё больше. Больше — потому, что оригинальный пост это неплохо начал. Это, на мой взгляд, и есть хамство, просто не такое прямолинейное.
Например, из комментария выше
> выражения реляционной алгебры редуцируемы к формулам исчисления отношений
Реляционная алгебра — замкнутая система операций над отношениями (оттого и реляция = relation = отношение). Что и куда вы там редуцировали, вернувшись к определению, я не знаю.
> Там же доказано, формулы определённого вида редуцируемы к выражениям реляционной алгебры
И в обратном направлении! Формулы сокращаются до выражений (опять-таки формул), надо же.
Я написал опровержение вашей статье (корневой комментарий этой ветке), написал решение (взятое с википедии, то самое «провокационное и логически безграмотное»). Ваша реакция возмутительна.
Однако вместо этого вы решили попробовать запудрить мозги людям ещё больше. Больше — потому, что оригинальный пост это неплохо начал. Это, на мой взгляд, и есть хамство, просто не такое прямолинейное.
Например, из комментария выше
> выражения реляционной алгебры редуцируемы к формулам исчисления отношений
Реляционная алгебра — замкнутая система операций над отношениями (оттого и реляция = relation = отношение). Что и куда вы там редуцировали, вернувшись к определению, я не знаю.
> Там же доказано, формулы определённого вида редуцируемы к выражениям реляционной алгебры
И в обратном направлении! Формулы сокращаются до выражений (опять-таки формул), надо же.
Я написал опровержение вашей статье (корневой комментарий этой ветке), написал решение (взятое с википедии, то самое «провокационное и логически безграмотное»). Ваша реакция возмутительна.
А первую половину поста с нахождением всех вариантов перестановок можно заменить формулой из комбинаторики = n!
Для трёх богов имеем 3! = 6.
Для трёх богов имеем 3! = 6.
И в пику — циничная задача:
www.explainxkcd.com/wiki/index.php/246:_Labyrinth_Puzzle
www.explainxkcd.com/wiki/index.php/246:_Labyrinth_Puzzle
Задача решаема. Её решение и написано в википедии. (тут: ru.wikipedia.org/wiki/Самая_сложная_логическая_задача#.D0.A0.D0.B5.D1.88.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87.D0.B8 )
Решение прекрасно формализуется (если нужно, приведу код). Скомпилированный код в виде .exe файла можно скачать тут: www.dropbox.com/s/azyb2rmca3v9usp/HardestQuestEverSolution.exe?dl=0
Правила игры: вы — арбитр, программа должна отгадать задуманные вами варианты богов.
Загадываем богов А. В, С в произвольном порядке, придумываем значения для da и ja. Запускаем программу, отвечаем на вопросы в соответствии со значениями da/ja. Получаем наши варианты.
Решение прекрасно формализуется (если нужно, приведу код). Скомпилированный код в виде .exe файла можно скачать тут: www.dropbox.com/s/azyb2rmca3v9usp/HardestQuestEverSolution.exe?dl=0
Правила игры: вы — арбитр, программа должна отгадать задуманные вами варианты богов.
Загадываем богов А. В, С в произвольном порядке, придумываем значения для da и ja. Запускаем программу, отвечаем на вопросы в соответствии со значениями da/ja. Получаем наши варианты.
Картинка из статьи повеселила:
Автор, а вы не думали, что запись должна быть вида
Автор, а вы не думали, что запись должна быть вида
А.ОТВЕТ = TRUE, а не просто TRUE? Потому что у вас боги все еще, по сути, обязаны ответить TRUE на каждый из заданных вопросов — что, вообще говоря, не так.Боги мне вообще ничего не обязаны и их ответов на вопросы не требуется. Развеселившая Вас формула – это формальная запись вопроса Богу А «Не является ли бог С богом случая», составленная с учетом возможных его ответов «да» (True – логическая константа) и «нет»» (False – тоже логическая константа). Формула упрощена с применением свойств логических связок «конъюнкция» и «импликация».
Последнее мое сообщение в этой теме, поскольку автор поста вообще не понимает, о чем ему говорят — и в упор не видит свою ошибку.
Рассмотрим следующую логическую задачку: есть два бога — бог правды и DanylZ. Требуется выяснить, кто из них кретин. Для этого воспользуюсь методикой автора.
Рассмотрим вспомогательную таблицу статусов, заполненную значениями «ИСТИНА», «DanylZ» и «КРЕТИН». Составим запрос, как было показано в посте, добавив в условие WHERE заданные богам вопросы. Вопросы богам зададим одинаковые — «является ли другой бог кретином?» (ответы богов нам не интересны).
На языке SQL такие вопросы будут записаны следующим образом:
что упрощается до
В результате мы получаем два решения, в которых присутствует один бог правды — и один кретин. Следовательно, кретином является DanylZ. И до тех пор, пока он не поймет свою ошибку — это так и будет.
Рассмотрим следующую логическую задачку: есть два бога — бог правды и DanylZ. Требуется выяснить, кто из них кретин. Для этого воспользуюсь методикой автора.
Рассмотрим вспомогательную таблицу статусов, заполненную значениями «ИСТИНА», «DanylZ» и «КРЕТИН». Составим запрос, как было показано в посте, добавив в условие WHERE заданные богам вопросы. Вопросы богам зададим одинаковые — «является ли другой бог кретином?» (ответы богов нам не интересны).
На языке SQL такие вопросы будут записаны следующим образом:
((А.СТАТУС = ИСТИНА AND TRUE) IMP B.СТАТУС = КРЕТИН) AND
((А.СТАТУС = ИСТИНА AND FALSE) IMP B.СТАТУС <> КРЕТИН) AND
((B.СТАТУС = ИСТИНА AND TRUE) IMP A.СТАТУС = КРЕТИН) AND
((B.СТАТУС = ИСТИНА AND FALSE) IMP A.СТАТУС <> КРЕТИН)
что упрощается до
(А.СТАТУС = ИСТИНА IMP B.СТАТУС = КРЕТИН) AND (B.СТАТУС = ИСТИНА IMP A.СТАТУС = КРЕТИН)
В результате мы получаем два решения, в которых присутствует один бог правды — и один кретин. Следовательно, кретином является DanylZ. И до тех пор, пока он не поймет свою ошибку — это так и будет.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Циничное решение логических задач