逻辑、计算和博弈 (20).pdf

《逻辑、计算和博弈 (20).pdf》由会员分享，可在线阅读，更多相关《逻辑、计算和博弈 (20).pdf（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 LOGIC,COMPUTATION AND GAMES Topology,Abstracting from Analysis Open sets in IR2 qualitative version of Analysis open neighborhoods approximating points,continuous maps Geometrical,informational,other interpretation of the pictures Moral of abstraction:saying less is saying more Topology,Basic Notio

2、ns Topological space(X,O),O family of subsets of X (i)containing empty set and X,closed under (ii)finite intersections,(iii)arbitrary unions.Closed sets:complement of open set,boundary bases and subbases that generate O Metric spaces subbase all sets U(s,)=t|dist(s,t)Continuous map f from one space

3、to another:inverse images f-1O of open sets O O are open Topology and Logic Another major family of topological spaces:trees opens upward closed sets base cones at points Modal Logic!Alexandrov topology:each point has smallest open neighborhood,fits with tree topology Topological Semantics M=(X,O,V)

4、:topological space plus valuation M,s|=iff there is O O,s O and for all t O:M,t|=defines an open set existential dual defines closed sets M,s|=iff for all O O with s O,there is t O:M,t|=difference with standard modalities in Weeks 1 4:two quantifiers instead of one Fact Equivalent on tree topologies

5、 Defining Regions,Model Checking TopoBisimulation Games Your first example of a logic game this one for analyzing expressive power of a language Distinguishing Topological Structures (c):correction to published pictures How many rounds are needed for Spoiler to win?(a):1,(b):2,(c):3 (c)Winning and L

6、osing Play The game fits the moday Adequacy Theorem The game fits the modal language precisely even stronger effective correspondence between Spoilers winning strategies formulas that distinguish s,t modal operator switches indicate when to switch models corollary game is determined one of the playe

7、rs has a winning strategy Completeness for S4 Valid principles:modal logic S4 ()(),what these say about open sets Theorem A modal formula is topologically valid iff it is provable in S4.Straightforward completeness proof:canonical model generates tree topology.Tarski-McKinsey Theorem Much stronger r

8、esult Theorem A modal formula is provable in S4 iff it is true in every model based on a metric space without isolated points.Proof need to connect abstract logical models to concrete structures in geometry validities may look weak,but logical formulas express spatial patterns Tarski-McKinsey Proof

9、must reproduce all finite tree-like S4 models in the reals ca in general also embedding fractals Extended Topological Languages Define connectedness using universal modality:Lots of recent results on axiomatizing richer topological structures in extended languages Handbook of Spatial Logics 2007 Mod

10、al Languages for Geometry Geometry:affine(betweenness),metric(length)Bxyz:x lies in between y and z Ternary relation,binary modality M,s|=iff t,u:Bstu&M,t|=&M,u|=correspondence modal axiom(infix notation)p(qr)(pq)r)Pasch Axiom Open Axiomatize complete modal logic of on IR2 Modal Logics of Vector Spa

11、ces Worlds/points=vectors vector addition:binary modality vector inverse:unary modality Minkowski subtraction Linear Algebra:vector spaces in big data,AI new area of current interest modal logics for qualitative reasoning Tsinghua Logic Center on-line Workshop 13 November PS Connecting with Computat

12、ional Complexity Several of you have asked questions about connections between the topics of this course and (recent)results in computational complexity theory I would find this very interesting to pursue further(I do not think much has been done by logicians here,but check the Complexity chapter,1996 Handbook of Modal Logic)so please send me your thoughts and suggestions!