Lecture 11
Lecture 11
Copyright By PowCoder代写 加微信 powcoder
Logic and Inference: Rules
The contents are taken from “A Semantic Web Primer – MIT press”
The slides are prepared by Dr.
A Semantic Web Primer
A specific Semantic Web Layer Stack
A Semantic Web Primer
Logic and Rules
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.
The primary original motivation of logic was the study of objective laws of logical consequence.
A Semantic Web Primer
Logical consequence
A Semantic Web Primer
Logic and Rules
Popularity and importance of logic
It provides a high-level language in which knowledge can be expressed in a transparent way.
It has a high expressive power.
It has a well-understood formal semantics, which assigns an unambiguous meaning to logical statements.
There is a precise notion of logical consequence, which determines whether a statement follows semantically from a set of other statements (premises).
A Semantic Web Primer
Logic and Rules
Popularity and importance of logic
There exist proof systems that can automatically derive statements syntactically from a set of premises.
Predicate logic is unique in the sense that sound and complete proof systems 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.
A Semantic Web Primer
Logic and Rules
The languages of RDF and OWL2 profiles (other than OWL2 Full) can be viewed as specializations of predicate logic.
One justification for the existence of such specialized languages is that they provide a syntax that fits well with the intended use (web languages based on tags).
Major justification: they define reasonable subsets of logic. There is a trade-off between the expressive power and the computational complexity of logics: the more expressive the language, the less efficient the corresponding proof systems.
A Semantic Web Primer
Logic and Rules
Most OWL variants correspond 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 Semantic Web Primer
Logic and Rules
A rule has the form A1,…An →B where Ai and B are atomic formulas.
As a deductive rule: If A1 , . . . , An are known to be true, then B is also true.
As a reactive rule: If the conditions A1, . . . , An are true, then carry out the action B.
Both views have important applications. However, we take the deductive approach.
A Semantic Web Primer
Logic and Rules
Description logics and Horn logic are orthogonal; neither of them is a subset of the other.
It is impossible to define the class of happy spouses as those who are married to their best friend in description logics. But this piece of knowledge can easily be represented using rules:
married(X, Y ), bestF riend(X, Y ) → happySpouse(X)
A Semantic Web Primer
Logic and Rules
Rules cannot (in the general case) assert
(a) negation/complement of classes;
(b) disjunctive/union information (for instance, that a person is either a man or a woman);
(c) existential quantification (for instance, that all persons have a father).
In contrast, OWL is able to express the complement and union of classes and certain forms of existential quantification.
A Semantic Web Primer
Logic and Rules
Monotonic vs Nonmonotonic Rules
R1 : If birthday, then special discount.
R2 : If not birthday, then not special discount.
R1 : If birthday, then special discount.
R2′ : If birthday is not known, then not special discount.
The premise of rule R2′ is not within the expressive power of predicate logic.
A Semantic Web Primer
Rules on the Semantic Web
Rule Interchange Format (RIF)
A W3C working group has developed the Rule Interchange Format (RIF) standard.
While RDF and OWL are meant for directly represent knowledge, RIF was designed primarily for the exchange of rules across different applications.
Due to the underlying aim of serving as an interchange format among different rule systems, RIF combines many of their features, and is quite complex.
A Semantic Web Primer
Rules on the Semantic Web
Alternatives to RIF
Rules over RDF can be expressed in an elegant way using SPARQL constructs; e.g., SPIN
Those wishing to use rules in the presence of rich semantic structures can use SWRL, which couples OWL DL functionalities with certain types of rules.
Those who wish to model in terms of OWL but use rule technology for implementation purposes may use OWL2 RL.
A Semantic Web Primer
Example of Monotonic Rules
Family Relationships
A Semantic Web Primer
Example of Monotonic Rules
Family Relationships
A Semantic Web Primer
Is there any logical problem with the rules in previous slide?
A Semantic Web Primer
Example of Monotonic Rules
Family Relationships
A Semantic Web Primer
Monotonic Rules
Syntax: Rules
A Semantic Web Primer
loyal customers with ages over 60 are entitled to a special discount:
• variables, which are placeholders for values: X
• constants, which denote fixed values: 60
• predicates, which relate objects: loyalCustomer, >
• function symbols, which denote a value, when applied to certain arguments: age
Monotonic Rules
Syntax: Rules
A Semantic Web Primer
This rule is applied for any customer: if a customer happens to be loyal and over 60, then she gets the discount.
In other words, the variable X is implicitly universally quantified (using ∀X).
In general, all variables occurring in a rule are implicitly universally quantified.
Monotonic Rules
Syntax: Rules
A Semantic Web Primer
Monotonic Rules
Syntax: Facts
A Semantic Web Primer
A fact is an atomic formula, such as loyalCustomer(a345678), which says that the customer with ID a345678 is loyal.
The variables of a fact are implicitly universally quantified.
Monotonic Rules
Syntax: Logic Programs
A Semantic Web Primer
A logic program P is a finite set of facts and rules. Its predicate logic translation pl (P) is the set of all predicate logic interpretations of rules and facts in P .
Monotonic Rules
Syntax: Goals
A Semantic Web Primer
A goal denotes a query G asked to a logic program. It has the form B1,…,Bn →
If n = 0 we have the empty goal □.
Interpret goals in predicate logic:
Monotonic Rules
Syntax: Goals
A Semantic Web Primer
In logic programming we prove that a goal can be answered positively by negating the goal and proving that we get a contradiction using the logic program.
For example, given the logic program p(a) and the goal ¬∃X p(X ) we get a logical contradiction: the second formula says that no element has the property p, but the first formula says that the value of a does have the property p. Thus ∃Xp(X) follows from p(a).
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
One way of answering a query is to use the predicate logic interpretation of rules, facts, and queries, and to make use of the well-known semantics of predicate logic.
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
Given a logic program P and a query B1,…,Bn →
with the variables X1 , . . . , Xk , we answer positively if, and only if,
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
In other words, we give a positive answer if the predicate logic representation of the program P , together with the predicate logic interpretation of the query, is unsatisfiable (a contradiction).
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
Once the predicate logic interpretation of P is true, ∃X1 . . . ∃Xk (B1 ∧ . . . ∧ Bn) must be true, too.
That is, there are values for the variables X1 , . . . , Xk such that all atomic formulas Bi become true.
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
For example, suppose P is the program
p(X) → q(X)
Consider the query q(X) →
q(a) follows from pl(P ). Therefore, ∃X q(X) follows from pl(P ), thus pl(P )∪{¬∃Xq(X)} is unsatisfiable, and we give a positive answer.
But if we consider the query q(b) →
then we must give a negative answer because q(b) does not follow from pl(P ).
Rewrite (2) using disjunctive statements.
A Semantic Web Primer
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
The components of the logical language (signature) may have any meaning we like. A predicate logic model, A, assigns a certain meaning. In particular, it consists of
a domain dom(A), a nonempty set of objects about which the formulas make statements,
an element from the domain for each constant,
a concrete function on dom(A) for every function symbol,
a concrete relation on dom(A) for every predicate.
Monotonic Rules
Semantics: Predicate Logic Semantics
A Semantic Web Primer
When the symbol = is used to denote equality (i.e., its interpretation is fixed), we talk of Horn logic with equality.
The meanings of the logical connectives ¬, ∨, ∧, →, ∀, ∃ are defined according to their intuitive meaning: not, or, and, implies, for all, there is.
This way we define when a formula is true in a model A, denoted as A |= φ.
Monotonic Rules
Semantics: Ground and Parameterized Witnesses
A Semantic Web Primer
So far we have focused on yes/no answers to queries. However, such answers are not necessarily optimal.
Suppose that we have the fact p(a) and the query p(X) →
The answer yes is correct but not satisfactory.
Monotonic Rules
Semantics: Ground and Parameterized Witnesses
A Semantic Web Primer
It resembles the joke where you are asked, “Do you know what time it is?” and you look at your watch and answer “yes.”
Monotonic Rules
Semantics: Ground and Parameterized Witnesses
A Semantic Web Primer
In our example, the appropriate answer is a substitution
{X/a} which gives an instantiation for X, making the answer positive. The constant a is called a ground witness.
Given the facts p(a) and p(b), there are two ground witnesses to the same query: a and b. Or equivalently, we should return the substitutions: {X/a} {X/b}
Is that enough?
A Semantic Web Primer
Monotonic Rules
Semantics: Ground and Parameterized Witnesses
A Semantic Web Primer
While valuable, ground witnesses are not always the optimal answer.
Consider the logic program add(X,0,X), add(X, Y, Z) → add(X, s(Y ), s(Z)). s is defined as the “successor function,” which returns as value the value of its argument plus 1.
Monotonic Rules
Semantics: Ground and Parameterized Witnesses
A Semantic Web Primer
Monotonic Rules
Semantics: Ground and Parameterized Witnesses
A Semantic Web Primer
The parameterized witness Z = s8(X) is the most general way to witness the existential query
It represents the fact that add(X, s8(0), Z) is true whenever the value of Z equals the value of X plus 8.
The computation of most general witnesses is the primary aim of a proof system, called SLD resolution, beyond the scope of this subject.
OWL2 RL: Description Logic Meets Rules
Integration of Horn logic and description logics
Consider the intersection of both logics: the part of one language that can be translated in a semantics-preserving way to the other language, and vice versa.
OWL2 RL seeks to capture this fragment of OWL.
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
A triple of the form (a, P, b) in RDF can be expressed as a fact P(a,b)
An instance declaration of the form type(a, C), stating that a is an instance of class C, can be expressed as C (a)
C is a subclass of D: C(X) → D(X)
C is the domain of property P : P (X, Y ) → C(X)
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
equivalentClass(C, D):
C(X) → D(X)
D(X) → C(X)
A Semantic Web Primer
Horn logic for
P1 is a sub property of P2
equivalentProperty(C, D)
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
Transitivity of a property P is easily expressed as
P (X, Y ), P (Y, Z) → P (X, Z)
Intersection of classes C1 and C2 is a subclass of D:
C is a subclass of the intersection of D1 and D2:
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
Transitivity of a property P is easily expressed as
P (X, Y ), P (Y, Z) → P (X, Z)
Intersection of classes C1 and C2 is a subclass of D:
C1(X), C2(X) → D(X)
C is a subclass of the intersection of D1 and D2:
C(X) → D1(X)
C(X) → D2(X)
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
The union of C1 and C2 is a subclass of D
C is a subclass of the union of D1 and D2
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
The union of C1 and C2 is a subclass of D
C1(X) → D(X)
C2(X) → D(X)
C is a subclass of the union of D1 and D2
would require a disjunction in the head of the corresponding rule, which is not available in Horn logic.
A Semantic Web Primer
Can you think of any special cases where “C is a subclass of the union of D1 and D2” can be expressed in Horn logic?
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
:C rdfs:subClassOf [rdf:type owl:Restriction ; owl:onProperty:P ;
owl:allValuesFrom :D] .
C(X), P (X, Y ) → D(Y )
A Semantic Web Primer
OWL2 RL: Description Logic Meets Rules
[rdf:type owl:Restriction ; owl:onProperty 😛 ;
owl:someValuesFrom 😀 ] rdfs:subClassOf :C .
P (X, Y ), D(Y ) → C(X)
A Semantic Web Primer
A Semantic Web Primer
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com