命题逻辑中一类正则标准矛盾体的构造与复合

归结原理是自动推理中一种简洁、可靠且完备的推理规则，标准矛盾体分离演绎理论是二元归结的一个延拓。矛盾体的结构非常复杂，现有的矛盾体种类和生成策略较少。针对该问题，文中基于命题逻辑的标准矛盾体分离演绎理论，首先通过复合两个或多个正则标准矛盾体，得到了生成新矛盾体的多个复合策略；其次，提出了一类特殊标准矛盾体结构——复合正则标准矛盾体，丰富了矛盾体的结构特征；然后讨论了复合得到的新矛盾体不同子句的可扩充性，进而得到相应的文字添加策略；最后，提出了矛盾体的生成算法，为进一步在计算机上实现新矛盾体的生成提供了参考。     

由一阶逻辑公式得到命题逻辑可满足性问题实例

命题逻辑可满足性(SAT)问题是计算机科学中的一个重要问题.近年来许多学者在这方面进行了大量的研究,提出了不少有效的算法.但是,很多实际问题如果用一组一阶逻辑公式来描述,往往更为自然.当解释的论域是一个固定大小的有限集合时,一阶逻辑公式的可满足性问题可以等价地归约为SAT问题.为了利用现有的高效SAT工具,提出了一种从一阶逻辑公式生成SAT问题实例的算法,并描述了一个自动的转换工具,给出了相应的实验结果.还讨论了通过增加公式来消除同构从而减小搜索空间的一些方法.实验表明,这一算法是有效的,可以用来解决数学研究和实际应用中的许多问题.     

命题逻辑可满足性问题的算法分析

1 引言可满足性问题(以下简称SAT)是问:对于一个命题逻辑公式,是否存在对其变元的一个真值赋值使之成立?这个问题在许多领域都有非常重要的意义,其快速求解算法的研究成为计算机科学的中心课题之一。例如在机器定理证明领域,某命题是否是一个和谐的公理集合的推论,这个问题归结为该命题的反面与该公理集合一起是否是不可满足的。通过量词消去技术和Herbrand定理的作用,谓词逻辑公式的不可满足性可以归结为命题逻辑公式的不可满足性。在知识库维护中,当知识以逻辑公式的形式表达时,知识库的一致性检查可以归结为命题逻辑公式的可满足性。在开放逻辑中,新事实是否与已有的知识矛盾,当遇到事实反驳时如何求得最大和谐的知识集,这些问题最后都要归结为命题逻辑公式的可满足性。1971年Cook首次证明了SAT是NP-完全的,从而大量的计算问题都可以归约到SAT。正是由于SAT的重要地位,各国学者对它进行了广泛而深入的研究。     

命题逻辑的子句集中文字的分类

检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类,并分别给出其定义。讨论3种文字与无冗余等价子集的性质,给出其等价子集的等价描述方法。得到题逻辑的子句集中必需文字、有用文字和无用文字的判定方法,借助子句集的可满足性得到3种文字与子句集的可满足性的等价条件。上述结果对命题逻辑中文字属性的判断提供了多种可选择方法,同时为命题逻辑公式的化简奠定了理论基础。     

格值命题逻辑系统中广义文字的正规性

基于格蕴涵代数的格值命题逻辑系统能定性地刻画不可比较性和不精确性。广义文字是该系统中α-归结自动推理的核心概念,是α-归结中的最基本单元。公式的正规性是α-归结原理中保持完备性的重要条件,其语义性质是公式形式的重要反映。从语义角度研究了广义文字的正规性,给出了两种典型正规公式F1→F2和(F1→F2)'的真值情况。为讨论广义文字的形式及其α-可归结性提供了理论基础。     

一类具有3种否定的模糊模态命题逻辑

对不同否定知识的认知、区分、表达、推理及计算是模糊知识研究处理的一个基础。具有矛盾否定、对立否定和中介否定的模糊命题逻辑形式系统FLCOM是一种能够完整描述模糊知识中的不同否定及其关系与规律的理论。基于FLCOM和中介模态命题逻辑MK,提出一类具有3种否定的模糊模态命题逻辑MKCOM及其扩充系统MTCOM,MS₄COM和MS₅COM;讨论了MKCOM的语义和语法解释,并证明了MKCOM的可靠性定理和完备性定理。     

利用命题逻辑最大可满足性的冗余通孔最优插入方法

在纳米尺度的集成电路设计中,冗余通孔插入是减轻通孔失效造成良率降低问题的常用技术.文中将最优冗余通孔插入问题规约到命题逻辑最大逻辑可满足性(maximum satisfiability, Max SAT)问题,并利用完备求解器求取最优解.MaxSAT问题是一个NP困难问题,采用2种方法来降低求解难度;一是预选取方法,将提前确定的不与其他通孔产生冲突的冗余通孔作为部分解来降低问题的规模;二是分治法,根据连通分量将原问题划分成多个子问题分别求解,降低求解的复杂度.同时,从理论上证明这2种方法能够保证解的最优性.在2019年国际物理设计研讨会(ISPD)举办的详细布线比赛基准测试集上进行实验的结果表明,所提出的插入方法带来的时间开销不到详细布线时间的5%,算法的最优性保证了最大化解决插入冲突后的插入率,在所有可插入通孔中,冗余通孔的插入率为67%～87%.     

启发式方法生成命题逻辑可读证明

探讨了自动生成命题逻辑系统R的可读证明.采用试探法和自然推理法分别从前推和后推模拟人类思维求证,试探法根据推理规则将待证公式反向分解,自然推理法从假设出发根据推理规则生成新的公式.两种方法都实现了相干命题逻辑系统R的可读证明,并结合实现了混合证明.试探法和自然推理法是生成可读证明的有效方法,前推和后推两种思维方法也适用于其他逻辑系统的自动证明.     

一种基于消解的变量极小不可满足子公式的提取方法

变量极小不可满足(VMU)问题是极小不可满足(MU)问题的一个扩充和延伸.着重研究VMU子公式的提取算法.首先从理论上比较MU和VMU的基本性质,并分析了目前流行的MU子公式提取算法.研究Davis-Putman-消解的基本性质,给出一个判定变量极小不可满足公式的充分必要条件,进而提出一个基于消解的VMU子公式提取算法.此算法可以使用ZBDDs压缩存储消解式,并实现单步多重消解.     

中介命题逻辑一种新的无穷值语义模型及意义

中介逻辑ML（Medium Logic）,自建立了它的三值语义模型后,ML就被许多学者认定为三值逻辑。对于中介逻辑核心理论的中介命题逻辑系统,潘给出了一种无穷值语义模型,并证明了中介命题逻辑在此模型下具有可靠性与完备性。在此基础上,给出一种真值域为[0,λ)∪(λ,1](λ∈(0.5,1))的无穷值语义模型,研究了它的性质,证明了中介命题逻辑在该模型下也具有可靠性与完备性。新模型的存在进一步表明,认定中介逻辑是一种三值逻辑的理由是不充分的。新模型不仅反映了中介逻辑的基本思想,而且为中介逻辑在其他领域的应用提供了基础。     

中介命题逻辑的一种无穷值语义模型及其意义

中介逻辑(medium logic, ML)自建立了它的三值语义模型后,ML就被许多学者认定为三值逻辑.对于中介逻辑核心理论的中介命题逻辑系统,给出一种真值域为[0,1]的无穷值语义模型,研究了它的性质,并证明了中介命题逻辑在此模型下具有可靠性与完备性.此模型的存在表明,认定中介逻辑是一种三值逻辑的理由是不充分的.该模型更适合反映中介逻辑的基本思想,而且为中介逻辑在其他领域的应用提供了一个基础.     

基于建模与推理的命题逻辑教学方法研究

面向计算机科学领域的教学,提出基于建模与推理的命题逻辑教学方法,说明该方法的教学步骤,从一个案例出发,说明如何引导学生学习使用命题逻辑进行建模,推理模型的性质,同时分析该方法在命题逻辑教学中的效果。     

一种新的基于扩展规则的定理证明算法

基于扩展规则的定理证明方法是一种与归结方法互补的新的定理证明方法,首先通过对扩展规则的深入研究,给出了扩展规则的一个重要性质,设计并实现了该性质的判定算法.此外,从理论上分析及证明了该判定算法的时问和空间复杂性.基于此,提出了一种新的基于扩展规则的定理证明算法NER,将判定子句集可满足性问题转化为一系列文字集合的包含问题,而非计数问题.实验结果表明,算法NER的执行效率较原有扩展规则算法IER和基于归结的有向归结算法DR有明显提高,有些问题可以提高两个数量级.     

离散数学中命题逻辑的应用研究

离散数学又称为计算机数学,它是研究离散量之间的科学.数理逻辑是离散数学的四大模块之一.为了满足自动化推理的客观需要,人类逐渐将逻辑学运用到了计算机科学领域.回顾人类计算机科学的发展历程,可以清晰地看到逻辑学在计算机科学中所奠定的理论基础和积极的推动作用,在计算机硬件设计和软件设计中的应用都非常突出.逻辑学是研究思维规律...     

■ukasiewicz命题逻辑系统中有限命题集的约简理论

在n值■ukasiewicz命题逻辑中提出了命题集Γ的约简理论,引入由命题集Γ所诱导的形式背景的概念,从Γ及其子集的关系出发给出了n值命题逻辑中有限命题集Γ约简的判定定理以及求Γ约简的方法。说明了无穷值■ukasiewicz命题逻辑中命题集Γ的约简可转化为n值情形。     

具有三种否定的模糊命题逻辑形式系统FLCOM的λ-归结

考虑到模糊逻辑中定理自动证明的重要性以及目前主要研究具有一种否定的模糊逻辑的归结原理,文中对具有三种否定(矛盾否定、对立否定和中介否定)的模糊命题逻辑(FLCOM)的归结原理进行研究.基于FLCOM的一种无穷值语义解释提出λ-可满足的和λ-不可满足的概念.将λ-归结方法引入FLCOM,给出FLCOM的λ-归结演绎定义,讨论FLCOM的λ-归结原理,并证明FLCOM的λ-归结方法的完备性.基于λ-归结方法和已证明的结论给出实例以佐证文中λ-归结方法和结论的正确性和可行性.因此,在FLCOM范围内可判定任一模糊命题公式是否是λ-可满足的或λ-不可满足的.     

一种约简动作变元的命题规划编码方式

基于动作的编码方式是2006年国际规划竞赛中著名的最优规划系统SATPLAN2006采用的一种基于约简状态变元的命题规划编码方式.依据基于动作的编码方式,提出一种基于约简动作变元的自动命题规划编码方式:基于命题的编码方式.首先分析构造新编码方式的理论依据,提出基于命题的编码方式的编码组成,证明其有效性,并描述某些公理的具体实现细节,最后分析其与已有几种编码方式的不同之处.在SATPLAN2006中实现了基于命题的编码方式,利用国际规划竞赛选用的标准测试问题予以测试,并分析其与基于动作的编码方式等两种极端编码方式的求解特性.实验结果表明:对于顺序规划问题域,基于命题的编码方式更有效,而对于并发规划问题域,基于动作的编码方式更有效.     

一种求解布尔不可满足子式的局部搜索算法

解释布尔公式不可满足的原因在众多领域都具有非常重要的理论与应用价值,而不可满足子式能够为公式不可满足的原因提供精确的解释,帮助应用领域的自动化工具迅速定位错误,诊断问题失败的本质缘由。近年来涌现了许多基于SAT求解器DPLL回溯搜索过程的完全算法,但关于不完全方法提取不可满足子式的研究相对较少。因此,本文提出一种采用启发式局部搜索过程从公式的不可满足性证明中求解布尔不可满足子式的算法。该算法根据公式的消解规则通过局部搜索过程直接构造证明不可满足性的消解序列,并融合了布尔推理技术以提高搜索效率;而后通过一个递归过程遍历证明序列从而得到不可满足子式。通过实验与贪心遗传算法进行对比,结果表明本文提出的算法优于贪心遗传算法。