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

Question

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

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

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

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

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

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

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

Answer 1

A -> !B
B -> !C
D -> !B
C -> !B
E -> !A & !D

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

X -> Y  <=>  !X | Y

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

Answer 2

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

X ₁ = НЕ X ₃

X ₅ = НЕ X ₂

и т. Д.

Сформировать граф с узлами в виде X _i и соединением X _i и X _j в случаепоявляется уравнение X _i = НЕ X _j .

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

Answer 3

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

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

Это, очевидно, «глупое» решение, которое не сработает для больших входных наборов, но, скорее всего, его будет проще кодировать, чем полный механизм «рассуждения».Часто я нахожу, что вы можете делать намного меньше, принимая во внимание, с какой проблемой вы действительно столкнетесь:)

Answer 4

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

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