【作者】 肖文洁；

【导师】 朱朝晖；

【作者基本信息】 南京航空航天大学 ， 计算机应用技术， 2010， 博士

【摘要】 计算机要对知识和信息有效地进行处理是离不开知识表示与推理(knowledge representation and reasoning)的,知识表示与推理是人工智能符号主义流派最主要的研究内容。在知识表示与推理的研究中,逻辑扮演着重要角色。用逻辑语言对各种知识类型进行公理刻画,构造公理系统并对系统的语义、计算复杂性等方面展开研究已成为知识推理的主要研究内容。为了有效地对人工智能中出现的各种不同类型的知识与信息进行推理,学术界先后提出并研究了模糊推理、不确定推理、非单调推理以及弗协调逻辑等推理模式及其系统。这些受人工智能中问题驱动的研究借鉴了数理逻辑的研究方法与成果,同时其研究范围已远远超出经典逻辑,成为现代非经典逻辑研究的重要组成部分。本文就知识表示与推理的若干问题进行了研究,主要研究内容包括如下方面:(Ⅰ)非充足理由推理的研究在经典逻辑中,Γ?α成立意味着Γ是α成立的充分条件,换言之,在Γ成立的前提下,α是必然成立的。在人工智能及实际应用领域,我们面临的信息往往是不完备的,此时,一味地追求经典逻辑意义上的逻辑后承是不现实的。我们更关心具有“合理”性的推理模式。本文将对一种非充足理由推理展开研究。我们基于有限的命题语言,定义了进行非充足理由推理的背景知识——认知体。直观上,认知体就是Agent有能力判断其真假的命题的集合。本文详细研究了认知体的结构,仿照线性空间中的基底概念引入认知体的认知基概念,并证明认知体可以完全由它的认知基决定。引入了刻画认知体间认知能力强弱的序关系,并给出了相应序关系下认知基的特征。研究了认知体认知能力发生变化时,推理关系相应的演变,并基于此给出非充足理由推理关系的三条逻辑规则和分类格语义模型并证明了相应的表示定理。为了将上述工作推广到一般语言情形,本文引入了无穷认知体及无穷认知体序列的极限,证明了几类无穷认知体序列的极限存在性,并给出一种极限的具体表达式。在有限语言非充足理由推理的三条推理规则基础上,引入一条极限推理规则用于刻画无穷语言下的非充足理由推理关系。构造了无穷认知体的分类格语义模型并证明了相应的表示定理。(Ⅱ)有缺指派下的迭代信念修正理论研究Agent所掌握的知识或信念不是一成不变的,而是随着外界环境或自身状态的变化而变化的。Agent理想化的认知状态是一种平衡状态。当有新的知识输入时,这种平衡状态就被破坏了,这时Agent应当调整自己的信念状态以达到一种新的平衡。这个调整的过程就是信念修正的过程。经典的AGM信念修正理论和以D-P系统为代表的迭代信念修正理论都是以完全指派为可能世界而进行的理论研究。但是由于技术水平和认识工具的限制,在特定的时期内,人类对事物的认知不可能面面俱到。在这种情况下,采用有缺指派(即,为每个原子命题符号赋予真、假和不知道三值之一的指派)作为可能世界来研究问题就是更为合理的选择。本文把D-P系统推广到有缺指派的情形。详细研究了有缺指派的性质并引入补充指派和补充指派间的契合度这两个概念。在此基础上对D-P系统进行了推广,建立了相应的表示定理。(Ⅲ)ES结构的相似性与等价性研究学术界普遍认为非单调推理与信念修正是同一个硬币的两面,它们之间存在着本质的联系。以色列学者Bochman提出的认知结构(即,ES结构)概念旨在为两者提供统一的语义框架。在逻辑系统的研究中,利用语义结构的结构性质刻画语义结构之间等价的充要条件是一个重要而且具有基础性的研究内容。Bochman提出了ES结构之间结构相似性概念,并通过ES结构的外在推理行为的一致性(即,产生相同的收缩后承)引入了刻画ES结构之间的语义等价的概念——怀疑等价。但遗憾的是,他并未就两者的内在联系进行进一步研究。本文将对此展开研究。可以验证,两相似的ES结构一定是怀疑等价的,但其逆命题不成立,即,两怀疑等价的ES结构不一定是相似的。为此,本文引入一个与怀疑等价类似的推理行为等价性概念——拟怀疑等价。进而,证明了对任意两个纯的有限ES结构M 1和M 2,它们是拟怀疑等价的当且仅当par( M 1)与par( M 2)相似,其中,par(.)是作用于ES结构的一个算子。更多还原

【Abstract】 Knowledge representation and reasoning (KRR) are indispensable to the effective computer processing of knowledge and information. KRR is the main research area in symbolic artificial intelligence (AI). In the field of KRR, logic plays an important role. The study of KRR mainly includes the following: the formalization of all kinds of knowledge types by means of logic, the construction of an axiom system and the investigation of the system’s semantics and computational complexity. KRR has been widely studied from 1980’s. Several reasoning systems such as fuzzy reasoning, uncertain reasoning, non-monotonic reasoning, paraconsistent logic and so on, have been proposed to achieve effective reasoning for processing knowledge and information in artificial intelligence. All the above studies motivated by solving the challenges in artificial intelligence not only have made use of the results of mathematical logic, but also have extended the scope of classical logic and thus have become an important part of modern non-classical logic studies.This paper focuses on the following issues related to KRR:(I) Studies on Non-sufficient Reasoning In classical logic, the fact thatΓ?αis true meansΓis the sufficient condition ofα. In other words, ifΓis true, then so isα. In artificial intelligence and practical applications, the available information is usually incomplete. In this situation, the blind pursuit of the logical consequence in the sense of classical logic is impractical. We are more interested in the reasoning methods with“reasonableness”. This paper will discuss the study on non-sufficient reasoning.In the framework of finite proposition language, we define the background of the non-sufficient reasoning---epistemic structure. It is defined as the set of all the facts which the agent can judge true or false in a finite language. Inspired by the notion of basal in linear space, we introduce the basal of epistemic structure ---epistemic basal and prove that the epistemic structure can be completely determined by its epistemic basal. An epistemic system comprises epistemic structures and a partial order which can reflect the strength of the epistemic ability of the epistemic structure. On the basis of epistemic system, we propose three syntax rules of non-sufficient reasoning and its categories lattice semantic and establish the corresponding representation theorem.In order to generalize the above work, we introduce the notion of infinite epistemic structures and the limit of a sequence of infinite epistemic structures. We further prove the existence of the limit of some sequences of infinite epistemic structures. Based on the three syntax rules of non-sufficient reasoning in finite language, we add a limit reasoning rule to describe the non-sufficient reasoning relations under infinite language. Finally, we construct the categories lattice semantic model of infinite epistemic structure and show the corresponding representation theorem. (II) Studies on Iterated Belief Revision in Absent ValuationThe knowledge or belief of the Agent is not unchangeable, but changes with the change of external environment or its own state. The ideal epistemic state of Agent is a state of equilibrium. When new knowledge is acquired, this state of equilibrium will be broken, and the Agent shall adjust its belief state to reach a new equilibrium. This adjustment process is exactly the process of belief revision.Classical AGM belief revision theories and iterated belief revision theories represented by D-P System are both developed in the framework of complete valuations. Due to the limitations of technology and learning tools, our understanding of the world during a particular period could also be partial and limited. In this case, it is more appropriate to use absent valuation, i.e. assigning one of the three possible values (true, false, or unknown) to an atomic proposition, to study problems.We extend the D-P System to absent valuation. Different from complete valuation, absent valuation may assign the unknown state to some atomic propositions. Adopting absent valuation as possible world, we define the especial relation between absent valuations---the supplementary valuation. Finally, we establish a model-based representation theorem which characterizes the proposed postulates and constraints.(III) Studies on Similarity and Equivalence of Epistemic States It is generally recognized that non-monotonic reasoning and belief revision is just like the two sides of a coin and that there exists a fundamental relation between the two. The concept of epistemic states (i.e., ES) introduced by Bochman aims to provide the two with a unified semantic framework.In logic system research, using the structural properties of semantic structure to describe the necessary and sufficient condition of equivalence among semantic structures is an important and fundamental research area. Bochman proposed the concept of similarity in ES, and introduced skeptical equivalence—a concept to describe the semantic equivalence among ES based on the consistency of external reasoning behavior of ES. Unfortunately, he did not further study the internal relations of the two. This paper will conduct study on this point. It can be shown that two similar ES must also be skeptically equivalent while the inverse proposition is not true, i.e., skeptically equivalent ES may not necessarily be similar. In order to explore the relationship between similarity and the reasoning behaviors of epistemic states, a new notation called quasi-skeptical equivalence and an operator par(.) over epistemic states are introduced. We conclude that any pair of pure finite epistemic states are quasi-skeptically equivalent if and only if par( M 1) is similar to par( M 2), where par (.) is an operator working on ES.更多还原