I am struggling with this question from my discrete mathematics class. I am just not sure how approach this problem. You're only supposed to use truth tables to solve it.

Here is the problem: "In an islander problem, we are given a set of statements that are about one another. Each of a set of islanders makes a statement about the truth or falsity of their own or other islanders’ statements. Each statement is either true or false, so we have a set of compound propositions with an atomic variable for each. Normally the problem is set up so that exactly one setting of the variables matches the variables. That is, each statement whose variable is set to true becomes true, and each one set to false becomes false. Given the following situations, which islanders, if any, are telling the truth?"

a) "There are two islanders. A says “Exactly one of us is lying”. B says “If A is telling the truth, then so am I."

Here is what I've tried:

I first wrote the two compound propositions given:

A ↔ (¬A ∨ ¬B)
B ↔ (A → B)

Next, I created a truth table for both propositions under the assumption that if A or B is telling the truth then when either of them are true, their statements should also be true, and when either of them are false their statements should also be false.

However, after doing this I realize that this is probably not the correct way. I feel like I'm misunderstanding something. If someone could please help to lead me in the correct direction that would be really great, thanks.

  • $\begingroup$ If A said “Exactly one of us is lying”, then I suspect disjunction alone is probably not sufficient; because $\lnot A \lor \lnot B$ is true even if just one is lying/not true. I think a more accurate formula is perhaps $(A \land \lnot B ) \lor (\lnot A \land B)$. $\endgroup$ – Daniel Mak Sep 22 '19 at 19:48
  • 1
    $\begingroup$ I think that the proposition for A should not include the case where both of them are lying. I usually handle these kinds of problems by thinking "What happens if A speaks truth?" and trying to figure out what it implies and if it could hold. (Which is exactly actually the same as using the truth table just without writing it.) $\endgroup$ – KeeperOfSecrets Sep 22 '19 at 19:50

Doing a truth table is a fine approach. There are four possibilities. For each of them you can see whether the statement each made is correct, then see if that is consistent with the assumption. Here if we assume both A and B told the truth, the statement A made is false, so we have a contradiction. You can keep going in this vein.

Another way is just to assume the truth of one statement and see where that leads. If we assume A tells the truth, we know that B is lying. If B is lying, his statement is false, so we have found a consistent truth assignment. If you trust the puzzle setter to make sure there is only one solution, you can quit here. Otherwise, let us assume A is lying. Then B is lying as well, but with A lying B's statement is true and we have an inconsistency. Therefore A is telling the truth and B is lying.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.