Dynamic logic (modal logic).doc

dynamic logic (modal logic)from wikipedia, the free encyclopediajump to: navigation, searchfor the subject in digital circuits also known as clocked logic, see dynamic logic (digital logic).dynamic logic is an extension of modal logic originally intended for reasoning about computer programs and later applied to more general complex behaviors arising in linguistics, philosophy, ai, and other fields.contentshide 1 language 2 axioms 3 derivations 4 derived rules of inference 5 assignment 6 test 7 quantification as random assignment 8 possible-world semantics 9 propositional dynamic logic (pdl) 10 history 11 the concurrency challenge 12 references 13 external linksedit languagemodal logic is characterized by the modal operators p (box p) asserting that p is necessarily the case, and p (diamond p) asserting that p is possibly the case. dynamic logic extends this by associating to every action a the modal operators a and , thereby making it a multimodal logic. the meaning of ap is that after performing action a it is necessarily the case that p holds, that is, a must bring about p. the meaning of p is that after performing a it is possible that p holds, that is, a might bring about p. these operators are related by ap p and p a p, analogously to the relationship between universal and existential quantifiers.dynamic logic permits compound actions built up from smaller actions. while the basic control operators of any programming language could be used for this purpose, kleenes regular expression operators are a good match to modal logic. given actions a and b, the compound action ab, choice, also written a+b or a|b, is performed by performing one of a or b. the compound action a;b, sequence, is performed by performing first a and then b. the compound action a*, iteration, is performed by performing a zero or more times, sequentially. the constant action 0 or block does nothing and does not terminate, whereas the constant action 1 or skip or nop, definable as 0*, does nothing but does terminate.edit axiomsthese operators can be axiomatized in dynamic logic as follows, taking as already given a suitable axiomatization of modal logic including such axioms for modal operators as the above-mentioned axiom ap p and the two inference rules modus ponens (p, pqq) and necessitation (p ap).a1. 0pa2. 1p pa3. abp ap bpa4. a;bp abpa5. a*p p aa*pa6. p a*(p ap) a*paxiom a1 makes the empty promise that when block terminates, p will hold, even if p is the proposition false. (thus block abstracts the essence of the action of hell freezing over.) a2 says that nop acts as the identity function on propositions, that is, it transforms p into itself. a3 says that if doing one of a or b must bring about p, then a must bring about p and likewise for b, and conversely. a4 says that if doing a and then b must bring about p, then a must bring about a situation in which b must bring about p. a5 is the evident result of applying a2, a3 and a4 to the equation a* = 1a;a* of kleene algebra. a6 asserts that if p holds now, and no matter how often we perform a it remains the case that the truth of p after that performance entails its truth after one more performance of a, then p must remain true no matter how often we perform a. a6 is recognizable as mathematical induction with the action n:=n+1 of incrementing n generalized to arbitrary actions a.edit derivationsthe modal logic axiom ap p permits the derivation of the following six theorems corresponding to the above.t1. pt2. p pt3. p p pt4. p pt5. p p pt6. p p (p p)t1 asserts the impossibility of bringing anything about by performing block. t2 notes again that nop changes nothing, bearing in mind that nop is both deterministic and terminating whence 1 and have the same force. t3 says that if the choice of a or b could bring about p, then either a could bring about p or b could. t4 is just like a4. t5 is explained as for a5. t6 asserts that if it is possible to bring about p by performing a sufficiently often, then either p is true now or it is possible to perform a repeatedly to bring about a situation where p is (still) false but one more performance of a could bring about p.box and diamond are entirely symmetric with regard to which one takes as primitive. an alternative axiomatization would have been to take the theorems t1-t6 as axioms, from which we could then have derived a1-a6 as theorems.the difference between implication and inference is the same in dynamic logic as in any other logic: whereas the implication pq asserts that if p true then so is q, the inference pq asserts that if p is valid then so is q. however the dynamic nature of dynamic logic moves this distinction out of the realm of abstract axiomatics into the common-sense experience of situations in flux. the inference rule pap for example is sound because its premise asserts that p holds at all times, whence no matter where a might take us, p will be true there. the implication pap is not valid however because the truth of p at the present moment is no guarantee of its truth after performing a. for example pap will be true in any situation where p is false, or in any situation where ap is true, but the assertion x=1 x:=x+1x=1 is false in any situation where x has value 1, and therefore is not valid.edit derived rules of inferenceas for modal logic, the inference rules modus ponens and necessitation suffice also for dynamic logic as the only primitive rules it needs, as noted above. however as usual in logic, many more rules can be derived from these with the help of the axioms. an example instance of such a derived rule in dynamic logic is that if kicking a broken tv once cant possibly fix it, then repeatedly kicking it cant possibly fix it either. writing k for the action of kicking the tv, and b for the proposition that the tv is broken, dynamic logic expresses this inference as bkb bk*b, having as premise b kb and as conclusion b k*b. the meaning of kb is that it is guaranteed that after kicking the tv, it is broken. hence the premise b kb means that if the tv is broken, then after kicking it once it will still be broken. k* denotes the action of kicking the tv zero or more times. hence the conclusion b k*b means that if the tv is broken, then after kicking it zero or more times it will still be broken. for if not, then after the second last kick the tv would be in a state where kicking it once more would fix it, which the premise claims can never happen under any circumstances.the inference bkb bk*b is sound. however the implication (bkb) (bk*b) is not valid because we can easily find situations in which bkb holds but bk*b does not. in any such counterexample situation b must hold but k*b must be false, while kb however must be true. but this could happen in any situation where the tv is broken but can be revived with two kicks. the implication fails because it only requires that bkb hold now, whereas the inference succeeds because it requires that bkb hold in all situations, not just the present one.an example of a valid implication is the proposition x3 x:=x+1x4. this says that if x is greater or equal to 3, then after incrementing x, x must be greater or equal to 4. in the case of deterministic actions a that are guaranteed to terminate, such as x:=x+1, must and might have the same force, that is, a and have the same meaning. hence the above proposition is equivalent to x3 x4 asserting that if x is greater or equal to 3 then after performing x:=x+1, x might be greater or equal to 4.edit assignmentthe general form of an assignment statement is x:= e where x is a variable and e is an expression built from constants and variables with whatever operations are provided by the language, such as addition and multiplication. the hoare axiom for assignment is not given as a single axiom but rather as an axiom schema.a7. x:=e(x) (e)this is a schema in the sense that (x) can be instantiated with any formula containing zero or more instances of a variable x. the meaning of (e) is with those occurrences of x that occur free in , i.e. not bound by some quantifier as in x, replaced by e. for example we may instantiate a7 with x:=e(x=y) e=y, or with x:=e(b=c+x) b=c+e. such an axiom schema allows infinitely many axioms having a common form to be written as a finite expression connoting that form.the instance x:=x+1x4 x+1 4 of a7 allows us to calculate mechanically that the example x:=x+1x4 encountered a few paragraphs ago is equivalent to x+1 4, which in turn is equivalent to x3 by elementary algebra.an example illustrating assignment in combination with * is the proposition x=7. this asserts that it is possible by incrementing x sufficiently often to make x 7. this of course is not alway true, e.g. if x is 8 to begin with, or 6.5, whence this proposition is not a theorem of dynamic logic. if x is of type integer however, then this proposition is true if and only if x is at most 7 to begin with, that is, it is just a roundabout way of saying x7.mathematical induction can be obtained as the instance of a6 in which the proposition p is instantiated as (n), the action a as n:=n+1, and n as 0. the first two of these three instantiations are straightforward, converting a6 to (n) (n:=n+1)*(n)n:=n+1(n) (n:=n+1)*(n). however the obstensibly simple substitution of 0 for n is not so simple as it brings out the so-called referential opacity of modal logic in the case when a modality can interfere with a substitution.when we substituted (n) for p, we were thinking of the proposition symbol p as a rigid designator with respect to the modality n:=n+1, meaning that it is the same proposition after incrementing n as before, even though incrementing n may impact its truth. likewise the action a is still the same action after incrementing n, even though incrementing n will result in its executing in a different environment. however n itself is not a rigid designator with respect to the modality n:=n+1; if it denotes 3 before incrementing n it denotes 4 after. so we cant just substitute 0 for n everywhere in a6.one way of dealing with the opacity of modalities is to eliminate them. to this end, expand (n:=n+1)*(n) as the infinite conjunction (n:=n+1)0(n) (n:=n+1)1(n) (n:=n+1)2(n) , that is, the conjunction over all i of (n:=n+1)i(n). now apply a4 to turn (n:=n+1)i(n) into n:=n+1n:=n+1(n) having i modalities. then apply hoares axiom i times to this to produce (n+i), then simplify this infinite conjunction to i(n+i). this whole reduction should be applied to both instances of (n:=n+1)* in a6, yielding (n) i(n+i)n:=n+1(n+i) i(n+i). the remaining modality can now be eliminated with one more use of hoares axiom to give (n) i(n+i)(n+i+1) i(n+i).with the opaque modalities now out of the way we can safely substitute 0 for n in the usual manner of first-order logic to obtain peanos celebrated axiom (0) i(i)(i+1) i(i), namely mathematical induction.one subtlety we glossed over here is that i should be understood as ranging over the natural numbers, where i is the superscript in the expansion of a* as the union of ai over all natural numbers i. the importance of keeping this typing information straight becomes apparent if n had been of type integer, or even real, for any of which a6 is perfectly valid as an axiom. as a case in point, if n is a real variable and (n) is the predicate n is a natural number, then axiom a6 after the first two substitutions, that is, (n) i(n+i)(n+i+1) i(n+i), is just as valid, that is, true in every state regardless of the value of n in that state, as when n is of type natural number. if in a given state n is a natural number then the antecedent of the main implication of a6 holds, but then n+i is also a natural number so the consequent also holds. if n is not a natural number then the antecedent is false and so a6 is remains true regardless of the truth of the consequent. we could strengthen a6 to an equivalence p a*(p ap) a*p without impacting any of this, the other direction being provable from a5, from which we see that if the antecedent of a6 does happen to be false somewhere then the consequent must be false.edit testdynamic logic associates to every proposition p an action p? called a test. when p holds, the test p? acts as a nop, changing nothing while allowing the action to move on. when p is false, p? acts as block. tests can be axiomatized as follows.a8. p?q pqthe corresponding theorem for is:t8. q pqthe construct if p then a else b is realized in dynamic logic as (p?;a)(p?;b). this action expresses a guarded choice: if p holds then p?;a is equivalent to a, whereas p?;b is equivalent to block, and ablock is equivalent to a. hence when p is true the performer of the action can only take the left branch, and when p is false the right.the construct while p do a is realized as (p?;a)*;p?. this performs p?;a zero or more times and then performs p?. as long as p remains true, the p? at the end blocks the performer from terminating the iteration prematurely, but as soon as it becomes false, further iterations of the body p are blocked and the performer then has no choice but to exit via the test p?.edit quantification as random assignmentthe random-assignment statement x:=? denotes the nondeterministic action of setting x to an arbitrary value. x:=?p then says that p holds no matter what you set x to, while p says that it is possible to set x to a value that makes p true. x:=? thus has the same meaning as the universal quantifier x, while similarly corresponds to the existential quantifier x. that is, first-order logic can be understood as the dynamic logic of programs of the form x:=?.edit possible-world semanticsmodal logic is most commonly interpreted in terms of possible world semantics or kripke structures. this semantics carries over naturally to dynamic logic by interpreting worlds as states of a computer in the application to program verification, or states of our environment in applications to linguistics, ai, etc. one role for possible world semantics is to formalize the intuitive notions of truth and validity, which in turn permit the notions of soundness and completeness to be defined for axiom systems. an inference rule is sound when validity of its premises implies validity of its conclusion. an axiom system is sound when all its axioms are valid and its inference rules are sound. an axiom system is complete when every valid formula is derivable as a theorem of that system. these concepts apply to all systems of logic including dynamic logic.edit propositional dynamic logic (pdl)ordinary or first-order logic has two types of terms, respectively assertions and data. as can be seen from the examples above, dynamic logic adds a third type of term denoting actions. the dynamic logic assertion x:=x+1x4 contains all three types: x, x+1, and 4 are data, x:=x+1 is an action, and x4 and x:=x+1x4 are assertions. propositional logic is derived from first-order logic by omitting data terms and reasons only about abstract propositions, which may be simple propositional variables or atoms or compound propositions built with such logical connectives as and, or, and not.propositional dynamic logic, or pdl, was derived from dynamic logic in 1977 by michael fischer and richard ladner. pdl blends the ideas behind propositional logic and dynamic logic by adding actions while omitting data; hence the terms of pdl are actions and propositions. the tv example above is expressed in pdl whereas the next example involving x:=x+1 is in first-order dl. pdl is to (first-order) dynamic logic as propositional logic is to first-order logic.fischer and ladner showed in their 1977 paper that pdl satisfiability was of computational complexity at most nondeterministic exponential time, and at least deterministic exponential time in the worst case. this gap was closed in 1978 by vaughan pratt who showed that pdl was decidable in deterministic exponential time. in 1977 krister segerberg proposed a complete axiomatization of pdl, namely any complete axiomatization of modal logic k together with axioms a1-a6 as given above. completeness proofs for segerbergs axioms were found by gabbay, parikh (1978), pratt (1979), and kozen and parikh (1981).edit historydynamic logic was developed by vaughan pratt in 1974 in notes for a class on program verification as an approach to assigning meaning to hoare logic by expressing the hoare formula paq as paq. the approach was later published in 1976 as a logical system in its own right. the system parallels a. salwickis system of algorithmic logic and edsger dijkstras notion of weakest-precondition predicate transformer wp(a,p), with ap corresponding to dijkstras wlp(a,p), weakest liberal precondition. those logics however made no connection with either modal logic, kripke semantics, regular expressions, or the calculus of binary relations; dynamic logic therefore can be viewed as a refinement of algorithmic logic and predicate transformers that connects them up to the axiomatics and kripke semantics of modal logic as well as to the calculi of binary relations and regular expressions.edit the concurrency challengehoare logic, algorithmic logic, weakest preconditions, and dynamic logic are all well suited to discourse and reasoning about sequential behavior. extending these logics to concurrent behavior howeve