All right. So let's get started. [NOISE] So today's lecture is going to be on logic. Um, to motivate things, I wanna start with, uh, hopefully an easy question. So if X_1 plus X_2 is 10, and X_1 minus X_2 is 4. What is X_1? Someone shout out the answer once you figure it out. 7. So how did you come to get 7? Yeah. You do the algebra thing that you learned a while ago, right? [NOISE] Um, so what's the point of this? Um, so notice that this is, uh, a factor graph where we have two variables,
they're connected by two constraints or factors. And you could in principle go and use backtracking search to try different values of X_1 and X_2 until you eventually arrive at the right answer. But clearly, this is not really an efficient way to do it. And somehow in this problem, there's extra structure that we can leverage to arrive at the answer in a much, much easier way. And this is kind of the- going to be the poster child of what we're gonna explore today and on next Monday's lecture, how you can do logical inference to Arrive at
answers much faster than you might have otherwise. [NOISE] So we've arrived at the end of the- of the class, um, and I wanna just, uh, [NOISE] reflect a little bit on what we've learned, and maybe this will be also a good review for the exam. Um, so in this class, we've boast- bolstered everything on the modeling, um, inference learning paradigm. And the picture you should have in your head is this. Abstractly, we take some data, we perform some learning on it, and we produce a model. And using that model, we can produce a perform inference
which looks like taking in a question and returning an answer. So what does this look like for all the different types of instantiations we've looked at? So for search problems, the model is a, is, is a search problem and the inference asked the question; what is the minimum cost path? Um, in MDPs and games, we asked the question what is the maximum value policy? In CSPs, we asked the question [NOISE] what is the maximum weight assignment? And in Bayesian networks, We can answer probabilistic inference queries of the form, what is the probability of some query
variables conditioned on some evidence variables? And for each of these case, we looked at the modeling, we look at the, the inference algorithms, and then we looked at different types of, uh, learning procedures going backwards, maximum likelihood. Uh, we looked at, uh, various reinforcement learning algorithms. We looked at structured perceptron and so on. And hopefully, this, this kind of sums up, um, the kind of the worldview that CS221 is trying to impart is That there are these different co- you know, components. Um, and depending on what kind of modeling you choose, you have different types
of algorithms, um, and learning algorithms. Inference algorithms and learning algorithms that emerge. Okay? So we looked at several modeling paradigms, um, roughly broken into three categories. The first is state based models, search problems, MDPs, and games. And here, um, the, the way you think about modeling is in terms of states, and as nodes in a graph and actions that take you between different states, um, Which incur either a cost or give you some sort of reward, and your goal is just to find paths, or contingent paths, or policies, um, in these graphs. Then we shifted
gears to talk about variable based models. Where instead we think about variables, um, and factors that constrain or, um, these variables to, uh, take on certain types of values. Um, so in today's lecture, I'm gonna talk about logical based models. So we're gonna look at propositional logic and first-order logic which are Two different types of logical languages or, um, models. And, um, we're gonna instead think about logical formulas and inference rules which is going to be another way of kind of thinking about, uh, modeling the world. Historically, logic was actually the dominant paradigm in AI,
um, before the 1990s. So it might be hard to kind of believe now. But just imagine the amount of excitement that is going into deep learning today. This equal amount, uh, of excitement was going into logical based methods in, in AI in, uh, um, in the '80s and before that too. Um, but there was kind of two problems with logic. One is that, um, logic was deterministic so it didn't handle uncertainty very well, and [NOISE] that's why probabilistic inference and other methods were developed to address this. And it was also rule-based which allow- didn't allow
you to naturally ingest a large amount of data to, you know, uh, guide behavior, and the emergence of machine learning has addressed this. Um, but one strength that kind of has been left on the table is the expressiveness. And I kind of emphasize that logic as you will see gives you, um, the ability to express very complicated things in a very, You know, succinct way. And that is kind of the main point of, uh, logic which I really want everyone to, um, kind of appreciate, and hopefully this will become clear through examples. Um, as I
motivated on the first day of class, the reason- uh, one, one good way to think about why we might want logic is, imagine, you wanna lie on a beach, um, and [NOISE] you want your assistant to be able to do things for you but, um, hopefully it's more like, um, Data from Star Trek rather than Siri. Um, you wanna take an assistant and you want to be able to at Least tell information and ask your questions, and have, um, these questions actually be answered in response- eh, to, to reflect the information that you've, uh, [NOISE]
told them. Um, so just kind of a brief refresher on the first day of class. I showed you this demo where you can talk to the system, [NOISE] uh, um, and say things and ask a question. So a small example is, um, let's say all students like CS221. It's great and teaches them important things. Um, and, uh, Alice does not like CS221. And then you can ask, um, you know, ''Is Alice a student?'' And the answer should be, ''No'', because it can kind of reason about this one. [NOISE] Um, and just to, uh, dive under
the hood a little bit, um, inside, it has some sort of knowledge-based stack contains the information at, um, it has, we'll come back to this in a second. Okay? Um, so this, this, uh, system needs to be able to digest heterogeneous information in the form of natural language, you know, uh, utterances, and it has to reason deeply with that information. So it can't just do, you know, Superficial pattern matching. So I've kind of suggested natural language as an interface to this. Um, and natural language is very powerful because, um, I can send up here and
use natural language to give a lecture and hopefully you guys can understand at least some of it. Um, and- but, you know, let's, let's go with natural language for now. So here- here's an example of how you can draw inferences using natural language. Okay? So a dime is better than a nickel. Um, a nickel is better than a penny. So therefore, a dime is better than a penny, okay? So this seems like pretty sound reasoning. Um, so what about this example, a penny is better than nothing, um, nothing is better than world peace. [inaudible]. Therefore,
a penny is better than world peace, right? Okay. So something clearly went, uh, wrong here. And this is because, languages- natural language is kind of slippery. It's not very precise, which makes it very easy to kind of make these, um, these mistakes. Um, but if we step back and think about what is the role of natural language, it's really- language itself is an ex- mechanism for expression. So there are many types of languages. There's natural languages, um, there's programming languages, which all of you are, you know, familiar with. Um, but we're going to talk about,
a different type of language called logical languages. Um, like programming languages, so they're gonna be formal. So we're gonna be absolutely clear what we mean by when we have a statement in a logical language. Um, but, and like natural language, it's going to be, um, declarative. Um, and this is maybe a little bit harder to appreciate right now, But it means that, uh, there's kind of a more of a, um, one to one isomorphism between logical languages, and natural languages, as they're compared to, um, programming languages and natural language. Okay. Um, so in a logical
language, we want to have two, uh, properties. First, a logical language should be, uh, rich enough to represent knowledge about the world. Um, and secondly, it's not sufficient just to represent the knowledge, because you know, uh, a hard drive can represent the knowledge, But you have to be able to use that knowledge in a- in a way to reason with it. Um, a logic contains three, uh, ingredients, um, which I'll, um, go through in a- in subsequent slides. There is a syntax, which defines, um, what kind of expressions are valid or grammatical in this language.
Um, there's semantics which is for each, um, expression or formula. What does it mean? And mean means is- is actually, means something very precise which I'll, you know, come back to. And then inference rules allow you to take various f- uh, formulas and, um, do kind of operations on them. Just like in the beginning, we- when we have the, um, algebra pro- problem, you can add equations, you can move things to different sides. Um, you can perform with these rules, which are syntactic manipulations on these formulas or expressions. That preserves some sort of, um, semantics.
Okay, so just to, uh, talk about syntax versus semantics a little bit, because, I think this might be a s- slightly subtle point which, Um, hopefully will be clear with this example. So syntax refers to, what are the valid expressions in this language, um, and semantics is about what these ex- expressions mean. So here is an example of two expressions, which have different syntax. 2 plus 3 is not the same thing as 3 plus 2, but they have the same semantics. Both of them mean, the number, you know, 5. Um, here's a case where, we
have two expressions with the same syntax, 3 divided by 2, But they have different semantics, betw- depending on which language you're in. Okay? So in order to define a language precisely, you not only have to specify the syntax, but also the, um, semantics. Because just by looking at the syntax you don't actually know what its, um, meaning is. Unless I tell you. Um, there's a bunch of different logics. Um, the ones highlighted in bold are the ones I'm gonna actually talk about in this class. So today's lecture is going to be,um, on propositional logic. Um,
and then, uh, in the next lecture, I'm gonna look at first-order logic. Um, as with most models in general, there's going to be a trade off between, the expressivity and the computational efficiency. So as I go down this list, to first-order logic and beyond, um, I'm going to be able to express more and more things, using the language. But it's gonna be harder to do, uh, computation in that language. Okay. So this is the- the kind of a key diagram, um, to have in your head, while I go through syntax semantics and inference rules. So
for every- I'm gonna do this for propositional logic, And then in, uh, Monday's lecture I'm gonna do it for, uh, first-order logic. Um, so just to get them on the board, um, we have syntax, and we have, um, semantics, and then we have inference rules. Um, let's just write it here. Um, so this lecture is going to have a lot of definitions and concepts, um, in them. Just to giv- give you a warning. There's a lot of kind of ideas here. Um, they're all very kind of, uh, um, simple by themselves and they kinda piece
together, but there's just gonna kind- kinda be a barrage of, uh, Terms and I'll try to write them on the board, so that you can kind of remember them. Um, so in order to find, uh, a logic called language, um, I need to specify what are the formulas. Um, um, so one maybe other comment about logic is that, some of you have probably taken, um, CS 103 or an equivalent class where you have been exposed to propositional logic. Um, what I'm gonna do here, is kind of a much more methodological and- and rigorous treatment of
it. Um, the- I wanted to distinguish the difference between, um, being able to do logic yourself. Like if I give you some, uh, logical expression you can manipulate it. That's different than, um, talking about a general set of algorithms, that can operate on logic itself. Right. So remember in AI, we're not interested in you guys doing logic, because that's just I. That's intelligence. Um, [LAUGHTER] but we're interested in developing general principles, or general algorithms that can actually do the wo- work, uh, for you. Okay? Just like in, uh, in the Bayesian networks, it's very fine
and Well that you can- you guys can, uh, manipulate and condition, uh, calculate conditional and marginal probabilities yourself. But the whole point is we devise algorithms like Gibbs sampling, and variable eliminish- elimination that can work on any, uh, Bayesian network. Just wanna get that out there. Okay. So let's, uh, begin. Um, this is gonna be building from the ground up. So first of all, there are in propositional logic, there are a set of propositional symbols. These are typically going to be uppercase letters or even, um, words, Um, and these are the atomic formulas. Um, these
are formulas that can't be any smaller. There is going to be logical connectives such as, uh, not and or, um, implication and bidirectional implication. And then, the set of formulas are built up recursively. So if F and G are formulas, then I can- these are also formulas. I can have not F. I can have F and G, F or G, F implies G and F, um, bidirectional implication G or equivalent to G. Okay? So key, um,you know ideas here are, we have, um, propositional symbols, um, we're gonna mo- move this down, because we're gonna run
out of space. Um, so this- these are things like A, there's- that gives rise to formulas in general, um, which is gonna be denoted, um, F. Um, and so here are some examples. So A is a formula. Okay? It's in particular, it's an atomic formula which is a propositional symbol, not A is a formula, not B implies C as a formula. This is a formula. Um, this is the formula. Double negation is fine. This is not a formula, Because there's no connective between A and not B. Um, this is also not a formula, because what
the heck is plus? It's not a connective. So- so I think in- in thinking about logic, you really have to divorce yourself from the common sense, that you all come with in interpreting these symbols. Right? Not is just a symbol or is just a symbol, and they don't have any semantics. In- in fact, I can go and define some semantics, which would be completely different from what you would imagine. It would be a lo- valid logical, um, system. These are just symbols, And all I'm here at defining is what symbols are valid and what symbols
are not valid, slash grammatical. Okay? Any questions about the syntax of propositional logic? So the syntax gives you the set of formulas or basically statements you can make. So you can- think about as- as this is our language. If we could only speak in propositional logic, I could say, A or not B or the or, um, A implies C. And that's all I would be able to say. Um, and of course now I have to tell you what do these things mean. Okay? And this is the realm of semantics. So semantics, there's gonna be a
number of definitions. So first, is a model. So this is really unfortunate and confusing terminology. But this is standard in the logical literature. So I'm just gonna use it. So a model, which is different from our general notion of a model. Um, for example, um, Hidden Markov Model for example. It- a model here, in propositional logic, just refers to an assignment of, um, truth values to propositional symbols. Okay? So if you have three propositional symbols, that they are 8 possible models. Um, A is, uh, 1, B is 0, C is 0 for example. So these
are just complete assignments that we saw from factor graphs. But now, um, in this new kind of language. Okay. So that's the first constant. And in first-order logic models are going to be more complicated. Um, but for now, you think about them as a complete sentence. And I'm using W, because sometimes you also call them, um, worlds. Um, because a complete assignments slash a model, is both to represent the state of the world at any one particular point in time. Yeah. [inaudible] Yeah. So the question is, can each propositional symbol either be true or false?
And in logic, as I'm presenting it, yes. Only true or false or 0 or 1. Okay? So these are models. Um, and next is a key thing that actually defines the semantics, which is the interpretation function. So the interpretation function, um, takes a formula and a model and returns true if that formula is, uh, is true in this model and false, um, you know, otherwise. Okay? So I can make the interpretation function whatever I want, um, and that just gives me the semantics. So when I talk about what are the semantics, It's the interpretation function.
Function i of f, w. [NOISE] So the way to think about this is, um, I'm gonna represent formulas as these, uh, horizontal bars. Okay? So this is- think about this as, uh, a thing you'd say. It sits outside though, uh, reality in so- in some sense. And then this box, I'm gonna draw on the space of all possible models. So think about this as a space of situations, uh, that we could be in the world, and a point here corresponds to a particular model. So an interpretation function takes one, a formula, takes, um, a model
and says, "Is this statement true if the world looks like this?" Okay? So just to ground this out, um, a little bit more, um, I'm gonna define this for propositional logic, again recursively. Um, so for propositional symbols, um, p, I'm just gonna interpret that propositional symbol as a lookup in, uh, the, the model, right? So if I'm asking, "Hey, is A true?" Well, I go to my, uh, model and I see well, Does it say A is true or false. Okay? That's a base case. So recursively, I can define the interpretation of any formula in
terms of its sub formulas. And the way I do this is suppose I have two formulas f and g and they're interpreted in some way. Okay. And now, I took a formula let's say f and g. Okay? So what is the interpretation of f and g, um, in w? Well, it's given by this truth table. So if f is 0 and g is, uh, interpreted to be 0, then f and g is also interpreted to be 0. And, um, 0,1 maps to 0, 1, 0 maps to 0 and 1, 1 maps to 1. So you
can verify that this is kind of, um, your intuitive notion of what and should be, right? Um, or is, um, 1 if, um, at least one of f and g are 1, um, implication is 1. If f is 0 or g is, uh, is, is 1. Um, if bidirectional implication just means that if f and g evaluate to the same thing, uh, not f is, you know, clearly just, you know, Negation of whatever the interpretation of f is. Okay. So this slide gives you the full semantics of propositional logic. There's nothing more to propositional logic
and at least the definition of what it is, um, aside from this. Um, let me go through example and then I'll maybe take questions. So, so let's look at this formula, not A and B, bidirectional implication C. Um, in this model A is 1, B is 1, C is 0. Um, how do I interpret this formula against this model? Well, I look at the, the tree, um, which breaks down the formula. So if I look at the leaves, um, let's start bottom-up. So the interpretation of A against w is just 1. Because for a proposition
symbols, I just look up what A is and A is 1 here. Um, the interpretation of not A is 0 because if I look back at this table. If this evaluates to 1, then this evaluates to 0. I'm just looking, um, based on the table. Um, B is 1 just by table lookup, and then, um, not A and B is 0 because I just take these two values and I add them together. Um, C is 0 by table look up and then, uh, bidirectional implication, um, is interpreted as, uh, 1 here because 0 is equal
to 0 here. Yeah. Yeah, question? Interpretation function is user defined in this case not like learning how to interpret [inaudible] Yeah, so the question is, is the interpretation function user defined? It is just written down. Um, this is it, there's no learning that's just these are- this is what you get. Um, it's not user-defined in the sense that not everyone's gonna go define their own, [LAUGHTER] you know, truth tables. Um, some logicians came up with this, and that's what it is. Um, but you could define your own logics, and it's kind of a fun thing
you could try doing. Okay? Any other questions about interpretation functions and models? So now, we're kind of connecting syntax and semantics, right? So an interpretation function binds what our formulas, which are in syntax land to, um, a notion of models which are, uh, in semantics. So a lot of logic is very, um, It might seem a little bit pedantic but it's just because we're trying to be very rigorous in a way that doesn't need to appeal to your common sense intuitions about of what these formulas mean. Okay? Any questions? All right. So, so while we
have the interpretation function that defines everything, it's really going to be useful to think about formulas in a slightly, uh, different way. So we're gonna think about a formula, um, as representing, um, the set of all models for which interpretation is, you know, true. Okay? So M of F, which is the- is the set of models, um, that f is, Uh, true on that model. Okay? So pictorially, this is, ah, f that you say out loud. And what you mean by this is, um, simply this subset of models, um, which, uh, this f is true.
Okay? So if I make a statement here, what I'm really saying is that I think we're in one of these models and not in one of these other models. So that's a kind of an important, uh, I think intuition to have, the meaning of a- a formula is carving Out a space of possible situations that you can be. And if I say there's a water bottle on the table, what I'm really saying is that, I'm ruling out all the possible worlds that we could be in where there is no water table- bottle on the table.
Okay? So models, um, M of f is gonna be a subset of all the possible models in the world. Okay? So here's an example. So if I say it's either raining or wet- rain or wet, then the set of models can be represented, um, by this, um, subset of this two-by-two. Okay? So over here, I have rain, over here I have wet. So this corresponds to no rain but it's wet outside, [NOISE] um, this corresponds to it's raining but it's not wet outside. And the set of models f is this red region which are these
three possible models. Okay? So I'm gonna use this kind of pictorial depiction throughout this, uh, lecture. So hopefully, this makes sense. So, so one key idea here- remember, I said that logic allows you to express very complicated and large things by using very small means. So here, I have a very small formula that's, um, able to represent a set of models, and that set of models could be exponentially large. And much of the power of logic allow- it comes from the ability to, um, do stuff like that. Okay. So, um, here's yet another definition. This
one's not somehow, um, such a new definition- um, sorry, a new concept but it's kind of just trying to give us a little bit more intuition for what these, um, formulas and, um, uh, models are doing. So knowledge base is just a set of formulas. Um, and, and think about this as the set of facts you know about the world. So this is what you have your head. And in general, it's going to be a- just a set of formulas and now the- the key thing as I need to connect us with semantics. So I'm
gonna define the set of models denoted by a knowledge base to be the intersection of all of the models denoted by the formulas. So in this case, if I've rain or snow being this, uh, green ellipse and traffic being this red ellipse, then the model is denoted by the knowledge base is just the intersection. Okay? So you can think about knowledge as how fine-grain, uh, we've kind of zoomed in on where we are in the world, right? So initially, if you don't know anything, we say anything is possible all 2 to the n, you know,
models are possible. And as you add formulas into your knowledge base, the set of, um, possible worlds that you think might exist, uh, are possible is going to shrink, um, and, you know, we'll see that in a sec- in a second. Okay. So here's an example of a knowledge base. If so have rain that corresponds to this set of models, um, rain implies wet corresponds to the set of models. And if I look at the models of this knowledge base, it's just going to be the intersection which is this, uh, red square down here. Okay?
Any questions about knowledge bases, models, interpretation functions so far? All right. So as I've alluded to earlier, knowledge base is the thing you have in your head. And as you go through life, you're going to add more formulas to your knowledge base. You're gonna learn more things. Um, so your knowledge base just gets, uh, union with whatever formula you- you have. And over time, the set of models is going to shrink because you're just taking your intersection. Um, and one question is, you know, how much is this sh- uh, shrinking? Okay? So here, there's a
bunch of different cases to contemplate. Um, the first case is, um, entailment. So suppose this is your knowledge base so far, and then someone tells you, um, the formula that corresponds to this, ah, set here. Okay. So in this case, um, intuitively, f doesn't add any information or new constraints that was known before. And in particular, if you take the intersection of these two, you end up with exactly the same set of models you had before so you didn't learn anything. Um, and this is called entailment. So, um, so there's kind of three notions here,
there's entailment which is written this way with two horizontal, uh, bars, Um, which means that the set of models, um, of f is at least as large as the set of models in, uh, KB or in another words, it's a superset. Okay? Um, so for example, rain and snow. If you already knew it was raining or snowing and someone tells you, "Ah, it's snowy." Then you say, "Well, um, duh, I didn't learn anything." Um, a second case is contradiction. [NOISE] So if you believe the world to be in here or somewhere and someone told you
it's actually out here, then, um, your brain explodes, right? Um, so this is where the set of models of The knowledge base on the set of models denoted by the formula is empty. So this- it doesn't make sense. Okay? So that's a contradiction. Um. Okay, so if you knew it was rainy and snowing and someone says it's actually not snowing, then you, you- right, know that, that can't- that can't be right. Okay. So the third case is, um, basically everything else. It's contingency where, um, f adds a non-trivial amount of information to a knowledge base.
So the, the new set of models- the intersection here is neither empty nor is it the original knowledge base. Okay? One thing to kind of uh- not get confused by is, if the set of models were actually strictly inside and the knowledge base, that would also be a contingency. Right, because when you intersect it, it's neither empty nor the original. Okay. So if you knew it was rainy, it's, um- raining and someone said, "Oh, it's also snowing too." Then you're like, "Oh cool, I learned something." Okay, so there- there's a relationship between contradiction and entailment.
So contradiction says that the knowledge base Mf, um, are- have zero intersection, and entailment, um, this is equivalent to, um, the knowledge base entailing not f. Okay so just, there's a simple proposition that says, um, KB contradicts f if KB- if and if KB entails not f. Okay so, um, there's the picture you should have in here is like not f is all of the models which are not in this. And if you think about kind of, wrapping that around, it kind of looks like this. Okay, [BACKGROUND] all right. So with these three, Um, notions:
entailment, contradiction, and contingency which are relationships between a knowledge base and a new formula, we can now go back to our kind of virtual assistant example and think about how to implement, um, these operations. So if I have a knowledge base and I tell, um, the- the virtual assistant of a particular, um, formula f, there are three possible abilities which correspond to different appropriate responses. So if I say it's raining, then, if it's in entailment, then I say, "I already knew that because I didn't learn anything new." If it's a contradiction, then I should say,
"I don't believe that because it's not consistent with my knowledge so far." And otherwise, you learn something new. Okay, um, there's also the ask operation which if you're asking a question, again, the same three, uh, entailment, contradiction, and contingency can hold. Uh, but now, the responses are- should be answers to this question. So if it's entailment, then I say yes. And this is a strong yes and it's not like, uh, probably yes, this is a definitely yes. If it's a contradiction, then I say no. It's- again, it's a strong no, it's impossible. And then in
the other case it's just contingent which you say I don't know, okay. So the answer to a yes or no question, there's three responses, not two, okay. Okay, any questions about this? Okay, how many of you are following along just fine? Okay, good. All right. So this is a little bit of a digression and it's going to connect to Bayesian networks. So you might be thinking in your head, well, we kind of did something like this already, right? In Bayesian networks, we had these complete assignments and we actually defined joint distributions over complete assignments. And-
and now, what we're talking about is not distributions but sets of assignments or models. And so we can actually think about the relation between a knowledge base and an f also having an analog in a Bayesian network land given by this formula. So, um, remember, a knowledge base is a set of models or possible worlds. So in probabilistic terms, this is an event. Um, and that event has some probability. So that's- that's a denominator here. And when you look at f and KB and you intersect them, you get some other, uh, event which is a
subset of that and you can ask for the probability mass of that, uh, intersecting event, that's the numerator here. And if you divide those, that actually just gives you the probability of a formula, uh, given the knowledge base. Okay, so this is actually a kind of pretty nice and direct, um, um, probabilistic generalization of propositional logic. Uh, yeah. It's only once if you had like all the var- all the variables required for that, for me they're already exists a set of networks like in this scenario, there's A, B, C, if we were asking something about
D, would still be in I don't know, because we don't have that information. Yeah so the question is this only works when restricted to the set of predefined, uh, propositional symbols and you are asking about D, Then yeah, you would say I don't know. And it's- in fact, when you define propositional logic, you have to pre-specify the set of symbols that you are dealing with, um, in general, yeah. [inaudible] given the example that we did earlier, like reading wasn't given a set of examples are things that our agent knew about before we started like training.
So is that something we'll get to later? Um, yes so the question is in the- in the- in practice, you could imagine giving you an agent like it is raining or it's snowing or it's sleeting, and having novel concepts. Um, it is true that you can devise, Build systems and the system I'm showing you has that capability. Um, um, and this is, uh, it'll be clear how we do that when we talk about inference rules because that allows you to operate directly on the syntax. Um, here, I'm talking about semantics where you essentially just, just
for convenience. I mean you can be smarter but- but we're just defining the- the world. Yeah. Yeah, so in this formula, why is this union not intersection? So I'm unioning the KB with a formula, which is equivalent to intersecting the models of the KB with the models of the formula. Okay. So this is a number between 0 and 1. And this reduces actually to, Uh, the logical case if, if this probability of 0, um, that means there's a [NOISE] contradiction, right? Because this intersection is- it's gonna be pros- probability 0. And if it's 1, that
means in its entailment. Um, and the cool thing is that instead of just saying I don't know, you're gonna actually give a probabilistic estimate of like, well, I don't know, but it's probably like 90%. Um, so, you know, we're not gonna talk, uh, this is all I'm gonna say about probabilistic extensions to logic, but there are a bunch of other things, um, that you can do that kind of marry the, um, The expressive power of logic with some of the more advanced capability of handling uncertainty of probabilities. Yeah? [inaudible]. Assuming that, I mean, the probability
distribution? Yeah. To do this, you are assuming that we actually have the joint distribution at hand. And a separate problem is of course, learning this. So for logic, I'm only talking about inference, I'm not gonna talk about learning although there are ways to actually in- infer logical expressions too. Okay. So back from the digression now, no probabilities anymore. We're just gonna talk about logic. Um, there's another concept which is, Um, really useful called, uh, satisfiability. [NOISE] Um, and this is going to allow us to implement, um, entailment, contradiction, contingency using kind of one, um, primitive.
[NOISE] And the definition is that knowledge base is satisfiable if, um, the set of models is non-empty, okay? So it's not self-contradictory in other words. So now, we can reduce ask and tell to satisfiability, okay? Um, remember, ask and tell have three possible outcomes. If I ask a satisfiable question, how many possible outcomes are there? Two? So how am I gonna make this work? I have to probably called satisfiable twice, okay? So let's start with asking if knowledge-based union, um, not f is satisfied or not, okay? So if the answer is, um, no, what can
I conclude? So remember, the answer is no. So it's not satisfiable, which means that KB contradicts not f, and what is that equivalent to saying? [inaudible]. Sorry? Like it's- like it's [inaudible]. Um, yeah so it's not f. So it's- which one of these should have been entailment, contradiction, or contingency? [inaudible]. Yeah, so, um, I'm interested in the relationship between KB and f. [NOISE] I'm asking the question about KB Union not f. Yeah? [inaudible]. Yeah, yeah. So exactly- so this should be an entailment, relation between KB and f. Remember, KB entails f is equivalent to KB
contradicting not f, okay? Um, okay, so what about, um, if it's yes, then I can ask another question, is KB Union f satisfiable or not? So the answer is no, Then what should I say? [inaudible]. It should be a contradiction because, I mean, this literally says KB contr- contradicts f. And then finally, if it's yes, then it's contingency, okay? So this is a way in which you can def- reduce answering ask and tell, which is basically about assessing entailment, contradiction, or contingency to just- uh, to- at most two satisfiability calls. So why are we reducing
things to satisfiability? For propositional logics, uh, checking satisfiability is just the classical SAT problem And it's actually a special case of solving constraint satisfaction problems. Um, and the mapping here is, we just call propositional symbols variables, um, mo- formulas constraints, and we get an assignment here and we call that a model. So in this case, if we have a knowledge base, um, like this, then there are three variables; A, B and C and we define this CSP and then we can, um, if we find a satisfying assignment, then, um, then we return satisfiable. If we
can't find one, then we Return unsat, okay? Um, so this is called model checking. Um, it's called model checking because we're checking whether a model, eh, exists or is, uh, um, is true. So you- in model checking takes a knowledge base and outputs whether there is a satisfying model. Um, there are a bunch of algorithms here which are, you know, very popular, there's something called DPLL named after, uh, four, four people. Um, and this is essentially backtracking search plus, uh, pruning that takes into account the, the structure of your CSPs, Um, which are propositional logic
formulas. Um, and, uh, there's something called WalkSat which is, you can think about the closest analog that we've seen as Gibbs sampling which is a- a randomized local search. Um, okay? So at this point, you really can't have all the ingredients you, uh, you need to do, um, inference and propositional logic. So to define what propositional logic symbols are, um, or formulas are, I define the semantics, um, And I've told you even how to solve, uh, entailment and, um, contradiction and contingency queries by reducing the satisfiability which is actually something we've already, you know, seen
coincidentally, um, so that should be it, okay? Um, but now, coming back to the, you know, original motivation of X_1 plus X_2 equals 10, and how we were able to perform their logical query much faster, we can, uh, ask the question now, can we exploit that, that the factors are, are formulas rather than arbitrary, you know, Functions, and this is where inference rules is gonna come into play, okay? So, um, so I'll try to explain this, uh, figure a little bit since it looks probably pretty mysterious, um, from the beginning. So I have a bunch
of formulas. This is my knowledge base over time, I accrue formulas. And these formulas carve out, um, a set of models in semantics land. And, and this formula here, if it's, um, a superset, that means it's entailed by these formulas, right? So I know that this is true given my knowledge, Which means that this is kind of a logical consequence of what I know, okay? So, so far, what we've talked about is taking formulas and doing everything over in semantics land. What I'm gonna talk about now is inference rules that are gonna allow us to
directly operate on the syntax and hopefully get, um, some results that way. Okay. So here is an example of making an inference. Um, so if I say it is raining, and I tell you if it's raining, it's wet, um, rain implies wet, then what should you be able to conclude? It's wet. It's wet, right? So I'm gonna write this inference rule this way with this, um, kind of fraction looking like thing where there's a set of premises which is a set of formulas which I know to be true. And if those things were true, then
I can derive a conclusion which is another formula. This is, um, an instance of a general rule called Modus ponens, um, that says for any propositional symbols p and q, if I have p and p implies q in my knowledge base, then I can- that entails, uh, q, okay? So let's talk about inference rules, [NOISE] um, inference. Actually, let me do it over here, Since we're gonna run out of space otherwise. [NOISE] Okay. So Modus ponens is a first thing we're gonna talk about. [NOISE] So notice here, that if I could do these type of
inferences, it's much less work, right? Because I- it's very localized. All I have to do is look at these three formulas. I don't have to care about all the other formulas or propositional symbols that exist, and going back to this question over here about- or how do I- what happens if I have new concepts that occur? Well, you can just treat everything as if it's just a new symbol. There's not necessarily a fixed set of symbols That you're working with at any given time. Okay, so this is the example of inference rule. In general, the
idea of the inference rule is that you have rules that say, ''If I see f 1 through f k which are formulas, then I can add g.'' Um, and the key ideas I mentioned before is that in these inference rules operate directly on the syntax, and not on the semantics. So given a bunch of inference rules I have this kind of meta algorithm, that can do a logical inference as follows. So I have a set of inference rules, and I'm just going to repeat until there's no changes to the knowledge base. I choose a set
of formulas from the knowledge base. Um, if I find a matching rule, inside rules, that exists, then I simply add g to the knowledge base. Okay? Um, so what the- other definition I'm going to make is, this idea of derives and proved. So, um, so inference rule, um, derives, proves, um, so I'm gonna write KB, and now with a single horizontal line. Um, to mean that from this knowledge base given a set of inference rules I can produce f via the rules. Okay? This is in contrast to entailment which is defined by the relationship between
The models of KB and the models of f. Now this is just a function of mechanically applying a set of rules. Okay, so that's a very, very important distinction. And if you think about it, why is it called proof? So whenever you do a mathematical proof or some sort of logical argument, you are in sense, in some sense, just doing logical inference: where you have some premises and then you can apply some rule. For example you can add, um, you know, multiply both sides of the equation by two. That's a rule. You can apply it.
And you get some other equation which you can- um, which you hope is true as well. Okay. So here's an example. Um, maybe I'll just for fun I'll do it over here. Um, oops. So I can say it is raining and if I dumped that, it gives me my knowledge base that has rain. Um, if it is raining it is wet. Um, so if I dumped then I have- this is the same as, um, rain implies wet. Okay. Just- just just, uh, in case you're rusty on your propositional logic. If I have P implies Q
that's the same as not p or q. Okay? And notice that I have also wet appear in my knowledge base because this in the background it's basically running forward inference to, um, try to derive as many conclusions as we can. Okay. Um, and if I say if it is wet, it is, uh, slippery. Um, Again. Now I have. Um, I have, uh, wet implies slippery. Um, and now I also derived slippery. Um, I also derived rain, um, Implies slippery which is actually as you have seen not derivable from modus ponens, so it behind the scenes
is actually a much more, uh, fancy inference algorithm. But, um, but- but the idea here is that you have your knowledge base. Um, you can pick up rain and rain implies wet and then you could add wet. And you pick up rai- wet- wet implies slippery and then you can add slippery here. And with modus ponens, um, you can't actually derive somethings. You can't derive not wet, um, which is probably good because it's not true. And you also can't derive rain implies slippery which actually is true but a modus ponens is not powerful enough to
derive it. Okay. So- so the burning question you should have in your head is- okay. I talked about there's two relations between a knowledge base KB and a formula f. There is entailment relation. And this is really what you want because this is semantics you all- you care about meaning. Um, and you also have this: KB derives f which is a syntactic relationship. So what's a connection here? In general there's no connection. Um, but there's the kind of these concepts that will help us think about that connection. So semantics these are things which are- Um,
when you look at semantics you should think about the models implied by the, um, formulas, and syntax is just some set of rules that someone made up. Okay. So how do these relate? Okay. So to, um, understand this, imagine you have a glass and this glass is um-um, what's inside the glass is formulas. And in particular it's the formulas which are true. Okay. So this glass is all formulas such that the- this formula is entailed by the knowledge base. So, um, soundness is a property of a set of rules. And it says if I apply
these rules until the end of time, do I stay within the glass? Am I always going to generate formulas which are inside the glass which are semantically valid or entailed? Okay. So soundness is good. Um, completeness says that the kinda, um, other direction which says that I am going to generate all the formulas which are true for entailed. I might generate extra stuff. But at least I'll cover everything. That's what it means to be complete. Okay. So the model you should have in your head is you want the truth, the whole truth and nothing but
the truth. Soundness is really about nothing but the truth and completeness is about the whole truth. Ideally you would want both. Sometimes you can't have both so you're going to have to pick your battles. Uh, but generally, you want soundness. Um, you can maybe live without completeness, um, but if you're unsound, that means you are just going to generate erroneous conclusions, which is, uh, bad. Whereas, if you're incomplete, then maybe you just can't, uh, infer certain f- notions, but at least you- the things that you do infer, you know, are actually true. Okay. So how
do we check, um, soundness? [NOISE] So is modus ponens sound? Um, so remember, uh, there's, kind of, a rigorous way to do this. And the rigorous way is to look at two formulas. Rain, rain, uh, implies wet, uh, and then look at their models. Okay. So rain corresponds to these set of models here. Um, rain implies wet and corresponds to this set. Um, and when I intersect them, that's the, the set of models which are conveyed by the knowledge base, which is this corner here. Um, and I have to check whether that is a s-
a subset of the models of wet. And wet is over here. So this one-one corner is a subset of one-one and zero-one. So this rule is sound. [NOISE] Remember this, why is this subset of the thing I wanna check? Because that's just the definition of entailment. Right? Okay. So let's do another example. So if someone said it was wet, and you know that rain implies wet, can you infer rain? [NOISE] Well, let's, let's, uh, let's just double-check this. Okay. So again, what are the models of wet? They're here. What is the models of rain implies
wet? They're here. And I intersect them, I get this, um, this- these two over here in dark red, and then is that a subset of models of rain? Nope. So this is unsound. Okay. So in general, soundness is actually a fairly, uh, easy condition to check, especially in propositional logic. But in higher-order logics, it's, you know, not as bad. So now completeness is a, Kind of, a different story, which I'm not gonna have time to really do full justice in this class. But, um, but here's a, kind of, a, a example showing modus ponens as,
um, incomplete, so, um, uh, for propositional logic. [NOISE] Uh, so here we have the knowledge base, some rain, rain or snow implies wet. Um, and is this entailed, wet? So it's raining, and if I know it's raining or snowing, then that should be wet. How many of you say yes? Yeah. It should be entailed, right? Okay. Well, what does modus ponens do? Well, all the rules look like this. Um, so [NOISE], um, clearly you can actually arrive at this with modus ponens because modus ponens can't reason about or, or disjunction. Yeah. Is it possible for
it to be right about the rain or snow? Or is it saying that it's not possible for it to be not wet given rain? Uh, is it [NOISE] not? Yeah. Because you're- you already [NOISE] know that it's raining. All right. So you should say that it's wet. Yeah. Okay. So this is incomplete. Um, so we can be, um, you know, sad about this. Uh, there are two ways you can go to fix this. The first way is, um, we say, okay, okay, propositional logic was, um, too fancy. Uh, question? Um, just going back to the
[inaudible] - Yeah. -of the notation, when it says KB equals rain, then comma, rain or snow implies wet, Is in implying in any type of assignment to rain there? Like, is it saying that it is raining or is it just saying that we have a variable rain? Yeah. So the question is what does this mean? Um, this- so the knowledge base is a set of, uh, formulas. So in this particular formula is rain. And remember, the models of a knowledge base is where are the formulas are true. So yes, in this case it does commit
to rain being 1. The- then models of KB are- only include the, um, the models where rain is 1. Otherwise, this formula would be false. Thank you. Yeah. Yeah? [inaudible] the probability of the model, um, as in way back before the [inaudible]? Oh, it was, how can we have a probability over a model? Um, so remember that a model is- um, where did it go? [NOISE] Okay. So remember a model here is just an assignment to a set of, uh, proposition symbols or variables, right? So when we talk about Bayesian networks, um, we're defining a
distribution over assignments to all the variables. So here, while I'm saying is that assume there is some distribution over, um, complete assignments to random variables, and I can use that to compute, um, Probabilistic queries of the form- of formula given knowledge base. Am I answering your question? Yeah. [inaudible] [NOISE] -shouldn't you- if you have two models that contradict, they can't be in the same knowledge base, right? [NOISE] Um, if you have two models that [NOISE], uh, or [NOISE] formulas that contradict, then this intersection is going to be, uh, 0 [NOISE]. So there is- exists a
set of models. So let me do it, um, you know, this way. So imagine you have these two [NOISE] variables, rain and wet. Um, [NOISE] a Bayesian network might assign a probability 0.1, point- um, I should make these sums of one. Um, point, what is this? Five? Um, so some distribution over these states, right? And, um, [NOISE] and if I have [NOISE] rain, [NOISE] that corresponds to these models. So I can write the probability of rain [NOISE] is 0.2 plus 0.5, [NOISE] so 0.7. Okay? And if I have the probability of wet [NOISE], um, given
rain, um, this is going to be the probability of the conjunction of these, which is going to be wet and rain, which is here. This is going to be 0.5 divided by the probability of rain, which is 0.7. [NOISE] Does that help? [NOISE] Okay. [NOISE] Whoops. Um, okay. So- okay. So modus ponens is sound, but it's not complete. So there's two things we can do about this. We can either say propositional logic is too fancy. Let's just restrict it so that modus ponens becomes complete with, with respect to a restricted set of formulas. Or we
can use more powerful inference rules. So today we're going to restrict propositional logic, um, to make it complete. Um, and then next time we're gonna show how a resolution which is, uh, even more powerful inference rule can be used to make, um, any arbitrary inferences. And this is what's, uh, powering the, the system that I showed you. [NOISE] Okay. So um, a few more definitions. [NOISE] So we're gonna define,um, a propositional logic with, with horn clauses. Okay. So, so a definite clause is, um, [NOISE] a propositional formula of the following form. So you have some
propositional symbols, all conjoined together, conjoined just means it's added, um, implies some other propositional symbol q. And the intuition of this, uh, formula says if p_1 through p_k hold, then q also holds. So here's some examples. Rain and snow implies traffic. Um, traffic is can be- is possible. Um, this is a non-example. Um, this is a valid propositional, uh, logic formula, but it's not a valid definite clause. Um, here is also another example. Um, rain and snow implies peace- uh, traffic or peaceful, okay? So this is not allowed because the only thing allowed on the
right side- hand side of, um, the implication is a single propositional symbol, and there's two things over here. Okay? So a horn clause is, um, a definite clause or a goal clause, um, which might seem a little bit mysterious. But, um, it's defined as a, [NOISE] um, something that, um, p_1 through p_k implies false. And the way to think about this is the negation of a conjunction of things, right? Because remember, um, p implies q is not p or q. So this would be not p or true, which is not p in this case. Okay?
So, so now we have these horn clauses. Um, now, remember the inference rule of modus ponens. Um, we are gonna slightly generalize this to include, um, not just p implies q, but p_1 through p_k implies q. So you get to match on, um, premises which include formulas which are atomic propositional symbols and a rule that, um, looks like this, and you can, uh, derive or prove, uh, q from that. Okay? So as an example, wet and weekday. If you see wet, weekday, wet and weekday implies traffic, those three formulas. Then you can- you're able to
add traffic. [NOISE] Okay. So, um, so here's the claim. So modus ponens is complete with respect to horn clauses for propositional logic. So in other words, what this means is that suppose that the knowledge base contains only horn clauses and that, um, p is, some entailed, uh, propositional, uh, symbol. By the entailed propositional symbol, I mean, like, KB actually entails p semantically. Then applying modus ponens will derive p. Means that the two relations are equivalent, and you can celebrate because you have both, uh, soundness and, uh, completeness. Okay. So just a quick example of this.
Um, so here imagine is your knowledge base, um, and you're asking the question, uh, is there traffic? And remember, because, um, this is a set of only horn clauses, and we're using modus ponens which is complete, that means, um, Entailment is the same as I'm being able to derive it using these rules- this particular rule. Um, and you would do it in the following way. So rain, rain implies wet, gives you wet. Wet, weekday, wet and weekday implies traffic, gives you traffic, and then you're done. Yeah? You are saying wet implies to, uh, like rain
and weekday, why are those horn clauses? [NOISE] The question is why are rain and weekday horn clauses? Yes. So if you look at the definition of horn clauses, they're definite clauses. If you look at the definite- definition of definite clauses, they look like this. And, um, k can be 0 here. Which means that, um, there's, um, there's kind of like nothing there. [NOISE] That makes sense? It's a little bit of like- I'm using this notation kind of, um, to exploit this corner case that if you have the n of zero things, then that's just, um,
you know, true. Or you can just say by definition, definite clauses contain propositional symbols. Um, that will do too. Okay. So let me try to give you some intuition why modus ponens and horn clauses. So the way you can think about, um, modus ponens is that, it only works with positive, uh, information in some sense. There's no branching, either or. It's like, every time you see this, you just definitively declare q to be true. So in your knowledge base, you're just gonna build up all these propositional symbols that you know are gonna be true. And
the only way you can add a new propositional symbol ever is by, um, matching a set of other things which you can definitely know to be true And some rule that tells you q should be true and then you make q true, um, add q to your knowledge base as well. The problem with propositional sym- uh, the more general clauses is, if you look at this, rain and snow implies traffic or peaceful. You can't just write down traffic or, or peaceful, or both of them. You have to reason about, well, it could be either one.
And that, um, is outside the scope of what modus, you know, ponens can do. Yeah? [inaudible] and peaceful, that way, you can say like [inaudible]. Yeah, yeah, good, good question. So what happens if it were traffic and peaceful? Um, so this is an interesting case where technically, it's not a definite clause, but it essentially is. Um, [LAUGHTER] so- I don't- there's a few subtleties here. So if you have a implies b and c, you can rewrite that. And this is exactly the same as having two formulas a implies b and a implies c. And these
are definite clauses. Um, just like, you know, technically if I gave you, "Hey, what about a not a or b?" It's not a definite clause by the definition, but you can rewrite that as, um, a implies b. So there is, um, slight [NOISE] kind of- you can extend this to say not only definite clauses, but all things which are morally, um, horn clauses, right? Where you can do a little bit of rewriting, um, and then you get a horn clause and then you can do your, you know, inference. Okay? Um, so resolution is this inference
rule that we'll look at next time that allows us to deal with these disjunctions. Um, okay. So to wrap up. So today, we talked about logic. So logic has three pieces. We introduced the syntax for propositional logic. There are propositional symbols which you string together into formulas. Um, and over in syntax land, uh, these are given meaning by, um, talking about, you know, semantics. And we introduced an idea of a model Which is a particular configuration of world that you can be in. A formula denotes a set of models which are true under that formula,
this is given by the interpretation function. Then we looked at, um, entailment contradiction [NOISE] and contingency, which are relations between a knowledge base and a new formula that you might pick up. You could either do satisfiability check or model checking, which tests for satisfiability to solve that, or you can actually do things in, um, syntax land by adjust, uh, operating directly on, um, inference rules. Um, so that's all I have for, uh, today. And I'll see you next Monday. [NOISE].
