【作者】 元振芳；

【导师】 邓安生；

【作者基本信息】 大连海事大学 ， 计算机科学与技术， 2010， 硕士

【摘要】 布尔表达式化简是一个NP问题,求给定布尔表达式的最简等价式的系统性算法是一个仍待解决的问题。布尔表达式的化简在逻辑电路的优化设计、开关代数及编码设计中都有很多应用。为了减少硬件设计中的输入变量,缩短硬件实现过程中的时间延迟,现有的方法一般仅考虑对布尔表达式实行化简,目前尚没有发现对带有整数关系表达式的布尔表达式化简方面的研究。本文的工作以描述和寻找带有整数关系表达式的布尔表达式的若干类可以化简的情形为出发点,目标是找到若干可以化简的类,将可以化简的情形加以描述并结合实例说明所给方法的正确性、可行性。本文工作的主要结果是：(1)含加减运算的布尔表达式,根据关系运算符“=,≠,≥,>,≤,<”进行分类,实现了形如f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn)的表达式的化简,其中Rij表示Aij=Bij,Aij>Bij,Aij≥Bij或Aij≠Bij且Aij和Bij代表整数表达式。(2)含乘法运算的带有整数关系表达式的布尔表达式,利用关系运算符分类后,根据表达式的形式能否化为范式形式展开进一步讨论,文中给出形如CiXi=±Xj±Cj和Xi*Xj>Xi-Xj+1等若干可以化简的类。(3)含除法运算的带有整数关系表达式的布尔表达式,文中给出形如Ci/Cj=Ck/Cl、Xi/Xj>Xk/Xl和Ci/Xi≥Xi±1等若干可以化简的类。本文工作的结果虽然是初步的有待于进一步研究,但我们相信它为布尔表达式化简提供了一个可供选择的方法并且对逻辑电路的优化具有积极性的作用。更多还原

【Abstract】 The simplification of Boolean expression is an NP problem, and the Systemic algorithm of getting its simplest equivalent formula is still a problem. Simplifications of Boolean expressions can be applied to the optimization of logic circuits, switching algebra and the code of design.In order to reduce the number of input variables and shorten the time delay during hardware implementations, the existing methods in general only consider the simplification of Boolean expression, and there is not any research discovered so far dealing with the simplification of Boolean expression with integer relation expressions.This paper starts with the description and searching for the simplification of Boolean expression with integeral relational expressions, and aiming to find the groups can be simplified and to describe them, then to illustrate the feasibility of the method provided by using examples.The main results of this paper are as follows:Firstly, Boolean expression with addition and subtration can be classified by the relational operators such as "=,≠,≥,>,≤,<". Thus the simplification of the following expression can be realized:f=(R11∧R12∧…∧R1n)∨…∨(Rm1∧Rm2∧…∧Rmn) among which Rij is the intergral relational expression, it represents the formula Aij=Bij, Aij>Bij,Aij≥Bij or Aij≠Bij, as well as Aij and Bij are integral expressions.Secondly, this paper provide certain classes simplification of Boolean expression with multiplicatin, such as,CiXi=±Xj±Cj and Xi*Xj>Xi-Xj+1.Finally, Boolean expression with division such as Ci/Cj=Ck/Cl, Xi/Xj>Xk/Xl and Ci/Xi≥Xi±1 also can be simplified in this paper.Although the results in this paper are only primary and they are further to be studied, we believe that it can be used as an optional method for simplification of the Boolean expression and that it is of positivity to the optimization of Logical Circuit.更多还原