In this paper we define a class of nested logic programs, nested logic programs with ordered disjunction (LP ODs+), which allows to specify qualitative preferences by means of nested preference expressions. For doing this we extend the syntax of logic programs with ordered disjunction (LPODs) to capture more general expressions. We define the LP ODs+ semantics in a simple way and we extend most of the results of logic programs with ordered disjunction showing how our approach effectively is a proper generalisation of LPODs.
Logic programs with ordered disjunction (LPODs) [
The syntax of an LPOD allows the writing of rules of the kind A1 ×. . .×Ak ←
B1, . . . , Bm, not Bm+1, . . . , not Bm+n, where each of the Ai (with 1 ≤ i ≤ k)
and Bj ’s (with 1 ≤ j ≤ m + n) are literals (elementary formulas), to express
context-dependent preferences. Hence, they can encode simple preferences such
as: In the night I prefer going to a pub over going to a cinema over watching
tv (encoded as pub × cinema × tv ← night [
However, they may exist more complex preference statements that neither LPODs nor DLPODs are able to express. For instance, in the night preferences above, we can be instead concerned of having both options at the same time, expressing that in case pub is not possible we do mind watching a movie in the cinema and not in the tv, i.e. expressions such as pub × (cinema ∧ ¬tv) ← night, or that we even want to have equality and indifferences at the same time, i.e. expressions such as (pub ∨ bar) × (cinema ∧ ¬tv) ← night, or even more complex preference expression such as (pub ∧ (expensive × cheap)) × bar × (not pub ∧ not bar) ← night ∨ (not busy ∧ af ternoon). These examples suggest to explore for a less restricted syntax language.
For this reason, in this paper we present a more general syntax which allows the writing of nested (or non-flat) preferences expressions built by means of connectives {∨, ∧, ¬, not, ×}. To represent these formulas and to capture their semantics we define an extension of logic programs with ordered disjunction called nested logic programs with ordered disjunction (LP ODs+).
The syntax of LP ODs+ is based on a language which allows nested formulas
that can provide a richer syntax at the moment of writing conditional
preferences. The language we use is constructed using as a basis the propositional
language of Qualitative Choice Logic [
To define the semantics of our LP ODs+ we consider and extend some of the
results in [
In the presence of nested expression in the head of preference rules, the
determination of the degree of satisfaction of an answer set of an LP OD+ can be
sometimes more involved in our approach. For this reason we propose a recursive
function to calculate the optionality of complex preference formulas in order to
determine the rule satisfaction degree. The optionality function is a
generalisation of the rule satisfaction degree in LPODs, as a consequence, we can directly
use the preference relations in [
Our paper is structured as follows: after introducing the language we adopt to define our logic programs (Section 2), in Section 3 we present the syntax and the semantics of LP ODs+, and the optionality function for answer sets selection. Finally Section 4 provides some prelimary discussions about related works, LP OD+ complexity and sketches an implementation design of an LP OD+ solver. Along the paper we present a running example which exemplifies the definitions of our approach. Due to space reasons we are not able to provide an extensive comparison with related approaches and we leave proofs’ results out of the paper. It is our intention to cover these missings in an extended version. 2
The language we will consider to define the syntax of our logic programs is based on the language of Qualitative Choice Logic (QCL) extended with negation as failure not.
QCL is a propositional logic for representing alternatives for problem
solutions defined by Brewka et al. in [
The language we consider consists with: (i) an enumerable set L of elements called atoms (denoted a, b, c, . . .), (ii) connectives ∧, ∨, ×, ¬, not, ⊥, > where {∧, ∨, ×}, {not, ¬}, {>,⊥} are 2-place, 1-place and 0-place connectives respectively and (iii) auxiliary symbols ”(”, ”)”, ”.”. If an atom a is negated by ¬ is known as negative literal, and a is known as positive literal if it is not preceded by ¬.
Literals, ⊥ and > are considered elementary formulas, while formulas (denoted A, B, C) are constructed from elementary formula using the connectives {∨, ∧, ¬, not, ×} arbitrarily nested.2
A theory is a set of formulas and a logic program corresponds to a finite theory, i.e. a finite set of formula.
Based on this language we will define in Section 3 the syntax of nested logic programs with ordered disjunction. In the tradition of logic programming we write conditional expressions as the formula B ← A. We will consider two types of negation in our logic programs: strong negation ¬ and negation as failure not. Intuitively not a is true whenever there is no reason to believe a, whereas ¬a requires a proof of the negated atom. In this paper we assume that L is a finite set and we restrict our attention to finite propositional theories, since the semantics can be extended to programs with variables by grounding. Function symbols are, however, not allowed to ensure the ground program to be finite. This is a standard procedure in ASP. 3
LP ODs+
This section presents the syntax of nested logic programs with ordered
disjunction (LP OD+) and their semantics which is characterised in terms of a recursive
1 The original connective is denoted by −→×, however we write × for consistent notation
with ordered disjunction used in Answer Set Programming [
Earlier in the paper we have pointed out how the syntax of existent logic programming approaches able to express qualitative preferences is usually quite restricted and for this reason we define a more expressive syntax.
Let L be a set of atoms, then a nested ordered disjunction rule (rule for short) is an expression of the form H ← B., where H is either an elementary formula or a {∨, ∧, ¬, not, ×} formula (known as the head) and B is either an elementary formula or a {∨, ∧, ¬, not} formula (known as the body) built using the atoms in L. Some particular cases are facts, of the form H ← > (written as H) and constraints, ⊥ ← B (written as ← B.). If no occurrences of not appear in a rule, the rule is a definite nested ordered disjunction rule (similarly a definite nested ordered disjunction formula). If no occurrences of × appear in a rule, the rule is a nested rule (similarly a nested formula). If no occurrences of × and not appear in a rule, then the rule is known as a definite nested rule (similarly a definite nested formula). Different formulas combinations can lead to different rules (some of them already defined in the literature) as shown in Table 1.
A nested logic program with ordered disjunction (LP OD+) is a finite set of nested ordered disjunction rules and/or constraints and/or facts. If the program does not contain not the program is called a definite LP OD+. The set of all the atoms which appear in an LP OD+ P is denoted by LP .
In our logic programs we will manage the strong negation ¬ as it is done in
ASP [
The use of {∨, ∧, ¬, not, ×} formulas in the head of nested ordered
disjunction rules, rather than elementary formulas or disjunctive formulas only (as in
[
Example 1. Let P be an LP OD+ representing the user preferences of the form: r1 = italian × peruvian × (not italian ∧ not peruvian) . r2 = (pub ∨ bar) × (cinema ∧ ¬tv) ← night. r3 = night.
Briefly, the intuitive reading of each of the rules of the program P is the following: r1 expresses that we generally prefer to have italian over peruvian food and we prefer to have one of the options over not having any of them; r2 tells that in the night we prefer to go to a pub or a bar, but if it not possible then we wish to see a movie in the cinema and not in the tv and r3 just tells that we imperatively want to do something in the night time.
In the next section we define the semantics for inferring the answer set of an LP OD+. 3.2
Keeping in mind that the definition of answer sets semantics [
Definition 1. [
Definition 3. [
Definition 4. The reduct of a nested ordered disjunction formula with respect a set of atoms M is defined recursively as follows: – for elementary A, AM = A – (A ∧ B)M = AM ∧ BM – (A ∨ B)M = AM ∨ BM – (not A)M (⊥, if M |= AM >, otherwise AM , if M |= AM – (A × B)M BM , if M 6|= AM ∧ M |= BM ⊥,
otherwise Definition 5. The reduct P M+ of a nested logic program with ordered disjunction with respect to a set of a×toms M is defined recursively as follows: – (H ← B)M = HM ← BM – P×M+ = {(H ← B)M | H ← B ∈ P } Please notice that P M+ is a definite nested logic program, i.e. × and not free.
× Hence, the following definition follows in a straightforward way from the answer set definition for definite nested logic programs.
Definition 6. Let P be an LP OD+ and M a set of atoms. M is answer set of P if it is an answer set of P M+ .
× Example 2. Let us consider the LP OD+ P in Example 13 and the set of atoms M = {b, d, g}. Then P {b+,d,g} can be obtained in three recursive steps applying Definition 4 and 5: ×
(1) (2) (3) (a × b × (not a ∧ not b)){b,d,g}. b{b,d,g}. b. (c ∨ d) × (e ∧ f 0) ← g){b,d,g}. (c ∨ d){b,d,g} ← g{b,d,g}. c ∨ d ← g. (g){b,d,g}.
g. g.
(← f ∧ f 0.){b,d,g}. ← f {b,d,g} ∧ f 0{b,d,g}. ← f ∧ f 0.
Clearly, M is an answer set of P {b,d,g} and so M is an answer set of P . Similarly, + it can be proved that the sets o×f atoms {a, c, g}, {a, d, g}, {a, e, f 0, g}, {b, c, g}, {b, e, f 0, g}, {c, g}, {d, g} and {e, f 0, g} are valid answer sets of P as well.
It can be noticed that there is an interesting property of our LP OD+
semantics. Besides the fact that LP OD+ has a richer syntax they show to have a richer
semantics as well. When all the rules of an LP OD+ P are ordered disjunction
rules (according to the syntax of LPODs in [
Proposition 1. Let P be an LP OD+ such that ∀r ∈ P , r = A1 × . . . × Ak ←
B1, . . . , Bm, not Bm+1, . . . , not Bm+n each Ai (with 1 ≤ i ≤ k) and Bj ’a (with
1 ≤ j ≤ m + n) are literals (or elementary formulas), and M be a set of atoms.
M is answer set of P M+ if and only if M is answer set of P M .4
× ×
3 Due to representation issues we have changed the signature of the program from
{italian, peruvian, pub, bar, cinema, tv, tv0night} to {a, b, c, d, e, f, f 0g} respectively.
4 The P×M reduction is defined as Sr∈P r×M , where r×M := {Ai ← B1, . . . , Bm|Ai ∈
M and M ∩ ({A1, . . . , Ai−1} ∪ {Bm+1, . . . , Bm+n}) = ∅} (see [
Another interesting property is that when the formulas in our LP ODs+
are formulas without the × connective, then the LP ODs+ semantics and the
semantics for nested logic programs defined in [
Proposition 2. Let P be an LP OD+ such that ∀r ∈ P , r = H ← B, H and B are well-formed formulas × free, and M be a set of atoms. M is answer set of P M+ if and only if M is answer set of ΠM .5
× 3.3
At the beginning of the paper we have pointed out how an LP OD+ is a
specification to express preferences about certain conditions inducing a preference
order among its answer sets. Thus, the key question now is how such ordering
can be achieved. In the simplest case where each rule of an LP OD+ corresponds
to an ordered disjunction rule, a satisfaction degree k (with 1 ≤ i ≤ k) can be
associated to an answer set M w.r.t. a rule (degM (r)) which corresponds to the
position of the best satisfied literal [
However, when we consider a nested ordered disjunction rule r = H × B where H and B can be formulas built from {∨, ∧, ¬, not, ×} and {∨, ∧, ¬, not} respectively, the assignation of a satisfaction degree is not so trivial. Let us assume in fact that M is an answer set of an LP OD+ P . How is possible to determine the satisfaction degree of M w.r.t. each rule r in P ? This degree may depend on how many options H admits. For this reason we first define the optionality of an answer set M w.r.t. a nested ordered disjunction formula H as follows: Definition 7. Let H be a {∨, ∧, ¬, not, ×} formula, and M be an answer set of an LP OD+ P . Then the optionality of M w.r.t. H, denoted by optM (H) is recursively defined as follows: optM (H) 1, if H = A and A is an elementary formula iiff HH == ((nPo∧tPQ)) tthheenn kk == omptaMx{(Pop)tM (P ), optM (Q)} k iiff HH == ((PP ∨× QQ)) tthheenn k(=kk m==aooxpp{ttMMop((tPPM))(,+Pi)fo,pMotpMt|M=(Q(PQ),M)}otherwise Based on this function, the satisfaction degree of an answer set M w.r.t. a nested ordered disjunction rule r = H ← B can be defined as: Definition 8. Let M be an answer set of an LP OD+ P . Then the satisfaction degree M w.r.t. a rule r = H ← B, denoted by degM+ (r) is: degM+ (r) (1,
if M 6|= BM
optM (H), otherwise
5 The ΠM reduction is defined as the P M+ without the × case (see [
×
The degrees can be viewed as penalties, in fact a higher degree expresses a
lesser satisfaction. Thus, if the body of a rule is not satisfied, then there is no
reason to be dissatisfied and the best possible degree 1 is obtained [
We can observe that there is a direct property w.r.t. the optionality function we defined for the answer sets of an LP OD+. The optionality function clearly generalises the satisfaction degree of answer sets of an LPOD.
Proposition 3. Let P be an LP OD+ such that ∀r ∈ P , r = A1 × . . . × Ak ← B1, . . . , Bm, not Bm+1, . . . , not Bm+n each Ai (with 1 ≤ i ≤ k) and Bj ’s (with 1 ≤ j ≤ m + n) are literals (or elementary formulas), and M be an answer set of P . Then degM+ (r) = degM (r).6
Therefore our approach also generalises in a consistent way the preference relation between answer sets of LPODs.
Definition 9. [
optM1 ((c ∨ d) × (e ∧ f 0)) = 1 optM1 (a × b) = 1 optM1 (a) 1 optM1 (c ∨ b) = 1 1
The case of M2 looks more interesting as it shows how determining the
degree of satisfaction can be sometimes more involved. As M2 satisfies only the
third condition in the head of rule r1, its optionality w.r.t. this rule has to take
into account that the first two conditions are not satisfied, i.e. degM+2 (r1) = 2
+ optM1 (not a ∧ not b). As shown below the degrees of M2 w.r.t. r1 and r2
correspond to degM+2 (r1) = 3 and degM+2 (r2) = 2 respectively since:
6 We refer to [
optM2 (a × b × (not a ∧ not b)) = 3 optM2 ((c ∨ d) × (e ∧ f 0)) = 2 optM2 (a × b) = 2 . . . (not a ∧ not b) = 1 . . . (c ∨ d) = 1 optM2 (e ∧ f 0) = 1 optM1 (a) optM2 (b) . . . (not a) . . . (not b) 1 1
The simplest case of r3 is not represented as r3 is clearly satisfied by degree 1 by both answer sets. Once the degrees are calculated the preference relation can be used to compare M1 and M2. It is easy to see how M1 is preferred to M2 since M1 satisfies the rules of the program in a better way (M2 ≯ M1 from Definition 9 as well). 4
Conclusions, Discussions and Future Research
The main scope of this paper has been to define the syntax and the semantics
for nested logic programs with ordered disjunction. The syntax of an LP OD+
is based on well-formed formulas built from connectives {∨, ∧, ¬, not} plus an
ordered disjunction connective × which was first introduced in QCL and then
used in logic programs with ordered disjunction. As a result, rules in LP ODs+
are more general than rules which can be specified in related approaches of
qualitative context-dependent preferences between literals such as LPODs [
We have shown how the LP OD+ semantics can be defined in a lighter way
(Definition 4, 5 and 6) than then LPODs semantics (which is based on split
programs [
As far the complexity of reasoning is concerned, we have reasons to believe
that the complexity of computing the answer sets of an LP OD+ corresponds to
the complexity of disjunctive logic programs. This can be informally motivated
by the fact that by means of a transformation, we are currently investigating,
which is able to convert nested ordered disjunction rules to × free ones (i.e.
nested rules), we can reuse the polynomial translation for nested logic programs
into disjunctive ones presented by Sarsakov et al. in [
Beside these extensions, as future work we are considering to extend the
LP OD+ formalism to be able to reason under incomplete evidence and
partially inconsistent knowledge associating to each rule of an LP OD+ a certainty
degree following the same spirit as in our framework of logic programs with
possibilistic ordered disjunction (LPPODs) we presented in [
Acknowledgements The authors would like to thank the anonymous referees for their useful suggestions and comments. This research has been partially supported by ICT-ALIVE (FP7-215890). 7 http://www.cs.uni-potsdam.de/~torsten/nlp/ 8 http://www.dbai.tuwien.ac.at/proj/dlv/