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

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

关于并发系统分支互模拟关系发散性保持的研究

带发散性说明的分支互模拟是van Glabbeek和Weijland提出的一个概念,并被用来定义等价关系.该等价关系应该是最弱的一个发散性保持的并且满足分支互模拟性质的等价关系.然而在概念提出时并没有提供这些重要性质的证明,并且我们认为在原定义的基础上这个证明是不显然的.本文通过co-induction的手段利用染色迹的概念定义了着色完全迹等价,并证明该等价关系是最弱的一个保持发散的并且满足分支互模拟性质的等价关系.然后我们证明了着色完全迹等价关系和≈_b^△是相同的,因而补充了van Glabbeek和Weijland的工作,即证明了≈_b^△是最弱的一个保持发散的并且是满足分支互模拟性质的等价关系.     

格值模态命题逻辑及其完备性

文中以满足第一及第二无限分配律的完备格为工具,建立了格值模态命题逻辑的语义理论,并指出这种语义是经典模态命题逻辑语义理论及[0,1]值模态命题逻辑语义理论的共同推广.给出了QMR0代数的定义,并分别以Boole代数及QMR0代数为背景构建了Boole型格值模态命题逻辑系统B及QMR0型格值模态命题逻辑系统QML*,并证明了系统B及系统QML*的完备性.     

G?del n值命题逻辑系统的真度理论

首先在G?del n值命题逻辑系统中添加了新的连接词Δ,～,给出了G?del n值命题逻辑系统中命题公式间的真度、相似度和伪距离的定义;讨论了在该系统下它们的一些相关性质,并给出了相应的证明。     

可满足性问题全部解的求解算法

SAT问题在人工智能、计算机基础理论研究和人工智能等领域有着广泛的应用,近年来,证明该问题的可满足性取得了巨大的成功,但在求出SAT问题的所有解方面还有待进一步研究。利用一个简单的变换,将可满足性(SAT)问题转化为多项式形式,然后根据命题逻辑的性质以及多项式的性质,得到一个求解出SAT问题所有解的算法。实验结果显示该算法是有效和可行的     

基于k阶秩函数的线性赋值循环程序的终止性分析

循环程序的终止性是确保循环程序完全正确的必要条件。 如果给定的线性赋值循环程序不存在传统定义的线性秩函数,那么基于传统定义的秩函数终止性证明方法将失效。基于Aⁿx的精确计算,对传统的秩函数概念进行了扩展,提出了k阶秩函数的概念。使用RegularChains软件包给出了合成k阶秩函数的具体方法。实验结果表明,相比于传统定义的线性秩函数,k阶秩函数的适应范围更广。对于 不能用传统定义的秩函数证明其终止性的部分循环程序,可以基于k阶秩函数来证明,从而体现了所提方法的优越性。     

直觉模糊逻辑的（α,β）-广义锁归结方法

归结方法是定理自动证明的重要工具。为了简化直觉模糊命题逻辑的归结过程,基于直觉模糊命题逻辑归结原理的一般形式,提出了子句(αβ)-可满足和(αβ)-归结式的概念。研究了广义子句与其归结式的可满足性。在直觉模糊命题逻辑系统中给广义子句配锁,规定在做归结时各子句中被消去文字在该子句中的序号最小,由此建立了(αβ)-广义锁归结方法,并证明了该方法的可靠性和完备性。给出了直觉模糊逻辑的广义锁归结算法步骤,并通过实例说明了该方法的有效性。     

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

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

区间值度量空间的紧性和仿紧性

给出了区间值度量空间的概念,根据一般拓扑学中紧性的相关定义及其等价条件,证明了由区间值度量诱导的拓扑具有的紧性及其一系列等价关系,讨论了该诱导的拓扑空间具有仿紧性。     

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

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

Some properties of fuzzy reasoning in propositional fuzzy logic systems

In order to analyze the logical foundation of fuzzy reasoning, this paper first introduces the concept of generalized roots of theories in ?ukasiewicz propositional fuzzy logic ?uk, Gödel propositional fuzzy logic Göd, Product propositional fuzzy logic Π, and nilpotent minimum logic NM (the R₀-propositional fuzzy logic L^∗). Next, it is proved that all consequences of a theory Γ, named D(Γ), are completely determined by its generalized root whenever Γ has a generalized root. Moreover, it is proved that every finite theory Γ has a generalized root, which can be expressed by a specific formula. Finally, we demonstrate the existence of a non-fuzzy version of Fuzzy Modus Ponens (FMP) in ?uk, Göd, Π and NM (L^∗), and we provide its numerical version as a new algorithm for solving FMP.     

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

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

命题模糊逻辑系统中有限理论的弱相容度

推广了命题模糊逻辑系统中有限理论相容性的概念。以理论Γ是否同时推出命题A和命题┐A为基准点引进了有限理论弱相容度的新概念,讨论了其性质,并给出了判定它大小的一系列准则。     

Axiomatizations of t-norm based logics – A survey

In fuzzy logic in wider sense, i.e. in the field of fuzzy sets applications, t-norms got a prominent rôle in recent times. In many-valued logic, the ?UKASIEWICZ systems, the GÖDEL sytems, and also the product logic all are t-norm based systems. The present paper discusses the more general problem of the adequate axiomatizability for such t-norm based logical systems in general, surveying results of the last years. The main emphasis in the present paper is on propositional logic.     

逻辑系统Gn中理论的真度概念及其应用

首次在命题逻辑系统中引入理论的真度概念,使得真度的概念由公式的真度推广为公式集的真度,从而简化了发散度的概念;在逻辑系统G_n中讨论了理论Γ1、Γ2和Γ1∪Γ2的真度、相容度和发散度之间的关系。     

Natural Deduction for First-Order Hybrid Logic

This is a companion paper to Braüner (2004b, Journal of Logic and Computation 14, 329–353) where a natural deduction system for propositional hybrid logic is given. In the present paper we generalize the system to the first-order case. Our natural deduction system for first-order hybrid logic can be extended with additional inference rules corresponding to conditions on the accessibility relations and the quantifier domains expressed by so-called geometric theories. We prove soundness and completeness and we prove a normalisation theorem. Moreover, we give an axiom system first-order hybrid logic.     

Gdel区间值逻辑系统的广义拟重言式

吴洪博博士将王国俊教授在R0逻辑系统中的广义重言式理论推广到Gdel逻辑系统中,通过定义两个同构映射,得到其逻辑系统F(S)的一个分划。将这一理论推广到区间值模糊命题逻辑系统中,定义了两个新的区间同构映射,最终得到区间值逻辑系统F(S)的一个分划。     

An Institutional View on Categorical Logic

We introduce a generic notion of categorical propositional logic and provide a construction of a preorder-enriched institution out of such a logic, following the Curry-Howard-Tait paradigm. The logics are speci ed as theories of a meta-logic within the logical framework LF such that institution comorphisms are obtained from theory morphisms of the meta-logic. We prove several logic-independent results including soundness and completeness theorems and instantiate our framework with a number of examples: classical, intuitionistic,linear and modal propositional logic.     

Extended IF逻辑的命题演算系统

Extended IF 逻辑是一阶逻辑的扩张,其主要特点是可表达量词间的相互依赖和独立关系,但其命题部分至今没有得到公理化.基于Cirquent 演算方法,给出了一个关于Cirquent 语义(命题水平)可靠完备的形式系统.该系统能够很好地解释和表达命题联结词间的相互依赖和独立关系,从而使Extended IF 逻辑在命题水平得到了真正意义上的公理化.     

An algebraic study of Peterson’s Intermediate Syllogisms

Peterson’s Intermediate Syllogisms, generalizing Aristotelian syllogisms by intermediate quantifiers ‘Many’, ‘Most’ and ‘Almost all’, are studied. It is demonstrated that, by associating certain values V, W and U on standard ?ukasiewicz MV-algebra with the first and second premise and the conclusion, respectively, the validity of a corresponding intermediate syllogism is determined by a simple MV-algebra (in-)equation. Possible conservative extensions of Peterson’s system are discussed. Finally it is shown that Peterson’s bivalued intermediate syllogisms can be viewed as fuzzy theories in Pavelka’s fuzzy propositional logic, i.e. a fuzzy version of Peterson’s Intermediate Syllogisms is introduced.