计算机科学与探索 ›› 2015, Vol. 9 ›› Issue (2): 221-226.DOI: 10.3778/j.issn.1673-9418.1409022

• 人工智能与模式识别 • 上一篇    下一篇

基于布尔语义的Gentzen推导模型

陈  博+,眭跃飞   

  1. 中国科学院 计算技术研究所 智能信息处理重点实验室,北京 100190
  • 出版日期:2015-02-01 发布日期:2015-02-03

Gentzen Deduction Model Based on Boolean Logic Semantics

CHEN Bo+, SUI Yuefei   

  1. Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • Online:2015-02-01 Published:2015-02-03

摘要: 布尔模型是信息检索系统的一种基础模型。给出了命题逻辑和布尔代数间的一种新的对应关系,其中布尔代数中的不等式对应Gentzen系统中的矢列式,使得当一个不等式在任意布尔代数中为真,当且仅当它所对应的矢列式是可证的。并且使得在信息检索中,针对信息的推理可以有效地转为偏序集上的运算。讨论的命题逻辑语言的运算符为¬、∧、∨;并且定义了项(at|t1t2|t1t2,其中a是一个元素)来替代原先的公式和表示布尔代数中的元素。此外,定义了以布尔代数为论域的赋值v,将命题逻辑中的项赋值为布尔代数中的元素,并且如果∩t∈Γtv≤∪t∈Δtv,则矢列式Γ→Δ为真。最后给出了Gentzen系统下的可靠性和完备性定理的证明。

关键词: 布尔代数, 命题逻辑, 不等式, 完备性

Abstract: Deduction systems are important arts of searching technology. This paper gives a new correspondence between the propositional logic and Boolean algebra, where an inequation is corresponding to a Gentzen sequent, so that the inequation is true in every Boolean algebra if and only if the Gentzen sequent is provable. In information retrieval, the information inference can effectively turn into the operation on poset. Precisely, the logical language for the propositional logic contains operators ¬、∧、∨; the terms instead of formulas are defined (at|t1t2|t1t2, where a is an element) and used to represent elements in Boolean algebra. This paper defines an assignment v using Boolean algebra as its domain, and assigns the terms to be the element in Boolean algebra. The sequence Γ→Δ is satisfied if∩t∈Γtv≤∪t∈Δtv. Finally, this paper gives a Gentzen system to prove the soundness and completeness theorem.

Key words: Boolean algebra, proposition logic, inequation, completeness