Bilattices and Reasoning in Artificial Intelligence: Concepts and Foundations

The past few decades have seen a resurgence ofreasoning techniques in artificial intelligenceinvolving both classical and non-classical logics. Inhis paper, ``Multi-valued Logics: A Uniform Approach toReasoning in Artificial Intelligence', Ginsberg hasshown that through the use of bilattices,several reasoning techniques can be unified under asingle framework. A bilattice is a structure that canbe viewed as a class of truth values that canaccommodate incomplete and inconsistent informationand in certain cases default information. Inbilattice theory, knowledge is ordered along twodimensions: truth/falsity and certainty/uncertainty. By defining the corresponding bilattices as truthspaces, Ginsberg has shown that the same theoremprover can be used to simulate reasoning in firstorder logic, default logic, prioritized default logicand assumption truth maintenance system. Although thisis a significant contribution, Ginsberg's paper waslengthy and involved. This paper summarizes some ofthe essential concepts and foundations of bilatticetheory. Furthermore, it discusses the connections ofbilattice theory and several other existingmulti-valued logics such as the various three-valuedlogics and Belnap's four-valued logic. It is notedthat the set of four truth values in Belnap's logicform a lattice structure that is isomorphic to thesimplest bilattice. Subsequently, Fitting proposed aconflation operation that can be used to selectsub-sets of truth values from this and otherbilattices. This method of selecting sub-sets oftruth values provides a means for identifyingsub-logic in a bilattice.     

否定非对合剩余格的IV-模糊理想

模糊代数是模糊逻辑的一个重要研究内容。为进一步了解否定非对合剩余格的理想之特性,在否定非对合剩余格中引入了区间值模糊理想概念。讨论了否定非对合剩余格的区间值模糊理想的相关性质。证明了一个否定非对合剩余格的区间值模糊理想的交、直积、同构像和同态原像仍是区间值模糊理想。     

Evidential bilattice logic and lexical inference

This paper presents an information-based logic that is applied to the analysis of entailment, implicature and presupposition in natural language. The logic is very fine-grained and is able to make distinctions that are outside the scope of classical logic. It is independently motivated by certain properties of natural human reasoning, namely partiality, paraconsistency, relevance, and defeasibility: once these are accounted for, the data on implicature and presupposition comes quite naturally.The logic is based on the family of semantic spaces known as bilattices, originally proposed by Ginsberg (1988), and used extensively by Fitting (1989, 1992). Specifically, the logic is based on a subset of bilattices that I call evidential bilattices, constructed as the Cartesian product of certain algebras with themselves. The specific details of the epistemic agent approach of the logical system is derived from the work of Belnap (1975, 1977), augmented by the use of evidential links for inferencing. An important property of the system is that it has been implemented using an extension of Fitting's work on bilattice logic programming (1989, 1991) to build a model-based inference engine for the augmented Belnap logic. This theorem prover is very efficient for a reasonably wide range of inferences.A shorter version of this material was originally presented at the Fifth International Symposium on Logic and Language, Noszvaj, Hungary, 1994. The author is now in the Mathematical Reasoning Group, Department of Artificial Intelligence, University of Edinburgh, 80 South Bridge, Edinburgh EH1 1HN, U.K.     

Residuated lattices of block relations: size reduction of concept lattices

We deal with size reduction of concept lattices by means of factorization by block relations defined on corresponding formal context. We show that all block relations with a multiplication defined by means of relational composition form a (non-commutative) residuated lattice. Such residuated lattice can be then thought of as a scale of truth degrees using which we evaluate formulas of predicate logic specifying the desired parameters of the factorization. We also introduce efficient algorithms computing operations on a residuated lattice of block relations. The naive way how to design such algorithms is to compute all the formal concepts of a given context in advance, and then apply some well-known properties of residuated lattices. Our algorithms get rid of the time-consuming precomputation of all concepts.     

Pseudo-BCK algebras as partial algebras

It is well-known that the representation of several classes of residuated lattices involves lattice-ordered groups. An often applicable method to determine the representing group (or groups) from a residuated lattice is based on partial algebras: the monoidal operation is restricted to those pairs that fulfil a certain extremality condition, and else left undefined. The subsequent construction applied to the partial algebra is easy, transparent, and leads directly to the structure needed for representation.In this paper, we consider subreducts of residuated lattices, the monoidal and the meet operation being dropped: the resulting algebras are pseudo-BCK semilattices. Assuming divisibility, we can pass on to partial algebras also in this case. To reconstruct the underlying group structure from this partial algebra, if applicable, is again straightforward. We demonstrate the elegance of this method for two classes of pseudo-BCK semilattices: semilinear divisible pseudo-BCK algebras and cone algebras.     

Partial residuated structures and quantum structures

Residuated structures, bounded commutative residuated lattices in particular, play an important role in the study of algebraic structures of logics—classical and non-classical. In this paper, by introducing partial adjoint pairs, a new structure is presented, named partial residuated lattices, which can be regarded as a version of residuated lattices in the case of partial operations, and their basic properties are investigated. The relations between partial residuated lattices and certain quantum structures are considered. We show that lattice effect algebras and D-lattices both are partial residuated lattices. Conversely, under certain conditions partial residuated lattices are both lattice effect algebras and D-lattices. Finally, dropping the assumption on commutativity, some similar results are obtained. Project supported by the NSF of China (No. 10771524).     

Are basic algebras residuated structures?

MV-algebras are bounded commutative integral residuated lattices satisfying the double negation and the divisibility laws. Basic algebras were introduced as a certain generalization of MV-algebras (where associativity and commutativity of the binary operation is neglected). Hence, there is a natural question if also basic algebras can be considered as residuated lattices. We prove that for commutative basic algebras it is the case and for non-commutative ones we involve a modified adjointness condition which gives rise a new generalization of a residuated lattice.     

Lattice pseudoeffect algebras as double residuated structures

Pseudoeffect algebras are partial algebraic structures which are non-commutative generalizations of effect algebras. The main result of the paper is a characterization of lattice pseudoeffect algebras in terms of so-called pseudo Sasaki algebras. In contrast to pseudoeffect algebras, pseudo Sasaki algebras are total algebras. They are obtained as a generalization of Sasaki algebras, which in turn characterize lattice effect algebras. Moreover, it is shown that lattice pseudoeffect algebras are a special case of double CI-posets, which are algebraic structures with two pairs of residuated operations, and which can be considered as generalizations of residuated posets. For instance, a lattice ordered pseudoeffect algebra, regarded as a double CI-poset, becomes a residuated poset if and only if it is a pseudo MV-algebra. It is also shown that an arbitrary pseudoeffect algebra can be described as a special case of conditional double CI-poset, in which case the two pairs of residuated operations are only partially defined.     

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables

Abstract. We consider generalized first-order sentences over < using both ordinary and modular quantifiers. It is known that the languages definable by such sentences are exactly the regular languages whose syntactic monoids contain only solvable groups. We show that any sentence in this logic is equivalent to one using three variables only, and we prove that the languages expressible with two variables are those whose syntactic monoids belong to a particular pseudovariety of finite monoids, namely the wreath product of the pseudovariety DA (which corresponds to the languages definable by ordinary first-order two-variable sentences) with the pseudovariety of finite solvable groups. This generalizes earlier work of Thérien and Wilke on the expressive power of two-variable formulas in which only ordinary quantifiers are present. If all modular quantifiers in the sentence are of the same prime modulus, this provides an algorithm to decide if a regular language has such a two-variable definition.     

Loop-separable programs and their first-order definability

An answer set program with variables is first-order definable on finite structures if the set of its finite answer sets can be captured by a first-order sentence. Characterizing classes of programs that are first-order definable on finite structures is theoretically challenging and of practical relevance to answer set programming. In this paper, we identify a non-trivial class of answer set programs called loop-separable programs and show that they are first-order definable on finite structures.     

可换双剩余格上的广义模糊粗糙集及其公理化

双剩余格是t-模、t-余模、模糊剩余蕴涵及其对偶算子的代数抽象,基于格的L-模糊关系是普通模糊关系的推广。作为Pawlak经典粗糙集及多种模糊粗糙集模型的共同推广,提出了一种基于可换双剩余格及L-模糊关系的广义模糊粗糙集模型,引入了正则可换双剩余格的概念,并给出了基于正则可换双剩余格的广义模糊粗糙上、下近似算子的公理系统,推广了多个文献中已有的结果。     

The pseudo-linear semantics of interval-valued fuzzy logics

Triangle algebras are equationally defined structures that are equivalent with certain residuated lattices on a set of intervals, which are called interval-valued residuated lattices (IVRLs). Triangle algebras have been used to construct triangle logic (TL), a formal fuzzy logic that is sound and complete w.r.t. the class of IVRLs.In this paper, we prove that the so-called pseudo-prelinear triangle algebras are subdirect products of pseudo-linear triangle algebras. This can be compared with MTL-algebras (prelinear residuated lattices) being subdirect products of linear residuated lattices.As a consequence, we are able to prove the pseudo-chain completeness of pseudo-linear triangle logic (PTL), an axiomatic extension of TL introduced in this paper. This kind of completeness is the analogue of the chain completeness of monoidal T-norm based logic (MTL).This result also provides a better insight in the structure of triangle algebras; it enables us, amongst others, to prove properties of pseudo-prelinear triangle algebras more easily. It is known that there is a one-to-one correspondence between triangle algebras and couples (L,α), in which L is a residuated lattice and α an element in that residuated lattice. We give a schematic overview of some properties of pseudo-prelinear triangle algebras (and a number of others that can be imposed on a triangle algebra), and the according necessary and sufficient conditions on L and α.     

THE ARCHITECTURE OF SYSTEMS PROBLEM SOLVING by George J. Klir. Plenum Press,New York, 1985, xvi + 540 pages.

This is an overview paper presenting the main results obtained by the author and his colleagues in the field of fuzzy logic and modelling of natural language semantics and is composed of an introduction followed by two main parts. Section 2 discusses our results in terms of fuzzy logic, namely that of prepositional and first-order fuzzy logic based on a residuated lattice of truth values. Section 3 presents the concept of the Alternative mathematical Model of natural Language semantics and pragmatics (AML) the development of which is based on a philosophical approach rather than the approaches usually adopted in most classical papers.     

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables

Abstract. We consider generalized first-order sentences over < using both ordinary and modular quantifiers. It is known that the languages definable by such sentences are exactly the regular languages whose syntactic monoids contain only solvable groups. We show that any sentence in this logic is equivalent to one using three variables only, and we prove that the languages expressible with two variables are those whose syntactic monoids belong to a particular pseudovariety of finite monoids, namely the wreath product of the pseudovariety DA (which corresponds to the languages definable by ordinary first-order two-variable sentences) with the pseudovariety of finite solvable groups. This generalizes earlier work of Thérien and Wilke on the expressive power of two-variable formulas in which only ordinary quantifiers are present. If all modular quantifiers in the sentence are of the same prime modulus, this provides an algorithm to decide if a regular language has such a two-variable definition.     

剩余格上的模糊滤子和模糊同余关系

介绍了剩余格上的模糊同余关系和模糊滤子的定义,给出了剩余格上模糊滤子和模糊同余关系间的一一对应,证明了在剩余格上模糊滤子和模糊同余关系上定义适当的序关系可使它们是完备格同构。     

On v-filters and normal v-filters of a residuated lattice with a weak vt-operator

In this paper, we study further the filter theory of residuated lattices. First, we discuss the concepts of filters and normal filters of residuated lattices and propose some equivalent conditions for them. Then we introduce and investigate the notions of v-filter and normal v-filter of a residuated lattice with a weak vt-operator and lay bare the formulas for calculating the v-filters and the normal v-filters generated by subsets. Finally we show that the lattices of v-filters and normal v-filters of a residuated lattice with a vt-operator are both complete Brouwerian lattices.     

Nominal Monoids

We develop an algebraic theory for languages of data words. We prove that, under certain conditions, a language of data words is definable in first-order logic if and only if its syntactic monoid is aperiodic.     

基于不同蕴涵算子的模糊概念格建格算法研究

概念格是进行数据分析的有力工具,模糊集是数据处理的有效方法之一,模糊概念格有重要的理论与应用价值,但它的结构与性质依赖于蕴涵算子的选择,基于此,介绍了基于下半连续三角模生成的剩余蕴涵以及模糊概念格的算子和定义,提出了基于不同蕴涵算子的模糊概念格的实现算法,分析了算法的复杂度等性能,最后通过实例说明了基于Godel 蕴涵和Lukasiewicz 蕴涵的模糊概念格的建格方法。