6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright 2003 by Massachusetts Institute of Technology. 6.034 Notes: Section 7.1 Slide 7.1.1 Weve now spent a fair bit of time learning about the language of first-order logic and the mechanisms of automatic inference. And, weve also found that (a) it is quite difficult to write first-order logic and (b) quite expensive to do inference. Both of these conclusions are well justified. Therefore, you may be wondering why we spent the time on logic? We can motivate our study of logic in a variety of ways. For one, it is the intellectual foundation for all other ways of representing knowledge about the world. As we have already seen, the Web Consortium has adopted a logical language for its Semantic Web project. We also saw that airlines use a language not unlike FOL to describe fare restrictions. We will see later when we talk about natural language understanding that logic also plays a key role. There is another practical application of logic that is reasonably widespread namely logic programming. In this section, we will look briefly at logic programming. Later, when we study natural language understanding, we will build on these ideas. Slide 7.1.2 We have seen that the language of logic is extremely general, with much of the power of natural language. One of the key characteristics of logic, as opposed to programming languages but like natural languages, is that in logic you write down whats true about the world, without saying how to compute it. So, for example, one can characterize the relationship between parents and grandparents in this sentence without giving an algorithm for finding the grandparents from the grandchildren or a different algorithm for finding the grandchildren given the grandparents. Slide 7.1.3 However, this very power and lack of specificity about algorithms means that the general methods for performing computations on logical representations (for example, resolution refutation) are hopelessly inefficient for most practical problems. 6.034 Artificial Intelligence by T. Lozano-Perez and L. Kaelbling. Copyright 2003 by Massachusetts Institute of Technology. Slide 7.1.4 There are, however, approaches to regaining some of the efficiency while keeping much of the power of the representation. These approaches involve both limiting the language as well as simplifying the inference algorithms to make them more predictable. Similar ideas underlie both logic programming and rule-based systems. We will bias our presentation towards logic programming. Slide 7.1.5 In logic programming we will also use the clausal representation that we derived for resolution refutation. However, we will limit the type of clauses that we will consider to the class called Horn clauses. A clause is Horn if it has at most one positive literal. There are three cases of Horn clauses: A rule is a clause with one or more negative literals and exactly one positive literal. You can see that this is the clause form of an implication of the form P1 . Pn - Q, that is, the conjuction of the Ps implies Q. A fact is a clause with exactly one positive literal and no negative literals. We generally will distinguish the case of a ground fact, that is, a literal with no variables, from the general case of a literal with variables, which is more like an unconditional rule than what one would think of as a “fact“. In general, there is another case, known as a consistency constraint when the clause has no positive literals. We will not deal with these further, except for the special case of a conjunctive goal clause which will take this form (the negation of a conjuction of literals is a Horn clause with no positive literal). Slide 7.1.6 There are many notations that are in common use for Horn clauses. We could write them in standard logical notation, either as clauses, or as implications. In rule-based systems, one usually has some form of equivalent “If-Then“ syntax for the rules. In Prolog, which is the most popular logic programming language, the clauses are written as a sort of reverse implication with the “:-“ instead of “ GP(x,z)Our rule is simply the clause form of this FOL statement. In our rule language, we will modify our notational conventions for FOL. Instead of identifying constants by prefixing them with $, we will indicate variables by prefixing them with ?. The rationale for this is that in our logic examples we had lots more variables than constants, but that will be different in many of our logic-programming examples. The next two rules specify that a Father is a Parent and a Mother is a parent. In usual FOL notation, these would be: x . y. F(x,y) - P(x,y)x . y. M(x,y) - P(x,y)Slide 7.1.16 Now, we set out to find the Grandparent of C. With resolution refutation, we would set out to derive a contradiction from the negation of the goal: g . GP(g,C)whose clause form is GP(g,C). T