SEMANTIC INTERPRETATION OF PREDICATE CALCULUS SYSTEM OF MEDIUM LOGIC ME~* AND ITS SOUNDNESS AND COMPLETENESS

Ⅰ. INTRODUCTIONThis note presents the semantic interpretation of predicate calculus system withequality symbol "=" of medium logic M E~* and its Soundness, Completeness, and Compact Theorem. In view of the characteristic of M E~*, when we construct

基于语义tableau的一阶逻辑自动定理证明

自动推理作为自动定理证明的扩展是人工智能研究的基础工作,许多重要的人工智能系统都是以推理系统为其核心部分,其中的tableau方法,由于具有通用性、直观性及易于计算机实现等特点,至今成为重要的自动推理方法之一。在tableau方法基础上,讨论了一阶逻辑中的自动定理证明理论,提出使用模型存在定理证明其可靠性和完备性的方法。同时也给出了带等词tableau方法的证明过程。

Verilog代数语义研究

给出了Verilog的代数语义.这是一个等式公理体系,它将Verilog语义特征通过代数规则简洁而准确地表达出来;并且这个代数语义相对于已经所作的操作语义模型来讲是可靠的,即所有的这些代数规则左右两边的进程在操作语义的观察模型下都是互模拟的.研究了此代数语义的相对完备性,即参照前面的操作语义模型,相对于扩展Verilog语言的一个子集而言,此代数语义是完备的.即所有符合这样语法的程序,如果它们是互模拟等价的,那么它们同样可以在所提出的代数系统中被推导相等.在完备性证明过程中,采用范式方法,即构造一种语法上特殊的程序,任何属于上述子集中的一个程序通过该代数规则都能够被转化为范式程序,而且范式程序在操作语义模型下是互模拟的当且仅当它们是语法相同的.上述结果具有重要的理论意义,因为现有的进程代数理论主要是针对管道通信并行语言而展开的,而对于像Verilog这种以共享变量通信为基础的复杂并行语言研究还是比较少的,对此类复杂的基于共享变量的并行语言的进程代数理论研究提出了一种通用、有效的方法.

语义树方法及其可靠性和完备性

Ａｎｄｒｅｗｓ在《ＡｎＩｎｔｒｏｄｕｃｔｉｏｎｔｏＭａｔｈｅｍａｔｉｃａｌＬｏｇｉｃａｎｄＴｙｐｅＴｈｅｏｒｙ：ＴｏＴｒｕｔｈＴｈｒｏｕｇｈＰｒｏｏｆ》一书中给出的语义树方法是一种能直接适用于句子集的反驳方法，但其中关于语义树方法的可靠性和完备性定理（３２０１）及其证明是错误的。本文通过例子指出并纠正了这一错误，同时对修正后的可靠性和完备性定理给出了详细的证明。

以目的与背景知识为双条件的逻辑AKC

首先,我们构造以目的和背景知识为双条件的条件句系统AKC,给出它的一些证明论结果。其次,我们引入有序邻域语义,给出描述AKC的特征公理和推理规则的框架条件,证明AKC相对这些框架条件是框架可靠的。最后,我们证明AKC相对这些框架条件也是框架完全的。

一个适于更新语义的涉景条件句逻辑

传统条件句逻辑研究的条件句没有明显提述条件句的背景.本文提出了一种明显提述背景的条件句逻辑BCS,并证明了该系统相对于Veltman提出的更新语义的模型可靠性和模型完全性.

描述逻辑SHIQ的ABox一致性判定算法

为判定描述逻辑SHIQ的ABox一致性,提出一种Tableau算法。给定TBox T、ABox A和角色层次H,通过预处理将A转换成标准的ABox A’,按照特定的完整策略将一套Tableau规则应用于A’,从而不断地对A’进行扩展,直到将其扩展成完整的ABox A’’为止。A、T和H一致,当且仅当算法能产生一个完整且无冲突的ABox A’’。该算法采用的阻塞机制能防止Tableau规则被无限次执行,避免多余的规则应用。通过证明Tableau规则的执行次数为有限次,确认算法的可终止性。通过证明由A’’能构造一个同时满足A、T和H的解释,确认算法的合理性。通过证明Tableau规则的执行不会破坏A’与H的一致关系,确认算法的完备性。

描述逻辑SHIN的ABox一致性判定算法

为了判定描述逻辑SHIN的ABox一致性,提出了一种Tableau算法。给定TBox T、ABox A和角色层次H,该算法通过预处理将A转换成标准的ABox A′,按照特定的完整策略将一套Tableau规则应用于A′,直到将它扩展成完整的ABox A″为止。A与T和H一致,当且仅当算法能产生一个完整且无冲突的ABox A″。算法所采用的阻塞机制可以避免Tableau规则的无限次执行,该机制允许一个新个体被在其之前创建的任意新个体直接阻塞,而不仅仅局限于其祖先。通过对算法的可终止性、合理性和完备性进行证明,算法的正确性得以确认。

刻画动态否定的逻辑

通常的逻辑只涉及静态否定的概念。文章建立了几类动态系统来刻画动态否定概念,并引入相应的语义,然后证明这些系统相对这些语义是可靠和完全的。

厘清形式系统的几个概念

一致性、可靠性、完全性、不完全性是形式系统的基本概念。在厘清上述概念的基础上,对其间相互关系的梳理使我们明晰了哥德尔完全性定理和不完全性定理的正确含义,以及其成立所需的条件。最后,依据上述分析,指出形式系统存在漏洞和局限性。同时,也看到了形式化方法的弊端和形式化的限度。

他连A都知道——认知逻辑EK1-EK3

首先,我们构造认知系统EK1-EK3,给出它们的一些证明论结果。其次,我们引入邻域语义,给出EK1-EK3的特征公理和规则的框架条件,证明EK1-EK3相对这些框架条件分别是框架可靠的。最后,我们证明EK1-EK3相对这些框架条件分别是框架完全的。

公式分层的谓词模态逻辑

由于必然模态词的引入,谓词模态逻辑的公式在一个可能世界中的真假值可能依赖于其可达的可能世界.在谓词模态逻辑中存在个体跨可能世界相等问题.针对这一问题,Lewis提出了对应物理论,并且在对应物理论中用对应物关系来表示个体跨可能世界相等.但是,当一个对象具有一个以上的对应物时,谓词模态逻辑中的跨可能世界相等关系无法与对应物关系建立一一对应.通过限制谓词模态逻辑中全称量词?的范围,给出了一种公式分层的谓词模态逻辑.它是谓词模态逻辑的一个子逻辑,并且其语言与谓词模态逻辑的语言是相同的.但其公式是分层定义的,使得?可以出现在的范围内,并且不能出现在?的范围内.由于任意形如?x?(x)的表达式都不是该逻辑的公式,以量词开头的公式在一个可能世界w中的真假值只依赖于w,该逻辑避免了个体跨可能世界相等问题.给出了该逻辑的语言、语法和语义,并证明了该逻辑是可靠的和完备的.

一个刻画句子顺序的逻辑

更新语义认为句子的意义在于改变了主体的信息状态。Veltman用更新语义刻画了一个关于认知的可能性的模态词might,S5系统相对于Veltman提出的更新语义是可靠的和完全的。在更新语义的基础上可以用形如φ;ψ公式刻画句子先φ后ψ的次序,对应的公理系统S5S也是可靠的和完全的。

GSOS算子下共变-异变模拟的公理刻画

进程的行为理论是进程演算研究的核心内容之一,其侧重于讨论进程间的行为等价和模拟关系。共变-异变模拟(Covariant-Contravariant Simulation,CC-模拟)的概念是对经典(互)模拟概念的推广,它通过区分动作类型,刻画了规范与实现对系统主动、被动和通讯动作在精化关系中的不同要求。行为关系的(前)同余性和公理刻画是进程演算代数特征的集中体现,它们对规范及实现的分析和推理至关重要。一般而言,行为关系(前)同余性的证明和公理系统的构造需要基于不同进程演算系统的结构化操作语义(Structural Operational Semantics,SOS)分别展开。为了避免这类研究工作中的重复劳动,学术界针对一般化SOS规则形式的元理论开展了研究,GSOS是其中被广泛研究的规则形式之一。文中在考量了动作类型的基础上,基于CC-模拟对GSOS规则形式做出扩充,提出了CC-GSOS规则类型,证明了CC-模拟相对于CC-GSOS算子具有前同余性,并给出了在这些算子下CC-模拟的可靠完备公理系统的一般性构造方法。

适于认知系统和条件句系统的更新语义(英文)

更新语义是一种刻画单个主体信息变化的语义。本文我们首先提出由Veltman[1]提出的更新语义的某些变种,从而证明某些认知系统和条件句系统相对这些变种有模型可靠性和模型完全性。其次,我们提出带两分定义的更新语义的某些变种,从而证明某些认知系统和条件句系统相对这些变种有框架可靠性。

三段论系统的一个关系解释

亚里士多德的三段论在莱布尼茨时代就具有了一个算术意义上的解释,但该解释中的整除关系实际上可以更进一步抽象成为一个偏序关系。借助于偏序关系就足以表达出四种直言命题,并可以证明该解释对于卢卡西维茨的三段论句法系统具有可靠性和完全性。