Skip to main content
Loading Explore guides…
AI Knowledge & Reasoning · Acedra
Home
Explore
Computer Science
AI Knowledge & Reasoning
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
234 segments
Copy
Hide video
0:00
[MUSIC PLAYING]
0:17
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
0:37
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
1:03
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
1:30
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.
1:55
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.
2:21
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
2:46
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?
3:09
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
3:36
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,
4:02
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.
4:27
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.
4:51
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.
5:20
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.
5:46
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--
6:11
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
6:36
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--
7:04
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.
7:40
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--
8:08
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,
8:39
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.
9:08
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.
9:42
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.
10:12
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.
10:40
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.
11:09
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.
11:42
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.
12:17
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.
12:47
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.
13:17
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.
13:43
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,
14:15
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,
14:38
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.
15:01
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,
15:33
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--
15:59
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.
16:28
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
16:54
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.
17:21
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.
17:56
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
18:24
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
18:50
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.
19:18
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.
19:45
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.
20:15
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.
20:45
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.
21:18
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,
21:42
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
22:07
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
22:36
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.
23:01
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,
23:30
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,
23:57
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
24:25
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.
24:56
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?
25:27
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
25:54
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,
26:28
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.
26:52
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
27:22
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,
27:47
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.
28:15
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.
28:46
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--
29:19
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
29:49
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,
30:15
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.
30:40
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.
31:13
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.
31:42
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.
32:06
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.
32:39
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.
33:12
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.
33:38
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.
34:05
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.
34:28
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,
34:53
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,
35:20
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
35:42
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.
36:11
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,
36:37
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.
37:04
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.
37:33
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
38:03
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
38:28
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.
38:58
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.
39:29
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
39:55
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
40:20
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.
40:46
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,
41:08
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.
41:32
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.
41:59
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
42:24
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
42:52
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.
43:22
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.
43:46
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.
44:12
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.
44:39
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.
45:08
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.
45:35
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,
45:58
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,
46:23
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.
46:49
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.
47:16
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.
47:47
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.
48:10
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
48:35
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,
49:01
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.
49:27
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.
49:55
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.
50:20
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.
50:47
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.
51:13
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.
51:41
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.
52:09
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.
52:32
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.
52:56
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
53:23
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
53:47
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.
54:10
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.
54:37
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.
55:03
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,
55:30
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.
55:57
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.
56:24
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.
56:52
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.
57:17
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.
57:49
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,
58:18
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.
58:47
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.
59:17
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
59:43
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.
1:00:09
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.
1:00:51
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,
1:01:18
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
1:01:40
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.
1:02:03
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?
1:02:28
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
1:02:52
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,
1:03:17
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.
1:03:43
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,
1:04:08
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.
1:04:33
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.
1:04:59
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
1:05:23
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.
1:05:52
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.
1:06:16
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.
1:06:42
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
1:07:10
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,
1:07:38
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.
1:08:07
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.
1:08:34
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?
1:09:06
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
1:09:37
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.
1:10:05
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.
1:10:35
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
1:11:04
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.
1:11:32
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,
1:12:00
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.
1:12:32
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
1:13:00
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.
1:13:26
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
1:13:56
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.
1:14:26
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.
1:14:53
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.
1:15:17
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,
1:15:44
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?
1:16:11
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,
1:16:35
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
1:17:02
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,
1:17:26
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.
1:17:52
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?
1:18:20
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,
1:18:44
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
1:19:17
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,
1:19:44
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,
1:20:12
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?
1:20:42
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.
1:21:14
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.
1:21:45
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.
1:22:18
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.
1:22:46
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.
1:23:18
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
1:23:50
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.
1:24:16
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,
1:24:42
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
1:25:13
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.
1:25:40
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.
1:26:04
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.
1:26:36
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.
1:27:07
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.
1:27:42
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.
1:28:07
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.
1:28:35
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.
1:29:05
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,
1:29:36
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.
1:30:07
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.
1:30:35
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,
1:31:04
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.
1:31:32
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
1:32:00
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.
1:32:31
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.
1:32:55
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.
1:33:25
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.
1:33:49
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.
1:34:15
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.
1:34:48
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,
1:35:21
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.
1:35:53
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.
1:36:23
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,
1:36:50
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
1:37:16
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.
1:37:41
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
1:38:05
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,
1:38:31
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.
1:38:55
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
1:39:19
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.
1:39:45
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.
1:40:10
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
1:40:39
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
1:41:08
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.
1:41:35
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.
1:42:01
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
1:42:30
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.
1:42:56
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.
1:43:25
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,
1:44:01
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,
1:44:31
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.
1:45:04
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.
1:45:35
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,
1:46:05
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
1:46:31
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,
1:46:57
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
1:47:23
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.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat