Xem mẫu

TLFeBOOK 5 Logic and Inference: Rules 5.1 Introduction From an abstract viewpoint, the subjects of the previous chapters were re-lated to the representation of knowledge: knowledge about the content of Web resources, and knowledge about the concepts of a domain of discourse and their relationships (ontology). Knowledge representation had been studied long before the emergence of the World Wide Web, in the area of artificial intelligence and, before that, in philosophy. In fact, it can be traced back to ancient Greece; Aristotle is consideredtobethefatheroflogic. Logicisstillthefoundationofknowledge representation, particularly in the form of predicate logic (also known as first-order logic). Here we list a few reasons for the popularity and importance of logic: • It provides a high-level language in which knowledge can be expressed in a transparent way. And it has a high expressive power. • It has a well-understood formal semantics, which assigns an unambigu-ous meaning to logical statements. • There is precise notion of logical consequence, which determines whether astatementfollowssemanticallyfromasetofotherstatements(premises). In fact, the primary original motivation of logic was the study of objective laws of logical consequence. • There exist proof systems that can automatically derive statements syn-tactically from a set of premises. • There exist proof systems for which semantic logical consequence coin-cides with syntactic derivation within the proof system. Proof systems TLFeBOOK TLFeBOOK 152 5 Logic and Inference: Rules should be sound (all derived statements follow semantically from the premises) and complete (all logical consequences of the premises can be derived in the proof system). • Predicate logic is unique in the sense that sound and complete proof sys-tems do exist. More expressive logics (higher-order logics) do not have such proof systems. • Because of the existence of proof systems, it is possible to trace the proof that leads to a logical consequence. In this sense, the logic can provide explanations for answers. The languages of RDF and OWL (Lite and DL) can be viewed as specializa-tions of predicate logic. The correspondence was illustrated by the axiomatic semantics in the form of logical axioms. Onejustificationfortheexistenceofsuchspecializedlanguagesisthatthey provide a syntax that fits well with the intended use (in our case, Web lan-guages based on tags). The other major justification is that they define rea-sonable subsets of logic. As mentioned in section 4.1, there is a trade-off between the expressive power and the computational complexity of certain logics: the more expressive the language, the less efficient (in the worst case) the corresponding proof systems. As we stated, OWL Lite and OWL DL cor-respond roughly to a description logic, a subset of predicate logic for which efficient proof systems exist. Another subset of predicate logic with efficient proof systems comprises the so-called rule systems (also known as Horn logic or definite logic programs) . A rule has the form A1,...An → B where Ai and B are atomic formulas. In fact, there are two intuitive ways of reading such a rule: 1. If A1,...,An are known to be true, then B is also true. Rules with this interpretation are referred to as deductive rules. 2. If the conditions A1,...,An are true, then carry out the action B. Rules with this interpretation are referred to as reactive rules. Both views have important applications. However, in this chapter we take the deductive approach. We study the language and possible queries that TLFeBOOK TLFeBOOK 5.1 Introduction 153 one can ask, as well as appropriate answers. Also we outline the working of a proof mechanism that can return such answers. It is interesting to note that description logics and Horn logic are orthogo-nal in the sense that neither of them is a subset of the other. For example, it is impossible to assert that persons who study and live in the same city are “home students” in OWL, whereas this can be done easily using rules: studies(X,Y ),lives(X,Z),loc(Y,U),loc(Z,U) → homeStudent(X) On the other hand, rules cannot assert the information that a person is either a man or a woman, whereas this information is easily expressed in OWL using disjoint union. Then we turn our attention to another kind of rules. We give a simple example. Suppose an online vendor wants to give a special discount if it is a customer’s birthday. An easy way to represent this application with rules is as follows: R1 : If birthday, then special discount. R2 : If not birthday, then not special discount. This solution works properly in case the birthday is known. But imagine a customer who refuses to provide his birthday because of privacy concerns. In such a case, the preceding rules cannot be applied because their premises are not known. To capture this situation we need to write something like R1 : If birthday, then special discount. R2 : If birthday is not known, then not special discount. However, the premise of rule R2 is not within the expressive power of predi-cate logic. Thus we need a new kind of rule system. We note that the solution with rules R1 and R2 works in case we have complete information about the situation (for example, either birthday or not birthday). The new kind of rule system will find application in cases where the available information is incomplete. Predicatelogicanditsspecialcasesaremonotonicinthefollowingsense: if a conclusion can be drawn, it remains valid even if new knowledge becomes available. But if rule R2 is applied to derive “not special discount,” then this conclusion may become invalid if the customer’s birthday becomes known at a later stage and it happens to coincide with the purchase date. Thus we talk of nonmonotonic rules to distinguish them from monotonic rules (which TLFeBOOK TLFeBOOK 154 5 Logic and Inference: Rules are a special case of predicate logic). In this chapter, we will discuss both monotonic and nonmonotonic rules. Our final concern will be the exchange of rules across different applica-tions. For example, an online store might wish to make its pricing, refund, and privacy policies, which are expressed using rules, accessible to intelli-gent agents. The Semantic Web approach is to express the knowledge in a machine-accessible way using one of the Web languages we have already discussed. In this chapter, we show how rules can be expressed in XML-like languages (“rule markup languages”). Some applications of rule systems are discussed in chapter 6. In this chapter we give an example using monotonic rules (a subset of predicate logic called Horn logic) in section 5.2. Sections 5.3 and 5.4 describe the syntax and semantics of Horn logic, and section 5.5 describes the syntax of nonmonotonic rules. Section 5.6 presents an example of nonmonotonic rules. Finally, sections 5.7 and 5.8 describe an XML-based representation of monotonic and non-monotonic rules. 5.2 Example of Monotonic Rules: Family Relationships Imagine a database of facts about some family relationships. Suppose that the database contains facts about the following base predicates: mother(X,Y ) father(X,Y ) male(X) female(X) X is the mother of Y X is the father of Y X is male X is female Then we can infer further relationships using appropriate rules. First, we can define a predicate parent: a parent is either a father or a mother. mother(X,Y ) → parent(X,Y ) father(X,Y ) → parent(X,Y ) Then we can define a brother to be a male person sharing a parent: male(X),parent(P,X),parent(P,Y ),notSame(X,Y ) → brother(X,Y ) TLFeBOOK TLFeBOOK 5.3 Monotonic Rules: Syntax 155 The predicate notSame denotes inequality; we assume that such facts are kept in a database. Of course, every practical logical system offers conve-nient ways of expressing equality and inequality, but we chose the abstract solution to keep the discussion general. Similarly, sister is defined as follows: female(X),parent(P,X),parent(P,Y ),notSame(X,Y ) → sister(X,Y ) An uncle is a brother of a parent: brother(X,P),parent(P,Y ) → uncle(X,Y ) A grandmother is the mother of a parent: mother(X,P),parent(P,Y ) → grandmother(X,Y ) An ancestor is either a parent or an ancestor of a parent: parent(X,Y ) → ancestor(X,Y ) ancestor(X,P),parent(P,Y ) → ancestor(X,Y ) 5.3 Monotonic Rules: Syntax Let us consider a simple rule stating that all loyal customers aged over 60 are entitled to a special discount: loyalCustomer(X),age(X) > 60 → discount(X) We distinguish some ingredients of rules: • variables, which are placeholders for values: X • constants, which denote fixed values: 60 • predicates, which relate objects: loyalCustomer, > • function symbols, which return a value for certain arguments: age TLFeBOOK ... - tailieumienphi.vn
nguon tai.lieu . vn