没有合适的资源?快使用搜索试试~ 我知道了~
欧拉图:形式化图形推理系统综述
理论计算机科学电子笔记134(2005)127-151www.elsevier.com/locate/entcs基于欧拉图的推理系统综述宝石Stapleton1视觉建模集团布莱顿大学Brighton BN 2 4GJ,英国摘要几个世纪以来,欧拉图一直被用作以直观、非正式的方式传达思想的手段。最近,许多研究已经进行了开发正式的,图形推理系统的基础上欧拉图。这些系统中的大多数通过添加进一步的语法来扩展欧拉图以增加表达能力。在本文中,我们调查这样的系统,并绘制它们之间的保留字:视觉逻辑,图解推理。1介绍欧拉图[2](有时称为欧拉圆)是一种简单的视觉语言,用于表达逻辑语句。它们利用包围、互斥和交的拓扑性质分别表示子集、不交集和集交。图1中的图是欧拉图,并表达了“所有老虎都是猫,没有狗是猫”的事实,我们将把作为平面的连通分量的区域称为2区。例如,在图1中,猫内部平面中的点集1电子邮件:g.e. brighton.ac.uk2一个区域可以通过包含一组轮廓和排除一组轮廓来识别,这些轮廓形成轮廓集的一个分区1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.02.022128G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127CATSTig ersDo g sFig. 1. 欧拉图。但老虎和狗的外面是一个区域欧拉图有各种不同的语义。欧拉图中的区域表示集合,图中区域所表示的所有集合的并集是全集。一些语义解释指定图中的每个区域表示非空集[31],而其他人则没有施加这种限制[17]。关于欧拉图语义的讨论可以在[19]中找到欧拉图的表现力有限。例如,没有欧拉图可以表示A=λ,仅此而已。它们只能通过使用缺失区域来表示集合为空(缺失区域可以被认为是可以通过轮廓标签集的分区来描述但不存在于图中的区域)。给定欧拉图上的某些形式良好的条件(例如轮廓必须是简单的,封闭的,平面曲线),欧拉图不能表达的语句的一些不太平凡的例子,在[30,52]中被确定,因为没有带有指定区域集的可绘制图。已经出现了许多推理系统,它们通过使用额外的语法来扩展欧拉图以增加表达能力。在本文中,我们提出了这样的系统的调查。在第二节中,我们概述了Hammer我们在第三节中简要地讨论了维恩图。皮尔士修改了维恩图,使用x序列来断言元素的存在[35]。我们在第4节简要概述了他的系统。ShinSwoboda和Allwein开发了一个基于欧拉图的推理系统[45],类似于Shin蜘蛛图再次扩展了Shin许多健全和完整的蜘蛛图系统已经开发出来,我们在第8节中描述这些。约束图通过使用额外的语法来扩展蜘蛛图[29]。它们大大增加了蜘蛛图的表达能力,并且可以表达涉及两个位置谓词的语句。本文中概述的任何其他系统都不能进行需要两个位置谓词的语句(相等除外)。我们在第9节中讨论了约束图。G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127129CATSTig ersMic e2使用Euler DiagramsHammer在[17]中给出了一个基于欧拉图的简单可靠的该系统只有三个推理规则:擦除规则(轮廓),引入新轮廓的规则和弱化规则(引入区域)。例2.1在图2中,我们举例说明了哈默 首先我们从图d1中删除标记为Dogs的轮廓。这接下来,我们引入标记为M ice的等高线。这样做时,我们必须确保新等高线重叠图中每个区域的适当部分,从而确保我们不会改变图的含义。最后,我们使用弱化规则来引入新的区域,给出d2。通过引入在老虎之内但在猫和老鼠之外的区域,我们已经CATSDo g sCATS天啊天啊D1CATSTig ersMic eD2图二. 汉默系统中的推理Hammer的欧拉图系统是可判定的。 这是一个必然的结果到我们现在概述的完整性证明策略。给定d1≠d2,Hammer构造了一个从d1到d2的证明(这里的证明是指应用于d 1给出d 2的一系列推理规则)。 这个证明的第一部分是将等高线添加到d1,直到在d2中出现的每个等高线标签都出现在d1中。 接下来,删除d1中的等高线,直到它具有与d2相同的等高线标签集。3在允许区域表示空集的语义下。130G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127最后利用弱化法则求出d2。可以证明,如果规则在此最后阶段不能应用削弱,则d1d2。3维恩图维恩图[50]类似于欧拉图。然而,不是使用缺失区域来表示集合是空的,而是使用阴影。在维恩图中,等值线之间所有可能的交点都出现了。因此,维恩图语言通过使用阴影来表示空集来扩展欧拉图语言的片段。图3中的维恩图表示CatsDo g sTig ers图三. 维恩图。与图1中的欧拉图相同。Venn提出了在n个等值线上画任意Venn图的构造方法[51],More给出了构造过程有效的拓扑证明[33]。文氏图的研究概况见[37]。4维恩-皮尔斯图维恩图不能断言元素的存在,也不能表达析取信息。为了克服这一点,皮尔士修改了维恩图,在系统中引入符号来表示集合的非空性和空性[35]。符号x和o分别用来表示非空和空。皮尔士也用线条来连接x阴影在维恩-皮尔斯图中不使用。例4.1图4中的维恩-皮尔士图表示,(i) 至少有一个实数,(ii) 所有的自然数都是实数。皮尔士为他的图解系统引入了六条推理规则[35],例如,我们可以将任何字符与任何现有字符联系起来。也就是说,我们可以使用一条线将x或o连接到任何现有的x或oG. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127131一BOCX一BX OCXRealnumbeNrsaturalnumbersx x o见图4。 一个维恩-皮尔斯图。图五.使用Venn-Peirce图进行推理。例4.2在图5中,我们可以引入一个x,放置在区域内所有三个轮廓,并将其连接到x-o序列。这个规则类似于命题逻辑中允许从P推导出PQ的规则。本文讨论的Venn-Peirce图与其它图的区别在于用o代替阴影。此外,o可以连接到x的事实意味着Venn-Peirce图可以表达,例如,在一个图中,A=BPeirce建议改进他的符号:而不是使用图中的线条来表示析取信息,绘制仅包含合取信息的图,并使用这些图的集合来表示析取信息,就像一种析取范式。稍后,我们将回顾允许使用“and”和“or”连接单个图的语言,5文氏图Shin [39]通过恢复到Venn的阴影来表示集合的空性(而不是使用O -序列)来适应Venn-Peirce图因为Shin使用了阴影她的Venn-I语言比Venn-Peirce语言更具限制性和更少的表达性。她还用符号代替x。例5.1图6中的维恩-I图d1表示:132G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127sCatsDoTig ersAB一BC(i) 没有猫是狗(通过使用阴影),(ii) 所有的老虎都是猫(通过使用阴影),(iii) 至少有一只狗(通过使用双序列),(iv) 存在至少一个猫(通过使用双序列)。图d2表达了与d1相同的内容:狗内部但猫和老虎外部的额外的序列没有提供额外的信息。所以,n-序列只是断言集合的非空性。g g sd1d2见图6。 两个维恩-I图。Shin为Venn-I定义了六个合理的推理规则,并证明了完备性。Venn-I推理规则之一允许引入轮廓。等高线必须有一个图中没有的标签,并且必须遵守部分重叠规则:引入给定图的新闭合曲线应该与该图中每个区域的适当部分重叠一次且仅一次[39],第57页。此外,还必须对序列,如下例所示。例5.2在图7中,我们可以给d1加上一个带有新标签C的等高线,得到d2。当引入轮廓时,我们必须确保阴影被保留。此外,我们必须确保修改所有的n-序列,使每个n-序列都被n-n-序列取代,每个新区域中有一个部分。d1d2见图7。使用Venn-I图进行推理。另一个规则,被称为统一的规则的图表,允许两个diagrams被替换为一个单一的图表。统一规则抓住了缺点-CATSDoTig ersG. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127133AB一个C在两个给定的图中的语义信息的连接(尽管该规则纯粹是语法上定义的),并用单个图来替换它们,表达这种连接信息。例5.3我们可以统一d1和d2,如图8所示,得到d3。d1d2D3见图8。 统一Venn-I图。其余四个完整性所需的规则,在[39]第81页中给出,如下所述。(i) 图形对象的擦除规则。轮廓,整个序列和阴影在一个区域可以删除。(ii) 擦除一个连续序列的一部分的规则。 如果一个序列的一部分在阴影区域中,那么该部分可以被擦除。(iii) 传播的规律。可以引入一个新序列并将其连接到现有的新序列。(iv) 信息冲突规则。 如果阴影区域包含整个那么这个图就可以被任何图所取代。在这种情况下,双序列断言由区域表示的集合的非空性,而阴影断言空性,这是一个矛盾。从一个矛盾中,任何事情都可以推断出来。6文氏图Venn-I在表达能力上是有限的,不能表达形式为A<$B <$A<$C的语句。Shin将Venn-I扩展为一个更具表现力的系统,称为Venn-II,允许Venn-I图由直线段连接。这样一条连接线代表着分离,就像连接两条线一样例6.1图9中Venn-II图的语义是它的两个Venn-I部分的语义的分离。一BC134G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127AB一个C见图9。 文氏图Shin为Venn-II定义了十条推理规则,并表明它们形成了一个完整的集合。Venn-I的六个规则推广到Venn-II。这四项新规定如下。(i) 序列的分裂规则。一个序列可以被分成两个(或者,一般来说,更多)片段,如下所示。如果D包含一个放置在两个或多个区域中的序列S,那么D可以被D1−D2代替,其中D1和D2都是D的拷贝,但都不包含S。的序列S被分成两部分,一部分放在D1,另一部分放在D2.(ii) 排除中间规则。一个图D有一个没有阴影的区域r,它不包含一个π序列,可以用一个图的析取D1−D2来代替,其中D1和D2都是D的一个副本,但是在D1中,r是阴影的,在D2中,r包含一个π序列。(iii) 连接图表的规则 A图D1可以替换为D1−D2,其中D2是任何图。(iv) 建筑的规则。D1−... −Dn可以用D代替,如果每个Di可以用D代替。Venn-II图不能表示集合基数的任意有限上下界。Shin证明了Venn-II在表达能力上等价于纯一元一阶逻辑(其中没有等式,所有谓词符号都是一个位置),她称之为L0,她的证明策略是算法的。为了证明Venn-II最多和L0一样有表现力,可以直接将任何给定的图翻译成一个句子。为了找到一个与句子表达等价的图,她首先将句子转换为前束范式,比如Q1x1...... QnxnG,其中每个Qi是一个量化器,G是无量化器的。若Qn是泛的,则G转化为合取范式.如果Qn是存在的,那么G被转化为析取范式。然后,量化器Qn通过G分布,并从其范围中删除尽可能多的公式。所有n个量化器都以这种方式分布在句子这个过程产生的句子没有嵌套的量化器。然后,可以为所得到的公式的每个简单部分绘制图表。G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127135L2L1例6.2将Shin算法应用P2(x2))产生图10所示的图表。d1d2见图10。Shin最近,Venn-II系统已经扩展到包括常数[1]。7Euler/Venn图欧拉/维恩图[45]类似于维恩-I图,但使用常数序列而不是连续对这些符号的解释各不相同。一个常数序列断言集合的非空性,而一个常数序列断言一个特定的个体在集合中另一个差异欧拉/维恩图有基本的欧拉图,而维恩- I图更有限制,只允许维恩图作为基本图。图11中的图是一个欧拉/维恩图,表示没有一个元素既是哺乳动物又是昆虫,有一种叫做“蒂姆”的东西MammIanlsecttimm见图11。 欧拉-维恩图。Swoboda在文[45]中给出了一组合理的Euler/Venn图推理规则。这些规则是Shin和Hammer [17,18,39]给出的规则的扩展在[48]中,Swoboda和Allwein给出了一个算法,该算法确定给定的Euler/Venn一元一阶公式是否信息只有在图中显式表示时才能从图中观察到。如果一个公式可以从图中观察到,那么这个公式就是图中包含的信息的结果。例7.1公式P(bob)<$Q(bob)可以从图12中观察到,但P(chris)<$<$P(chris)不能,因为chris没有出现在图12中。136G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127图表。P Qb o b b o b见图12。可观测公式。[49]中关于观察的工作允许在欧拉/维恩图和一阶逻辑之间定义重铸关系(见[47])。两个语句S和T(用不同语言所作)在一个重铸关系下相联系,即S所表达的信息可以从T中提取出来。在这里的特殊情况下,例如,欧拉/维恩图D与一阶逻辑句子S相关,当S从D可观察时,在重铸关系下。8蜘蛛图Shin在Venn-I和Venn-II上的工作是开创性的,并挑战了数学家中普遍持有的概念,即图不能用作形式化工具,而只能作为理解诸如证明之类的形式化构造的辅助工具。虽然Venn-II系统不是特别的express- sive,申确实表明,图形符号可以形式化,并给出健全和完整的推理规则。蜘蛛图[13,22,25,26,32]适应并扩展了Venn-II图。与使用双序列表示区域表示非空集不同,蜘蛛用于表示元素的存在,并且与双序列不同,不同的蜘蛛表示不同元素的存在。因此蜘蛛图允许在集合的基数上设置有限的下限。在Venn-II图中,如果将阴影放置在与那么这个图就是一个矛盾。此外,Venn-Peirce di-图和欧拉/维恩图也可以用类似的方式表示矛盾对于蜘蛛图,如果阴影被放置在与蜘蛛相同的区域中,则该图表示该区域所表示的集合中的所有元素都由其蜘蛛表示因此,阴影,连同蜘蛛,允许有限的上限被放置在集合的基数上。此外,像欧拉/维恩图,蜘蛛图是基于欧拉图。例8.1图13中的蜘蛛图d1表示没有一个元素既是哺乳动物又是昆虫,并且集合中至少有两个元素G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127137哺乳动物和昆虫。蜘蛛图d2表示只有两种昆虫不是哺乳动物。MmmnlseMcatmmnlsectsd1d2图十三. 两张蜘蛛图。在上面的例子中,spider表示元素的存在,称为存在性spider。一些蜘蛛图系统使用给定的或恒定的蜘蛛[26]。常量蜘蛛总是被标记的,类似于一阶逻辑中的常量。 我们在这里注意到,常量蜘蛛的语义和常量序列的语义(用于欧拉/维恩图)是不同的:两者都表示特定的个体,但在图中,具有不同标签的常量序列不一定表示不同的个体,而具有不同标签的常量蜘蛛确实表示不同的个体。tMsammCaltsDsogsCatswe bwe bd1d2d3tMsammCaltsDsogsCatsd4d5d6见图14。蜘蛛图与不断蜘蛛。例8.2图14中的图d1、d2和d3都包含常数蜘蛛(常数蜘蛛是一个带有正方形节点的标记树图d1表示web要么是猫要么是狗,但不是两者都是。图d2表示web是一只猫和一种哺乳动物,所有的猫都是哺乳动物。从d1和d2的连接我们可以推断web是猫而不是狗,用d3表示。相比之下,从包含存在蜘蛛(存在蜘蛛是一个具有圆形节点的树)的d4和d5,我们不能推导出d6。对于常数蜘蛛来说,选择方形节点,对于存在蜘蛛来说,选择圆形节点是没有意义的。Do g sCawe bDo g sCa138G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127一BC有许多蜘蛛图系统,在[26]中,提出了一个健全但不完整的蜘蛛图系统,其中包括常数蜘蛛但不包括存在性蜘蛛。8.1SD1图表SD1系统是第一个被证明是健全和完整的蜘蛛图系统[24,32]。SD1不包括常量蜘蛛,但包括存在性蜘蛛。在SD1中,存在性蜘蛛不能将节点放置在阴影区域中。因此,SD 1图扩展了Venn-II系统,允许在集合的基数上设置下限SD1系统中的所有图都基于维恩图而不是欧拉图。例 8.3 图 15 是 一 个 SD1 图 。 它 表 示 C=π , |U− ( A<$B<$C ) |≥2 ,|A∩B|≥1and|一|≥2,其中U是全称集。图15. SD1图表。Molina区分了抽象语法和具体语法[32],在[20,21]中分别称为类型语法和标记语法。具体语法捕获的是一个图的物理表示,而抽象语法是一个具体图的数学描述。这在图论中有一个类比。 图被定义为一组顶点和一组边,就像抽象语法一样。图在平面上的嵌入类似于具体的语法.分离出这两个层次的语法克服了[38]中提出的关于应用推理规则后图的良构性的问题Molina提出了抽象语法克服的其他问题,[32]第88-89页:Shin引入了许多概念,例如图的所有区域的集合,这似乎表明需要一个抽象语法来为她的图解系统增加精度。...抽象的语法将提供精确性,并将在符号的不同方面实现正式性。例如,这将通过推理规则的形式描述来感知,在推理规则中,我们可以安全地忽略某些方面,这些方面对于预期的含义来说是不需要的当为SD1或更有表现力的符号构建工具时,这种区别也会带来明显的好处,这些符号可能会在不久的将来扩展这个系统。对于图形用户界面的设计,具体的语法将发挥核心作用,而抽象的语法将发挥核心作用。语法将是实现符号演算的指导方针G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127139一BBSwoboda和Allwein使用有向无环图(DAG)作为欧拉/维恩图的抽象表示[48]。DAG转换用于检查推理步骤的正确性。SD1的不同之处在于推理系统本身是在抽象层次上定义的,而不是在具体层次上。具体层次纯粹用于可视化抽象图。例8.4图15中的具体SD1图被称为酉diagram,并有以下抽象描述。(i) C ={c 1,c 2,c 3}是一组等高线。边界矩形不是C的元素。(ii) Z =P C是区域的集合。(iii) Z ={{c3},{c 1,c 3},{c 2,c 3},{c 1,c 2,c 3}}是阴影区域的集合。(iv) R =P Z − {\displaystyle {Z}}是区域的集合。(v) R =P Z −{}是阴影区域的集合。(vi) L={A,B,C}是等高线标签的集合。(vii) S={s 1,s 2,s 3,s 4}是一组蜘蛛。(viii) η:S → {r ∈ R:r <$Z(d)=}是一个函数,它返回每个蜘蛛的栖息地,定义为η(s1)={},η(s2)={},η(s3)={{c1,c2}}和η(s4)={{c1},{c1,c2}}。(ix) l:C → L是一个函数,它返回由l(c 1)= A,l(c 2)= B和l(c3)= C定义的每个轮廓的标签。使用这种抽象语法,具体的酉图具有非唯一的抽象。例如,在具有一个轮廓、没有蜘蛛和阴影的具体图中,轮廓的任何单个元素集C(连同区域集等)将作为抽象描述而出现。抽象酉图在[32]的第63-64页中定义,并形成复合图和多重图的构建块。复合图是一组酉图,而复图是一组复合图。例8.5在图16中,{d1,d2}是一个复合图,{{d1,d2},{d3}}是一个多图。d1d2d3图16. 一个多图。从语义上讲,不同的蜘蛛代表不同元素140G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127B阴影区域表示空集。复合图D的语义是图中酉图的语义的析取,D.对于一个多图,即图,语义是图中复合图的语义的合取。因此,多重图是合取范式。莫利纳也将“图”定义为一个假的酉图[32]。这允许在定义推理规则时,将不满意的图替换为不满意的图为系统。他为SD 1定义了12个合理的推理规则,类似于Venn-II的规则,并证明这是一个完整的集合。8.2SD2图表在SD1中,蜘蛛不允许将节点放置在阴影区域中。因此,SD1图可以表示集合的基数的有限下界,集合是空的,但缺乏表示集合的基数的任意有限上界的设施。SD2系统解决了这个问题,通过允许蜘蛛将节点放置在阴影区域来扩展SD1。在阴影区域中,所有元素都由蜘蛛表示,允许在集合的基数上放置任意的有限上限例8.6图17是SD2图,而不是SD1图。有两个节点的蜘蛛表示存在一个在B或U-B中的元素。 在第一种情况下,|B|= 1,在后一种情况下,|= 0。|= 0. 图表表明,|U |≥ 2,|U − B| ≥ 1且|B| ≤ 1。图17. SD2图表。现在我们概述SD2的两个推理规则。虽然这些规则是在抽象层次上具体化的,但我们将陈述莫利纳给出的非正式的具体层次的定义。完整的规则集的抽象描述可以在[32],第150-157页中找到。蜘蛛的消失我们可以从任何一个完全没有阴影的区域中抹去蜘蛛.例8.7我们可以消去图18中d1中栖息在(A<$B)−C上的蜘蛛s,并推导出d2。图d1断言(除其他事项外),|≥ 1。| ≥ 1. 删除%s将丢失此基数信息。 注意G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127141一BC一BC一BCCB一CB一删除(A<$C)−B中的蜘蛛不是一个有效的推理步骤:从d1我们不能得出C=C。d1d2图18. 删除蜘蛛。分裂蜘蛛。设d是幺正图,其中蜘蛛s接触两个不相交区域r1和r2的每个区域。设d1和d2是两个酉图,它们是d的副本,除了都不包含s,但每个都包含一个额外的蜘蛛,其栖息地是d1中的r1和d2中的r2。然后d可以用复合图{d1,d2}代替。这个规则是可逆的,也就是说,{d1,d2}可以被d代替。例8.8在图19中,d中的蜘蛛断言A−C或AC中存在一个元素。我们可以拆分这个spider并将d替换为{d1,d2}。第一天第二天图19. 分裂蜘蛛。8.3ESD2图表ESD2系统通过允许基于欧拉图(而不是限制为维恩图)和使用额外的语法来扩展SD2系统[32]。例8.9图20中的图表是ESD2图表。这个图包含一个连接,它是一对平行的直线段,在A内的蜘蛛和居住在图中所有区域的蜘蛛之间。 领带允许我们表达,如果由领带连接的蜘蛛表示的两个元素x和y都满足x,y∈A-B,那么这些蜘蛛表示同一元素的存在。图中还包含一条链,这是一条波浪形线段,位于B中的蜘蛛和整个图中的蜘蛛之间。该串表明,如果两个元素x142G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127AB和y,由由串连接的蜘蛛表示,都满足x,y∈B−A,那么它们可以表示相同的元素。该图表示AB=,<$x1<$x2<$x3·x2∈A<$x3∈B<$(x1∈A<$x1= x2)。图20. ESD2图表。ESD2并不比SD2更有表现力。ESD2的推理规则是SD2的推理规则以及完整性所需的进一步规则。ESD2的完备性证明是SD2完备性证明的一个8.4更多蜘蛛图系统虽然ESD2系统允许基于欧拉的图,但使用ESD2图进行推理可能会产生不必要的冗长证明:首先转换为SD2形式,然后推理并转换回欧拉形式的需求并不理想。在[27]中,SD2系统被修改为允许基于欧拉的图。 我们将把这个扩展系统称为SD3。SD3的所有推理规则都在(抽象)欧拉图级别上运行。此外,SD3删除了对合取范式的限制(在SD2中强加的)。SD3是我们回顾过的第一个推理系统,它允许使用“and”和“的任意连接‘or’如果d1和d2,那么d1≠d2,d1≠d2。已经证明,SD3 在表达能力上等同于具有等式的一元一阶逻辑(MFOL=)[43,44]。将SD3图转换成逻辑句子的任务,从而表明蜘蛛图最多与MFOL=一样具有表达力,是很简单的。在[44]中,证明了对于MFOL=中的每个句子S,存在一个有限的模型集,可以用来对S的所有模型进行分类。每个分类模型都有一个有限域,可以用来构造一个图。所有这些图的析取在表达上等价于S。下面的例子说明了这个想法。例8.10设S为句子xA(x)xA(x)。S有四个分类模型,它们产生了图21中的d1、d2、d3和d4。G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127143一CB一CB一一一一d1d2d3d4图21.从模型构建图表。图d1<$d2<$d3<$d4在表达上等价于S。这不是人们会与S联系在一起的Venn-II图不能表示一个特定的属性对一个唯一的元素成立:x(A(x)因此,SD 3比Venn-II适当地增加了表现力。已经证明,扩展SD3以包括常量蜘蛛并不会导致表达能力的增加[42]。目前正在进行工作,以扩展SD3,以包括投影轮廓[28]。投影轮廓[15,16]允许我们表示集合之间的部分关系。例8.11图22中的图d1包含一条标为B的投影等值线它表示A和C是不相交的,并且A<$B只包含一个元素。图d2在语义上等价于d1。预计轮廓减少了区域的数量。d1d2图22. 描绘了投影的轮廓。在一个没有投影的图中,要说明两个集合之间的关系,就需要存在区域,而在有投影的情况下,某些区域就不需要存在。自动定理证明器已经开发了蜘蛛图使用直接[11]和启发式方法[8,9]。将自动生成的证明作为具体图的序列呈现给用户依赖于从抽象图自动生成具体图。在[7]中,作者描述了一种从抽象图生成具体欧拉图的算法。这些自动生成的具体diagram的布局可以使用度量来改进,以测量布局质量和hill144G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127提高攀登技术的质量[10]。这项工作在[34]中得到了扩展布局技术已经扩展到允许以这样的方式绘制给定的抽象图,即它看起来类似于另一个具体图[36]。这在自动定理证明中很重要,因为在应用推理规则(发生在抽象层次)后,我们希望自动生成的具体图看起来与前提相似9约束图由Kent [29]介绍,约束图是为软件工程师设计的,用于在面向对象系统中指定形式约束。图23中的约束图指定没有成员是视频,并且对于每个成员,所有过去的租赁(其中至少有一个)都是视频。形式化的数学方法还没有被软件工程所采用,MemberVsideosp a st_re nt al s图23岁使用约束图对软件系统进行因为他们倾向于不喜欢使用数学符号[29]。然而,有一个普遍使用的图表建模软件系统。约束图的语言通过添加进一步的语法元素扩展了蜘蛛图的语言,包括箭头、通用蜘蛛(由箭头表示)和派生轮廓(未标记的轮廓)。箭头及其源、目标和标签表示二元关系的属性。万能蜘蛛代表万能量化。导出的轮廓必须是箭头的目标,并且当域被限制到源时表示关系的图像。箭头源可以是蜘蛛,轮廓和衍生轮廓。目标可以是存在蜘蛛、常量蜘蛛、轮廓和派生轮廓。约束图增加了蜘蛛图的表达能力,能够表达软件工程师所需的复杂约束。例9.1图24中的约束图表示<$x∈A·{x}.f=B<$A<$B=<$G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127145一Bƒ一ƒ其中{x}.f是x在关系f下的关系图像,即{x}.f={b:(a,b)∈({x} ×U)<$f}.图24. 约束图。例9.2图25中的约束图包含一个通用蜘蛛和一个导出轮廓。该图表示,<$x∈A·{x}.f<$U−A图25.包含通用蜘蛛的约束图。上面两个例子中的约束图是明确的,易于解释。当试图将约束图形式化时,出现的一个困难与量化器的排序有关。 图解符号的非线性引起了这些顺序问题:通常没有明确的起点来解释图表,即使一旦阅读已经其中许多困难在[12]中提出,并在[14]中进一步讨论。例9.3在图26中,约束图有两种可能的解释:和<$x∈A<$y ∈U−A·{x}.f={y}y ∈ U − A146G. Stapleton/Electronic Notes in Theoretical Computer Science 134(2005)127一ƒ它们在语义上并不等同。例如,第一种解释,在存在性蜘蛛之前读取通用蜘蛛,有一个空的模型4,而第二种解释没有。图26. 解释歧义:量化器的排序。要解释一个酉图,需要进行依存分析:某些句法成分的解释有时取决于对其他句法成分的第一次解释。在[4]中,给出了一种阅读算法,该算法涉及对图的句法成分进行详细而复杂的依赖分析。这种依赖性分析允许在解释图时指定图的哪些语法组件需要排序产生部分有向依赖图,其指示哪些语法元素在语义上相互依赖。从图的依赖图中,可以生成读取树,并且每棵树都会产生图的语义解释。在[5]中可以找到从依赖图和图构造所有读树的算法。因此,我们可以将约束图看作是区域(有些是阴影)、蜘蛛和箭头以及阅读树的集合。例9.4图27中的图d有依赖图G(d)。蜘蛛s必须在标记为g的箭头之前被类似地,t必须读在标记为f的箭头之前,给出从t到f的有向边。 T的解释和标记为g的箭头是相关的(g所指向的导出轮廓定义了t的栖息地),但我们可以选择是先读t后读g,还是先读g后读t。 在G(d)中,这个选择由t和g之间的无向边表示。依赖图用于构造读树R(d)ford。两个这样的读树是R1(d)和R2(d)。如果G(d)中存在从a到b的有向边,则R(d)中必存在从a到b的 如果a和b通过如果G(d)中有一条边,则一定存在从a到b或从b到a的路径。对于平面平铺条件,读取树还具有标记为PTC的根节点。 平面平铺条件断言,在大多数一阶逻辑的处理中,空模型是不允许的,但在约束图的应用领域(即软件工程),允许空模型是很重要的。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功