Comments 23
См. язык программирования Пролог.
В общем виде NP-полная задача. Например, первая:
Четыре кандидата a (Ницше), b (Саломе), c (Маркс), d (Фейребах). Событие что кандидат говорит правду обозначим ax, bx, cx, dx. Событие что кандидат убийца обозначим ay, by, cy, dy. Убица всегда лжёт, а не убийца всегда говорит правду:
ay ≡ ¬ax
by ≡ ¬bx
cy ≡ ¬cx
dy ≡ ¬dx
Убийца ровно один:
(ay ∧ ¬by ∧ ¬cy ∧ ¬dy) ∨ (¬ay ∧ by ∧ ¬cy ∧ ¬dy) ∨ (¬ay ∧ ¬by ∧ cy ∧ ¬dy) ∨ (¬ay ∧ ¬by ∧ ¬cy ∧ dy)
Теперь их высказывания, плюс условие ложности:
ax ≡ by - Ницше сказал (ax), что Саломе убийца (by)
bx ≡ ¬dx - Саломе сказал (bx), что Маркс лжёт (dx)
cx ≡ bx - Фейрбах сказал (cx), что Саломе говорит правду (bx)
dx ≡ ¬ax - Маркс сказал (dx), что Ницше лжёт (ax).
Если заменим все операторы на И, ИЛИ, НЕ, получим SAT в чистом виде. Обычно упрощаем схему как можем, делаем замены, сложные булевые формулы заменяются на один оператор (в sat нет эквивалентности, нужно писать не a == b, а a & b | -a & -b).
Вот нет. Если вы свели задачу к NP-полной, это еще не значит, что она NP-полная. В первой задаче убийца один, - достаточно перебрать N вариантов, сложность линейная от числа проверок.
Асимптотики применимы к классам задач, а не к одной конкретной. Нельзя говорить, что задача сортировки массива [1,3,2] имеет какую-то асимптотическую сложность, можно говорить что класс всех задач сортировки массива произвольных элементов имеет сложность N logN (если мы знаем что элементы - числа из множества int32, то асимпотика линейная, например).
Доказать, что класс задач "логические задачи про убийц, рыцарей и лжецов, которые можно разобрать на научпоп сайте" является NP-трудным (не P) не берусь.
В общем виде NP-полная задача
А, ну это смотря как обобщать.
Кто-то убил Витгенштейна. Преступником является один из N. В результате их допроса были записаны следующие заявления (причём известно, что убийца лжёт, а все остальные всегда говорят правду):
1. ...
2. ...
В таком виде задача полиномиальная.
Способ изучается в рамках курса "формальные системы".
Простой способ формализации для этой задачи таков. Переформулируем утверждения:
Ницше: Убийца - Саломе XOR убийца - Ницше.
Саломе: Маркс - не убийца XOR убийца - Саломе.
Фейербах: Саломе - не убийца XOR убийца - Фейербах.
Маркс: Убийца - Ницше XOR убийца - Маркс.
Все четыре утверждения в такой форме одновременно истинны. Только утверждение "убийца - Ницше" встречается дважды. Если оно ложно, те два утверждения, где оно встречается, противоречат друг другу. Следовательно, оно истинно. После чего убеждаемся, что это не противоречит всем остальным утверждениям - иначе задача не имеет решения.
получается, что Маркс виновен
Тут ошибка. Должно быть получается, что Маркс лжет, и это тупик.
a) Убийца ВСЕГДА лжёт по условию.
Если Ницше прав, то Саломе ОБЯЗАН врать. Соотвественно согласно его утверждению Маркс - убийца в дополнение к Саломе. По условию убийц только один и мы получаем противоречие. Соотвественно утверждение, что Саломе убийца - неправда и Ницше соврал. Соотвественно он и убийца исходя из постулата а)
В последней задаче у меня не получилось понять кто из Раймона Арона и Симоне де Бовуар пил пиво, а кто - джин. Не нашел утверждений, чтобы их различить....
Я не уверен, что это правильный подход, а не косяк формулировки задачи, но если представить что четверо за столом сидят в ряд, то можно определить что они сидят в порядке Арно-Сартр-МерлоПонти-Бовуар, чтобы Бовуар не сидела "рядом" с Сартром согласно 2 условию
Но вообще 4 условие настолько избыточное, что я предполагаю ошибку в переводе
На мой взгляд, во второй задаче подходит решение "Аристотель - честный безопасный водитель, Мёрдок и Сунь-цзы - лгущие убийцы".
Сунь-цзы: Мёрдок и Аристотель говорят правду
Мёрдок лжет -> Сунь-цзы лжет.
Мёрдок: Чтобы выжить, выбирайте Сунь-цзы или Аристотеля.
Выбор Сунь-цзы приводит к смерти -> Мёрдок лжет.
Аристотель: Если хотите жить, не выбирайте Мёрдок.
Мёрдок убийца, Аристотель говорит правду.
В оригинале "To survive, choose Sun Tzu, or choose Aristotle". Имхо и оригинальное утверждение, и перевод можно понимать как "любой выбор будет безопасен -> ни Сунь-цзы, ни Аристотель не являются убийцами"; по смыслу же приведенного решения похоже, что идея автора была "хотя бы один из двух не является убийцей", из чего делается вывод "Мёрдок лжет -> оба остальные убийцы -> Мёрдок не убийца".
У меня тоже проблемы с последней задачей, вроде как вариант стол на четверых, Альбер Камю (джин-тоник), Жан-Поль Сартр (виски), Симона де Бовуар (пиво), Морис Мерло-Понти (абрикосовый коктейль) и одиночка Раймон Арон (вино). И в целом в четвертом пункте можно опустить ", который не пил ни джин с тоником, ни пиво." — вроде как по условию задачи каждый пил свой напиток, да?
Вы меня прям заставили напрячься, чтобы найти что не так
Если мы подразумеваем под "сидел рядом" - "сидел за одним столом", то вот где не сходится:
Камю(джин-тоник) и Бовуар(пиво) сидели рядом с Мерло-Понти согласно 4
Однако Камю не мог сидеть рядом с Бовуар(пиво) согласно 3
Вообще застопорился на том, как это правильно формализовывать. Как они сидят - все в линию, т. е. так, что есть два крайних участника или в кружком, т. е. так что у каждого есть по 2 соседа? Имеет ли значение пол Симоны де Бовуар в словах условий вроде "пил", "сидел"? И нужно ли, чтобы все упомянутые напитки кто-то пил (например, про виски сказано только, что кто-то его не пил, но то, что его пил хоть кто-то не утверждается)?
Понятно, что можно порешать задачу с разными предположениями и найти условия при которых решение существует и единственно, но все-таки как-то много неясностей.
Про Аристотеля, Сунь-Цзы, Мёрдока решил почти по найтию.
Всех мысленно поставил в true, тогда цепочка рассуждений приводит к НЕвыбору Мёрдока, но один точно лжёт (неизвестно, кто), по этой причине делаю инверсию и получается, что Мёрдок лжёт, но он не хочет убивать.
Простым задачам - простые решения.
Задача 1.
Ницше своим утверждением "убийца – Саломе" сразу сузил круг подозреваемых до двух лиц: Ницше и Соломе.
Утверждение Соломе "Маркс невиновен" дало ему алиби, т.к. убийца-лжец не может оправдывать другого человека.
Фразы Фейербаха и Маркса уже опоздали.
Задача 2.
Сунь-цзы: "Мёрдок и Аристотель говорят правду" - по условию задачи (1+ лжецов) такое может сказать только лжец. При этом он спалил ещё одного лжеца, теперь их 2+.
Утверждения Мёрдока и Аристотеля идентичны. Лжецов все 3-е.
Пять экзистенциалистов заходят в бар: занимательные логические задачки