Блог

Главная - Вопросы по программированию - Каков подход к решению такого рода логических задач?

Каков подход к решению такого рода логических задач?

#algorithm #logic

#алгоритм #Логические

Вопрос:

Каким был бы подход к проблеме, которая звучит примерно так:

A говорит, что B лжет

B говорит, что C лжет

D говорит, что B лжет

C говорит, что B лжет

E говорит, что A и D лгут

Сколько лгут и сколько говорят правду? Я ищу не ответ на проблему выше, а подход к такого рода задачам. Большое спасибо.

Комментарии:

1. Вы имеете в виду подход к программному решению этой проблемы?

2. Вы ищете программное решение или математическое решение? В более позднем случае cstheory.stackexchange.com может быть, лучше спросить.

3. Да, подход к решению такого рода задач с использованием языка программирования, такого как C, Java, а не prolog или clips

4. @Task: Нет, это не подходит для cstheory, поскольку это не уровень повторного поиска. На самом деле, это достаточно хорошо известно, чтобы быть домашним заданием.

5. @Aryabhatta, я думаю только о cstheory, поскольку это может быть решено с помощью дискретной математики / теории логики без программирования. Оператор подтвердил, что он ищет программное решение. Я не был уверен, поэтому я не подал никакого близкого голоса, просто прокомментировал.

Ответ №1:

 A -> !B
B -> !C
D -> !B
C -> !B
E -> !A amp; !D

Напоминание:

 X -> Y  <=>  !X | Y

Преобразуйте 5 уравнений в логические предложения, и вы найдете ответы.

Комментарии:

1. Разве этот подход не позволил бы лжецам говорить правду? Если бы единственным условием было это, X -> Y и мы рассмотрели логический эквивалент !X | Y , который имеет истинное значение, если Y == 0 и X == 1, что позволяет X и Y быть одновременно лжецами. Но если X ==Y ==0 и они лжецы, то X сказал, что Y говорит правду, и, следовательно, лжец сказал правду. Возможно, это то, чего хотел OP, но другие ответы, похоже, предполагают, что лжецы всегда лгут…

2. Я не совсем уверен, соответствует ли это теме приведенных выше комментариев, но лжецы всегда лгут, а те, кто говорит правду, всегда говорят правду

3. @DDD, в этом случае этот ответ не приведет к правильному решению.

4. В моем ответе A -> !B означает «если A говорит правду, B лжет». Теперь, если «A говорит, что B лжет» означает, что «если A говорит правду, то B лжет» И «если A лжет, то B говорит правду», тогда вы должны интерпретировать «A говорит, что B лжет» как A -> !B И A <- !B что эквивалентно A == !B .

5. Я все еще не уверен в том, как интерпретировать вопрос. Потому что в одном случае наличие как «B говорит, что C лжет», так и «C говорит, что B лжет» является подозрительным повторением.

Ответ №2:

Для решения уравнений вида

X1 = НЕ X 3

X5 = НЕ X 2

и т. Д

Сформируйте граф с узлами в виде Xi и соедините Xi и X j, если появится уравнение Xi = НЕ X j.

Теперь попробуйте раскрасить график в 2 цвета, используя поиск по ширине.

Комментарии:

1. Я бы подумал, что «A говорит, что B и C оба лгут» логически эквивалентно «A —> !B» и «A —> !C», что по-прежнему равно 2-SAT. Я что-то упускаю?

2. @david: Я допустил ошибку: я преобразовал A подразумевает B в НЕ A или НЕ B, вместо НЕ A или B. Исправлено. Спасибо, что указали на это.

3. Комментарии выше относятся к предыдущему ответу на предыдущий вопрос.

Ответ №3:

Предполагая, что вы хотите решить это с помощью программы … на самом деле довольно легко применить грубую силу, если у вас достаточно небольшой набор входных данных. Например, в этом случае у вас в основном есть 5 логических переменных — независимо от того, говорит каждый человек правду или нет.

Закодируйте инструкции в виде тестов, а затем запустите все возможные комбинации, чтобы увидеть, какие из них допустимы.

Очевидно, что это «тупое» решение и оно не сработает при больших наборах входных данных, но, вероятно, его будет гораздо проще кодировать, чем полноценный «рассуждающий» движок. Часто я нахожу, что вам может сойти с рук выполнение намного меньшего объема работы, принимая во внимание, с каким размером проблемы вы на самом деле столкнетесь 🙂

Комментарии:

1. Разве это не знаменитая SAT-проблема?

2. @csl: Не уверен, что ты имеешь в виду. Ссылка?

3. Логическая выполнимость, которая, как известно, является NP-полной: en.wikipedia.org/wiki/Boolean_satisfiability_problem

4. @csl: А, я думал, ты говорил о тесте SAT в средней школе. Да, это логическая выполнимость. Хотя я не уверен, как это влияет на мой ответ… для небольших входных данных вы можете использовать грубую силу. Для больших входных данных вы можете быть в состоянии написать код, чтобы рассуждать об этом более эффективно… но в некоторых случаях это будет просто «сложно».

5. В своем текущем виде это всего лишь 2-SAT, который все еще разрешим за полиномиальное время. Чтобы стать 3-SAT (и, следовательно, NP-завершенной), задача должна была бы содержать утверждения типа «A говорит ‘B говорит, что C лжет'».

Ответ №4:

Используйте язык логического программирования, такой как Prolog. Они специально разработаны для решения таких задач.

Другие альтернативы включают языки функциональной логики и средства проверки моделей.

Комментарии:

1. Он попросил подход , а не программу, которая выполняет его за вас.

2. Да, но программистам следует научиться использовать правильный инструмент для работы.

3. Согласен, но тогда было бы лучше учить обратному отслеживанию или логике сигналов, например. Или, в частности, как решить эту проблему.