How to build a deontic action logic Piotr Kulicki Robert Trypuz ∗ Abstract The aim of the paper is to point out the modelling choices that lead to different systems of deontic action logic. A kind of a roadmap is presented. On the one hand it can help the reader to find the deontic logic appropriate for an intended application relying on the information considering the way in which a deontic logic represents actions and how it characterises deontic properties in relation to (the representation of) actions. On the other hand it is a guideline how to build a deontic action logic which satisfies the desired properties. Introduction Most generally, deontic logic can be seen as a formal tool for analysing rational agent's behaviour in the context of systems of norms. Those norms can be of a different nature, moral, legal, technical are the main ones. Different systems of norms have different content and structure, and consequently, the correct schemas of reasoning about them may also differ. Thus, there may be many useful systems of deontic logic depending on their applications. Taking into account that fact we are interested in comparing the foundational principles of a group of deontic logics. Research on deontic logic can be divided, from the technical point of view, into two main groups: in one of them deontic notions, such as permission, forbiddance or obligation are attributes of situations (in the language – propositions), in the other they are attributes of actions (in the language – names). In the former one deontic notions ∗The project was funded by the National Science Center awarded by decision number DEC-2011/01/D/HS1/04445. 2 P. Kulicki and R. Trypuz are treated as a special case of modal operators and investigated with the use of tools of modal logic. So called Standard Deontic Logic is a logic of that type. In the present paper we are interested in the latter one – deontic action logic (DAL). The approach is used in the pioneering works of G. H. von Wright (Wright, 1951) and J. Kalinowski (Kalinowski, 1953), the following papers (Fisher, 1961; Åquist, 1963) the paper of K. Segerberg (Segerberg, 1982), which restored the "action approach" to deontic logic after the years of domination of the "propositional approach" and several papers developing the logics in question further. They include its presentation in a form of first-order theories (Lokhorst, 1996; Trypuz, 2011) and deontic logics of action built in connection with Propositional Dynamic Logic (PDL). In the latter class of systems two approaches can be distinguished. In one of them deontic operators are introduced with the use of dynamic operators and the notion of violation initiated in (Meyer, 1988), in the other one at least some of them are taken as primitive (McCarty, 1983; Meyden, 1996; Castro & Maibaum, 2009). Other recent work in the area include a system of deontic logic based on Kleene algebra (Prisacariu & Schneider, 2012). The aim of the present paper is to point out the modelling choices that lead to different systems of DAL. We present a kind of a roadmap, which can help the reader to find a logic appropriate for an intended field of application on the basis of the way actions can be represented and how the deontic characteristics of actions relate to their representation. The decisions made in the construction of systems of deontic action logic are rarely explicitly stated by their authors, who usually treat their choices as obvious and their intuitions as the only possible ones. In the presentation we do not attempt to introduce new technical results, we concentrate on systems already defined in the literature, which is rich enough to provide a large number of examples. The paper is a continuation of our previous work form (Trypuz & Kulicki, 2009, 2010), but in contrast to it, we do not limit ourselves to DAL based on Boolean algebra, but also consider multi-valued deontic action logics and logics with sequences of actions. We start from analysing the notion of action and the ways actions can be represented in deontic logic. In the following sections we study logics in which respectively one-step and multiple-step actions are considered. How to build a deontic action logic 3 1 Actions and their representation in the context of norms At the beginning we will try to clarify the concept of action itself. In (Trypuz, 2008) several notions of actions are collected and analysed. Let us revoke some of the different definitions of action presented there: • action is an event carried out by an agent (additionally one may require that the agent causes the event, has the intention to cause the event, has the reason for causing the event or that the event is constituted by a bodily movement of the agent); • action is a bodily movement of an agent; • action is an event, which is under control of an agent; • action is a trying of an agent; • action is a transition between states. We shall not discuss which of those definitions is adequate. In the context of deontic logic it is enough to adopt the following features of actions present in or presupposed by most of the definitions: • action is related to an agent, which is responsible for it; • action has results, i.e. transforms the world from one state to another; • actions can be combined. Generally, in logic, valid inferences are based on the structure of formulas used in them. This applies also to DAL in which the structure of actions is crucial. In this case actions can be treated as composed from basic actions using several operators. Most common of them present in the papers on deontic logic are: parallel composition (doing two things at the same time), sequential composition (doing two things in sequel), free choice (performing an action arbitrarily chosen out of two) and negation of action (not doing something, refraining from doing something, doing something else). 4 P. Kulicki and R. Trypuz Basic actions are least meaningful elements of agent's behaviour. They are chosen depending on the granularity of analysis and the type of considered agents, e.g.: "providing first aid", "paying $100 in cash", "making a bank transfer of $100", "turning left in the crossroads", "opening the window", "pressing the 'ok' button", "turning the switch on", "waving a hand". As it was noticed already in (Wright, 1951) one can look at those actions as action individuals (particular actions performed by a concrete agent at a certain time in a certain place) or types of actions. In the latter case we use a name of an action as a description of many possible action individuals. It is important to be aware in which of those two meanings actions are used in a system of deontic logic, since one can build systems employing any of them, but they must not be mixed up. Action operators, when applied to actions understood in one of those meanings, should return actions that can be understood in the same way. That causes some problems for actions understood as individuals. We can combine them using parallel and sequential composition but, when we apply action negation or free choice operator to them, we do not receive well defined individuals. Intuitively, not performing a particular action individual can be realised by many other action individuals. Doing one thing or another (the result of free choice between the two action individuals) is not a particular action individual as well. It can be realised by any of the two actions but it is not identical with any of them. Thus, if we want to use any of those two operators, we are forced to understand actions as types. In DAL actions are arguments of deontic operators, usually permission, forbiddance and obligation. Any kind of norms considered in deontic logic by their nature can be applied to many action individuals. Action individuals are permitted, forbidden or obligatory not per se, but because they fulfil certain specification, e.g. a particular act of providing first aid to a person hurt in an accident is obligatory for a driver because it is always obligatory to provide first aid when an accident happens, not because the norm-giver predicted that this particular person at this particular place and time needs help. When one understands action as types, this is achieved automatically. It is necessary, however, to be able to recognise actions in different situations as being of the same type. For example when we consider traffic regulations, my left turn at the crossroads in Hejnice How to build a deontic action logic 5 last morning must be recognised as being of the same type as any left turn of any car at the same crossroads (or even any left turn at any crossroads). When, on the other hand, we understand actions as individuals we have to categorise them, for example by using special predicates. We can then state that if a specific action α is an instant of providing first aid to a person hurt in an accident, then α is obligatory for any action α. This approach leads us naturally to deontic logics formulated as first order theories. That gives one strong expressive power, but, on the other hand, causes high complexity problems. Moreover, DAL defined in such a way loses its specificity. Thus, in the rest of the paper we shall concentrate on logics in which actions are understood as types, which are more domain specific. One can apply deontic characteristics to actions in two ways. The first way is to look only at the current situation of an agent and limit our judgements only to actions that may be performed in it. The other way is to consider also sequences of actions starting from the current situation. In the first one each situat ion can only be considered separately, in the other we may discuss a space of possible situations globally. From the technical point of view the distinction is between systems with or without sequential composition of actions. We shall refer to the systems employing those strategies respectively as one-step and multi-step deontic action logics. We shall use the following formal notation: a, b, . . . (possibly with subscripts) will stand for basic actions; α, β, . . . will represent any actions; 0 and 1 will stand for impossible action and universal action (doing anything) respectively; overline will be used for unary operator of action negation; ⊓, ;, ⊔ will represent respectively binary operators of parallel and sequential compositions of actions and free choice between actions; P, F and O will be used respectively for permitted, forbidden and obligatory predicates. The following definition of a well formed formula of DAL is a usual routine: φ ::= ⊥ | F(α) | P(α) | O(α) | ¬φ | φ → φ α ::= a | 0 | 1 | α | α ⊓ α | α ⊔ α | α;α 6 P. Kulicki and R. Trypuz 2 One-step systems This section is divided into two parts. In the first one we consider systems of DAL in which deontic value of complex action is a function of deontic values of basic actions that are used to define that complex actions. In those systems deontic matrices can be used. In the other, systems of DAL in which more complex attribution of deontic notion to complex actions are considered. 2.1 Multivalued deontic action logic The basic idea of multivalued DAL is to mark each basic action by its deontic value, calculate deontic value of complex actions on that basis, and finally, truth value of a deontic formula. Historically the first and also the simplest system of this kind of Kalinowski and Fisher1 is defined using three deontic values: good (g), neutral (n) and bad (b) by the following matrices: α P (α) O(α) F (α) b 0 0 1 n 1 0 0 g 1 1 0 ⊓ b n g α b b b b g n b n g n g b g g b Intuitively one may understand the first matrix as stating that good and neutral actions are permitted and bad ones are not, good actions are obligatory and neutral and bad ones are not, and bad actions are forbidden and good and neutral ones are not. The second matrix informs us how to obtain a deontic value of negation and parallel composition of two actions. Free choice operator is understood as a de Morgan dual of parallel composition. The least obvious is the deontic characterisation of a parallel composition of a good and a bad action. The matrix states that such an action is always bad. That may be unacceptable in some contexts. The problem can be solved within the multi-valued approach, since the system is not a single possible DAL defined by means of matrices. One of the alternative solutions2 is based on the lattice inspired by N. Belnap's lattice of truth and information (Belnap, 1977). In the resulting system four deontic values are used: good (g) and bad (b), as in the previous system, and two new ones: bottom 1Kalinowski introduced a general idea and the matrix for negation, Fisher How to build a deontic action logic 7 ⊤ ⊥ gb saturated neutral deontic moral valuebad good saturation Figure 1: A bilattice of moral value and deontic saturation (⊥) and top (⊤). Bottom value is understood as neutral and top as oversaturated, which is applied to action defined as a combination of good and bad elements. The interpretation of deontic operators is given by the following matrix. α P (α) O(α) F (α) b 0 0 1 ⊥ 1 0 0 ⊤ 1 0 0 g 1 1 0 One may notice that both ⊤ and ⊥ are treated as n in the system of Kalinowski and Fisher. The parallel composition and free choice are interpreted respectively as supremum and infimum of the lattice from figure 1. We can also present those operators along with action negation in the following matrices: ⊓ b ⊥ ⊤ g α b b b ⊤ ⊤ g ⊥ b ⊥ ⊤ g ⊥ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ g ⊤ g ⊤ g b ⊔ b ⊥ ⊤ g b b ⊥ b ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊤ b ⊥ ⊤ g g ⊥ ⊥ g g added matrices for ⊓ and ⊔. 2The formal details of the system sketched here and other possible multivalued DAL are the subject of our ongoing research. 8 P. Kulicki and R. Trypuz In contrast to the system of Kalinowski and Fisher a combination of good and bad actions is now neutral (is neither forbidden nor obligatory). In both presented multivalued systems deontic operators of permission, forbiddance and obligation are interdefinable in the sense that any one of them is sufficient to define the remaining ones. 2.2 Deontic action logics based on Boolean algebra More sophisticated considerations on deontic value of complex actions can be performed with the use of techniques of Boolean algebra of actions3. The first problem to discuss is whether a set of basic actions should be finite. In (Segerberg, 1982) it is not, while in (Castro & Maibaum, 2009) it is. Using finite sets makes the algebra atomic, which is pleasing from the technical point of view. Moreover, it seems to be a natural restriction, since actions are understood as types and it is reasonable to consider a finite number of action types. If we recognise infinitely many types of basic actions we can always group them into a finite set of categories. In systems of DAL based on Boolean algebra known from the literature, in contrast to multi-valued DAL, permission and forbiddance are not inter-definable. Permitted and forbidden actions are understood in a so called strong sense as permitted and forbidden in any context (in combination with any other possible actions). A basic system of that kind can be defined by the following axioms introduced in (Segerberg, 1982): P(α ⊔ β) ≡ P(α) ∧ P(β) (1) F(α ⊔ β) ≡ F(α) ∧ F(β) (2) α = 0 ≡ F(α) ∧ P(α) (3) That opens an opportunity to discuss problems of openness and closedness of deontic action logic. For which class of actions an action is either permitted or forbidden? Basic actions and atomic actions are 3The structures of deontic values of the systems from the previous section can also be treated as algebras, but the negation there is not the negation of Boolean algebra and the number of elements is limited to 3 or 4. How to build a deontic action logic 9 candidates. The following formulas expressing the discussed properties can be considered as different axioms of DAL (Act0 is a set of basic actions) that can be added to a basic open system: F(ai) ∨ P(ai), for ai ∈ Act0 (4) P(a1 ⊓ ... ⊓ an) ∨ F(a1 ⊓ ... ⊓ an), where {a1, ..., an} = Act0 (5) (a1 ⊔ * * * ⊔ an) = 1 (6) F(δ) ∨ P(δ), for δ being an atom of algebra. (7) Relation between systems resulting from using the above formulas as axioms are illustrated in figure 2.4 DAL0 (4) DAL1 (4,5) DAL2 (4,6) DAL3 DAL4 (7) DAL5 (7,6) Figure 2: A structure of DALn systems Moreover, we may introduce obligation operators in different manners. In (Trypuz & Kulicki, 2010) we discussed several notions of obligation defined on the basis of permission and forbiddance. Out of them most turned out not to fulfil the basic intuitions about obligation. The one worth mentioning is defined as follows: O(α) , P(α) ∧ F(α) (8) 4Proofs of the results concerning the relations between the systems and semantic presentation of them one can find in (Trypuz & Kulicki, 2009). 10 P. Kulicki and R. Trypuz The problem is that definition 8 allows only one action to be obligatory, that is: O(α) ∧ O(β) → α = β (9) Alternatively to definition 8, obligation can be introduced independently from permission and forbiddance as a primitive notion introduced with the following axioms: O(α) ∧ O(β) → O(α ⊓ β) (10) ¬O(0) (11) O(α) → P(α) (12) 3 Multi-step systems Propositional dynamic logic (PDL) is a modal logic created to model behaviours of computer programs (Harel, 1984). It was soon noticed by philosophers that it can also be applied per analogiam to represent human actions (Segerberg, 1980). Actions in PDL are interpreted as transitions between states. In the language of this logic we also find interesting action-forming operators, which allow for expressing free choice, parallel execution, refraining, sequential processing and action repetition. As we have mentioned in the introduction, there are two main approaches to combining deontic logic with PDL. In one of them deontic operators are introduced in Andersonian style, with the use of dynamic operators and the notion of violation (Meyer, 1988), in the other one at least some of them are taken as primitive (McCarty, 1983; Meyden, 1996; Castro & Maibaum, 2009). Dependening on the particular type of deontic logic built in connection with PDL, the idea of modelling norms slightly differs. Some of them focus on the actions/transitions - describing them as legal (green) or illegal (red) - whereas the other ones take into account the states which actions/transitions lead to - describing them as desired or undesired (by the norm-giver). One of the basic problems of DAL with sequential composition is the introduction of action negation. The notion of action negation (or complement) is problematic in action theory in general (see e.g. How to build a deontic action logic 11 (Segerberg, 1996)). In the context of deontic action logic with sequential composition the problem was studied in (Broersen, 2004). The problem has two levels: intuitive and technical. The intuitive level is how to understand a negation of action when actions consists of multiple steps. The technical level is that the calculi containing sequential composition and complement of relations are unndecidable and difficult to axiomatise. The most straightforward way to understand negation of action α is by analogy to relation complement. One takes the set of all possible complex actions available for an agent, let us call it R, and action α is understood as R\α (R can also be understood as the set S × S, where S is the set of all the possible states of the world). This is, however, unintuitive for actions, because gives us much more then actions alternative to α at a given situation. Moreover, using such a notion of negation leads to an unndecidable system. Broersen (Broersen, 2004) introduces another notion of negation by restricting the set R to actions available for an agent in a current state. In terms of state space he uses only reachable states. Depending on an accessibility relation on states, he receives different members of a family of negation operators. Another notion of action negation comes from (Wansing, 2005). In that approach the standard de Morgan laws for negation, parallel composition and free choice, and the following law: α;β = α;β (13) holds. That allows us to push the negation down to the basic actions. For that reason this notion is pleasing from the technical point of view. However (13) is not intuitively clear and there is no clear connection between a basic action and its negation. Yet another notion of negation is used in (Meyer, 1988; Prisacariu & Schneider, 2012). In that notion the basic idea is that refraining from performing a sequence of actions is a free choice between not doing the first of them and a sequence of doing the first of them and not doing the rest. Formally: α;β = α ⊔ α;β (14) The difference is that in the latter paper this notion is introduced as a defined operation restricted to actions in canonical form. That 12 P. Kulicki and R. Trypuz restriction makes the system decidable. The other problem is how to relate deontic predicates with sequences of actions. Should obligatory actions be all obligatory instantly? Formally such a constraint can be expressed by formula (10). An obligation operator respecting (10) is called in (Prisacariu & Schneider, 2012) a natural obligation. Alternatively, we may think of its weaker version in which two obligatory action can be performed simultaneously or consecutively, formally: O(α) ∧ O(β) → O(α ⊓ β) ∨ O(α;β) ∨ O(β;α) (15) Another problem is when the sequence of two actions is forbidden. In (Prisacariu & Schneider, 2012) it is so when both actions are forbidden, what can be formally expressed by the following law: F(α;β) → F(α) ∧ F(β) (16) Alternatively one may consider a sequence as forbidden, when one of its elements is forbidden, formally: F(α;β) → F(α) ∨ F(β) (17) Conclusions In the paper we point out that the crucial factors that influence the construction of any particular system of deontic action logic are the way actions are represented and the way deontic operators are attached to elements of that representation. References Åquist, L. (1963). Postulate sets and decision procedures for some systems of deontic logic. Theoria, 29 , 154-175. Belnap, N. (1977). A useful four-valuedlogic. In G. Epstein & J. M. Dunn (Eds.), Modern uses of multiple-valued logic (p. 737). Dordrecht: Reidel. Broersen, J. (2004). Action negation and alternative reductions for dynamic deontic logics. Journal of Applied Logic, 2 (1), 153– 168. How to build a deontic action logic 13 Castro, P. F., & Maibaum, T. S. E. (2009). Deontic action logic, atomic boolean algebras and fault-tolerance. Journal of Applied Logic, 7 (4), 441–466. Fisher, M. (1961). A three-valued calculus for deontic logic. Theoria, 27 , 107-118. Harel, D. (1984). Dynamic logic. In D. Gabbay & F. Guenthner (Eds.), Handbook of philosophical logic, volume II: Extensions of classical logic (Vol. 165, pp. 497–604). Dordrecht. Kalinowski, J. (1953). Theorie des propositions normatives. Studia Logica, 1 , 147–182. Lokhorst, C. G.-J. (1996). Reasoning about actions and obligations in first-order logic. Studia Logica, 57 (1), 221–237. McCarty, L. T. (1983). Permissions and Obligations. In Proccedings of ijcai-83 (pp. 287–294). Meyden, R. V. D. (1996). The dynamic logic of permission. Journal of Logic and Computation, 6 , 465–479. Meyer, J. J. C. (1988). A Different Approach to Deontic Logic: Deontic Logic Viewed as a Variant of Dynamic Logic. Notre Dame Journal of Formal Logic, 1 , 109–136. Prisacariu, C., & Schneider, G. (2012). A dynamic deontic logic for complex contracts. The Journal of Logic and Algebraic Programming, 81 , to appear. Segerberg, K. (1980). Applying Modal Logic. Studia Logica, 39 (2-3). Segerberg, K. (1982). A Deontic Logic of Action. Studia Logica, 41 (2-3). Segerberg, K. (1996). To do and not to do. In J. Copeland (Ed.), Logic and reality: Essays on the legacy of arthur prior (p. 301 313). Oxford University Press. Trypuz, R. (2008). Formal Ontology of Action: a unifying approach. Wydawnictwo KUL. Trypuz, R. (2011). Simple theory of norm and action. In A. Brożek, J. Jadacki, & B. Žarnić (Eds.), Theory of imperatives from different points of view (pp. 120 – 136). Wydawnictwo Naukowe Semper. Trypuz, R., & Kulicki, P. (2009). A systematics of deontic action logics based on boolean algebra. Logic and Logical Philosophy, 18 (3–4), 253–270. Trypuz, R., & Kulicki, P. (2010). Towards metalogical systematisation of deontic action logics based on Boolean algebra. In G. Gov14 P. Kulicki and R. Trypuz ernatori & G. Sartor (Eds.), Deontic logic in computer science (deon 2010) (pp. 132–147). Springer. Wansing, H. (2005). On the negation of action types: Constructive concurrent pdl. In Logic methodology and philosophy of science. proceedings of the twelfth international congress (p. 207-225). London: King's College Publications. Wright, G. H. von. (1951). Deontic logic. Mind , LX (237), 1–15. Piotr Kulicki & Robert Trypuz The John Paul II Catholic University of Lublin Al. Raclawickie 14, Lublin, Poland, e-mail: {kulicki,trypuz}@kul.pl