In modal deontic logics, the focus is on inferring logical consequences, for example inferring whether or not an obligation O mail, to mail a letter, logically implies O [mail burn] ,an obligation to mail or burn the letter. Here I present an alternative approach in which obligations are sentences (such as mail) in first-order logic (FOL), and the focus is on satisfying those sentences by making them true in some best model of the world. To facilitate this task and to make it manageable in this alternative approach, models are defined by a logic program (LP) extended by means of action assumptions (A). The resulting combination of FOL, LP and A is a variant of abductive logic programming (ALP).
We will see that the models M0 and W can be defined constructively, by using a logic program P to define M0, and by using a set of candidate actions A to specify alternative ways of extending M0. We will also see that it is possible to satisfy goals without generating complete models, by using backward reasoning.
There can be many models that satisfy the same goal satisfaction problem, and some models may be better than others. Usual formulations of ALP ignore this fact, and are neutral with respect to the choice between different models satisfying the same goals. In contrast, in deontic logic, an agent is obliged to satisfy its goals in the best way possible.
To capture this normative character of deontic logic in FOL/ALP, we introduce a partial ordering between the models in W.
A normative goal satisfaction problem is a tuple G, M0, W, < where: < is a strict partial ordering over W, where M < M’ represents M’ being better than M.
MW satisfies a normative goal satisfaction problem G, M0, W, < if and only if
There is an obvious relationship with the possible world semantics of modal logics:
W is like a frame of possible worlds. The extension of M0 to M is like the
accessibility relation between possible worlds. The partial ordering < is like the
preference relation in preference-based deontic logics, such as those of [
However, whereas preference-based deontic logics build the preference relation into the semantics, complicating the logic, here the partial ordering is external to the logic, which is simply FOL. Moreover, while in modal logics, actions and events are normally represented by labels on the accessibility relation, here they are “reified”, as part of the record of a partial history of the world.
Deontic logic, the logic of obligation, contrasts with alethic logic, the logic of necessity. In alethic logic, a necessary truth cannot be falsified. But in deontic logic, an obligation is a normative ideal. If an obligation is violated, the world does not end, but the resulting world is less than ideal.
The focus on deriving logical consequences in modal logics makes it difficult to deal with violations, conflicting norms, and contrary-to-duty obligations. In contrast, the focus on goal satisfaction in FOL/ALP turns these problems into pragmatic choices between alternative models. Moreover, it makes it possible for an agent, aspiring towards the normative deal, to fall short, but nonetheless succeed in generating a best model possible with the limited resources available.
These definitions of goal satisfaction imply that, for an agent to satisfy its goals G, whether in some best way or not, the agent needs to search the space of alternative world histories W, to find some model M W of G. For this to be feasible in practice, the models M W must be constructible, and the space W itself must be searchable. This is where ALP comes in. Logic programs in ALP provide a constructive representation of models, and an efficient way to guarantee truth in a model without necessarily generating the model in its totality.
In our variant of ALP, the given model M0 is defined by a logic program P, and the space of candidate models MW is defined by logic programs P , where A and A is a set of ground atomic sentences representing candidate assumptions.
In ordinary abduction, the goals G represent observations, and A represents candidate, hypothetical external events that can be used to explain G. In default reasoning, A represents assumptions that conditions are normal, and G represents constraints that ensure conditions are not assumed to be normal if they are exceptional. In deontic applications, G represents obligations and prohibitions, and A represents candidate actions that can be used to satisfy G.
In the simplest case, a logic program is a set of definite clauses of the form
conclusion condition1 … conditionn, where conclusion and each conditioni
is an atomic formula. All variables are universally quantified with scope the entire
clause. Every such set of definite clauses P has a unique minimal model M [
In LP, it is convenient to represent models M as Herbrand interpretations, which are sets of atomic sentences representing all the atomic sentences that are true in M. A Herbrand interpretation M of a logic program P is then a minimal model of P if and only if M M’ for any other Herbrand model M’ of P. Minimal models can be constructed by forward reasoning: using modus ponens to exhaustively derive atomic sentences that are instances of the conclusions of clauses from atomic sentences that are instances of the conditions of clauses.
Forward reasoning can also be used to satisfy a goal: guessing a set of candidate assumptions A, adding them to P, generating the minimal model M of P , and then checking whether M is also a model of G. However, this kind of reasoning is not computationally feasible. It is not feasible to generate candidate blindly and independently of G; nor is it feasible to generate models in their totality.
In contrast, backward reasoning using SLD resolution [
In the following three, simple examples, the logic program P is either an empty set of clauses {} or a singleton set containing the clause X = X. Backward reasoning only identifies those assumptions/actions in A or those instances of X = X that are needed to satisfy the goal. Moreover, in the first two examples, the preference relation {} is empty. So all models are equally good.
The classic map colouring problem illustrates the use of FOL/ALP for goal satisfaction. However, it can also be formulated in deontic terms:
G = { X [country(X) C [colour(C) paint(X, C)]], X C1 C2 [paint(X, C1) paint(X, C2) C1 = C2], X Y C ¬ [adjacent(X, Y) paint(X, C) paint(Y, C)] } W = {M0 | A} where A = {paint(X, C) | country(X), colour(C)} < = {}. i.e. all models are equally good.
The initial model M0 is given by a logic program that specifies the countries, the colours, the adjacency relation, and the identity relation. For a simple problem with two adjacent countries and two colours, this is given by the program P and its minimal model M0:
P = {country(iz), country(oz), adjacent(iz, oz), colour(red), colour(blue), X = X} M0 ={country(iz), country(oz), adjacent(iz, oz), colour(red), colour(blue), iz = iz, oz = oz, red = red, blue = blue} Because the program P is so simple, the only difference between P and M0 is that P contains a general clause X = X, whereas M0 contains all variable free instances of the clause.
There are exactly two models that satisfy the goals G, and both are equal good: M1 = M0 { paint (iz, red), paint (oz, blue)} and
M2 = M0 { paint (iz, blue), paint (oz, red)} The map colouring problem can also be expressed in modal deontic logic, formalising the English statement of the problem. It would then be possible to infer the following logical consequence:
O [paint (iz, red) paint (oz, blue)] O [paint (iz, blue) paint (oz, red)] which describes all solutions of the problem. It is not obvious how to infer a single solution, which would be more useful in practice.
SDL (Standard Deontic Logic) is commonly used as a basis for comparison between different deontic logics. It is a propositional logic with a modal operator O representing obligation. Among the many problems of SDL, which also affects many other deontic logics, is Ross’s Paradox [12]. i.e.
O mail, mail mail burn.
As McNamara [11] puts it, “it seems rather odd to say that an obligation to mail the letter entails an obligation that can be fulfilled by burning the letter (something presumably forbidden), and one that would appear to be violated by not burning it if I don't mail the letter”.
The “Paradox” can be understood as another example of the inadequacy of logical consequence for dealing with problems of satisfying obligations. Here is a formulation of the paradox as a goal satisfaction problem G, M0, W, <: G = {mail, burn} M0 = {} W = {M0 | A} where A = {mail, burn}
= {{}, {mail}, {burn}, {mail, burn}} < = {}.
P = {} and M0 is the minimal model of P.
M = {mail} is the only minimal model that satisfies G. But mail burn is true in M. So satisfying G, entails satisfying mail burn. But, contrary to suggestions that may be associated with the fact that O [mail burn] is a logical consequence of O mail, satisfying the goal mail burn does not satisfy the goal mail.
Viewed in this way, Ross’s Paradox is not a paradox at all, but rather, as Fox [
Ross’s Paradox and the map colouring problem do not show the need for preferences
between alternative models. However, the need for preferences arises with
Chisholm’s Paradox [
Much of the discussion [
G = {go → tell, ¬go → ¬tell} M0 = {} W = {M0 | A} where A = {go, tell}
= {{}, {go}, {tell}, {go, tell}}
M < M’ if go M and go M’.
Here the “obligation” for Jones to go is represented by the preference for models in which go is true over models in which go is false. There are two models M1 = {} and M2 = {go, tell} that make G true. But M2 is better than M1. So only M2 satisfies G, M0, W, <. This means that Jones must go and tell.
Now suppose that Jones doesn’t go. We can represent this simply by removing go from the candidate actions A, updating the problem to G, M0, W’, < where W’ = {{}, {tell}}. The only (and best) candidate model that now satisfies the updated problem is the less than ideal model M1 = {}, which means that Jones must not tell, as is intuitively correct.
In a more realistic representation with explicit time, when we discover that Jones doesn’t go, we would update M0 to a new world history in which going is no longer an option. Notice that, in any case, whether we update M0, W or both, the solution of the updated problem changes, even though the goals remain the same. This gives the satisfiability problem for FOL a non-monotonic character, even though logical consequence itself is monotonic.
The logic and computer language LPS [
Computation in LPS generates a sequence M0 … Mi-1 Mi …. of partial histories, which in the limit determines a model M = M0 … Mi-1 Mi …. which makes all the goals true. Each history Mi is obtained from the previous history Mi-1 by updating Mi-1 with the set of all actions and external events that take place between Mi-1 and Mi. These updates are performed destructively, like change of state in the real world, and like destructive updates in imperative computer languages.
Computation in LPS gives rules both a logical and imperative interpretation. Whenever any instance of an antecedent of a rule becomes true in Mi, forward reasoning treats the corresponding instance of the consequent of the rule as a command to perform actions, to make the instance of the consequent true in some future Mj, j i+1.
Clauses conclusion conditions in LP also have both a logical and imperative interpretation. In addition to their purely logical interpretation, they have an imperative interpretation as procedures, which use backward reasoning to decompose a goal of determining whether a conclusion is true or of making a conclusion true to the subgoal of determining or making the conditions true. Conditions representing actions are made true by adding them to future histories Mj.
Preference between models in the current implementation can be indicated only by the order in which clauses are written. This gives preference to models generated by clauses written earlier over models generated by clauses written later. There is also an in-built preference for models that satisfy goals as soon as possible.
An online implementation of LPS is accessible from http://lps.doc.ic.ac.uk/. The LPS examples notebook in the examples menu contains executable links to the map colouring problem, and to several other examples having a deontic goal satisfaction interpretation. The first steps notebook goes through an example in which two agents have conflicting goals. Agent bob wants the light on whenever he is in a room, and agent dad wants the light off in any room where the light is on. It may be natural to think of bob’s goal as a personal goal, and dad’s goal as an obligation. But LPS makes no distinction between the two kinds of goals.
In this short paper, I have formulated deontic reasoning in ALP as goal satisfaction in FOL, with the A and LP components of ALP used to define the space of candidate models. I have argued that backward reasoning with LP overcomes the need to generate complete models, and makes it possible to avoid generating candidate actions blindly without relevance to the goals that need to be satisfied. I have also argued that, for philosophical applications, the focus on goal satisfaction in ALP is more useful than the focus on logical consequence in modal deontic logic. 11. McNamara, P. (2006) Deontic logic. Handbook of the History of Logic, 7, 197289. 12. Ross, A. (1941) Imperatives and Logic. Theoria, 7, 53–71. 13. Simon, H. (2001) Production systems. In The MIT encyclopedia of the cognitive sciences. MIT press. 14. van Benthem, J., Grossi, D. and Liu, F. (2014) Priority structures in deontic logic.
Theoria