缺省理论的简化

缺省理论△=(D,W)中的缺省规则集D,是该理论的不确定因素.如果能去掉一些缺省规则而又不影响该理论的延伸,则就在一定程度上简化了该理论.本文证明了关于规范缺省理论的延伸的若干性质,利用这些性质,我们可以把某些规范缺省理论在一定条件下得以化简,有的甚至可以把它们化为一阶逻辑理论.     

缺省推理中的三个定理

本文证明了缺省推理中的三个定理.定理1表明了缺省推理的非单调性这一特点.定理2的实际意义在于,在一个封闭规范缺省理论(D,W)中,只要W能推出D中某些缺省的结论,则可以把这样的缺省规则从理论中删除,所得到的较小的缺省理论其延伸仍与原来缺省理论一样.尤其是若W能推出D中所有的缺省规则结论,则(D,W)的延伸就是W,这就是本文推论的结论.     

不协调知识的缺省推理

提出了一个新的缺省推理理论,称为双缺省理论,使得缺省逻辑在四值语义下能够同时处理不协调的知识而不导致扩张的平凡性.为此,定义了命题公式的正变换和负变换,以便分离一个文字与其否定的语义联系.大多数关于缺省逻辑的定理都可以在双缺省逻辑下重建,证明了双缺省逻辑是缺省逻辑在不协调情形下的一般化.提供了一种方法使得超协调逻辑能够获得类似经典逻辑的推理能力.     

若干限制形式的缺少推理的复杂性

该研究判定一字是否出现在缺省理论〈Ｄ,Ｗ〉的某一扩张中的复杂性,其中,Ｄ是一种Ｈｏｒｎ缺省规则,而Ｗ是ｄｅｆｉｎｉｔｅ公式或Ｂｉ－Ｈｏｒｎ公式。     

利用格论研究缺省推理

本文提出了一组转换规则,使用这组转换规则可以把缺省规则转换成扩展规则,然后使用这些扩展规则去扩展缺省理论的初始逻辑公式集合,在这些扩展规则的基础上,我们提出了缺省格(default lattice)的概念,证明了缺省理论的外延刚好对应于它的缺省格的相容性集合的D-极大值,因此可以使用缺省格求出缺省理论的所有外延.     

子句型自相容缺省理论的扩张

自相容缺省理论是一种颇具优良性质的特殊缺省理论,从子句着手是一般逻辑揄常用的方法,文中Ｒｅｉｔｅｒ缺省理论和张明义的自相容缺省的理论的研究基础上,进一步研究了子句型闭自相容缺省理论,文中首先给出了自相容缺省理论的扩张个数的单调性定理,然后将Ｒｅｔｅｒ关于正规缺省理论的证明论推广到自相容缺省理论,得出了自相容缺省理论的缺省证明、自顶向下缺省证明和信念个性的相关定理。     

基于缺省理论演绎的规则型T—R程序生成系统

本文建立子基于缺省理论的时态逻辑公式演绎系统。演绎过程除了使用一阶逻辑理论外，还采用了缺省理论来处理用户说明以及系统中知识不完全的问题。这种演绎系统演绎公式的过程也就是生成的过程，只要被演绎的公式序列能描述待生成的程序即可。     

基于四值语义的缺省逻辑

基于公式变换,给出一组缺省理论的变换方法,将命题语言L中的缺省理论变换到对应的命题语言L^-＋中,保证了所得到的缺省理论的所有扩张均不平凡,并通过一种弱变换可同时保证缺省扩张的存在性．为缺省理论定义了各种四值模型,使得缺省逻辑具有非单调超协调推理能力,并证明了L^-＋中的缺省扩张与L中缺省理论的四值模型之间具有一一对应关系．四值模型描述了公式变换的语义,基于四值语义的缺省推理通过缺省理论的变换技术能在标准的缺省逻辑中实现．     

一种带缺省推理的描述逻辑

该文提出了一种新的带缺省推理的描述逻辑，它以描述逻辑为主要框架，对单调逻辑和非单调逻辑进行了整合，但又避免了一般缺省逻辑的困难．基于带缺省推理的描述逻辑，构建了一种同时具有Tbox，Abox和缺省规则的知识库系统，研究了带缺省推理的描述逻辑的可满足性、缺省可满足性、概念包含、缺省包含以及实例检测等推理问题，提出了一种用来检测可满足性和缺省可满足性的Tableau—D算法，并得到了缺省可满足性和缺省包含的转换定理．     

累积缺省逻辑的扩充

针对缺省理论的一大热点问题—缺省扩充,将Grigoris Antonion的语义算子理论算法及V.W.Marek和M.Frusz-cyuski的语构算法用于计算累积缺省逻辑(CDL)的扩充,系统地讨论了CDL及其新变种CADL与QDL的理论的扩充问题,从而使得具有累积性的缺省逻辑扩充的计算问题系统化,同时指出这两种方法可用于其他类型的缺省理论扩充的计算。     

Learning Conjunctions of Horn Clauses

An algorithm is presented for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable.) The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula.     

The Unique Horn-Satisfiability problem and quadratic Boolean equations

The unique satisfiability problem for general Boolean expressions has attracted interest in recent years in connection with basic complexity issues [12,13]. We investigate here Unique Horn-Satisfiability, i.e. the subclass of Unique-Sat restricted to Horn expressions. We introduce two operators,reduction andshrinking, each transforming a given Horn expression into another Horn expression involving strictly fewer variables and preserving the unique satisfiability property, if present.Uniquely satisfiable Horn expressions are then characterized as those Horn expressions which can be converted into a formula composed of an empty set of clauses on an empty set of free variables through finitely many applications of the shrink-and-reduce operator.Finally, an algorithm for testing whether a given irreducible Horn formula is uniquely satisfiable is described. Data structures for its implementation are discussed, leading toO(mn) complexity for the general case (m=number of clauses,n=number of variables), hence to linear complexity for dense formulae.     

Polynomial-time inference of all valid implications for Horn and related formulae

This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae.To the memory of Robert G. Jeroslow     

Belief revision within fragments of propositional logic

Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given within a certain language fragment, but also the result of the revision has to be located in the same fragment. So far, research in this direction has been mainly devoted to the Horn fragment of classical logic. Here we present a general approach to define new revision operators derived from known operators, such that the result of the revision remains in the fragment under consideration. Our approach is not limited to the Horn case but applicable to any fragment of propositional logic where the models of the formulas are closed under a Boolean function. Thus we are able to uniformly treat cases as dual Horn, Krom and affine formulas, as well.     

Deduction graphs: an algorithm and applications

A deduction graph (DG) for logically deducing a new functional dependency (FD) or function-free Horn formula (extended from Horn clauses) from a subset of a given FDs or function-free headed Horn clauses in a relational database or rule-based expert systems is defined. An algorithm with a polynomial time complexity for constructing a DG based on a number of rules is designed. Applications of DGs to relational databases, rule-based expert systems, logic programming, and artificial intelligence are investigated. In addition to graphically solving the inference problem by DGs, many logic queries can be answered by DGs with substitutions for unifying expressions     

Double Horn Functions

In this paper, we define double Horn functions, which are the Boolean functionsfsuch that bothfand its complement (i.e., negation)fare Horn, and investigate their semantical and computational properties. Double Horn functions embody a balanced treatment of positive and negative information in the course of the extension problem of partially defined Boolean functions (pdBfs), where a pdBf is a pair (T, F) of disjoint setsT, F⊆{0, 1}ⁿof true and false vectors, respectively, and an extension of (T, F) is a Boolean functionfthat is compatible withTandF. We derive syntactic and semantic characterizations of double Horn functions, and determine the number of such functions. The characterizations are then exploited to give polynomial time algorithms (i) that recognize double Horn functions from Horn DNFs (disjunctive normal forms), and (ii) that compute the prime DNF from an arbitrary formula, as well as its complement and its dual. Furthermore, we consider the problem of determining a double Horn extension of a given pdBf. We describe a polynomial time algorithm for this problem and moreover an algorithm that enumerates all double Horn extensions of a pdBf with polynomial delay. However, finding a shortest double Horn extension (in terms of the size of a formula?representing it) is shown to be intractable.     

Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances

An enhanced concept of sub-optimal reverse Horn fraction of a CNF-formula was introduced in [18]. It was shown that this fraction is very useful in effectively (almost) separating 3-colorable random graphs with fixed node-edge density from the non-3-colorable ones. A correlation between this enhanced sub-optimal reverse Horn fraction and satisfiability of random 3-SAT instances with a fixed density was observed. In this paper, we present experimental evidence that this correlation scales to larger-sized instances and that it extends to solver performances as well, both of complete and incomplete solvers. Furthermore, we give a motivation for various phases in the algorithm aHS, establishing the enhanced sub-optimal reverse Horn fraction, and we present clear evidence for the fact that the observed correlations are stronger than correlations between satisfiability and sub-optimal MAXSAT-fractions established similarly to the enhanced sub-optimal reverse Horn fraction. The latter observation is noteworthy because the correlation between satisfiability and the optimal MAXSAT-fraction is obviously 100%. AMS subject classification 90C05, 03B99, 68Q01, 68W01     

An algorithm to compute maximal contractions for Horn clauses

In the theory of belief revision, the computation of all maximal subsets (maximal contractions) of a formula set with respect to a set of facts is one of the key problems. In this paper, we try to solve this problem by studying the algorithm to compute all maximal contractions for Horn clauses. First, we point out and prove the conversion relationship between minimal inconsistent subsets of union of the formula set and the set of facts and maximal contractions of the formula set with respect to th...     

一个在Horn子句中求解极大缩减的算法

在信念修正理论中,一个核心问题是求解一个公式集合关于事实集合的所有极大协调子集,即极大缩减.本文尝试从算法的角度来解决这一问题,研究在Horn子句中求解所有极大缩减的算法.首先,本文指出并证明了公式集合和事实集合并集的极小不协调子集与公式集合关于事实集合的极大缩减之间的转化关系.其次,给出并证明了Horn子句集合极小不协调的一个必要条件.然后,基于上述两个结论,本文提出了一个在Horn子句中枚举公式集合和事实集合并集的极小不协调子集的交互式算法和一个通过这些极小不协调子集计算所有极大缩减的算法.最后,综合这两个算法,提出了一个在Horn子句中求解所有极大缩减的交互式算法.