Algebra, Proof Theory and Applications for an Intuitionistic Logic of Propositions, Actions and Adjoint Modal Operators

作者：Dyckhoff Roy^*; Sadrzadeh Mehrnoosh; Truffaut Julien

来源：ACM Transactions on Computational Logic, 2013, 14(4): 34.

DOI：10.1145/2536740.2536742

• Theory
• Verification
• Proof theory
• cut admissibility
• algebra
• adjoint modalities
• epistemic scenarios
• logics for multi-agent systems
• decision procedures

We develop a cut-free nested sequent calculus as basis for a proof search procedure for an intuitionistic modal logic of actions and propositions. The actions act on propositions via a dynamic modality (the weakest precondition of program logics), whose left adjoint we refer to as %26quot;update%26quot; (the strongest postcondition). The logic has agent-indexed adjoint pairs of epistemic modalities: the left adjoints encode agents%26apos; uncertainties and the right adjoints encode their beliefs. The rules for the %26quot;update%26quot; modality encode learning as a result of discarding uncertainty. We prove admissibility of Cut, and hence the soundness and completeness of the logic with respect to an algebraic semantics. We interpret the logic on epistemic scenarios that consist of honest and dishonest communication actions, add assumption rules to encode them, and prove that the calculus with the assumption rules still has the admissibility results. We apply the calculus to encode (and allow reasoning about) the classic epistemic puzzles of dirty children (a.k.a. %26quot;muddy children%26quot;) and drinking logicians and some versions with dishonesty or noise; we also give an application where the actions are movements of a robot rather than announcements.

• 出版日期2013-11