>>This course is about problem solving.
It's my motto that any problem worth solving
is worth thinking about.
To that end, I have a series of example problems
that we'll try throughout the course
just to sort of get your intellectual juices flowing.
So here's one now.
This is called the Smullyan's Island problem.
On Smullyan's Island, the inhabitants on the island
are either what were known as truth tellers or liars.
That is, everybody that lives on this island
is either known to always tell the truth
or known to always lie.
Let's say that you meet two people on the island,
Glen and Maggie.
So Glen and Maggie walk up to you
and they're both going to tell you something
and it's your job to figure out
which one of these is a truth-teller
and which one of these is a liar.
So Glen, he walks up to you and he says,
exactly one of us is lying.
Maggie, her statement is that,
at least one of us is telling the truth.
So now your job is to figure out between Glen and Maggie,
are they both truth-tellers, are they both liars?
Who's telling the truth and who's lying?
So how do you go about resolving this problem?
I want you to pause the video just for a second,
think about this problem and see what you can do
to come up with a solution to the Smullyan's Island problem.
Okay, so let's now think about this problem.
In this case, we have a proposition.
The proposition is that Glen
is a truth-teller.
So I'll say proposition P is that Glen is a truth-teller.
Proposition Q is that Maggie
is a truth-teller.
A proposition is just any statement
that has to be either true or false.
And so we have these two propositions,
P is that Glen is a truth-teller
and Q that Maggie is a truth-teller.
And so what we wanna do is evaluate
what are all the possibilities that exist
for these two propositions in this problem?
So what we could have is that
P and Q, it might be that P is true
and Q is true, so that both Glen and Maggie
are both truth-tellers.
It might be that Glen is a truth-teller,
but Maggie is not.
Or that Glen is a liar
and Maggie is the truth-teller.
Or that they're both liars.
So this would represent a model of all possible scenarios
that exist in this problem.
So what I wanna do, is once we think about the exhaustive
solutions that exist in the problem,
that we can now start analyzing this
by breaking the problem up into its pieces.
So statement one made by Glen was that
exactly one of us is lying.
And then the statement number two
that was made by Maggie,
is that at least one of us is truthful.
So in this case, now we have our all the world possibilities
that exist and then we have these two statements.
So now what I wanna do is to decompose the problem
and think about these individually.
So in this case, exactly one of us is lying.
We can look and we see we have a truth-teller
and we have another truth-teller
so this statement is false.
We look down at the next possibility,
truth-teller and a liar, in this case,
the statement exactly one of us is lying is true.
Here we also have that that is true.
And here the last case is false
because both individuals are lying.
Now we can evaluate this statement,
at least one of us is telling the truth.
So in this case that would be true.
Here that would also be true.
Here it would be true.
And here it would be false.
So now we have all the world possibilities.
Then we're able to decompose the problem,
analyze the individual statements as they are
with respect to the possibility in the world
and then now we can analyse the problem
in a quantitative and a robust way.
So what we have, is we have a truth-teller
that in this first world scenario is lying
and another truth-teller, but is telling the truth.
But we know that truth-tellers cannot lie
so it's impossible for this scenario to be consistent
with the rules of Smullyan's Island.
Here we have a truth-teller that's telling the truth,
but we have a liar that is telling the truth.
And so that is also inconsistent.
Again, a liar is telling the truth,
so we know that that is an inconsistent possibility
in this world.
And so the only case that's left is that Glen is a liar
and Maggie is a liar.
So we have a liar telling a lie
and another liar telling a lie.
So now we can decompose the problem
and realize the only consistent case that exists
is that both Glen and Maggie are liars.
Now the point of this problem
is not that we're gonna be dealing with this type of problem
exactly in our class, although it's consistent
with the Boolean Satisfiability Problem
'cause we have variables that we're trying to evaluate.
The point is, we can take a relatively
weird sounding problem,
we can find a mathematical model
to be able to abstract the problem
and we could analyze it in a quantitative
and a robust way and end up
with a solution.