What's the approach to solving this kind of logic problem?

What would be the approach to a kind of problem that sounds like this:

A says B lies

B says C lies

D says B lies

C says B lies

E says A and D lie

How many lie and how many tell the truth? I am not looking for the answer to the problem above, but the approach to this kind of problem. Thanks a l开发者_开发知识库ot.

---

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

Reminder:

X -> Y  <=>  !X | Y

Transform the 5 equations into logical propositions, and you will find answers.

---

To solve equations of the form

X₁ = NOT X ₃

X₅ = NOT X ₂

etc

Form a graph with nodes as X_i and connecting X_i and X _j iff the equation X_i = NOT X _j appears.

Now try to 2-colour the graph using Breadth First Search.

---

Assuming you're looking to solve this with a program... it's actually pretty easy to brute force, if you've got a reasonably small input set. For example, in this case you've basically got 5 Boolean variables - whether each person is a truth-teller or not.

Encode the statements as tests, and then run through every possible combination to see which ones are valid.

This is obviously a "dumb" solution and will fail for large input sets, but it's likely to be rather easier to code than a full "reasoning" engine. Often I find that you can get away with doing a lot less work by taking into account what size of problem you're actually going to encounter :)

---

Use a logic programming language such as Prolog. They are specifically designed to solve such problems.

Other alternatives include functional-logic languages and model checkers.