Combining Rules and Ontologies Via Parametrized Logic Programs Ricardo Gonçalves NOVA LINCS Faculdade de Ciências e Tecnologia Universidade NOVA de Lisboa Abstract non-monotonic reasoning, without having to give up of the monotonic logic at hand. Parametrized logic programs are very expressive In recent years, there has been a considerable amount of logic programs that generalize normal logic pro- effort devoted to combining Description Logics (DLs) with grams under the stable model semantics, by allow- logic programming non-monotonic rules – see, e.g., related ing complex formulas of a parameter logic to ap- work in [Eiter et al., 2008; Motik and Rosati, 2010]. pear in the body and head of rules. In this paper we In this paper we explore precisely the use of description explore the use of description logics as parameter logics as parameter logics, and show the expressivity of the logics, and show the expressivity of this framework resulting framework for combining rules and ontologies. for combining rules and ontologies. Parametrized logic programs Introduction Parametrized logic programs are very expressive logic pro- Parametrized logic programming [Gonçalves and Alferes, grams that generalize normal logic programs under the sta- 2010] was introduced as an extension of answer set program- ble model semantics, by allowing complex formulas of a pa- ming [Gelfond and Lifschitz, 1988] with the motivation of rameter logic to appear in the body and head of rules. In providing a meaning to theories combining both logic pro- this section we introduce the syntax and semantics of normal gramming connectives with other logical connectives, and al- parametrized logic programs [Gonçalves and Alferes, 2010]. lowing complex formulas using these connectives to appear in the head and body of a rule. The main idea is to fix a mono- Language tonic logic L, called the parameter logic, and build up logic The syntax of a normal parametrized logic program has programs using formulas of L instead of just atoms. The ob- the same structure of that of a normal logic program. The tained parametrized logic programs have, therefore, the same only difference is that the atomic symbols of a normal structure of normal logic programs, being the only difference parametrized logic program are replaced by formulas of a pa- the fact that atomic symbols are replaced by formulas of L. rameter logic, which is restricted to be a monotonic logic. Let When applying this framework, the choice of the pa- us start by introducing the necessary concepts related with the rameter logic depends on the domain of the problem to notion of (monotonic) logic. be modeled. As examples, [Gonçalves and Alferes, 2010] shows how to obtain the answer-set semantics of logic pro- Definition 1 A (monotonic) logic is a pair L = hL, `L i grams with explicit negation, a paraconsistent version of it, where L is a set of formulas and `L is a Tarskian conse- and also the semantics of MKNF hybrid knowledge bases quence relation [Wójcicki, 1988] over L, i.e., satisfying the [Motik and Rosati, 2010], using an appropriate choice of following conditions, for every T ∪ Φ ∪ {ϕ} ⊆ L, the parameter logic. In [Gonçalves and Alferes, 2012] de- Reflexivity: if ϕ ∈ T then T `L ϕ; ontic logic programs are introduced using standard deontic logic [von Wright, 1951] as the parameter logic. Moreover, Cut: if T `L ϕ for all ϕ ∈ Φ, and Φ `L ψ then T `L ψ; in [Gonçalves and Alferes, 2013] the decidability and imple- Weakening: if T `L ϕ and T ⊆ Φ then Φ `L ϕ. mentation of parametrized logic was discussed. Parametrized logic programming can thus be seen as a When clear from the context we write ` instead of `L . framework which allows to add non-monotonic rule based Let T h(L) be the set of logical theories of L, i.e. the set of reasoning on top of an existing (monotonic) language. This subsets of L closed under the relation `L . One fundamental view is quite interesting, in particular in those cases where characteristic of the above definition of monotonic logic is we already have a monotonic logic to model a problem, but that it has as a consequence that, for every (monotonic) logic we are still lacking some conditional or non-monotonic rea- L, the tuple hT h(L), ⊆i is a complete lattice with smallest soning. In these situations, parametrized logic programming element the set T heo = ∅` of theorems of L and the greatest offers a modular framework for adding such conditional and element the set L of all formulas of L. Given a subset A of L we denote by A`L the smallest logical theory of L that Definition 4 An interpretation T satisfies a rule contains A. A`L is also called the logical theory generated by A in L. ϕ ← ψ1 , . . . , ψn , not δ1 , . . . , not δm In what follows we consider fixed a (monotonic) logic if ϕ ∈ T whenever ψi ∈ T for every i ∈ {1, . . . , n} and L = hL, `L i and call it the parameter logic. The formulas δj ∈/ T for every j ∈ {1, . . . , m}. of L are dubbed (parametrized) atoms and a (parametrized) literal is either a parametrized atom ϕ or its negation not ϕ, An interpretation is a model of logic program P if it sat- where as usual not denotes negation as failure. We dub de- isfies every rule of P. We denote by M odL (P ) the set of fault literal those of the form not ϕ. models of P . The ordering over interpretations is the usual one: If T1 Definition 2 A normal L parametrized logic program is a set and T2 are two interpretations then we say that T1 ≤ T2 if of rules T1 ⊆ T2 . Moreover, given such ordering, minimal and least ϕ ← ψ1 , . . . , ψn , not δ1 , . . . , not δm (1) interpretations may be defined in the usual way. As in the case of non parametrized programs, we start where ϕ, ψ1 , . . . , ψn , δ1 , . . . , δm ∈ L. by assigning semantics to definite parametrized programs. A definite L parametrized logic program is a set of rules Recall that the stable model of a definite logic program without negations as failure, i.e. of the form ϕ ← ψ1 , . . . , ψn is its least model. In order to generalize this definition to where ϕ, ψ1 , . . . , ψn ∈ L. the parametrized case we need to establish that the least parametrized model exists for every definite L parametrized logic program. As usual, the symbol ← represents rule implication, the symbol “,” represents conjunction and the symbol not repre- Theorem 1 Every definite L parametrized logic program has sents default negation. A rule as (1) has the usual reading that a least model. ϕ should hold whenever ψ1 , . . . , ψn hold and δ1 , . . . , δm are We denote by SPL the least model of a definite program P . not known to hold. If n = 0 and m = 0 then we just write It is important to note that Theorem 1 holds for every ϕ ←. choice of the parameter logic L. Given a rule r of the form (1), we define head(r) = ϕ, The stable model semantics of a normal L parametrized body + (r) = {ψ1 , . . . , ψn }, body − (r) = {δ1 , . . . , δm } and logic program is defined using a Gelfond-Lifschitz like oper- body(r) = body + (r) ∪ body − (r). Given a parametrized ator. logic program P we define f orm(P) to be the set of all formulas of theS parameter language L appearing in P, i.e., Definition 5 Let P be a normal L parametrized logic pro- f orm(P) = r∈P ({head(r)} ∪ body(r)). We also define gram and T an interpretation. The GL-transformation of P the set head(P) = {head(r) : r ∈ P}. modulo T is the program PT obtained from P by performing the following operations: Semantics • remove from P all rules which contain a literal not ϕ Given this general language of parametrized logic programs, such that T `L ϕ; we define its stable model semantics, as generalization of the • remove from the remaining rules all default literals. stable model semantics [Gelfond and Lifschitz, 1988] of nor- mal logic programs. Since PT is a definite L parametrized program, it has an In the traditional approach an interpretation is just a set unique least model J. We define Γ(T ) = J. of atoms. In a parametrized logic program, since we substi- Stable models of a parametrized logic program are then tute atoms by formulas of a parameter logic, the first idea is defined as fixed points of this Γ operator. to take sets of formulas of the parameter logic as interpreta- tions. The problem is that, contrary to the case of atoms, the Definition 6 An interpretation T of an L parametrized logic parametrized atoms are not independent of each other. This program P is a stable model of P iff Γ(T ) = T . A formula ϕ interdependence is governed by the consequence relation of is true under the stable model semantics, denoted by P SMS the parameter logic. For example, if we take classical propo- ϕ iff it belongs to all stable models of P. sitional logic (CPL) as the parameter logic, we have that if the An important feature of parametrized logic programming parametrized atom p ∧ q is true then so are the parametrized is that its stable model semantics is independent of the se- atoms p and q. If we take, for example, standard deontic logic mantics of the parameter logic, since the central concept is SDL [von Wright, 1951] as parameter, we have that, since the consequence relation of the parameter logic. O(p ∨ q), O(¬p) `SDL O(q), any SDL logical theory con- Let us now show an example of how parametrized logic taining both O(p ∨ q) and O(¬p) also contains O(q). programs can be used to combine a monotonic formalism To account for this interdependence, we use logical the- with a non-monotonic one. We choose three different logics ories (sets of formulas closed under the consequence of the over the same propositional language. logic) as the generalization of interpretations, thus capturing the above mentioned interdependence. Example 1 (Propositional logic programs) Let us now consider a full propositional language L built over a set Definition 3 A (parametrized) interpretation is a logical the- P of propositional symbols using the usual connectives ory of L. (¬, ∨, ∧, ⇒). Many consequence relations can be defined over this language. We present three interesting exam- ples: classical logic, Belnap’s paraconsistent logic and Table 1: Syntax and semantics of ALC. intuitionistic logic. Consider the following programs: Syntax Semantics  p ← ¬q atomic concept A ∈ NC AI ⊆ ∆ I P1 P2 { p ← ¬q ∨ q p←q atomic role R ∈ NR R I ⊆ ∆I × ∆I  r← individual a ∈ NI aI ∈ ∆I q← (  ¬p ←  P3 (q ∨ s) ⇒ p ← P4 top > ∆I r←p  (p ∨ q) ← r  s←q bottom ⊥ ∅ P5 { p ← not q, not ¬q P6 { p ← not (q ∨ ¬q) conjunction C uD C I ∩ DI disjunction C tD C I ∪ DI Let L = hL, `CP L i be Classical Propositional Logic (CPL) over the language L. Let us study the semantics of P1 . complement ¬C ∆I \ C I Note that every logical theory of CP L that does not contain existential ∃R.C {x ∈ ∆I | ∃y ∈ ∆I : neither p nor ¬p satisfies P1 . In particular, the set T aut of tautologies of CP L is a model of P1 . So, SPCP L = T aut. restriction (x, y) ∈ RI ∧ y ∈ C I } 1 This means that p, ¬p, q, ¬q ∈ CP L / SP1 . We also have that universal ∀R.C {x ∈ ∆I | ∀y ∈ ∆I : SPCP2 L = {p}` . So, in the case of P2 we have that p ∈ SPCP 2 L . restriction (x, y) ∈ RI ⇒ y ∈ C I } CP L CP L Also, we have that r ∈ SP3 and s ∈ SP4 . In the case of P5 its stable models are the theories of CP L concept inclusion CvD C I ⊆ DI that contain p and do not contain q and ¬q. Therefore, we can concept assertion C(a) aI ∈ C I conclude that p ∈ SPCP 5 L . In the case of P6 , since (p ∨ ¬p) ∈ T for every logical theory T of CP L we can conclude that role assertion R(a, b) (aI , bI ) ∈ RI the only stable model of P6 is the set T heo of theorems of CP L. Therefore p ∈ / SPCP 6 L . Consider now L = hL, `4 i the 4-valued Belnap paracon- part of Table 1 are axioms. A concept equivalence C ≡ D is sistent logic F our. Consider the program P4 . Contrarily to an abbreviation for C v D and D v C. Concept and role as- the case of CPL, in F our it is not the case that ¬p, (p ∨ q) `4 sertions are ABox axioms and all other axioms TBox axioms, q. Therefore we have that q, s ∈ / SPF4our . and an ontology is a finite set of axioms. Let now L = hL, `IP L i be the propositional intuitionistic The semantics of ALC is defined in terms of interpreta- logic IP L. It is well-known that q ∨ ¬q is not a theorem of tions I = (∆I , I ), which consist of a non-empty domain IP L. Therefore, considering program P2 we have SPIP2 L = ∆I and an interpretation function I . The latter is defined for (arbitrary) concepts, roles, and individuals as in Table 1. ∅`IP L . So, contrarily to the case of CP L, we have that p ∈ / Moreover, an interpretation I satisfies an axiom α, written SPIP2 L . Using the same idea for program P6 we can conclude, I |= α, if the corresponding condition in Table 1 holds. If I contrarily to the case of CP L, that p ∈ SPIP6 L . satisfies all axioms in an ontology O, then I is a model of O, written I |= O. If O has at least one model, then it is called Combining rules and ontologies consistent, otherwise inconsistent. Also, O entails axiom α, written O |= α, if every model of O satisfies α. In this section we discuss the use of description logics as Given the consequence relation of ALC we can now illus- parameter logic in the framework of parametrized logic pro- trate how ALC can be used as parameter logic. gramming. We will then illustrate the expressivity of the re- sulting framework to combine non-monotonic rules and on- Example 2 The following program (P1 ) is an adaptation of tologies. an example taken from [Motik and Rosati, 2007], which uses In what follows, and for simplicity, we use description MKNF knowledge bases to combine rules and ontologies. logic ALC [Schmidt-Schaubß and Smolka, 1991]. We start The scenario is about determining the car insurance premium by briefly recalling the syntax and semantics of ALC. For a based on various information about the driver. more general and thorough introduction to DLs we refer to N otM arried ≡ ¬M arried ← [Baader et al., 2010]. The language of ALC is defined over countably infinite sets of concept names NC , role names NR , N otM arried v HighRisk ← and individual names NI as shown in the upper part of Table 1. ∃Spouse.> v M arried ← Building on these, complex concepts are introduced in the middle part of Table 1, which, together with atomic concepts, N otM arried(x) ← p(x), not M arried(x) form the set of concepts. We conveniently denote individuals Discount(x) ← Spouse(x, y), p(x), p(y) by a and b, (atomic) roles by R and S, atomic concepts by A and B, and concepts by C and D. All expressions in the lower p(Jonh) ← Note that in parametrized logic programming the combi- In [Gonçalves and Alferes, 2010] the authors show how nation of an ontology with a rule system can be done in a parametrized logic programming can capture the semantics natural way, simply by adding the ontology elements as facts of MKNF hybrid knowledge bases [Motik and Rosati, 2010] of the rule system. As usual in logic programming, variables by an appropriate choice of the parameter logic. As future in rules stand for all their possible instantiations by individ- work we aim to study the relation between parametrized logic uals appearing in the program. programs and other frameworks for combining rules and on- Program P1 can be rewritten in order to remove its first tologies, e.g., the DL-programs of [Eiter et al., 2008]. rule, which is nothing but an artificial tool to overcome the impossibility of having complex DL formulas in the head of Aknowledgments MKNF rules (in this case, having the classical negation of Ricardo Gonçalves was supported by FCT under project an atom in a head). Moreover, we may also add bodies to ERRO (PTDC/EIA-CCO/121823/2010). the facts coming from the ontology. E.g. we can add a non- monotonic condition to the second statement of P1 above, to state that non married are only considered high-risk in non References exceptional periods, obtaining P2 : [Baader et al., 2010] Franz Baader, Diego Calvanese, Deb- ¬M arried v HighRisk ← not exceptionalP eriod orah L. McGuinness, Daniele Nardi, and Peter F. Patel- Schneider. The description logic handbook, theory, im- ∃Spouse.> v M arried ← plementation, and applications (2nd edition). Cambridge ¬M arried(x) ← p(x), not M arried(x) University Press, 2010. [Eiter et al., 2008] Thomas Eiter, Giovambattista Ianni, Discount(x) ← Spouse(x, y), p(x), p(y) Thomas Lukasiewicz, Roman Schindlauer, and Hans p(Jonh) ← Tompits. Combining answer set programming with description logics for the semantic web. Artif. Intell., Let us now study the stable model semantics of this pro- 172(12-13):1495–1539, 2008. gram. We should again stress that such stable model seman- tics does not depend on the semantics of ALC, but only on its [Gelfond and Lifschitz, 1988] Michael Gelfond and consequence relation. If I is a 2-valued interpretation such Vladimir Lifschitz. The stable model semantics for that I(M arried(Jonh)) = 1 then Γ(I) is the least model of logic programming. pages 1070–1080. MIT Press, 1988. the following program PI2 : [Gonçalves and Alferes, 2013] Ricardo Gonçalves and ¬M arried v HighRisk ← José Júlio Alferes. Decidability and implementation of parametrized logic programs. In Pedro Cabalar and ∃Spouse.> v M arried ← Tran Cao Son, editors, LPNMR, volume 8148 of LNCS, pages 361–373. Springer, 2013. Discount(x) ← Spouse(x, y), p(x), p(y) [Gonçalves and Alferes, 2010] R. Gonçalves and J. J. p(Jonh) ← Alferes. Parametrized logic programming. In T. Janhunen It is clear that the smallest model of PI2 does not con- and I. Niemelä, editors, JELIA, volume 6341 of LNCS, tain M arried(Jonh), and so, such interpretation I cannot pages 182–194. Springer, 2010. be a stable model. Therefore, every stable model must satisfy [Gonçalves and Alferes, 2012] Ricardo Gonçalves and ¬M arried(Jonh) and consequently HighRisk(Jonh). José Júlio Alferes. An embedding of input-output logic Consider now program P3 obtained by adding to P2 in deontic logic programs. In Thomas Ågotnes, Jan the following facts: p(Bill) ←, ∃Spouse.>(Bill) ←, Broersen, and Dag Elgesem, editors, DEON, volume 7393 and exceptionalP eriod ←. Note that, although ev- of LNCS, pages 61–75. Springer, 2012. ery stable model now contains ¬M arried(John), we [Motik and Rosati, 2007] Boris Motik and Riccardo Rosati. no longer conclude HighRisk(Jonh) since we have A faithful integration of description logics with logic pro- exceptionalP eriod. Every stable model of P3 contains gramming. In IJCAI, pages 477–482, 2007. M arried(Bill). So, the Stable Model Semantics of P3 does not entail ¬M arried(Bill) nor HighRisk(Bill). [Motik and Rosati, 2010] B. Motik and R. Rosati. Reconcil- Consider now program P4 obtained by adding to P2 the ing description logics and rules. J. ACM, 57(5), 2010. facts: Spouse(Bob, Ann) ←, p(Bob) ←, and p(Ann) ←. [Schmidt-Schaubß and Smolka, 1991] Manfred Schmidt- Every stable model of P4 contains Discount(Bob), and so it Schaubß and Gert Smolka. Attributive concept de- entails Discount(Bob). scriptions with complements. Artif. Intell., 48(1):1–26, 1991. Conclusions [von Wright, 1951] G. H. von Wright. Deontic logic. Mind, In this paper we have discussed the use of the frame- 60:1–15, 1951. work of parametrized logic programming for combining non- [Wójcicki, 1988] R. Wójcicki. Theory of Logical Calculi. monotonic rules and ontologies. This approach is quite ex- Synthese Library. Kluwer Academic Publishers, 1988. pressive since it allows complex DL axioms to appear both in the body and in the head of non-monotonic rules.