[MUSIC PLAYING] BRIAN YU: All right. Welcome back, everyone, to an
introduction to artificial intelligence with Python. Last time we took a
look at search problems in particular, where
we have AI agents that are trying to solve some sort
of problem by taking actions in some sort of environment,
whether that environment is trying to take actions
by playing moves in a game, or whether those actions are something
like trying to figure out where to make turns in order to get driving
directions from point A to point B. This time we're going to turn
our attention more generally to just this idea of knowledge. The idea that a lot of intelligence
is based on knowledge, especially if we think about human intelligence. People know information. We know facts about the world. And using that information
that we know, we're able to draw conclusions--
reason about the information that we know in order to figure out
how to do something or figure out some other piece of information that
we conclude based on the information we already have available to us. What we'd like to focus on now is the
ability to take this idea of knowledge and being able to reason
based on knowledge, and apply those ideas to
artificial intelligence. In particular, we're
going to be building what are known as knowledge-based agents. Agents that are able to reason and act
by representing knowledge internally. Somehow inside of our AI,
they have some understanding of what it means to know something. And ideally, they have some
algorithms, or some techniques they can use based on that
knowledge that they know in order to figure out the solution
to a problem, or figure out some additional piece of information
that can be helpful in some sense. So what do we mean by
reasoning based on knowledge to be able to draw conclusions? Well, let's look at a simple example
drawn from the world of Harry Potter. We take one sentence
that we know to be true. If it didn't rain, then
Harry visited Hagrid today. So one fact that we might
know about the world. And then we take another fact. Harry visited Hagrid or
Dumbledore today, but not both. So it tells us something
about the world. That Harry either visited
Hagrid but not Dumbledore, or Harry visited
Dumbledore but not Hagrid. And now we have a third piece
of information about the world that Harry visited Dumbledore today. So we now have three
pieces of information now. Three facts inside of a knowledge base,
so to speak-- information that we know. And now we, as humans, can
try and reason about this, and figure out based on
this information, what additional information
can we begin to conclude? And well, looking at
these last two statements, Harry either visited Hagrid
or Dumbledore but not both, and we know that Harry
visited Dumbledore today. Well, then it's pretty
reasonable that we could draw the conclusion that,
you know what, Harry must not have visited Hagrid today. Because based on a combination
of these two statements, we can draw this inference, so to speak. A conclusion that Harry
did not visit Hagrid today. But it turns out we can even do a little
bit better than that-- get some more information-- by taking a
look at this first statement and reasoning about that. This first statement says, if it didn't
rain, then Harry visited Hagrid today. So what does that mean? In all cases where it didn't rain,
then we know that Harry visited Hagrid. But if we also know now that
Harry did not visit Hagrid, then it tells us something
about our initial premise that we were thinking about. In particular, it tells
us that it did rain today. Because we can reason if it didn't rain,
that Harry would have visited Hagrid. But we know for a fact that
Harry did not visit Hagrid today. So it's this kind of reasoning,
the sort of logical reasoning where we use logic
based on the information that we know in order to take
information and reach conclusions. That is going to be the focus of what
we're going to be talking about today. How can we make our artificial
intelligence logical so that they can perform the same kinds of
deduction, the same kinds of reasoning that we've been doing so far. Of course, humans reason about logic
generally in terms of human language. That I just now was speaking
in English, talking in English, about these sentences and
trying to reason through how it is that they relate to one another. We're going to need to be a
little bit more formal when we turn our attention
to computers and being able to encode this notion of logic,
and truthhood and falsehood inside of a machine. So we're going to need to introduce a
few more terms and a few symbols that will help us reason
through this idea of logic inside of an artificial intelligence. And we'll begin with
the idea of a sentence. Now, a sentence in a natural
language like English is just something that I'm saying,
like what I'm saying right now. In the context of AI though, a sentence
is just an assertion about the world in what we're going to call a
knowledge representation language, some way of representing
knowledge inside of our computers. And the way that we're going
to spend most of today, reasoning about knowledge,
is through a type of logic known as propositional logic. There are a number of different types
of logic, some of which we'll touch on. But propositional logic is based
on a logic of propositions, or just statements about the world. And so we begin in propositional
logic with the notion of propositional symbols. We will have certain symbols
that are oftentimes just letters, something like P or Q or R,
where each of those symbols is going to represent some fact
or sentence about the world. So P, for example, might represent
the fact that it is raining. And so P is going to be a symbol
that represents that idea. And Q, for example, might represent
Harry visited Hagrid today. Each of these propositional
symbols represents some sentence or some fact about the world. But in addition to just having
individual facts about the world, we want some way to connect these
propositional symbols together in order to reason more complexly about
other facts that might exist inside of the world in which we're reasoning. So in order to do that, we'll need to
introduce some additional symbols that are known as logical connectives. Now, there are a number of
these logical connectives, but five of the most important, and
the ones we're going to focus on today, are these five up here, each
represented by a logical symbol. Not is represented by this symbol here. And is represented as sort
of an upside-down V. Or is represented by a V shape. Implication-- and we'll talk about
what that means in just a moment-- is represented by an arrow. And biconditional-- again, we'll talk
about what that means in a moment-- is represented by these double arrows. But these five logical
connectives are the main ones we're going to be focusing on
in terms of thinking about how it is that a computer
can reason about facts and draw conclusions based
on the facts that it knows. But in order to get there
we need to take a look at each of these logical connectives
and build up an understanding for what it is that they actually mean. So let's go ahead and
begin with the not symbol. So this not symbol here. And what we're going to show for
each of these logical connectives is what we're going
to call a truth table. A table that demonstrates
what this word not means when we attach it to a
propositional symbol or any sentence inside of our logical language. And so the truth table for
not is shown right here. If P-- some propositional symbol
or some other sentence, even-- is false, then not P is true. And if P is true, then not P is false. So you can imagine
placing this not symbol in front of some sentence
of propositional logic. Just says the opposite of that. So if, for example, P
represented it is raining, then not P would represent the
idea that it is not raining. And as you might expect, if P is false,
meaning if the sentence it is raining is false, well, then the
sentence not P must be true. The sentence that it is not
raining is, therefore, true. So not, you can imagine, just takes
whatever is in P and it inverts it. It turns false into true,
and true into false. Much analogously to what
the English word not means. Just taking whatever comes after it
and inverting it to mean the opposite. Next up, and also very
English-like, is this idea of and, represented by this upside-down
V shape, or this point shape. And as opposed to just taking a
single argument the way not does-- we have P and we have not P-- and is going to combine
two different sentences and propositional logic together. So I might have one sentence
P and another sentence Q, and I want to combine them
together to say P and Q. And the general logic for
what P and Q means is it means that both of
its operands are true. P is true, and also, Q is true. And so here's what that
truth table looks like. This time we have two
variables, P and Q. And when we have two variables, each
of which can be in two possible states, true or false, that
leads to two squared, or four, possible combinations
of truth and falsehood. So we have P is false and Q is false. We have P is false and Q is true. P is true and Q is false. And then P and Q both are true. And those are the only
four possibilities for what P and Q could mean. And in each of those situations,
this third column here, P and Q, is telling us a little bit about what it
actually means for P and Q to be true. And we see that the only case where
P and Q is true is in this fourth row here, where P happens to be
true, Q also happens to be true. And in all other situations, P and
Q is going to evaluate to false. So this, again, is much in line with
what our intuition of and might mean. If I say P and Q, I probably mean
that I expect both P and Q to be true. Next up, also potentially
consistent with what we mean, is this word or, represented
by this V shape, sort of an upside-down and symbol. And or, as the name might suggest,
is true if either of its arguments are true. As long as P is true or Q is true,
then P or Q is going to be true. Which means the only time that P or
Q is false is if both of its operands are false. If P is false and Q is false,
then P or Q is going to be false. But in all other cases, if at
least one of the operands is true-- maybe they're both true-- in which case P or Q is
going to evaluate to true. Now, this is mostly consistent with the
way that most people might use the word or, in the sense of speaking
the word or in normal English. Though there is sometimes
when we might say or where we mean P or Q, but not both. Or we mean sort of it can
only be one or the other. It's important to note that this symbol
here, this or, means P or Q or both. That those are totally OK. As long as either or both of
them are true, then the or is going to evaluate to be true as well. It's only in the case
where all of the operands are false that P or Q ultimately
evaluates to false as well. In logic there's another symbol
known as the exclusive or, which encodes this idea of exclusivity of,
like, one or the other, but not both. But we're not going to be
focusing on that today. Whenever we talk about or, we're
always talking about either or both, in this case, as represented
by this truth table here. So that now is not, and an, and or. And next step is what we might
call implication, as denoted by this arrow symbol. So we have P and Q.
And this sentence here will generally read as
P implies Q. And what P implies Q means is that if P
is true, then Q is also true. So I might say something like, if it
is raining, then I will be indoors. Meaning it is raining
implies I will be indoors is the logical sentence
that I'm saying there. And the truth table for this can
sometimes be a little bit tricky. So obviously, if P is true and Q is
true, then P implies Q, that's true. That definitely makes sense. And it should also stand to reason
that when P is true and Q is false, then P implies Q is false. Because if I said to you, if it is
raining, then I will be indoors, and it is raining, but I'm
not indoors, well, then it would seem to be that my
original statement was not true. P implies Q means that if P is
true, then Q also needs to be true. And if it's not, well, then
the statement is false. Also worth noting, though, is
what happens when P is false. When P is false, the implication
makes no claim at all. If I say something like, if it is
raining, then I will be indoors, and it turns out it's not
raining, then in that case, I am not making any
statement as to whether or not I will be indoors or not. P implies Q just means that
if P is true, Q must be true. But if P is not true, then
we make no claim about whether or not Q is true at all. So in either case, if P is
false, it doesn't matter what Q is, whether it's false or true. We're not making any
claim about Q whatsoever. We can still evaluate
the implication to true. The only way that the
implication is ever false is if our premise, P is true, but
the conclusion that we're drawing, Q, happens to be false. So in that case, we would say P
does not imply Q in that case. Finally, the last connective that
we'll discuss is this biconditional. You can think of a biconditional as a
condition that goes in both directions. So originally, when I said
something like, if it is raining, then I will be indoors. I didn't say what would
happen if it wasn't raining. Maybe I'll be indoors,
maybe I'll be outdoors. This biconditional you can
read as an if and only if. So I can say, I will be indoors
if and only if it is raining. Meaning if it is raining,
then I will be indoors. And if I am indoors, it's reasonable
to conclude that it is also raining. So this biconditional is only
true when P and Q are the same. So if P is true and Q is true, then
this biconditional is also true-- P implies Q. But also
the reverse is true. Q also implies P. So if P and
Q both happen to be false, we would still say it's true. But in any of these other two
situations, this P if and only if Q is going to ultimately
evaluate to false. So a lot of trues and
falses going on there, but these five basic
logical connectives are going to form the core of the
language of propositional logic, the language that we're going to
use in order to describe ideas, and the language that we're going to
use in order to reason about those ideas in order to draw conclusions. So let's now take a look at
some of the additional terms that we'll need to know
about in order to go about trying to form this
language of propositional logic, and writing AI that's actually able
to understand this sort of logic. The next thing we're going
to need is the notion of what is actually
true about the world. We have a whole bunch of
propositional symbols-- P and Q and R and maybe others. But we need some way of knowing, like,
what actually is true in the world. Is P true or false, is Q true
or false, so on and so forth. And to do that, we'll introduce
the notion of a model. A model just assigns a truth value where
a truth value is either true or false to every propositional symbol. In other words, it's creating what
we might call a possible world. So let me give an example. If, for example, I have
two propositional symbols, P is it is raining, and
Q is it is a Tuesday, a model just takes each
of these two symbols and assigns a truth value to
them, either true or false. So here's a sample model. In this model, in other
words, in this possible world, it is possible that P is true,
meaning it is raining, and Q is false, meaning it is not a Tuesday. But there are other possible
worlds or other models as well. There is some model where both
of these variables are true. Some model where both of
these variables are false. In fact, if there are N variables that
are propositional symbols like this, that are either true or false,
then the number of possible models is two to the N, because each
of these possible models-- possible variables
within my model could be set to either true or false, if I
don't know any information about it. So now that I have the symbols-- the symbols and the
connectives that I'm going to need in order to construct
these parts of knowledge, we need some way to
represent that knowledge. And to do so, we're going
to allow our AI access to what we'll call a knowledge base. And a knowledge base is
really just a set of sentences that our AI knows to be true. Some set of sentences
in propositional logic that are things that our
AI knows about the world. And so we might tell our AI
some information, information about a situation that
it finds itself in, or situation about a problem that
it happens to be trying to solve. And we would give that
information to the AI, that the AI would store
inside of its knowledge base. And what happens next
is the AI would like to use that information
in the knowledge base to be able to draw conclusions
about the rest of the world. And what do those conclusions look like? Well, to understand
those conclusions, we'll need to introduce one more
idea, one more symbol, and that is the notion of entailment. So this sentence here, with this double
turnstile and these Greek letters-- this is the Greek letter alpha
and the Greek letter beta-- and we read this as alpha entails beta. And alpha and beta here are just
sentences in propositional logic. And what this means is that alpha
entails beta means that in every model, in other words, in every possible
world in which sentence a is true-- or sentence alpha is true, then
sentence beta is also true. So if something entails something
else, if alpha entails beta, it means that if I
know alpha to be true, then beta must, therefore, also be true. So if my alpha is something like, I
know that it is a Tuesday in January, then a reasonable beta
might be something like, I know that it is January. Because in all worlds, where
it is a Tuesday in January, I know for sure that it must
be January, just by definition. This first statement, or
sentence about the world, entails the second statement. And we can reasonably use deduction,
based on that first sentence, to figure out that the second
sentence is, in fact, true as well. And ultimately, it's
this idea of entailment that we're going to try and
encode into our computer. We want our AI agent to
be able to figure out what the possible entailments are. We want our AI to be able to take
these three sentences, sentences like, if it didn't rain, Harry visited Hagrid. That Harry visited Hagrid
or Dumbledore but not both. And that Harry visited Dumbledore. And just using that
information, we'd like our AI to be able to infer, or figure out,
that using these three sentences inside of a knowledge base, we
can draw some conclusions. In particular, we can
draw the conclusions here that one, Harry did
not visit Hagrid today. And we can draw the entailment two,
that it did, in fact, rain today. And this process is known as inference. And that's what we're
going to be focusing on today, this process of deriving
new sentences from old ones. That I give you these three sentences,
you put them in the knowledge base in, say, the AI, and the AI is able to
use some sort of inference algorithm to figure out that these two
sentences must also be true. And that is how we define inference. So let's take a look
at an inference example to see how we might actually go about
inferring things in a human sense, before we take a more algorithmic
approach to see how we could encode this idea of inference in AI. And we'll see there are a number of
ways that we can actually achieve this. So again, we'll deal with a
couple of propositional symbols. We'll deal with P, Q and
R. P is it is a Tuesday. Q is it is raining. And R is Harry will go for a run. Three propositional symbols that
we are just defining to mean this. We're not saying anything yet about
whether they're true or false. We're just defining what they are. Now we'll give ourselves, or an
AI, access to a knowledge base, abbreviated to KB, to knowledge
that we know about the world. We know this statement. All right, so let's try to parse it. The parentheses here are
just used for precedent, so we can see what associates with what. But you would read this
as P and not Q implies R. All right, so what does that mean? Let's put it piece by piece. P is it is a Tuesday. Q is it is raining. So not Q is it is not raining. And implies R is Harry
will go for a run. So the way to read this entire sentence
in human natural language at least, is if it is a Tuesday and it is not
raining, then Harry will go for a run. So if it is a Tuesday and it is not
raining, then Harry will go for a run. And that is now inside
of our knowledge base. And let's now imagine that our
knowledge base has two other pieces of information as well. It has information that P is
true, that it is a Tuesday. And we also have the information
not Q, that it is not raining. That this sentence Q, it is
raining, happens to be false. And those are the three
sentences that we have access to. P and not Q implies R, P and not Q. Using that information, we should
be able to draw some inferences. P and not Q is only true if
both P and not Q are true. Well, all right, we know that P is true. And we know that not Q is true. So we know that this
whole expression is true. And the definition of implication is if
this whole thing on the left is true, then this thing on the
right must also be true. So if we know that P and not Q is
true, then R must be true as well. So the inference we should be
able to draw from all of this is that R is true, and we know
that Harry will go for a run, by taking this knowledge inside of our
knowledge base and being able to reason based on that idea. And so this ultimately, is the
beginning of what we might consider to be some sort of inference algorithm. Some process that we can use to
try and figure out whether or not we can draw some conclusion. And ultimately, what these inference
algorithms are going to answer is the central question
about entailment. Given some query about
the world, something we're wondering about the world,
and we'll call that query alpha, the question we want to ask,
using these inference algorithms, is does it KB, our knowledge
base, entail alpha? In other words, using
only the information we know inside of our knowledge base,
the knowledge that we have access to, can we conclude that this
sentence alpha is true? And that's ultimately
what we would like to do. So how can we do that? How can we go about writing an algorithm
that can look at this knowledge base and figure out whether or not
this query alpha is actually true? Well, it turns out there are a couple
of different algorithms for doing so. And one of the simplest, perhaps,
is known as model checking. Now remember, that a model
is just some assignment of all of the propositional symbols
inside of our language to a truth value, true or false. And you can think of a
model as a possible world. That there are many possible
worlds where different things might be true or false. And we can enumerate all of them. And the model checking
algorithm does exactly that. So what does our model
tracking algorithm do? Well, if we wanted to
determine if our knowledge base entails some query
alpha, then we are going to enumerate all possible models. In other words, consider all
possible values of true and false for our variables. All possible states in
which our world can be in. And if in every model where
our knowledge base is true, alpha is also true, then we know that
the knowledge base entails alpha. So let's take a closer
look at that sentence and try and figure out
what it actually means. If we know that in every model, in
other words, in every possible world, no matter what assignment of true
and false to variables you give, if we know that whenever
our knowledge is true-- what we know to be true is true-- that this query alpha is also true. Well, then it stands to reason that
as long as our knowledge base is true, then alpha must also be true. And so this is going to form the
foundation of our model checking algorithm. We're going to enumerate
all of the possible worlds, and ask ourselves, whenever the
knowledge base is true, is alpha true? And if that's the case, then
we know alpha to be true. And otherwise, there is no entailment. Our knowledge base
does not entail alpha. All right, so this is
a little bit abstract. But let's take a look at an example to
try and put real propositional symbols to this idea. So again, we'll work
with the same example. P is it is a Tuesday. Q is it is raining. R is Harry will go for a run. Our knowledge base contains
these pieces of information. P and not Q implies R. We
also know P, it is a Tuesday. And not Q, it is not raining. And our query, our alpha in this
case, the thing we want to ask is R. We want to know, is it guaranteed? Is it entailed that
Harry will go for a run. So the first step is to enumerate
all of the possible models. We have three propositional
symbols here, P, Q, and R, which means we have 2 to the
third power, or 8 possible models. All false. False, false, true. False, true, false. False, true, true. Et cetera. Eight possible ways you could assign
true and false to all of these models. And we might ask in each one of
them, is the knowledge base true? Here are the set of things that we know. In which of these worlds could this
knowledge base possibly apply to? In which world is this
knowledge base true? Well, in the knowledge
base, for example, we know P. Like, we know it is a Tuesday. Which means we know that these four--
first four rows-- where P is false, none of those are going to
be true, are going to work for this particular knowledge base. Our knowledge base is
not true in those worlds. Likewise, we also know not Q.
We know that it is not raining. So any of these models where Q is
true, like these two and these two here, those aren't going to work either
because we know that Q is not true. And finally, we also
know that P and not Q implies R. Which means
that when P is true-- where P is true here-- and Q is false-- Q is false in these two-- then R must be true. And if ever P is true, Q is
false, but R is also false, well, that doesn't satisfy
this implication here. That implication does not hold
true under those situations. So we could say that
for our knowledge base, we can conclude under which of these
possible worlds is our knowledge base true, and under which of the possible
worlds is our knowledge base false. And it turns out there is
only one possible world where our knowledge base is actually true. In some cases, there might
be multiple possible worlds where the knowledge base is true. But in this case it just so
happens that there's only one. One possible world where
we can definitively say something about our knowledge base. And in this case, we
would look at the query. The query of R. Is R true? R is true. And so as a result, we
can draw that conclusion. And so this is this
idea of model checking. Enumerate all the possible models,
and look in those possible models to see whether or not if
our knowledge base is true, is the query in question true as well. So let's now take a look
at how we might actually go about writing this in a
programming language like Python. Take a look at some
actual code that would encode this notion of
propositional symbols, and logic, and these connectives, like
and, and or, and not an implication, and so forth, and see what that
code might actually look like. So I've written in
advance a logic library. It's more detailed than we need
to worry about entirely today. But the important thing
is that we have one class for every type of logical symbol,
or connective, that we might have. So we just have one class
for logical symbols, for example, where every symbol
is going to represent and store some name for that particular symbol. And we also have a class for
not, that takes an operand. So we might say not one symbol
to say something is not true, or some other sentence is not true. We have one for and, one
for or, so on and so forth. And I'll just demonstrate
how this works. And you can take a look at
the actual logic.py later on. But go ahead and call
this file, Harry.py. We're going to store information
about this world of Harry Potter, for example. So I'll go ahead and import
from my logic module. I'll import everything. And in this library, in order to create
a symbol, you use capital S symbol. And I'll create a symbol for rain
to mean it is raining, for example. And I'll create a symbol
for Hagrid to mean Harry visited Hagrid is what
the symbol is going to mean. So this symbol means it is raining. This symbol means Harry visited Hagrid. And I'll add another
symbol called Dumbledore for Harry visited Dumbledore. Now I'd like to save these symbols
so that I can use them later, as I do some logical analysis. So I'll go ahead and save each
one of them inside of a variable. So, like, rain, Hagrid,
and Dumbledore, that you could call the variables anything. And now that I have
these logical symbols, I can use logical connectives
to combine them together. So for example, if I have a
sentence like, and rain and Hagrid, for example-- which is not necessarily true,
but just for demonstration-- I can now try and print
out sentence.formula, which is a function I wrote that takes
a sentence and propositional logic and just prints it out so
that we, the programmers, can now see this in order to get an
understanding for how it actually works. So if I run Python
Harry.py, what we'll see is this sentence and propositional
logic, rain and Hagrid. This is the logical
representation of what we have here in our
Python program of saying and, whose arguments
are rain and Hagrid. So we're saying rain and
Hagrid by encoding that idea. And this is quite common in
Python object-oriented programming where you have a number
of different classes, and you pass arguments into
them in order to create a new and object, for example, in
order to represent this idea. But now what I'd like to do is
somehow encode the knowledge that I have about the
world, in order to solve that problem from the
beginning of class, where we talked about trying to
figure out who Harry visited, and trying to figure out if it's
raining or if it's not raining. And so what knowledge do I have? I'll go ahead and create a
new variable called knowledge. And what do I know? Well, I know the very
first sentence that we talked about was the idea that
if it is not raining, then Harry will visit Hagrid. All right. How do I encode the idea
that it is not raining? Well, I can use not and
then the rain symbol. So here's me saying
that it is not raining. And now the implication is that if it is
not raining, then Harry visited Hagrid. So I'll wrap this
inside of an implication to say, if it is not raining, this
first argument to the implication, well, then Harry visited Hagrid. So I'm saying implication, the
premise is that it's not raining. And if it is not raining,
then Harry visited Hagrid. And I can print out knowledge.formula
to see the logical formula equivalent of that same idea. So I run Python of Harry.py,
and this is the logical formula that we see as a result, which
is a text-based version of what we were looking at before. That if it is not raining, then that
implies that Harry visited Hagrid. But there was additional information
that we had access to as well. In this case, we had access
to the fact that Harry visited either Hagrid or Dumbledore. So how do I encode that? Well, this means that
in my knowledge, I've really got multiple pieces
of knowledge going on. I know one thing, and another
thing, and another thing. So I'll go ahead and wrap all of
my knowledge inside of an and. And I'll move things on a new
line just for good measure. But I know multiple things. So I'm saying knowledge is an and
of multiple different sentences. I know multiple different
sentences to be true. One such sentence that I know
to be true is this implication that if it is not raining,
then Harry visited Hagrid. Another such sentence that I know
to be true is or Hagrid Dumbledore. In other words, so Hagrid
or Dumbledore is true, because I know that Harry
visited Hagrid or Dumbledore. But I know more than that, actually. That initial sentence from
before said that Harry visited Hagrid or Dumbledore, but not both. So now I want a sentence that'll
encode the idea that Harry didn't visit both Hagrid and Dumbledore. Well, the notion of Harry
visiting Hagrid and Dumbledore would be represented like this. And of Hagrid and Dumbledore. And if that is not true, I want
to say not that, then I'll just wrap this whole thing inside of a not. So now these three lines, line 8
says that if it is not raining, then Harry visited Hagrid. Line 9 says Harry visited
Hagrid or Dumbledore. And line 10 says Harry didn't
visit both Hagrid and Dumbledore. That it is not true that both the
Hagrid symbol and the Dumbledore symbol are true. Only one of them can be true. And finally, the last piece
of information that I knew was the fact that Harry
visited Dumbledore. So these now are the pieces
of knowledge that I know. One sentence, and another
sentence, and another, and another. And I can print out what I know, just
to see it a little bit more visually. And here now is a logical
representation of the information that my computer is now
internally representing using these various
different Python objects. And again, take a look at logic.py if
you want to take a look at how exactly it's implementing this. But no need to worry too much
about all of the details there. We're here saying that if it is not
raining, then Harry visited Hagrid. We're saying that Hagrid
or Dumbledore is true. And we're saying it is not the case
that Hagrid and Dumbledore is true. That they're not both true. And we also know that
Dumbledore is true. So this long, logical sentence
represents our knowledge base. It is the thing that we know. And now what we like to do is we like
to use model checking to ask a query. To ask a question like,
based on this information, do I know whether or not it's raining? And we, as humans, we're able
to logic our way through it and figure out that, all right, based
on these sentences we can conclude this and that to figure out that
yes, it must have been raining. But now we'd like for the
computer to do that as well. So let's take a look at the
model checking algorithm that is going to follow that same
pattern that we drew out in pseudocode a moment ago. So I've defined a
function here in logic.py that you can take a look
at called model check. Model check takes two arguments,
the knowledge that I already know and the query. And the idea is, in order
to do model checking, I need to enumerate all
of the possible models. And for each of the possible
models, I need to ask myself, is the knowledge base true,
and is the query true? So the first thing I
need to do is somehow enumerate all of the possible models. Meaning for all possible
symbols that exist, I need to assign true and
false to each one of them and see whether or not it's still true. And so here is the way
we're going to do that. We're going to start-- so I've defined another
helper function internally that we'll get to in just a moment. But this function starts by
getting all of the symbols, in both the knowledge and
the query, by figuring out what symbols am I dealing with? In this case, the
symbols I'm dealing with are rain, and Hagrid, and Dumbledore. But there might be other symbols,
depending on the problem. And we'll take a look soon at
some examples of situations where ultimately, we're going to
need some additional symbols in order to represent the problem. And then we're going to run
this check all function, which is a helper function that's basically
going to recursively call itself, checking every possible configuration
of propositional symbols. So we start out by looking at this
check all function, and what do we do? So if not symbols means if we
finish assigning all of the symbols. We've assigned every symbol of value. So far we haven't done that, but
if we ever do, then we check. In this model, is the knowledge true? That's what this line is saying. If we evaluate the knowledge,
propositional logic formula, using the models assignment of
truth values, is the knowledge true? If the knowledge is true, then we should
return true, only if the query is true. Because if the knowledge is true, we
want the query to be true as well, in order for there to be entailment. Otherwise, we don't know
that there-- otherwise, there won't be an entailment. If there's ever a situation where
what we know in our knowledge is true, but the query, the thing we're
asking, happens to be false. So this line here is
checking that same idea. That in all worlds where the knowledge
is true, the query must also be true. Otherwise, we can just return true,
because if the knowledge isn't true, then we don't care. This is equivalent to
when we were enumerating this table from a moment ago. In all situations where the
knowledge base wasn't true-- all of these seven rows here-- we didn't care whether or not
our query was true or not. We only care to check
whether the query is true when the knowledge
base is actually true, which was just this green
highlighted row right there. So that logic is encoded
using that statement there. And otherwise, if we haven't
assigned symbols yet, which we haven't seen anything
yet, then the first thing we do is pop one of the symbols. I make a copy of the symbols first,
just to save an existing copy. But I pop one symbol off
of the remaining symbols, so that I just pick
one symbol at random. And I create one copy of the
model where that symbol is true, and I create a second copy of the
model where that symbol is false. So I now have two copies of the model. One where the symbol is true, and
one where the symbol is false. And I need to make sure
that this entailment holds in both of those models. So I recursively check all on the
model where the statement is true, and check all on the model
where the statement is false. So again, you can take
a look at that function to try to get a sense for how
exactly this logic is working. But in effect, what it's doing
is recursively calling this check all function again and again and again. And on every level of the
recursion we're saying, let's pick a new symbol that
we haven't yet assigned. Assign it to true. And assign it to false. And then check to make sure that
the entailment holds in both cases. Because ultimately, I need to
check every possible world. I need to take every
combination of symbols and try every combination
of true and false in order to figure out whether the
entailment relation actually holds. So that function we've written for you. But in order to use that function
inside of Harry.py, what I'll write is something like this. I would like to model check,
based on the knowledge, and then I provide, as a second
argument, what the query is. What the thing I want to ask is. And what I want to ask in
this case is, is it raining? So model check, again,
takes two arguments. The first argument is the
information that I know. This knowledge. Which in this case, is this information
that was given to me at the beginning. And the second argument, rain, is
encoding the idea of the query. What am I asking? I would like to ask,
based on this knowledge, do I know for sure that it is raining? And I can try and print
out the result of that. And when I run this program,
I see that the answer is true. That based on this information, I can
conclusively say that it is raining. Because using this model
checking algorithm, we were able to check that in every
world where this knowledge is true, it is raining. In other words, there's no world
where this knowledge is true and it is not raining. So you can conclude that
it is, in fact, raining. And this sort of logic
can be applied to a number of different types of problems. That if confronted with a problem
where some sort of logical deduction can be used in order
to try to solve it, you might try thinking about
what propositional symbols you might need in order to
represent that information. And what statements
and propositional logic you might use in order to encode
that information which you know. And this process of
trying to take a problem and figure out what propositional
symbols to use in order to encode that idea, or how
to represent it logically is known as knowledge engineering. That software engineers and AI
engineers will take a problem and try and figure out how to
distill it down into knowledge that is representable by a computer. And if we can take any general
purpose problem, some problem that we find in the human world,
and turn it into a problem that computer's know how
to solve, as by using any number of different
variables, well, then, we can take a computer that
is able to do something like model checking or some
other inference algorithm, and actually figure out
how to solve that problem. So now we'll take a look at two or
three examples of knowledge engineering and practice. Of taking some problem and figuring
out how we can apply logical symbols and use logical formulas to
be able to encode that idea. And we'll start with a very popular
board game in the US and the UK, known as Clue. Now, in the game of Clue, there's
a number of different factors that are going on. But the basic premise of the game
if you've never played it before, is that there are a number
of different people-- for now we'll just use three,
Colonel Mustard, Professor Plum, and Miss Scarlet. There are a number of different
rooms, like a ballroom, a kitchen, and a library. And there are a number of different
weapons-- a knife, a revolver, and a wrench. And three of these-- one person,
one room, and one weapon-- is the solution to the mystery-- the murderer and what room they were
in, and what weapon they happen to use. And what happens at the beginning of
the game is that all these cards are randomly shuffled together, and
three of them-- one person, one room, and one weapon-- are placed into a sealed
envelope that we don't know. And we would like to figure out, using
some sort of logical process, what's inside the envelope. Which person, which
room, and which weapon. And we do so by looking at some,
but not all, of these cards here. By looking at these cards to try and
figure out what might be going on. And so this is a very
popular game, but let's now try and formalize it and see
if we could train a computer to be able to play this game by
reasoning through it logically. So in order to do this
we'll begin by thinking about what propositional symbols
we're ultimately going to need. Remember again, that
propositional symbols are just some symbol, some variable, that can
be either true or false in the world. And so in this case, the
propositional symbols are really just going to correspond
to each of the possible things that could be inside the envelope. Mustard is a propositional
symbol, that in this case will just be true, if Colonel
Mustard is inside the envelope, if he is the murderer. And false otherwise. And likewise, for Plum for Professor
Plum, and Scarlet for Miss Scarlet, and likewise for each of the
rooms, and for each of the weapons. We have one propositional
symbol for each of these ideas. Then using those
propositional symbols we can begin to create logical
sentences, create knowledge that we know about the world. So for example, we know that
someone is the murderer. That one of the three people
is, in fact, the murderer. And how would we encode that? Well, we don't know for
sure who the murderer is, but we know it is one person, or the
second person, or the third person. So I could say something like
this: Mustard, or Plum, or Scarlet. And this piece of knowledge encodes
that one of these three people is the murderer. We don't know which, but one of
these three things must be true. What other information do we know? Well, we know that, for
example, one of the rooms must have been the room in the envelope. That the crime was committed either
in the ballroom, or the kitchen, or the library. Again, right now we don't
know which, but this is knowledge we know at the outset--
knowledge that one of these three must be inside the envelope. And likewise we can say the
same thing about the weapon. That it was either the knife,
or the revolver, or the wrench. That one of those weapons must
have been the weapon of choice, and therefore, the
weapon in the envelope. And then as the game
progresses, the game play works by people get
various different cards. And using those cards, you
can deduce information. That if someone gives
you a card, for example, I have the Professor
Plum card in my hand, then I know the Professor Plum
card can't be inside the envelope. I know that Professor
Plum is not the criminal. So I know a piece of information,
like not Plum, for example. I know that Professor
Plum has to be false. This propositional symbol is not true. And sometimes I might not know for
sure that a particular card is not in the middle. But sometimes, someone
will make a guess, and I'll know that one of three
possibilities is not true. Like someone will guess Colonel Mustard
in the library with the revolver, or something to that effect. And in that case, a card might
be revealed that I don't see. But if it is a card, and it is either
Colonel Mustard, or the revolver, or the library, then I know
that at least one of them can't be in the middle. So I know something like, it is either
not Mustard, or it is not the library, or it is not the revolver. Now maybe multiple of these are not
true, but I know that at least one of Mustard, library and revolver
must, in fact, be false. And so this now is a propositional logic
representation of this game of Clue. A way of encoding the knowledge
that we know inside this game using propositional logic that a
computer algorithm, something like model checking that
we saw a moment ago, can actually look at and understand. So let's now take a look at some code
to see how this algorithm might actually work in practice. All right. So I'm now going to open
up a file called clue.py, which I've started already. And what we'll see here is I've
defined a couple of things. I've defined some symbols initially. Notice I have a symbol for Colonel
Mustard, a symbol for Professor Plum, a symbol for Miss Scarlet,
all of which I put inside of this list of characters. I have a symbol for
ballroom, and kitchen, and library inside of a list of rooms. And then I have symbols for
knife, and revolver, and wrench. These are my weapons. And so all of these characters
and rooms and weapons altogether, those are my symbols. And now I also have this
check knowledge function. And what the check knowledge function
does is it takes my knowledge, and it's going to try and draw
conclusions about what I know. So for example, we'll loop over all of
the possible symbols and we'll check. Do I know that that symbol is true? And a symbol is going to be something
like Professor Plum, or the knife, or the library. And if I know that it
is true, in other words, I know that it must be
the card in the envelope, then I'm going to print
out, using a function called C print, which prints things in color. I'm going to print out the word yes,
and I'm going to print that in green, just to make it very clear to us. And if we're not sure
that the symbol is true, maybe I can check to see if I'm
sure that the symbol is not true. Like, if I know for sure that it
is not Professor Plum, for example. And I do that by running
model check again. This time checking if my
knowledge is not the symbol. If I know for sure that
the symbol is not true. And if I don't know for sure
that the symbol is not true, because I say elif not model
check, meaning I'm not sure that the symbol is
false, well, then I'll go ahead and print out
maybe next to the symbol. Because maybe the symbol is true. Maybe it's not. I don't actually know. So what knowledge do I actually have? Well, let's try and
represent my knowledge now. So my knowledge is, I know a couple
of things so I'll put them in an and. And I know that one of the three
people must be the criminal. So I know or Mustard, Plum, Scarlet. This is my way of encoding that it is
either Colonel Mustard, or Professor Plum, or Miss Scarlet. I know that it must have
happened in one of the rooms. So I know or ballroom,
kitchen, library, for example. And I know that one of the weapons
must have been used as well. So I know or knife, revolver, wrench. So that might be my initial knowledge. That I know that it must
have been one of the people. I know it must have been
in one of the rooms. And I know that it must have
been one of the weapons. And I can see what that knowledge
looks like as a formula, by printing out knowledge.formula. So I'll run Python clue.py. And here now is the information
that I know in logical format. I know that it is Colonel Mustard,
or Professor Plum, or Miss Scarlet. And I know that it is the ballroom,
the kitchen, or the library. And I know that it is the knife,
the revolver, or the wrench. But I don't know much more than that. I can't really draw
any firm conclusions. And in fact, we can see
that if I try and do-- let me go ahead and run my knowledge
check function on my knowledge. Now let's check is
this function that I-- or check knowledge rather. Is this function that I just wrote
that looks over all of the symbols and tries to see what conclusions I can
actually draw about any of the symbols. So I'll go ahead and run clue.py
and see what it is that I know. And it seems that I don't
really know anything for sure. I have all three people are maybes. All three of the rooms are maybes. All three of the weapons are maybes. I don't really know anything
for certain just yet. But now let me try and add
some additional information and see if additional
information, additional knowledge, can help us to logically reason
our way through this process. And we are just going to
provide the information. Our AI is going to take care of
doing the inference and figuring out what conclusions it's able to draw. So I start with some cards, and
those cards tell me something. So if I have the Colonel
Mustard card, for example, I know that the Mustard
symbol must be false. In other words, Mustard is
not the one in the envelope. It's not the criminal. So I can say, knowledge
supports something called-- every and in this library supports .add,
which is a way of adding knowledge, or adding an additional logical
sentence to an and clause. So I can say,
knowledge.add, not Mustard. I happen to know, because
I have the Mustard card, that Colonel Mustard is not the suspect. And maybe I have a couple
of other cards, too. Maybe I also have a
card for the kitchen, so I know it's not the kitchen. And maybe I have another card that
says that it is not the revolver. So I have three cards-- Colonel Mustard, the
kitchen, and the revolver. And I encode that into my AI this way,
by saying it's not Colonel Mustard, it's not the kitchen, and it's not the
revolver, and I know those to be true. So now when I rerun clue.py,
we'll see that I've been able to eliminate some possibilities. Before I wasn't sure if it was the
knife, or the revolver, or the wrench. Knife was maybe, revolver
was maybe, wrench was maybe. Now I'm down to just the
knife and the wrench. Between those two, I don't know which
one it is-- they're both maybes-- but I've been able to eliminate
the revolver, which is one that I know to be false because
I have the revolver card. And so additional information might be
acquired over the course of this game, and we would represent that
just by adding knowledge to our knowledge set, or knowledge
base that we've been building here. So if, for example, we
additionally got the information that someone made a guess. Someone guessed, like, Miss Scarlet
in the library with the wrench. And we know that that card was revealed,
which means that one of those three cards-- either Miss Scarlet,
or the library, or the wrench-- one of those at minimum, must
not be inside of the envelope. So I could add some knowledge. Say knowledge.add, and I'm going
to add an or clause, because I don't know for sure which one it's not. But I know one of them
is not in the envelope. So it's either not Scarlet
or it's not the library. And or supports multiple arguments. I can say it's also or not the wrench. So at least one of those-- Scarlet, library, and wrench-- at
least one of those needs to be false. I don't know which, though. Maybe it's multiple, maybe it's
just one, but at least one I know needs to hold. And so now if I rerun
clue.py, I don't actually have any additional
information just yet. Nothing I can say conclusively. I still know that maybe it's Professor
Plum, maybe it's Miss Scarlet. I haven't eliminated any options. But let's imagine that I
get some more information. That someone shows me the
Professor Plum card, for example. So I say, all right. Let's go back here. Knowledge.add, not Plum. So I have the Professor Plum card. I know that Professor
Plum is not in the middle. I rerun clue.py, and right now,
I'm able to draw some conclusions. Now I've been able to
eliminate Professor Plum. And the only person that could
remaining be is Miss Scarlet. So I know, yes, Miss Scarlet,
this variable must be true. And I've been able to infer that based
on the information I already had. Now, between the ballroom and the
library, and the knife and the wrench, for those two, I'm still not sure. So let's add one more
piece of information. Let's say that I know that
it's not the ballroom. Someone has shown me the ballroom
card, so I know it's not the ballroom. Which means at this point, I should be
able to conclude that it's the library. Let's see. I'll say knowledge.add,
not the ballroom. And we'll go ahead and run that. And it turns out that after
all of this, not only can I conclude that I know
that it's the library. But I also know that the
weapon was the knife. And that might have been an inference
that was a little bit trickier. Something I wouldn't have
realized immediately. But the AI, via this
model checking algorithm, is able to draw that conclusion. That we know for sure
that it must be Miss Scarlet in the library with the knife. And how do we know that? Well, we know it from
this or clause up here. That we know that it's either not
Scarlet, or it's not the library, or it's not the wrench. And given that we know
that it is Miss Scarlet, and we know that it is the
library, then the only remaining option for the weapon is that
it is not the wrench, which means that it must be the knife. So we, as humans, now can go
back and reason through that, even though it might not
have been immediately clear. And that's one of the advantages of
using an AI or some sort of algorithm in order to do this,
is that the computer can exhaust all of these
possibilities and try and figure out what the solution actually should be. And so for that reason,
it's often helpful to be able to represent knowledge in this way. Knowledge engineering,
some situation, where we can use a computer to be able
to represent knowledge and draw conclusions based on that knowledge. And anytime we can translate
something into propositional logic symbols like this, type
of approach can be useful. So you might be familiar
with logic puzzles, where you have to puzzle your way through
trying to figure something out. This is what a classic logic
puzzle might look like. Something like Gildaroy,
Minerva, Pomona, and Horace each belong to a different
one of the four houses-- Gryffindor, Hufflepuff,
Ravenclaw, and Slytherin. And then we have some
information, that Gildaroy belongs to Gryffindor or Ravenclaw. Pomona does not belong in Slytherin. And Minerva does belong to Gryffindor. We have a couple of
pieces of information. And using that
information, we need to be able to draw some conclusions
about which person should be assigned to which house. And again, we can use the exact same
idea to try and implement this notion. So we need some propositional symbols. And in this case, the
propositional symbols are going to get a little
more complex, although, we'll see ways to make this a
little bit cleaner later on. But we'll need 16 propositional symbols. One for each person and house. So we need to say-- remember,
every propositional symbol is either true or false. So Gildaroy Gryffindor
is either true or false. Either he's in Gryffindor or he is not. Likewise, Gildaroy Hufflepuff
also true or false. Either it is true or it's false. And that's true for every
combination of person and house that we could come up with. We have some sort of propositional
symbol for each one of those. Using this type of
knowledge, we can then begin to think about what
types of logical sentences we can say about the puzzle. That if we know-- before even think about the
information we were given, we can think about the
premise of the problem. That every person is assigned
to a different house. So what does that tell us? Well, it tells us sentences like this. It tells us, like, Pomona Slytherin
implies not Pomona Hufflepuff. Something like if
Pomona is in Slytherin, then we know that Pomona
is not in Hufflepuff. And we know this for all four people
and for all combinations of houses. That no matter what you person
you pick, if they're in one house, then they're not in some other house. So I'll probably have a whole
bunch of knowledge statements that are of this four. That if we know Pomona's
in Slytherin, then we know Pomona is not in Hufflepuff. We were also given the information that
each person is in a different house. So I also have pieces of knowledge
that look something like this. Minerva Ravenclaw implies
not Gildaroy Ravenclaw. If they're all in different houses,
then if Minerva is in Ravenclaw, then we know that Gildaroy
is not in Ravenclaw as well. And I have a whole bunch
of similar sentences like this that are expressing that
idea for other people and other houses as well. And so in addition to
sentences of these form, I also have the knowledge
that was given to me. Information like, Gildaroy was
in Gryffindor or in Ravenclaw that would be represented like this. Gildaroy Gryffindor
or Gildaroy Ravenclaw. And then using these
sorts of sentences, I can begin to draw some
conclusions about the world. So let's see an example of this. We'll go ahead and actually try
and implement this logic puzzle to see if we can figure
out what the answer is. I'll go ahead and open up
puzzle.py where I've already started to implement this sort of idea. I've defined a list of
people and a list of houses. And I've, so far, created one symbol
for every person and for every house. That's what this double for loop
is doing-- looping over all people, looping over all houses, creating
a new symbol for each of them. And then I've added some information. I know that every person
belongs to a house, so I've added the information
for every person-- that person Gryffindor,
or person Hufflepuff, or person Ravenclaw,
or person Slytherin. That one of those four
things must be true. Every person belongs to a house. What other information do I know? I also know that only
one house per person. So no person belongs to multiple houses. So how does this work? Well, this is going to
be true for all people. So I'll loop over every person. And then I need to loop over
all different pairs of houses. The idea is I want to encode the idea
that if Minerva is in Gryffindor, then Minerva can't be in Ravenclaw. So I'll loop over all houses, h1. And I'll loop over all houses again, h2. And as long as they're
different, h1 not equal to H2, then I'll add to my knowledge
base this piece of information. That implication, in other words,
an if/then, if the person is in h1, then I know that they
are not in house h2. So these lines here
are encoding the notion that for every person, if
they belong to house one, then they are not in house two. And the other piece of
logic we need to encode is the idea that every house
can only have one person. In other words, if Pomona is
Hufflepuff, then nobody else is allowed to be in Hufflepuff either. And that's the same logic
but sort of backwards. I loop over all of the houses, and loop
over all different pairs of people. So I loop over people once,
loop over people again. And only do this when the people
are different, p1 not equal to p2. And I add the knowledge that
if, as given by the implication, if person one belongs
to the house, then it is not the case that person
two belongs to the same house. So here I'm just encoding
the knowledge that represents the problems constraints. I know that everyone's
in a different house. I know that any person can
only belong to one house. And I can now take my knowledge and
try and print out the information that I happen to know. So I'll go ahead and print
out knowledge.formula, just to see this in action. And I'll go ahead and skip
this for now, but we'll come back to this in a second. Let's print out the knowledge that
I know by running Python puzzle.py. It's a lot of information,
a lot that I have to scroll through, because there's
16 different variables all going on. But the basic idea if we
scroll up to the very top is I see my initial information. Gildaroy is either in Gryffindor,
or Gildaroy is and Hufflepuff, or Gildaroy is and Ravenclaw,
or Gildaroy is in Slytherin. And then way more information as well. So this is quite messy. More than we really
want to be looking at. And soon, too, we'll see ways of
representing this a little bit more nicely using logic. But for now, we can just say these are
the variables that we're dealing with. And now we'd like to
add some information. So the information we're going to
add is Gildaroy is in Gryffindor or he is in Ravenclaw. So that knowledge was given to us. So I'll go ahead and
say knowledge.add, and I know that either or Gildaroy
Gryffindor or Gildaroy Ravenclaw. One of those two things must be true. I also know that Pomona
was not in Slytherin. So I can say knowledge.add,
not this symbol. Not the Pomona Slytherin symbol. And then I can add the knowledge that
Minerva is in Gryffindor by adding the symbol Minerva Gryffindor. So those are the pieces
of knowledge that I know. And this loop here at the bottom
just loops over all of my symbols, checks to see if the knowledge entails
that symbol by calling this model check function again. And if it does, if we know the symbol
is true, we print out the symbol. So now I can run Python
puzzle.py, and Python is going to solve this puzzle for me. We're able to conclude that
Gildaroy belongs to Ravenclaw, Pomona belongs to Hufflepuff,
Minerva to Gryffindor, and Horace to Slytherin just by encoding
this knowledge inside the computer-- although, it was quite
tedious to do in this case-- and as a result, we were able to get
the conclusion from that as well. And you can imagine this being applied
to many sorts of different deductive situations. So not only these situations
where we're trying to deal with Harry Potter
characters in this puzzle. But if you've ever played
games like Mastermind where you're trying to figure out
which order different colors go in and trying to make predictions about
it, I could tell you, for example. Let's play a simplified version
of Mastermind where there are four colors-- red, blue, green, and yellow-- and they're in some order, but
I'm not telling you what order. You just have to make a
guess, and I'll tell you of red, blue, green, and
yellow, how many of the four you got in the right position. So a simplified version of this game. You might make a guess, like
red, blue, green, yellow. And I would tell you something
like, two of those four are in the correct position,
but the other two are not. Then you could reasonably make a guess
and say, all right, let's try this. Blue, red, green, yellow. Try switching two of them around. And this time maybe I tell you,
you know what, none of those are in the correct position. And the question then
is, all right, what is the correct order of these four colors? And we, as humans, could
begin to reason this through. All right, well, if none of these were
correct, but two of these were correct, well, it must have been because
I switched the red and the blue. Which means red and blue
here must be correct. Which means green and yellow
are probably not correct. You can begin to do this
sort of deductive reasoning. We can also equivalently try and
take this and encode it inside of our computer as well. And it's going to be very
similar to the logic puzzle that we just did a moment ago. So I won't spend too much time on this
code because it is fairly similar. But again, we have a
whole bunch of colors, and four different positions
in which those colors can be. And then we have some
additional knowledge. And I encode all of that knowledge. And you can take a look at
this code on your own time. But I just want to demonstrate
that when we run this code, run Python mastermind.py
and run and see what we get, we ultimately are able to
compute red in the zero position, blue in the one position,
yellow in the two position, and green in the three position
as the ordering of those symbols. Now, ultimately, what
you might have noticed is this process was
taking quite a long time. And, in fact, model checking is not
a particularly efficient algorithm. What I need to do in
order to model check is take all of my possible
different variables and enumerate all of the
possibilities that they could be in. If I have n variables, I have
2 to the n possible worlds that I need to be looking through in
order to perform this model checking algorithm. And this is probably not
tractable, especially as we start to get to much
larger and larger sets of data where you have many, many more
variables that are at play. Right here we only have a relatively
small number of variables, so this sort of approach
can actually work. But as the number of
variables increases, model checking becomes less and
less good of a way of trying to solve these sorts of problems. So while it might have been OK
for something like Mastermind to conclude that this is,
indeed, the correct sequence, where all four are in the correct
position, what we'd like to do is come up with some better ways to
be able to make inferences, rather than just enumerate all
of the possibilities. And to do so, what we'll transition to
next is the idea of inference rules. Some sort of rules that we can apply
to take knowledge that already exists and translate it into
new forms of knowledge. And the general way we'll
structure inference rule is by having a horizontal line here. Anything above the line is going
to represent a premise, something that we know to be true. And then anything below the
line will be the conclusion that we can arrive at
after we apply the logic, or from the inference rule that
we're going to demonstrate. So we'll do some of
these inference rules by demonstrating them in English
first, but then translating them into the world of
propositional logic so you can see what those inference
rules actually look like. So for example, let's
imagine that I have access to two pieces of information. I know, for example,
that if it is raining, then Harry is inside, for example. And let's say I also know it is raining. Then most of us could reasonably
then look at this information and conclude that, all
right, Harry must be inside. This inference rule is
known as modus ponens, and it's phrased more
formally in logic as this. If we know that alpha implies
beta, in other words, if alpha, then beta, and we also
know that alpha is true, then we should be able to
conclude that beta is also true. We can apply this inference rule to
take these two pieces of information and generate this new
piece of information. Notice that this is a totally different
approach from the model checking approach, where the approach was
look at all of the possible worlds and see what's true in
each of these worlds. Here, we're not dealing
with any specific world. We're just dealing with
the knowledge that we know and what conclusions we can
arrive at based on that knowledge. That I know that A implies B, and
I know A, and the conclusion is B. And this should seem like
a relatively obvious rule. But of course, if alpha than
beta, and we know alpha, then we should be able to
conclude that beta is also true. And that's going to be true for many,
maybe even all of the inference rules that we'll take a look at. You should be able to look
at them and say, yeah, of course that's going to be true. But it's putting these
all together, figuring out the right combination
of inference rules that can be applied that ultimately
is going to allow us to generate interesting knowledge inside of our AI. So that's modus ponens, this
application of implication. That if we know alpha, and we
know that alpha implies beta, then we can conclude beta. Let's take a look at another example. Fairly straightforward. Something like Harry is
friends with Ron and Hermione. Based on that information,
we can reasonably conclude Harry is friends with Hermione. That must also be true. And this inference rule is
known as and elimination. And what and elimination says, is
that if we have a situation where alpha and beta are both true-- I have information alpha and beta-- well, then just alpha is true. Or likewise, just beta is true. That if I know that both parts
are true, then one of those parts must also be true. Again, something obvious from the
point of view of human intuition. But a computer needs to be
told this kind of information. To be able to apply
the inference rule, we need to tell the computer that
this is an inference rule that you can apply so the computer
has access to it, and is able to use it in
order to translate information from one form to another. In addition to that, let's
take a look at another example of an inference rule. Something like, it is not true
that Harry did not pass the test. Bit of a tricky sentence
to parse so read it again. It is not true, or it is false,
that Harry did not pass the test. Well, if it is false that
Harry did not pass the test, then the only reasonable conclusion
is that Harry did pass the test. And so this, instead of
being and elimination, is what we call double
negation elimination. That if we have two negatives
inside of our premise, then we can just remove them altogether. They cancel each other out. One turns true to false, and the
other one turns false back into true. Phrased a little bit
more formally, we say that if the premise is not not alpha,
then the conclusion we can draw is just alpha. We can say that alpha is true. We'll take a look at a
couple more of these. If I have it is raining, then Harry
is inside, how do I reframe this? Well, this one is a little bit trickier. But if I know if it is
raining, then Harry is inside, then I conclude one of
two things must be true. Either it is not raining,
or Harry is inside. Now, this one's trickier, so
let's think about it a little bit. This first premise here, if it
is raining, then Harry is inside, is saying that if I know that it is
raining, then Harry must be inside. So what is the other possible case? Well, if Harry is not inside, then
I know that it must not be raining. So one of those two
situations must be true. Either it's not raining, or it is
raining, in which case Harry is inside. So the conclusion I can draw is either
it is not raining, or it is raining, so therefore, Harry is inside. So this is a way to translate if/then
statements into or statements. And this is known as
implication elimination. And this is similar to what we
actually did in the beginning when we were first looking at those very
first sentences about Harry and Hagrid and Dumbledore. And phrased a little
bit more formally, this says that if I have
the implication alpha implies beta, that I can draw the
conclusion that either not alpha or beta. Because there are only
two possibilities. Either alpha is true
or alpha is not true. So one of those possibilities
is alpha is not true. But if alpha is true, well,
then we can draw the conclusion that beta must be true. So either alpha is not true, or alpha is
true, in which case beta is also true. So this is one way to turn an
implication into just a statement about or. In addition to eliminating
implications, we can also eliminate biconditionals as well. So let's take an English example. Something like, it is raining
if and only if Harry is inside. And this if and only if really
sounds like that biconditional, that double arrow sign that we saw in
propositional logic not too long ago. And what does this actually mean
if we were to translate this? Well, this means that if it is
raining, then Harry is inside. And if Harry is inside,
then it is raining. The implication goes both ways. And this is what we would call
biconditional elimination. That I can take a biconditional,
A if and only if B, and translate that into
something like this. A implies B, and B implies A.
So many of these inference rules are taking logic that
uses certain symbols and turning them into different
symbols, taking an implication and turning it into an or. Or taking a biconditional and
turning it into implication. And another example of it
would be something like this. It is not true that both
Harry and Ron passed the test. Well, all right, how
do we translate that? What does that mean? Well, if it is not true that
both of them passed the test, well, then the reasonable conclusion we
might draw is that at least one of them didn't pass the test. So the conclusion is either
Harry did not pass the test, or Ron did not pass the test, or both. This is not an exclusive or. But if it is true that it is not
true, that both Harry and Ron passed the test, well, then either
Harry didn't pass the test or Ron didn't pass the test. And this type of law is
one of De Morgan's laws. Quite famous in logic, where the idea
is that we can turn an and into an or. We can take this and, that both
Harry and Ron passed the test, and turn it into an or by
moving the nots around. So if it is not true that
Harry and Ron passed the test, well, then either Harry
did not pass the test, or Ron did not pass the test either. And the way we frame that more
formally using logic is to say this. If it is not true that alpha
and beta, well, then either not alpha or not beta. The way I like to think
about this is that if you have a negation in front
of an and expression, you move the negation
inwards, so to speak. Moving the negation into each
of these individual sentences, and then flip the and into an or. So the negation moves inwards,
and the and flips into an or. So I go from not A and
B, to not A or not B. And there's actually a
reverse of De Morgan's law that goes in the other direction
for something like this. If I say, it is not true that
Harry or Ron passed the test, meaning neither of them passed the test,
well, then the conclusion I can draw is that Harry did not pass the
test, and Ron did not pass the test. So in this case, instead of turning
an and into an or, we're turning an or into an and. But the idea is the same. And this, again, is another
example of De Morgan's laws. And the way that works is that
if I have not A or B this time, the same logic's going to apply. I'm going to move the
negation inwards, and I'm going to flip, this time,
flip the or into an and. So if not A or B, meaning it is not
true that A or B, or alpha or beta, then I can say not alpha and not beta. Moving the negation inwards in
order to make that conclusion. So those are De Morgan's laws. And a couple of other inference rules
that are worth just taking a look at, one is the distributive
law that works this way. So if I have alpha and beta or gamma,
well, then much in the same way that you can use, in math,
use distributive laws to distribute operands, like
addition and multiplication, I can do a similar thing here. Where I can say if
alpha and beta or gamma, then I can say something like,
alpha and beta, or alpha and gamma. That I've been able to distribute this
and sign throughout this expression. So this is an example of
the distributive property or the distributive law, as applied
to logic in much the same way that you would distribute like a
multiplication over the addition of something, for example. This works the other way, too. So if, for example, I have
alpha or beta and gamma, I can distribute the or
throughout the expression. I can say alpha or beta,
and alpha or gamma. So the distributive law
works in that way, too. And it's helpful if I want to take an
or and move it into the expression. And we'll see an example soon of
why it is that we might actually care to do something like that. All right. So now we've seen a lot of
different inference rules. And the question now is how can we
use those inference rules to actually try and draw some conclusions? To actually try and prove
something about entailment, proving that given some
initial knowledge base, we would like to find some way
to prove that a query is true. Well, one way to think
about it is actually to think back to what we
talked about last time, when we talked about search problems. Recall again that search problems
have some sort of initial state. They have actions that you can
take from one state to another, as defined by a transition model that
tells you how to get from one state to another. We talked about testing
to see if you had a goal. And then some path cost function to see
how many steps did you have to take, or how costly was the
solution that you found. Now that we have these
inference rules that take some set of sentences
and propositional logic and get us some new set of
sentences in propositional logic, we can actually treat those
sentences, or those sets of sentences, as states inside of a search problem. So if we want to prove
that some query is true, prove that some logical
theorem is true, we can treat theorem proving as
a form of a search problem. I can say that we begin
in some initial state, where that initial state is the
knowledge base that I begin with. The set of all of the sentences
that I know to be true. What actions are available to me? Well, the actions are any
of the inference rules that I can apply at any given time. The transition model just tells me
after I apply the inference rule, here is the new set of all
of the knowledge that I have, which will be the old set of knowledge,
plus some additional inference that I've been able to draw,
much as in the same way we saw what we got when we
applied those inference rules and got some sort of conclusion. That conclusion gets added
to our knowledge base, and our transition
model will encode that. What is the goal test? Well, our goal test
is, you know, checking to see if we have proved the
statement we're trying to prove. If the thing we're trying to prove
is inside of our knowledge base. And the path cost function, the
thing we're trying to minimize, is maybe the number of inference
rules that we needed to use. The number of steps, so to
speak, inside of our proof. And so here we've been able to
apply the same types of ideas that we saw last time
with search problems, to something like trying to
prove something about knowledge by taking our knowledge and framing
it in terms that we can understand as a search problem,
with an initial state, with actions, with a transition model. So this shows a couple of things. One being how versatile
search problems are. That they can be the same types of
algorithms that we use to solve a maze, or figure out how to get from point A to
point B. Inside of driving directions, for example, can also be used
as a theorem proofing method. Of taking some sort of
starting knowledge base and trying to prove something
about that knowledge. So this, yet again, is a second
way, in addition to model checking, to try and prove that
certain statements are true. But it turns out there's yet another
way that we can try and apply inference, and we'll talk about this now,
which is not the only way, but certainly one of the most common. Which is known as resolution. And resolution is based
on another inference rule that we'll take a look at now. Quite a powerful
inference rule that will let us prove anything that can
be proven about a knowledge base. And it's based on this basic idea. Let's say I know that either
Ron is in the Great Hall, or Hermione is in the library. And let's say I also know that
Ron is not in the Great Hall. Based on those two pieces of
information, what can I conclude? Well, I could pretty reasonably conclude
that Hermione must be in the library. How do I know that? Well, it's because these two
statements, these two, what we'll call, complementary literals-- literals
that complement each other, they are opposites of each other-- seem to conflict with each other. This sentence tells us that
either Ron is in the Great Hall or Hermione is in the library. So if we know that Ron
is not in the Great Hall, that conflicts with this one, which
means Hermione must be in the library. And this we can frame as a more general
rule, known as the unit resolution rule. A rule that says that if we have P or
Q, and we also know not P, well, then from that we can reasonably conclude Q. That if P or Q are true, and
we know that P is not true, the only possibility is
for Q to then be true. And this, it turns out, is
quite a powerful inference rule in terms of what it can do,
in part because we can quickly start to generalize this rule. This Q right here doesn't need to
just be a single propositional symbol. It could be multiple, all chained
together in a single clause, as we'll call it. So if I had something like P or Q1,
or Q2, or Q3, so on and so forth, up until Qn, so I had n,
different, other variables, and I have not P, well, then what
happens when these two complement each other is that these two
clauses resolve, so to speak, to produce a new clause that is
just Q1 or Q2, all the way up to Qn. And in an or, the order of the arguments
in the or doesn't actually matter. The P doesn't need to
be the first thing. It could've been in the middle. But the idea here is that
if I have P in one clause, and not P and the other
clause, well, then I know that one of these
remaining things must be true. I've resolved them in order
to produce a new clause. But it turns out we can generalize
this idea even further, in fact, and display even more power that we
can have with this resolution rule. So let's take another example. Let's say, for instance, that I
know the same piece of information, that either Ron is in the Great
Hall or Hermione is in the library. And the second piece
of information I know is that Ron is not in the Great
Hall or Harry is sleeping. So it's not just a single
piece of information. I have two different clauses, and
we'll define clauses more precisely in just a moment. What do I know here? Well, again, for any propositional
symbol, like Ron is in the Great Hall, there are only two possibilities. Either Ron is in the Great Hall,
in which case, based on resolution, we know that Harry must be sleeping. Or Ron is not in the
Great Hall, in which case we know, based on the same rule,
that Hermione must be in the library. Based on those two
things in combination, I can say, based on these
two premises, that I can conclude that either Hermione is
in the library or Harry is sleeping. So again, because these two
conflict with each other, I know that one of
these two must be true. And you can take a closer look and
try and reason through that logic. Make sure you convince yourself
that you believe this conclusion. Stated more generally, we
can name this resolution rule by saying that if we
know P or Q is true, and we also know that
not P or R is true, we resolve these two clauses
together to get a new clause, Q or R. That either Q or R must be true. And again, much as in
the last case, Q and R don't need to just be single
propositional symbols. It could be multiple symbols. So if I had a rule that had a P or
Q1 or Q2 or Q3, so on and so forth, up until Qn, where n
is just some number. And likewise, I had not P or R1 or F2,
so on and so forth, up until Rm, m, where m, again, is
just some other number, I can resolve these two clauses together
to get one of these must be true. Q1 or Q2, up until Qn. Or R1 or R2, up until Rm. And this is just a generalization
of that same rule we saw before. Each of these things here
we're going to call a clause. Where a clause is formally defined
as a disjunction of literals. Where a disjunction means it's a bunch
of things that are connected with or. Disjunction means things
connected with or. Conjunction, meanwhile, is
things connected with and. And a literal is either a
propositional symbol or the opposite of a propositional symbol. So it's something like P
or Q, or not P or not Q, those are all propositional symbols,
or not of the propositional symbols, and we call those literals. So a clause is just something like this. P or Q or R, for example. Meanwhile, what this
gives us an ability to do is it gives us an ability to
turn logic, any logical sentence, into something called
conjunctive normal form. A conjunctive normal form
sentence is a logical sentence that is a conjunction of clauses. Recall again, conjunction means things
are connected to one another using and. And so a conjunction of
clauses means that it is an and of individual clauses,
each of which has in it. So something like this. A or B or C, and D or not E, and
F or G. Everything in parentheses is one clause. All of the clauses are connected
to each other using an and, and everything in the clause
is separated using an or. And this is just a standard form that
we can translate a logical sentence into that just makes it easy to
work with and easy to manipulate. And it turns out that we can
take any sentence in logic and turn it into
conjunctive normal form, just by applying some inference
rules and transformations to it. So we'll take a look at how
we can actually do that. So what is the process for
taking a logical formula and converting it into injunctive
normal form, otherwise known as CNF? Well, the process looks a
little something like this. We need to take all of
the symbols that are not part of conjunctive normal form-- the
biconditionals, and the implications, and so forth. And turn them into something
that is more closely like conjunctive normal form. So the first step will be
to eliminate biconditionals. Those if and only if double arrows. And we know how to
eliminate biconditionals because we saw there was an
inference rule to do just that. Anytime I have an expression,
like alpha, if and only if beta, I can turn that into alpha implies
beta, and beta implies alpha, based on that inference rule we saw before. Likewise, in addition to
eliminating biconditionals, I can eliminate implications as well. The if/then arrows. And I can do that using the same
inference rule we saw before, too. Taking alpha implies
beta, and turning that into not alpha or beta,
because that is logically equivalent to this first thing here. Then we can move nots inwards,
because we don't want nots on the outsides of our expressions. Conjunctive normal form requires
that its just clause and clause and clause and clause. Any nots need to be immediately
next to propositional symbols. But we can move those nots
around using De Morgan's laws. By taking something like, not A and
B, and turn it into not A or not B, for example, using de Morgan's
laws to manipulate that. And after that, all we'll be
left with are ands and ors, and those are easy to deal with. We can use the distributive law to
distribute the ors so that the ors end up on the inside of the
expression, so to speak, and the ands end up on the outside. So this is the general pattern
for how we'll take a formula and convert it into
conjunctive normal form. And let's now take a
look at an example of how we would do this, and explore
then, why it is that we would want to do something like this. Here's how we can do it. Let's take this formula, for example. P or Q implies R, and
I'd like to convert this into conjunctive normal form,
where it's all ands of clauses, and every clause is
a disjunctive clause. It's or is together. So what's the first thing I need to do? Well, this is an implication. So let me go ahead and
remove that implication. Using the implication inference
rule, I can turn P or Q into-- P or Q implies R, into not P or
Q or R. So that's the first step. I've gotten rid of the implication. And next, I can get rid of the not on
the outside of this expression, too. I can move the nots inwards so they're
closer to the literals themselves by using De Morgan's laws. And De Morgan's law says
that not P or Q is equivalent to not P and not Q. Again here,
just applying the inference rules that we've already seen in order
to translate these statements. And now I have two things
that are separated by an or, where this thing on
the inside is an and. What I'd really like is to move the
or so the ors are on the inside, because conjunctive normal form means
I need clause and clause and clause and clause. And so to do that, I can
use the distributive law. If I have not P and not Q or R, I can
distribute the or R to both of these to get not P or R, and not Q or
R using the distributive law. And this now, here at the bottom,
is in conjunctive normal form. It is a conjunction, an
and, of disjunctions, of clauses that just
are separated by ors. So this process can be used by any
formula to take a logical sentence and turn it into this
conjuncture normal form, where I have clause and clause and clause
and clause and clause, and so on. So why is this helpful? Why do we even care about
taking all these sentences and converting them into this form? It's because once they're in this
form where we have these clauses, these clauses are the inputs to the
resolution, inference rule that we saw a moment ago. That if I have two clauses where
there's something that conflicts, or something complementary
between those two clauses, I can resolve them to get a new
clause, to draw a new conclusion. And we call this process
inference by resolution. Using the resolution rule to
draw some sort of inference. And it's based on the same idea,
that if I have P or Q, this clause, and I have not P or R, that I can
resolve these two clauses together to get Q or R as the resulting clause. A new piece of information
that I didn't have before. Now, a couple of key points that are
worth noting about this before we talk about the actual algorithm. One thing is that, let's
imagine we have P or Q or S, and I also have not P or R or
S. The resolution rule says that because this P
conflicts with this not P, we would resolve to put everything
else together, to get Q or S or R or S. But it turns out that this double S is
redundant-- or S here and or S there. It doesn't change the
meaning of the sentence. So in resolution, when we
do this resolution process, we usually also do a
process known as factoring, where we take any duplicate variables
that show up and just eliminate them. So Q or S or R or S just becomes Q or R
or S. The S only needs to appear once. No need to include it multiple times. Now, one final question
worth considering is what happens if I try to
resolve P and not P together? If I know that P is true, and
I know that not P is true, well, resolution says I can merge
these clauses together and look at everything else. Well, in this case,
there is nothing else. So I'm left with what we
might call the empty clause. I'm left with nothing. And the empty clause is always false. The empty clause is equivalent
to just being false. And that's pretty reasonable. Because it's impossible for both P and
not P to both hold at the same time. P is either true or it's not true. Which means that if P is
true, then this must be false. And if this is true,
then this must be false. There's no way for both of
these to hold at the same time. So if ever I try and resolve
these two, it's a contradiction, and I'll end up getting this empty
clause, where the empty clause I can call equivalent to false. And this idea that if I resolve
these two contradictory terms I get the empty clause, this is the
basis for our inference by resolution algorithm. Here is how we're going
to perform inference by resolution at a very high level. We want to prove that our knowledge
base entails some query alpha. That based on the knowledge we
have, we can prove conclusively that alpha is going to be true. How are we going to do that? Well, in order to do
that, we're going to try to prove that if we know the
knowledge and not alpha, that that would be a contradiction. And this is a common technique in
computer science more generally. This idea of proving
something by contradiction. If I want to prove
that something is true, I can do so by first
assuming that it is false, and showing that it
would be contradictory. Showing that it leads
to some contradiction. And if the thing I'm trying to
prove, if when I assume it's false leads to a contradiction,
then it must be true. And that's the logical approach, or the
idea, behind a proof by contradiction. And that's what we're going to do here. We want to prove that
this query alpha is true, so we're going to assume
that it's not true. We're going to assume not alpha. And we're going to try and
prove that it's a contradiction. If we do get a
contradiction, well, then we know that our knowledge
entails the query alpha. If we don't get a contradiction,
there is no entail. This is this idea of a
proof by contradiction of assuming the opposite of
what you're trying to prove, and if you can demonstrate that that's a
contradiction, then what you're proving must be true. But more formally, how
do we actually do this? How do we check that
knowledge base and not alpha is going to lead to a contradiction? Well, here is where
resolution comes into play. To determine if our knowledge
base entails some query alpha, we're going to convert knowledge
base and not alpha to conjunction normal form. That form where we have a whole bunch
of clauses that are all anded together. And when we have these
individual clauses, now we can keep checking to
see if we can use resolution to produce a new clause. We can take any pair
of clauses and check. Is there some literal that is
the opposite of each other, or complementary to each
other, in both of them? For example, I have a P in one
clause, and a not P in another clause. Or an R in one clause, and
a not R in another clause. If ever I have that
situation, where once I convert to conjunctive normal form
and I have a whole bunch of clauses, I see two clauses that I can resolve to
produce a new clause, then I'll do so. This process occurs in a loop. I'm going to keep checking to
see if I can use resolution to produce a new clause, and keep using
those new clauses to try to generate more new clauses after that. Now, it just so may
happen that eventually, we may produce the empty clause. The clause we were talking about before. If I resolve P and not P together,
that produces the empty clause. And the empty clause
we know to be false. Because we know that there's
no way for both P and not P to both simultaneously be true. So if ever we produce the empty
clause, then we have a contradiction. And if we have a contradiction,
that's exactly what we were trying to do in
a proof by contradiction. If we have a contradiction, then
we know that our knowledge base must entail this query alpha. We know that alpha must be true. And it turns out-- and we
won't go into the proof here-- but you can show that, otherwise, if
you don't produce the empty clause, then there is no entailment. If we run into a situation where
there are no more new clauses to add, we've done all the
resolution that we can do, and yet we still haven't
produced the empty clause, then there is no
entailment in this case. And this now is the
resolution algorithm. And it's very abstract
looking, especially this idea of what does that even
mean to have the empty clause. So let's take a look at an example. Actually try and prove some
entailment by using this inference by resolution process. So here's our question. We have this knowledge base. Here is the knowledge that we know. A or B, and not B or C, and not C.
And we want to know if all of this entails A. So this is our knowledge base
here, this whole log thing. And our query alpha is just
this propositional symbol A. So what do we do? Well, first we want to
prove by contradiction. So we want to first
assume that A is false, and see if that leads to
some sort of contradiction. So here is what we're
going to start with. A or B, and not B or C, and not
C. This is our knowledge base. And we're going to
assume not A. We're going to assume that the thing we're
trying to prove is, in fact, false. And so this is now in
conjunctive normal form, and I have four different clauses. I have A or B. I have not B or C.
I have not C. And I have not A. And now, I can begin to just pick two
clauses that I can resolve and apply the resolution rule to them. And so looking at these
four clauses I see, all right, these two clauses
are ones I can resolve. I can resolve them because there
are complementary literals that show up in them. There's a C here, and a not C here. So just looking at these two clauses,
if I know that not B or C is true, and I know that C is
not true, well, then I can resolve these two clauses to say,
all right, not B. That must be true. I can generate this new clause
as a new piece of information that I now know to be true. And all right, now I
can repeat this process. Do the process again. Can I use resolution again
to get some new conclusion? Well, it turns out I can. I can use that new clause I just
generated, along with this one here. There are complementary literals. This B is complementary to, or
conflicts with this not B over here. And so if I know that A or B is
true, and I know that B is not true, well, then the only remaining
possibility is that A must be true. So now we have A. That is a new clause
that I've been able to generate. And now I can do this one
more time, and looking for two clauses that can be resolved. And you might programmatically
do this by just looping over all possible pairs
of clauses and checking for complementary literals in each. And here I can say, all
right, I found two clauses. Not A and A that
conflict with each other. And when I resolve these
two together, well, this is the same as when we were
resolving P and not P from before. When I resolve these two clauses
together, I get rid of the As, and I'm left with the empty clause. And the empty clause we know
to be false, which means we have a contradiction. Which means we can safely
say, that this whole knowledge base does entail A. That
if this sentence is true, that we know that A,
for sure, is also true. So this now, using
inference by resolution, is an entirely different
way to take some statement and try and prove that
it is, in fact, true. Instead of enumerating
all of the possible worlds that we might be in in order to
try to figure out in which case is the knowledge base true, and
in which case is our query true. Instead we use this
resolution algorithm to say, let's keep trying to figure out
what conclusions we can draw and see if we reach a contradiction. And if we reach a
contradiction, then that tells us something about whether our
knowledge actually entails the query or not. And it turns out there are
many different algorithms that can be used for inference. What we've just looked at here
are just a couple of them. And, in fact, all of this is just
based on one particular type of logic. It's based on propositional logic,
where we have these individual symbols and we connect them using and,
and or, and not, and implies, and biconditionals. But propositional logic is not the
only kind of logic that exists. And in fact, we see that
there are limitations that exist in propositional
logic, especially as we saw in examples like
with the Mastermind example, or with the example
with the logic puzzle where we had different Hogwart's has
people that belong to different houses, and we were trying to figure out
who belonged to which houses. There were a lot of different
propositional symbols that we needed in order to
represent some fairly basic ideas. So now as a final topic
that we'll take a look at, just before we end class today,
is one final type of logic, different from
propositional logic, known as first order logic,
which is a little bit more powerful than
propositional logic, and is going to make it easier for us to
express certain types of ideas. In propositional logic, if
we think back to that puzzle with the people and
the Hogwart's houses, we had a whole bunch of
symbols, and every symbol could only be true or false. We had a symbol for Minerva
Gryffindor, which was either true if Minerva was in Gryffindor,
and false otherwise. And likewise, for Minerva
Hufflepuff, and Minerva Ravenclaw, and Minerva Slytherin, and so forth. But this was starting
to get quite redundant. That we wanted some way
to be able to express that there's a relationship between
these propositional symbols. That Minerva shows up in all of them. And also, I would have
liked to have not have had so many different
symbols to represent what really was a fairly
straightforward problem. So first order logic will
give us a different way of trying to deal with
this idea by giving us two different types of symbols. We're going to have constant symbols
that are going to represent objects, like people or houses. And then predicate
symbols, which you can think of as relations or functions,
that take an input and evaluate them to, like, true or false, for example. That tell us whether or not
some property of some constant, or some pair of constants, or
multiple constants, actually holds. So we'll see an example
of that in just a moment. But for now, in this same problem,
our constant symbols might be objects. Things like people or houses. So Minerva, Pomona, Horace, Gildaroy. Those are all constant symbols. As are my four houses-- Gryffindor, Hufflepuff,
Ravenclaw, and Slytherin. Predicates, meanwhile,
these predicate symbols are going to be properties
that might hold true or false of these individual constants. So person might hold true of Minerva,
but it would be false for Gryffindor, because Gryffindor is not a person. And house is going to
hold true for Ravenclaw, but it's not going to hold
true for Horace, for example, because Horace is a person. And belongs, meanwhile, is going
to be some relation that is going to relate people to their houses. And it's going to only tell me when
someone belongs to a house or does not. So let's take a look at some examples
of what a sentence in first order logic might actually look like. A sentence might look
like something like this. Person Minerva, with
Minerva in parentheses. And person being a predicate symbol,
Minerva being a constant symbol. This sentence in first order logic
effectively means Minerva is a person, or the person property
applies to the Minerva object. So if I want to say something
like Minerva is a person, here is how I express that
idea using first order logic. Meanwhile, I can say something
like house Gryffindor to, likewise, express the idea
that Gryffindor is a house. I can do that this way. And all of the same logical connectives
that we saw in propositional logic, those are going to work here, too. So and, or, implication,
biconditional, not. In fact, I can use not to say
something like, not house Minerva. And this sentence in first order
logic means something like Minerva is not a house. It is not true that the house
property applies to Minerva. Meanwhile, in addition to some
of these predicate symbols that just take a single argument,
some of our predicate symbols are going to express binary relations. Relations between two of its arguments. So I could say something like,
belongs to, and then two inputs, Minerva and Gryffindor
to express the idea that Minerva belongs to Gryffindor. And so now here's the key difference,
or one of the key differences, between this and propositional logic. In propositional logic, I needed
one symbol for Minerva Gryffindor, and one symbol for Minerva
Hufflepuff, and one symbol for all the other people's
Gryffindor and Hufflepuff variables. In this case, I just need one
symbol for each of my people, and one symbol for each
of my houses, and then I can express, as a predicate,
something like, belongs to, and say, belongs to Minerva
Gryffindor to express the idea that Minerva belongs
to Gryffindor house. So already we can see
that first order logic is quite expressive in being able to
express these sorts of sentences using the existing constant
symbols and predicates that already exist, while minimizing
the number of new symbols that I need to create. I can just use eight symbols
for people, for houses, instead of 16 symbols for every
possible combination of each. But first order logic gives us
a couple of additional features that we can use to express
even more complex ideas. And these additional features are
generally known as quantifiers. And there are two main
quantifiers in first order logic. The first of which is
universal quantification. Universal quantification
lets me express an idea, like something is going to be
true for all values of a variable. Like for all values of x, some
statement is going to hold true. So what might a sentence in
universal quantification look like? Well, we're going to use this
upside-down A to mean for all. So upside-down Ax means for all
values of x, where x is any object, this is going to hold true. Belongs to x Gryffindor implies
not belongs to x Hufflepuff. So let's try and parse this out. This means that for all values
of x, If this holds true, if x belongs to Gryffindor,
then this does not hold true. X does not belong to Hufflepuff. So translated into
English, this sentence is saying something like, for all
objects x, if x belongs to Gryffindor, then x does not belong to
Hufflepuff, for example. Or phrased even more simply, anyone
in Gryffindor is not a Hufflepuff. A simplified way of
saying the same thing. So this universal quantification
lets us express an idea, like something is going to hold true
for all values of a particular variable. In addition to universal
quantification, though, we also have existential quantification. Whereas universal quantification
said that something is going to be true for
all values of variable, existential quantification
says that some expression is going to be true for
some value of a variable. At least one value of the variable. So let's take a look at
a sample sentence using existential quantification. One such sentence looks like this. There exists an x-- this
backwards E stands for exists. And here we're saying there
exists an x, such that house x and belongs to Minerva x. In other words, there exists some
object x, where x is a house, and Minerva belongs to x. Or phrased a little more succinctly
in English, you're just saying, Minerva belongs to a house. There's some object that is a house,
and Minerva belongs to a house. And combining this universal
and existential quantification, we can create far more
sophisticated logical statements than we were able to just
using propositional logic. I could combine these to
say something like this. For all x, person x implies there
exists a y, such that house y and belongs to xy. So a lot of stuff going on there. A lot of symbols. Let's try and parse it out and
just understand what it's saying. Here we're saying that for all values of
x, if x is a person, then this is true. So in other words, I'm
saying for all people, and we call that person x, this
statement is going to be true. What statement is true of all people? Well, there exists a y that is the
house, so there exists some house, and x belongs to y. In other words I'm saying,
that for all people out there, there exists some house, such that x,
the person, belongs to y, the house. So say it more succinctly, I'm saying
that every person belongs to a house. That for all x, if x is a person, then
there exists a house that x belongs to. And so we can now express a lot more
powerful ideas using this idea now of first order logic. And it turns out there are many
other kinds of logic out there. There's second order logic and other
higher order logic, each of which allows us to express more
and more complex ideas. But all of it, in this case, is really
in pursuit of the same goal, which is the representation of knowledge. We want our AI agents to be
able to know information, to represent that
information, whether that's using propositional logic, or first
order logic, or some other logic. And then be able to
reason based on that. To be able to draw conclusions. Make inferences. Figure out whether there's some
sort of entailment relationship, as by using some sort
of inference algorithm. Something like inference by
resolution, or model checking, or any number of these
other algorithms that we can use in order to take
information that we know and translate it to
additional conclusions. So all of this has
helped us to create AI that is able to represent
information about what it knows and what it doesn't know. Next time though, we'll
take a look at how we can make our AI even more powerful
by not just encoding information that we know for sure to be true,
and not to be true, but also, to take a look at uncertainty. To look at what happens if AI thinks
that something might be probable, or maybe not very probable, or
somewhere in between those two extremes, all in the pursuit of trying to build
our intelligent systems to be even more intelligent. We'll see you next time.
