# Stanford CS221 | Autumn 2025 | Lecture 16: Logic II

## Метаданные

- **Канал:** Stanford Online
- **YouTube:** https://www.youtube.com/watch?v=x9Mbqu06OVo

## Содержание

### [0:00](https://www.youtube.com/watch?v=x9Mbqu06OVo) Segment 1 (00:00 - 05:00)

All right. So, welcome back everyone. This is going to be the second of the two logic lectures. We're going to talk about first order logic. Um, and this is where you really get to see logic shine and do something interesting. And to motivate why logic is useful, I'm going to go through a example. Um, so in this example, I'm going to build up a knowledge base of facts and I'm going to ask you to really pay attention and follow along um and do some logical reasoning yourself. Okay. So here um each fact I'm going to write the natural language sentence. Alice is a student and I'm going to write also the first order logic expression. Now I haven't told you what first order logic is so we're just going to go through it intuitively but just pay attention to maybe the natural language. Okay so Alice is a student um this is written student of Alice in first order logic. Alice is from Phoenix. So um from Alice Phoenix uh Phoenix is a hot city. So um hot is applies to Phoenix and also um city applies to Phoenix. Um students are people. Okay. So for every X um if X is a student that means uh X is a person as well. Um cities are places. So the same thing but um city of X implies a place of X. If it's snowing, it's cold. Um, so this is just propositional logic, but first order logic is a superset. So we can do that, too. Okay. So now the first question I'm going to ask you, um, is it snowing? — Yes or no or I don't know? — Okay. I don't know. Okay. So we asked the knowledge base and the knowledge base says I don't know. Okay, good. All right. So how about um if a person is from a hot place and it is snowing then they are not happy. Okay. So this would be represented like this. Um don't worry about it too much. So then is it snowing? Okay. Um I don't know. Okay. What if we say Alice is happy? Then is it snowing? You don't know or you don't know whether you know the answer is I don't know or you don't know it should be no okay so I'll let you kind of ponder on this in your maybe uh offline but this is example of performing inference in first logic and as you can see it's quite uh powerful. I gave you a lot of sentences with a lot of ands and ors and implications and um you know the question here is um you know what kind of sentences can first order logic represent and how can we do inference in them. Okay, so this is one example but for logic is going to be able to represent any sort of uh complicated statement about the world and also allow you to reason about this. And we also want it to be logically coherent. Okay, so this is sort of a tall order, right? Imagine like any sentence you u can you know write down we want to be able to do reasoning with it. I mean as it turns out that for logic isn't powerful enough to do all sentences but um it goes quite far as we'll see. All right so let me uh just review logic. So last time remember we talked about propositional logic. Um but more importantly I think it introduces the basic way you should think about logic which is a language for representing knowledge and reasoning with it. Okay. So to define a logic we need to define its syntax uh semantics and inference rules. So the picture you should have is that there's syntax LAN. These are just symbols and you can perform inference rules on these symbols. they generate more symbols. But what in order for these symbols to mean something, we have to define a mapping known as an interpretation function that takes formulas and says what statement do they make about the world. Okay. And later we saw a soundness and completeness which tells you how these inference rules relate to um the actual reality.

### [5:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=300s) Segment 2 (05:00 - 10:00)

Okay. So um maybe just go through the different concepts. So remember last time there are a lot of different concepts that build on top of each other. Um so the first is you know syntax what are the valid formulas and propositional logic. We started with the primitives which are propositional symbols like P or Q or rain or wet. Um then we can given these symbols we can recursively combine them using logical connectives like and or not implication and birectional implication. So we might build rain and not wet. Okay. So these are remember these are just symbols and in order to define uh say what the define the semantics we have to say what these formulas mean. Okay. So in propositional logic, a model is assignment of truth values to propositional symbols. So here's a possible model. Rain is true, wet is not true. And so a model also you can refer to it as a world is a possible situation that we might be in. It's raining but it's not wet. Okay, there are many models and in general the way to think about it is we don't know which exactly which world we live in. And by um and then a logic allows making formulas allows you to basically um express which are the pos constraints on the possible worlds. So we given models we have an interpretation function which takes a formula and a model and returns essentially whether this formula is satisfied by that model. In this case, this is true because the formula is rain and not wet and the model is rain um rain is true and wet is false. If you had the formula wet, the result would be uh false. If you had the formula rain, there would be true. Okay. So interpretation function in sense is a bridge between syntax and uh semantics and the way we use that is we define a set of models m of f which says given a formula what are the possible worlds that we might live in okay so in this case it's just the one possible world which train rain as true and wet as false then we talked about knowledge bases which is a set of formulas so you should have in their head. Over time, an agent acquires knowledge and it just adds formulas into this knowledge base. So, for example, it might know that it's raining. It might also have the general rule that whenever it's raining, it's wet. And then, um what you do is you have a new formula and you think about the relationship between the knowledge base and the new formula. So the two um things to keep in mind is that we have the original knowledge base that defines a set of models which is the intersection of all of the models of the formulas. So these are the possible states of the world that are consistent with all the knowledge. Um and then we look at what happens if we add f to the knowledge base. What models do we get? So, and based on the relationship between old models and new models, we there's three possibilities. One is that they're equal, and that's entailment. And this means that F did not add any more information over KB. And in this case, it is entailment. Um, you know, wet is entailed by uh rain and imply rain implies wet. Um it could be a contradiction meaning that there's no possible states of the world that uh no possible worlds that satisfy both the knowledge base and f and otherwise it's a contingency which is that the intersection is not empty and it's also not the original set. Okay. So these three notions are used to implement um ask function and a tell function. So ask checks whether um f uh is entailed or contingent or contradiction um with the knowledge base. So this is asking yes or no questions and tell is you're trying to add f to the knowledge base and you're only going to do it if it's contingent because it's not contradicting and it's also adding new information. Okay. Then we talked about how um we can

### [10:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=600s) Segment 3 (10:00 - 15:00)

so do inference by reducing everything to satisfiability. Right? So KB is satisfiable if um it's sort of self-consistent. So when you and model checking is the task of taking a knowledge base and determining whether it's satisfiable and given that's primitive we can reduce entailment contradiction contingency to two uh invocations of satisfiability right we add basically f into knowledge base see what happens if it's uh if it's you know not satisfiable then we say it's contradiction then we add not f into kb and see what happens If the in if m of that is empty then we say it's entailment otherwise it's a contingency. Okay. Finally we talked about inference rules um which is how do you derive new formulas given existing ones. Um the set of rules um remember operates on the syntax and we talked about the modus ponent which is this particular uh rule template. If you're given a propositional symbol P and you're given a formula um P implies Q then you get to derive um Q. Okay. So if it's a rain and rain implies wet then you can derive wet. So then there's two notions here in the syntax. You have a knowledge base. It's a set of formulas and you can do these uh apply these rules over and over again and if you can generate a particular formula then you say the knowledge base derives or proves that formula. Over in semantics land you say that knowledge base entails f and this is just by definition whether the models that are denoted by the knowledge base is equal to the modal with f. Okay, so these at the surface are very different notions, right? It's not even clear what these have to do with each other. And so um the relationship is given by these two properties. Soundness is the property that if the knowledge base uh can derive a set of rules can be used to derive f given a knowledge base then uh f is entailed by the knowledge base. So remember the glass. Glass is the truth. And um soundness means that you're staying within the glass. If every time you um you add some water, it stays within the glass. It's true. And completeness is um saying that whenever you're filling up the glass, so whenever a formula is entailed, you also can prove it. Okay. And ideally you want both. You want um uh soundness which is nothing but the truth and completeness which is the whole truth. Okay. So that's where we left off uh last time. So let's talk about why propositional logic isn't uh good enough. Um, and just to motivate this, let's just try to represent some facts in propositional logic. Um, so let's say we have a sentence, Alice and Bob both know arithmetic. So in propositional logic, remember all you have is propositional symbols. So you might define a propositional symbol. Alice knows arithmetic and Bob knows arithmetic. And you define a formula which is um and the and of the two. Okay, so you know it works. Um seems like okay fine it works. What if you have a sentence like you want to represent the fact that all students know arithmetic. Okay. So then um you might say okay Alice is a student uh Bob is a student um these are um these are symbols and then you define a formula which says and uh Alice is student implies Alice knows arithmetic and Bob is a student implies Bob knows arithmetic but the problem is that if you have more student if you have a thousand students then you have a very large uh formula. Okay. So um here's another example. Every even integer greater than two is a sum of two primes. You know this is code box conjecture and uh in order to express this you know now you have to wait a minute

### [15:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=900s) Segment 4 (15:00 - 20:00)

you have to list all possible integers uh and make them propositional symbols. This doesn't seem like a good uh way forward. So remember the goal of logic is you're representing very complicated things about the world in very compact ways and this is a property that's shared by natural language. Language is very powerful because I can say a few words and I can say very complicated things. Um so we see that propositional logic is very clunky and not expressive enough because all it has is these um these proposition no symbols. So what's missing? What's missing is that uh we'll see that there's notions of objects um and predicates, right? So Alice knows arithmetic is just one monolithic predicate which is either true or false, but it has more internal structure, right? There's Alice, there's no there's arithmetic. So we're going to try to break that apart. The other thing is it's missing quantifiers and variables. So all is known as a quantifier. Um and this applies to all people or objects. And there's cases where you can't just enumerate all the objects. Okay? In programming this is kind of like trying to program without for loops, right? You like have to write down all the different cases which clearly doesn't work. So we figured out in programming that you need to have more uh complex uh languages rather than just you know um I guess there's not really a language that doesn't have uh for loops that's uh people really use okay so let's introduce first order logic now okay so remember in order to introduce the logic we have to go through the syntax the semantics and the inference rules just like we did for propositional logic but now we're doing for first order logic So let's talk about the syntax. Okay, so syntax remember is what are the set of all valid formulas. Um there's going to be a bit more machinery here. In propositional logic, formulas denote truth values. So rain denotes either true or false depending on what uh what's happening in the world. In forced order logic, we still have formulas that denote truth values as before, but we also have these things called terms which denote objects. So what is a term? There's multiple types of terms. There's first constants terms. It's constant symbols like Alice or arithmetic. Um these are not to be confused with propositional symbols because proposition symbols are formulas. They represent um either true or false. Alice and arithmetic represent objects either concrete objects or abstract objects. Okay, Alice is not true or false. Okay, we also have variables um like x and y and then we have functions. So um a function is uh something that takes uh zero or one or more um you know arguments and returns a term. Okay. So we might have father that's a function add that takes an object and returns the object. Add is a function that takes two objects and returns object. So we might uh now we can use um functions um to build terms by passing in other terms as arguments. So father of Alice is a term and add XY is a term. Okay. So you can also have father of Alice or add XY and then you add Z. So you can imagine building this up recursively and in particular functions are take things that take uh terms and return you know terms and remember a term denotes an object. Okay. So again keep the object the terms and the formulas separate. All right. Um so now we get to formulas. in propositional logic, atomic formulas were just propositional symbols like rain or wet. And now atomic formulas are going to be a bit more complicated. They're going to be predicates applied to terms. So what are predicates? These are not functions but um well they are functions in a general sense but they are things that take some number of arguments and returns true or false. Okay so snowing is a zero error

### [20:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=1200s) Segment 5 (20:00 - 25:00)

predicate error means that it takes zero arguments and returns either true or false. It is either snowing or it's not snowing. Um, student is a one error predicate otherwise known as a unary predicate. It takes an object and returns a bool. Okay. And nose um is a two area predicate. So it takes two arguments and returns a bool. So for example, you might have a formula that says nos x arithmetic. Notice that X and arithmetic are terms. So predicates takes as argument terms, but it returns a boolean. Okay. So after you define these atomic formulas, you can apply uh connect them together using connectives. So this is this part is the same as propositional logic. For example, you can have uh um student of X implies X knows arithmetic. Okay, so that is a formula. And um finally, you have quantifiers that apply to formulas. So you can take a formula with a variable and you can put either for all x um in front of it or um exist x where x is some variable that shows up. Okay. So just to sanity check there are these are not formulas. So father of x is not a formula. It's a term right? You think about father is a person. is not a true or false. Uh student is no student arithmetic is not a formula or at least not a well- definfined formula because student is a predicate not a term. If I had student of X would that be a formula? The answer is no. Right? Because student of student is a um a predicate which returns a bool. So if I take a student of X that's a term uh sorry that's that just returns a pool and here anything that gets passed in needs to represent an object. Okay. Um and then this is also not uh kosher for similar reasons. So um if you had a function fu um you can't take nose alice and arithmetic because nose is uh is a predicate. So this returns bool um and you can't pass boolean into um into anything. Okay. So anything that shows up an argument has to be a term and the outermost function is for a formula has to return a pool. Okay to help you um remember so there's a convention that we've been following um so we're using lowercase for terms so which includes variables constants functions everything is lowercase and this represents denotes objects and we're using uppercase for formulas so nodes is a predicate so it returns a b okay so that's this is just a convention um I mean you technically name them anything you want. Okay, so just to sum summarize there's two things here. There's terms that denote objects. These are things like Alice arithmetic XY father of X add XY and then there's formulas which denote truth values. So for example for all X student X implies knows X arithmetic. Okay, so that's the syntax of first order logic. Uh any questions? So question is can a function return another function in first order logic? No, functions have to return uh terms. So yeah, so this is uh in some ways it's a much more restrictive language than if you're using Python which you can like have functions that return functions and um anything goes. Um first order logic is much more restricted which allows you to be able to compute efficient. the more restrictive language it's easier to do stuff with but less expressive. So can I explain no student arithmetic and why this is not a not formula. So student is a predicate right? So um and so it's not a term and only thing that can go here in here as a

### [25:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=1500s) Segment 6 (25:00 - 30:00)

term. Okay. So this is a common mistake because you say oh students know arithmetic then if I ask you to write down the first order logic for it the natural thing would be like oh you know well Alice knows arithmetic I just do knows Alice arithmetic if student knows arithmetic I just put student in but that's incorrect okay so that's the syntax of first order logic remember it's all logics Pro languages in general define recursively, right? So you define the atomic formulas and then you say how you take these atomic formulas and you produce more uh you know bigger formulas and the difference in for logic is the we have to introduce idea of terms and build terms um first get them into predicates and those are the um you know atomic formulas. All right. So now let's talk about the semantics of first order logic. So what do these formulas mean? And we're going to follow the same recipe as of propositional logic or at least try to. So in general remember that a model represents a possible uh world. So in propositional logic a model is assignment of truth values to atomic formulas. So um I might have if I had my um propositional way of representing things I have two um propositional symbols and this basically says this world or model says Alice knows arithmetic true Bob knows okay so that's propositional logic so what about in first order logic so any ideas how should I do this how do I just try to lift what I know about propositional logic and put into first order logic remember the general principle is a model is assign a truth values to atomic formulas okay so why don't I just try to do that so here's my first attempt so atomic formulas in first order logic are predic cuts apply to terms. So for example, nose Alice arithmetic is a formula atomic formula. Okay. And student Alice is also, you know, a formula. Okay. Atomic formula. So let's just define a model as assignment to truth values to these atomic formulas. So I have student Alice true knows Alice arithmetic true. Okay. So far so good. So what might be a problem with this? So how many uh atomic formulas are there? Probably uh a potentially a lot. Okay, let's figure out. So the problem is with functions. If you could actually this is fine if you didn't have uh mostly fine if you don't have functions. But if you have functions for example father is a function and remember a function takes a term denoting an object and returns another term denoting an object. So Alice is a term father Alice father father Alice and so on so forth. So there are infinite number of atomic formulas potentially if you allow for functions. So then a single model would have to have assignment of truth values to infinite number of atomic formulas and this clearly is no good. Okay. So there's also another problem which is that you could have two terms that actually might refer to the same object. For example, father of Alice is uh this is a term and Bob is a term. So these are both denoting objects. Um but it could be the case that Bob is Alice's father, right? U but if you just naively don't pay attention to any of that, you say you might have something like you know nos father says arithmetic is true but knows Bob arithmetic is false. So there's no way of assuming any sort of coherence between uh different atomic formulas with respect to what might uh connect the different terms. Right? So different terms might actually represent the same object. Okay? So we're going to try again here. And the key idea is we're going to introduce a layer of indirection. So

### [30:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=1800s) Segment 7 (30:00 - 35:00)

instead of just taking the symbols and mapping them true values um we're going to um define a set of objects explicitly. So a domain in logic is a set just a set of objects. So um I'm just going to represent them with arbitrary names like 01 023. Okay. So then I'm going to define this interpretation function that maps um these symbols such as Alice and arithmetic into these objects in the domain. So we start with a primitive symbols um constants functions and predicates. So each symbol is mapped to something that involves um the objects in the domain. So for the constants, so this is a particular um instantiation I might have say Alice gets assign 01, Bob gets assign O2, arithmetic gets assign 03. Okay. And then for functions, um I might have the father function which says if I pass in 01, I get O2. So note that I'm not referencing the constants. So the constants are in syntax land, right? So Alice Bob arithmetic and this maps them into a sort of a canonical object space and then the functions are just all going to take um elements in the object space in the domain. Um so this says O2 is a father of 01 and then predicates. So for every predicates I now I assign if nose takes in 01 03 I return true. If I take in O23 I return uh false for example and every other combination I guess I'll just assume is false. Okay. So, so student is a unary predicate. It takes in an object and for 01 it might return true. O2 and 03 are false. Okay. So, uh that is the interpretation you know function. So this interpretation along with um the domain is going to be my representation of um the a model in first order logic. So just to kind of recap before we were saying a model is just assignment of truth values to atomic formulas and those had two problems with it. the fact that there could be infinite also uh have you know two terms that reference the same object. Now what is a model in first order logic is this sort of a larger structure where I have my domain which is a set of 01 023 and then I have a mapping that specifies how the symbols should be interpreted in the domain. So I map the symbols and syntax into um 01, 02, 03 which are in semantics. — So the question is the mapping uh hardcoded? So I will say that this is uh just the way to think about this is a kind of mathematically uh a mathematical object. It's written in code um just to make it concrete u and formal. Um but this is not to say that you would actually instantiate um these models. Um sometimes you would um or more often you would like partially instantiate them um lazily. Right? So the question is uh if father Alice and Bob are the same term so why do they have different truth values? Um so this is I guess part of the point is that um this should not even potentially be let's say allowed in some sense but um you can write it down and is it represents a state of the world. Um so you could have in these inconsistencies. Okay. So a pictorial way to think about this is that you have a graph where objects in your domain are nodes and then um constant symbols um are basically labels or pointers onto nodes. So Alice points to 01 arithmetic

### [35:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=2100s) Segment 8 (35:00 - 40:00)

03 um Bob O2. Um I just added Robert just for fun to suggest that um there need not be a onetoone relationship between the objects and the constants. Um and then for the predicates student is a unary predicate. So you can attach unary predicates onto a subset of the nodes to say that it apply. And then you for binary predicates you can have edges um between uh pairs of um objects. So if you've interacted with or heard of knowledge graphs um knowledge graphs are basically these type of things that have some roots in uh first order logic. Okay. So now what we have so far we've defined what a model is. Okay just to be clear a model is has a domain and interpretation which specifies how to map uh symbols into elements of that domain. Okay. So now how do I define an interpretation of a formula? So remember in propositional logic the interpretation function um takes a formula and a world and maps um that to a truth value which means whether the formula is true or false in that world. Okay. So in first order logic we can do something similar. It's going to be um more complicated because there's more moving parts now, but it's again going to be this kind of recurrence that which I'll walk through which basically takes a formula and sort of breaks it down and recursively calls interpret. Okay, so this is the I function for first logic. I'm going to um Okay. Um, so I'm going to pass in a formula and a world. Um, and also there is a substitute uh this mapping from variable to object domain which I'll explain later. And so I'm calling this with f which is um this formula and w remember this actually is a nice view to say this is a possible world. Okay, it's a mapping from all these uh the symbols to O's. There could be other worlds out there um but this is the world that we're uh interpreting right now. Okay. So um there's a bunch of cases what happens if f is a quantifier what and that's a for all or if it there's exists um and then I look at the number of arguments uh whether it's zero or one or two so in this case um this is a binary predicate so there should be two arguments um and this is a binary predicate so um I have the predicate is knows arg one is Alice and arg two is arithmetic. Um and then what I do is um the predicate remember is just a symbol knows right. So I'm going to take that I'm going to um W which is the world and look at look up what this predicate means to get its value. So and the meaning of this predicate knows uh denotes this which is a mapping from you know objects to true or false. Okay. So now I recurse on arg one. Um so let's just do arg one. So arg one is Alice. So there's also another function called interpret term. So um Alice is a constant uh symbol. So I'm going to look up basically the constants and I say Alice is 01. Okay. So I got I'm going to return 01. So I also do the same thing with arg 2. So remember arg 2 was o arithmetic and I look up um arithmetic gives me 03. So the value is 03 and now I look at this predicate value and I pass in the value of arg1 and value of arg 2 and that gives me the result. So I look at 0103 true. So the result is true.

### [40:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=2400s) Segment 9 (40:00 - 45:00)

Okay. So the result here um is true. knows Alice arithmetic is true in this uh particular you know world. Okay. So the general recipe is you take your formula you break it down and once you recurse and get to the leaves you just look up um what the appropriate um items are in W. So similar to what we did in propositional logic but just there's a few more moving parts. Now, so um let me just quickly go through part of how would you do this? This is for all x nose x arithmetic. So um so here uh this is a universal quantifier. Um so what I'm going to do is we have this a variable. Um I've just kind of canonicalized this. Um so this variable what it I want to do is iterate over all possible um objects in the domain and sort of push put that object here and see if this holds and if it holds for all objects then it's true. Okay. So what I'm going to do here is for each object in the domain I'm going to um interpret the body of this which is the body is knows um the knows variable zero arithmetic and I'm passing in this um substitution. So I'm going to keep track of this assignment that says um variable uh is zero sorry is O. Okay. So if I go um recurse basically I am let's see um actually let me not recurse uh because that's going to take a while. So in the end here um I get false and why is this false? It's because um not all the objects know arithmetic. Right? Alice knows arithmetic, but 01 knows arithmetic and O2 um O2 knows actually here I've said O2 doesn't know arithmetic but um so that al already makes it uh false. Okay. So, so to summarize um the semantics in all logics are defined by this interpretation function. So in first order logic the model is a domain which is a set of objects and interpretation which maps all the symbols constants um you know predicates functions into objects in that domain and then we recursively interpret the formulas and um define the interpretation function recursively uh in terms of the structure of the formulas and terms. Okay, let me uh stop there and ask if there's any questions about uh the semantics of first order logic. So the question is why is and or all handled differently than any other predicate. So um if you look at the code here, if you're interpreting a not or let's say an and um this is looks like what we did in propositional logic where you if you have the and f is the and of g and h then you interpret g and you interpret h and you take the and right and your question is why is the binary predicate handled sort of differently than that? So remember a binary predicate is a atomic formula and um the arguments that binary predet are not formulas they're terms and so you evaluate the terms and the terms return not booleans but um but actual um objects and then the way you turn that into a boolean is you look up the actual you know the interpretation base interpretation uh under W um to see whether that pair gives you um uh

### [45:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=2700s) Segment 10 (45:00 - 50:00)

of true or false. Okay, so let's move on. Um so we've defined the syntax of first order logic, we've defined the semantics of first order logic. Um so now let's perform some logical inference. Um and remember logical inference um we motivated it with this like ask and tell um and that reduces to entailment contradiction contingency which reduces to satisfiability. So um here's one thing you could do. Um so suppose we have this knowledge base and we wanted to do inference in it. So we want to ask questions of this knowledge base or add new facts. One thing you could do is just try to reduce it to propositional logic because for propositional logic we know what to do, right? We could do model checking. Um so obviously we can't do this in general because for logic is more powerful. So you shouldn't be able to just always reduce it to propositional logic but you can in a very you know specific instance. um assume uh if you make two assumptions and the two assumptions are unique names and domain closure. Okay, so this has to do with the relationship between the objects and the constants. So unique name says that each constant maps each objects uh sorry this should say um each object corresponds to at most one constant. So for example in this case John and Bob are two constants that map to 01. So 01 does not have a unique name. So this is ruled out um under this assumption. And domain closure says that each object corresponds to at least one constant. So in this case O2 does not have a name or a label um which means that it's also um needs to be ruled out. Okay. So if you have do unique games and dopamine closure which basically means that there's a onetoone relationship between objects and the constants then what you can do is you propositionalize the knowledge base. In some sense, we already saw this where you basically say every atomic formula, you just remove the commas and the parentheses and the spaces and you just call that a you know the name of the um of the propositional symbol. So you have student Alice, student Bob knows Alice arithmetic knows Bob arithmetic and then you um write down your knowledge base um in terms of those things. So before u we have student Alice B student Bob those are going to be the same. Oh, well, not quite the same because uh now instead of having a predicate applied to a constant, we now have just a monoton monolithic propositional symbol and then for all um something gets converted to uh the conjunction and applied to everything where the variable um have been substituted out. So we have student and something that applies to Alice Bon. And if you have an exist that means that converts to an or where over all the different um instantiations of its uh body. Okay. So at this point you just have propositional logic and then you can use any inference technique you want from last time. So in this case first logic is uh in some sense just syntactic sugar for propositional logic. It's the same expressivity but it's just easier to read and write. Okay. So that's a kind of a basic uh you know case. That's an easy case. So now let's uh look at propositional logic in general. Okay. Um so you know recall that when we talk about inference rules um what we're saying is we have a set of rules that you pick up some formulas in the knowledge base. You match the rule to that formula and that allows you to derive or prove uh new formulas. So let's define the modus ponent inference rule which we did uh for propositional logic. Um and modus ponent assumes a special type of u formula and that's called a definite clause. So if you have a formula that looks like this for all x um one through xn

### [50:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=3000s) Segment 11 (50:00 - 55:00)

um a1 and all the way to a k implies b. So where x1 and x through xn are variables and a1 through a k and b are atomic formulas that's a definite clause. So an example of a definite clause might be this. So you have for all xyz and then you have the conjunction of a bunch of uh um atomic formulas uh takes xy and covers x yz um and implies another atomic formula um knows xz. Okay. So the interpretation of this is that uh if you have you know someone who takes someone X who takes a core uh let's say a class Y and that class covers a concept Z then X knows Z. So um these are not definite clauses. So anything essentially involving disjunction is not. So for like for example if you have student Alice or student Bob that's not allowed and there exists X uh and student and knows arithmetic. If there's a exist students that knows arithmetic that's also not allowed because remember exists is basically a compact representation of or and for all is a compact representative and. Okay. So let's now introduce modus ponents. It's going to work on definite clauses. So in order to define a rule, there's premises and then there's a conclusion. So the premises are I have a um a set of a you know formula and that look and then I have another um formula in the knowledge base that looks like this then I can conclude B. Okay. So this should be intuitive. It basically says if a1 through a k are true and it's also the fact that if I have a rule that says a1 and through a k implies b then I can derive uh b. So it looks like modus ponent the only difference is that we have this for all here over a bunch of variables. So let's u look at the concrete uh case here. So you have let's say Alice has taken 221 and 221 covers logic and then you have a rule this is sort of grand rule that says u whenever um x takes y and y covers z then x knows z. Okay. So intuitively given this knowledge base I should be able to infer that Alice knows logic right however I can't actually apply this rule and the reason is that this these rules are just remember everything is syntactic right so the rule is just going to do like equality check and it says okay well let's see a1 could be takes Alice 221 one. But then I look at this A1 and it says takes XY and these are not the same thing, right? So we can't apply the rule. So in some senses is like kind of it's kind of dumb, but that's the rules are just the rules. You just follow them. Okay. So what can we do here? So you can't apply the rule because the rule says that whenever you have anything that A1 there has to be the exact same string that goes there. So remember in propositional logic this was not a problem. If I have rain and rain implies wet, then I can you know match wet because these are exactly the same string, right? But if I have um you know takes Alice uh CS221 and then this says takes you know XY um and then bunch of stuff then these are not the same so I can't just uh conclude. So any ideas on what I should do here?

### [55:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=3300s) Segment 12 (55:00 - 60:00)

Yeah. So somehow I have to look at y and x right remember x and y are variables and what does for all mean? It really means that for any x and any y and any z this holds. So in particular it should hold of Alice and 221 right so in some sense I need to like convert set x equals alice and y equals 221 and then it'll work. So this rule really says I can set X YZ to anything I want. So it's really like a rule template. Okay. So what I'm going to do here is um introduce these notions of substitution and unification which will give us what we need. So substitution is I need a mechanism to operate do surgery on formulas. Okay. So uh I have a formula nose xy nose is a predicate x and y are variables and I have um a substitution that says x maps to alice and y maps to c221. Okay. And I want to substitute use the substitution apply it to this formula. Okay. So again I'm going to do this uh recursively. where I have um nose xy and applying the substitution. Um so I'm going to look at the f it has a number of arguments x and y. So two arguments I'm going to recursively call substitute and then I'm going to you know put it together. So I'm going to recurse on X. And so X is in this uh this mapping. So I'm going to that returns uh Alice. So I fetch Alice here. And then um same with Y. Y gets mapped to 221. And then um so now I have these new arguments. I apply uh the same function f. All is basically nose um to these new arguments and I get my fresh uh formula knows Alice 221. Okay. So this is a you know a function that basically um substitutes these whatever's on the right hand side uh with sorry whatever's on the left hand side with whatever's on the right hand side. Okay so um that worked and now let's try another one. So formula student X and knows XY I replace X with Alice, Y with Z and I get um and a student Alice knows Alice Z. So what can be on the right hand side can also be variables. It doesn't always have to be a constant. Okay. So I think it's should be straightforward. uh substitution takes a formula and just substitutes uh does a search and replace um recursively in that formula. Okay, so unification is basically generalized equality, right? So the problem with takes LS21 and takes XY is that uh they're not literally equal. So unification says, find me a substitution that makes the two terms equal. And if I can't find a substitution, then I'm going to just say that they're not equal. Okay? And of course, I can only substitute the thing on the left hand side of a substitution. They can only be variables, right? I can't replace Alice with Bob, right? I can replace X with anything I want. I can replace y with anything I want, but I can't replace Alice with something else. Okay, so um Unifi takes two formulas and empty substitution which it's going to build up and tries to make these the same thing. So um the recurses um and if at any point something like you can't replace nose with takes for example. So if they're not equal then we just you know return. And now I'm going to go through all the arguments and I'm going to unify X with Alice. Um you know that and then unify um you know Y with Bob and that returns

### [1:00:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=3600s) Segment 13 (60:00 - 65:00)

this substitution. X is Alice, Y is Bob. Okay. So, which means that if I applied um this substitution to both arguments, then the two should be identical. And indeed, if I replace X with Alice and Y with Bob, then these two are the same. Okay. So, here's another example. nose alice y unified with nose xz. So the result here is I replace x with alice and then y with z and then I ended up both things become nose uh z. And if I try to uh unify knows Alice Y with knows Bob Z, this fails and returns none because Alice and Bob are just cannot be unified. Okay, so now I have the tools of substitution unification and this is basically going to give me like generalized equality. So now I'm going to try again. Okay, here's modus ponent take two. So the rule says the premises are if I have a bunch of formulas, I'm going to use this prime um to distinguish from um the non-prime version. So these are different. Um so I have a1 prime through a1 a k prime and then I have this rule that says a1 through a k implies b. And then in order to apply the rule, I'm going to have to first unify um A1 prime through AK prime with the A1 and then uh the if I can unify things then I conclude um you know I don't conclude B uh but I um I can't conclude B because I need to take this um unifier theta and do the substitution to get B prime. Okay, so let's walk through an example to make this clear. So again I have this knowledge base takes Alice 221 covers logic and there's a general rule that if you uh take a class that covers something you know that so first of all I'm going to unify um the conjunction um up here which is um takes Alice 221 and 221 uh covers logic and I'm unifying it with takes xy and covers yz. So that gives me this uh substitution which says x needs to map to Alice, y to 221 and z to logic and then um I substitute nose xz with that same theta and I can conclude nose alice logic. Okay, so this version of modus ponents works because I can now bridge the gap between these general variables and these concrete instances. All right. So what's the complexity of this? So every time you apply modus ponent it produces an atomic uh formula for example nose alice logic. So if you don't have any functions then the total number of um atomic formulas you can produce is simply the number of constant symbols to the maximum predicate error. So if you have binary predicates like nose um Alice logic then that would be the number of constant symbols. Let's say you have 10 constant symbols and maximum RDS2 then that's 10 time different uh atomic formulas you can create but if you have functions then the complexity actually can become infinite. Um so you can have knows Alex Alice logic knows father father logic and so on right so there might not be an even n to um this and you can definitely imagine rules that can generate infinite formulas for example you have a rule that says um if x knows logic then the father of x knows logic okay so you can easily see how you can just you know kind of just keep on generating the these uh these add

### [1:05:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=3900s) Segment 14 (65:00 - 70:00)

infinite item. Okay. So um that's just how it is. Uh so what do we know about the properties of the sumotus ponents? The good news is that it's sound. So which remember that means if the knowledge base can derive or prove a formula so if you can apply modus ponent and that you get a formula then that formula is actually true then knowledge base entails f but it's not complete there are formulas where the knowledge base entails f but um but you can't prove it and a simple kind example of this is um you can't um derive things with you know disjunction in them. So you know you need to uh there's another rule called resolution which allows you to be complete for first logic but I'm not going to cover this. Um uh this was covered in previous uh you know lectures. Uh it's a little bit more complicated but um we're just going to skip it this time. Okay. So here is the summary. So modus ponent works on these definite clauses uh which have this sort of if then structure. So if rain then wet or if um you know city of X then place of X. The intuition behind these definite clauses is that there's no disjunction allowed. Um substitution um is you know search and replace on formula terms in a formula and unification finds a substitution that makes two terms equal. substitution and unification are required to um carry out um these rules and first order logic because you need to match variables with constants. Okay. So in the final part of the lecture um I want to talk about natural language to first order logic expression. So some of the assignment will um involve essentially translating natural language into first order logic expressions. Um first order logic as I've demonstrated hopefully with examples is a way is a very natural way of encoding the meaning of natural language um you know sentences. So we'll just go through some examples. So Alice and Bob both know arithmetic. So the way you would represent that is knows Alice arithmetic knows Bob and knows Bob arithmetic. All students know for all X students student of X implies knows X arithmetic some student knows arithmetic there exist X um such that student of X and knows X arithmetic. So I'll pause a bit um and point out that universal quantification for all is usually paired with an implication. Right? So usually if you see for all there's some something implies something else and existential quantification is usually paired with a conjunction. There exists X such that student and knows. Okay. So 99% of the time this is basically the rule you should follow. So if you see stuff like this it's probably wrong. So why is this wrong? For all x student of x and knows x arithmetic. What is this actually saying? That means says every object in your domain is both a student and knows arithmetic which is not what you want. Right? Well, you want to say if X is a student then student that X knows arithmetic. Likewise, if you see this, it's probably wrong. So, exist X student and X implies knows X arithmetic. What this is saying is that there exists some object X that is either not a student or knows arithmetic. So as long as you have a non- studentent this is you know true. So that's also not what we want. Okay. So just remember for all implication exists and you know you'll be fine. Okay. So here are some other examples. Uh there is some course that every

### [1:10:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=4200s) Segment 15 (70:00 - 75:00)

student has taken. Okay. So to translate that. Okay. So there exists an x um actually I have some course uh course should be in there. There exists an x such that for all y if y is a student it implies uh take yx. Okay. And um you know notice that there's an implication that's paired with the and um technically there should be like exist x course of x and this thing um so how about this gold blocks conjecture every even number is greater than two is a sum of two prime numbers. So this says for all x um even if x and greater than uh x is greater than 2 implies there exists y and z such that y a is prime and z is prime and when you add y and z that equals x. Okay. And finally this is uh the one that we kind of already saw. If a student takes a course and the course covers a concept and the student knows that concept. So for all XYZ if a student X student is a X is a student X takes Y is a course Y covers Z and uh Z is a concept then X knows Z. Okay. So, you know, this is something that um you know, might take a little bit of kind of practice just kind of reading uh natural language and understanding how you map to logic. Um it's not in some sense that different from you know translating informal natural language specifications into code. Um but it's just like a different language that you have to get used to. Um one thing to notice is um you know this is a definite clause. So modus ponent will give you something. Um these are not definite clauses because there's exist x here and then there's exist over here which make it more complicated. Okay. So um this is just a motivating example. I was I'll skip that since we already covered it in the beginning. You can go back to this example and uh kind of this is more examples of how you translate natural language into um uh to first order logic. Um okay so now let's summarize um so first order logic this is the topic of today it gives you a language that's more powerful than propositional logic in produce in particular it gives you notions of terms which denote objects it gives you functions which allows you to derive other fun objects from objects and you get predicates which takes objects and returns um you know booleans we then can define variables and quantifiers that operate over all the objects or so you can think about this as a for loop over objects and this is what gives us a power think about you know if you had a language without a for loop it would be very verbose um but you have a for loop you can write you know oneliners that do a lot of things so the semantics of first order logic um are given by the interpretation function that maps the symbols which are the constants the functions and the predicates to the objects in the domain. Um so then after we defined the uh the semantics of first order logic we said well if you have domain closure and unique names we can propositionalize and reduce the propositional logic. But if you um if you can't then um or if you have only definite clauses you can run modus ponent with substitution and unification. Okay. And if you want to have completeness and you can do resolution, but we're not going to talk about that. So the final thing is that our journey and logic ends here. Uh but if you're curious, there are other higher order logics that allow you to express more. So for example, think about how you will represent 70% of students uh know machine learning. Okay? Try to write that in first logic and you'll realize that wait, you can't actually do this. Um and therefore you need um some other higher order logics that allow you to essentially not only just quantify over individual elements existent for

### [1:15:00](https://www.youtube.com/watch?v=x9Mbqu06OVo&t=4500s) Segment 16 (75:00 - 75:00)

allow you quantify individual elements but this requires u knowing a you have a set and you want to operate on that set. So this kind of relates to the you know the functions of functions comment earlier. Okay. So that's it for logic. Um next time we're going to start thinking more broadly about AI. We're going to zoom out and talk about language models and um AI in society. That's going to be the last three lectures and then we'll uh the final lecture will um be more of like a kind of in fireside chat with you know some presentations.

---
*Источник: https://ekstraktznaniy.ru/video/20905*