（应用数学专业论文）计算机代数在布尔运算系统的研究与设计中的应用.pdf

摘要 本文利用吐笠扭盛数的方法对查玺垡塾与在玺杰达中的一些主要运算的 计算机自动实现进行研究，把运算的原理与方法转化成能由计算机语言实现 的算法，并改进了一些布尔运算算法，提出了一种求解真值方程- 的新算法。 在算法研究的基础上，设计了一个研究布尔代数与布尔方法的软件系 统：布尔运算系统( b 0 0 1 c a no p e r a t i o ns y s t o m ，简称b l o s ) ，该系统基于 m a t h e m a t i c a 平台，由计算机代数语言m a t h e m a t i c a 语言写成，具有如下主要 功能：求布尔函数的各种表达式、环和范式；布尔函数化简：真值方程( 组) 的求解；一般布尔方程及其混合组的求解；线性伪布尔方程、不等式及其混 合组的求解；非线 生伪布尔方程及非线 生伪布尔不等式的求解。这些功能在 m a t h e m a t l c a 和其他计算机代数系统中是没有的，该系统扩充了m a t h e m a t i c a 的功能，可作为研究布尔代数与布尔方法的工具，也可作为布尔代数、数字逻 辑等课程的教学软件。 a b s t r a c t i nt h i s p a p e r ，u s i n gc o m p u t e ra l g e b r am e t h o d ，w es t u d yc o m p u t e r a l l t o m a t i cr e a l i z a t i o np r o b l e mo fb o o l c a na l g e b r am a i no p e r a t i o n s t h e o p e r a t i o nm e t h o d s a r et r a n s f o r m e di n t o a r i t h m e t i c e ，w h i c hc a nb e c o m p u t e rl a n g u a g ed o n e s o m eb o o l e a no p e r a t o na r i t h m e t i c sa r ei m p r o v e d a n dan e wa r i t h m e t i ct os 0 1 v es i m u l t a n e o u sb o o l e a ne q u a t i o n sb ep u t f o r w a r d o nt h eb a s eo fa r i t h m e t i c s t u d y t h es o f t w a r e s y s t e mo fb o o l e a n a l g e b r aa n db o o l e a nm e t h o ds t u d y ( b o o l e a no p e r a t i o ns y s t e m ：b l o s ) js d e s i g n e d t h es y s t e m i sb a s eo nm a t h e m a t i c a p l a t f o r m i t sm a i n f u n c t i o n sa sf o l l o w s ：t og i v eb o o l e a nf u n c t i o nv a r i o u se x p r e s s i o n s ： b o o l e a nf u n o t i o ne x p a n d ：b o o l e a nf u n c t i o ns i m p l i f y ：t os o l v eb o o l e a n e q u a t i o n so n9 2 ：t o s o l v eb o o l e a ne q u a t i o n so nb ：t os o l v e1 i n e a r p s e u d o b o o l e a ne q u a t i o n sa n d n o n l i n e a rp s e u d o b o o l e a ne q u a t i o n s a s m a t h e m a t i c aa n do t h e r c o m p u t e ra l g e b r as y s t e m s h a v en o tt h e s e f u n c t i o n s ，b l o se x p a n d sm a t h e m a t i c a sf u n c t i o n s i tn o to n l yc a nb e u s e da sat o o lo fb o o l e a na l g e b r aa n db o o l e a nm e t h o ds t u d yb u ta l s o l j s e da sc a is o f t w a r e 第一章 计算机代数与m a t h i 珈a t i c a 系统 本章分两部分。第一部分是计算机代数的文献综述，论述了计算机代数、 计算机代数系统的作用及特点，综述了计算机代数的发展史。第二部分对计 算机代数系统m a t h e m a t i c a 进行概述，对编程中常用的函数、模式、语句 进行了简要说明。 计算机代数是用计算机进行符号推演及准确计算的一门科学，也称符号 和代数处理或符号和代数计算，它是与数值计算并行的一种数学计算，起源 于本世纪六十年代，象数值计算一样，随着计算机科学的发展，它本身亦得 到迅速发展。现已成为数学、计算机科学中的一个独立分支，在理论研究及 实际中都有广泛应用l 。 计算机首先是为数值计算而设计的。自从计算机问世以来数值计算得到 了迅猛发展，但数值计算只是数学演算的一种，许多数学演算是不能或不能 只用数值计算来完成的。例如：求函数的极限，求不定积分，求微分方程解 析解等，它们是不同于数值计算的另一类数学演算，要应用有关的数学公式、 法则去处理数学符号才能完成，这类演算就是符号推演。 符号计算是以符号作为运算对象的计算，在准确计算中数字亦被当作符 号看待，符号计算包含了符号推演与准确计算，因此计算机代数亦被简称为 符号计算“l 。符号计算是无误差的，而数值计算大多数结果是带有误差的， 这是符号计算的一个特点，也是符号计算与数值计算的一个显著区别”1 例 如：求解方程2 1 x2 一1 0x + 1 = 0 ，用符号计算可得根为x = 1 7 ，x ， = 1 3 ，而用数值计算求解方程会得到近似结果x ，= 0 1 4 2 8 5 6 ，x ，= f l 2 5 1 1f _ 2 9 1 7 1 1 0 33 3 3 3 3 。求矩阵l23 8 l 的逆阵时符号计算得准确值二i 一2 1 2l ， 1 2 7 9 j7 l8 3 1 j f 一4 , 1 4 2 8 6 2 a 2 8 5 70 1 4 2 8 5 71 数值计算得近似值i 一0 2 8 5 7 4 一o 1 4 2 8 5 7 0 , 2 8 5 7 1 4l 。符号计算的另一特 l1 1 4 2 8 6 0 4 2 8 5 7 1 0 1 4 2 8 5 7 ) 点是能进行公式推导和数学恒等式的证明。有了计算机符号计算，我们可以 用计算机推导厂( 砷2 丽享尹，丛丛掣) ) 2 丽 n 亏x ；善”2 百三f l + x 2 。：磊一 、1 + 2 忑【l x j ( i x l x z + y z ，( x 。) 。一 x ，x 、 y 、z 为任意变元) 是不可逆的，而l 2 = ( ( x y ) z 一 x ( y z ) ，x ( y z ) 一 x y z ，x + x 。 一 l ，x y z 一 ( x y ) z l 则是可逆的。 从不可逆规则的定义及布尔表达式的有限性可得下述定理： 定理2 1任一不可逆的布尔规则集作用到一布尔表达式上，经过有 限步结果必然不变。 己b l ，名fx + ( y + z ) x * y + x * z ，( ( x )一 x ，x * x 一 0 ，x + x - - x ， ( x + y ) 7 一 x y 。，x + x 专x ，17 一 0 ，0 7 一 1 ) ( 积之和式规则库) ，显然 1 3 b l 是不可逆的。 算法2 i ( 求积之和式基于规则的算法) 输入布尔函数的任一表达式p r e 输出布尔函数的积之和式s o p 1 p 0 - p r e ，k = 1 2 p k = p 。b l 。( p 。b l 。表示对p 。用规则集b l 。作用一次) 3i f p k 与pk - i 相同t h e ns t o p 输出s o p = p k e ls e k = k + 1 返 回2 规则集b l ，对布尔表达式作用主要是去括号的过程，当表达式中再没有 括号时即得积之和式，而b l 是不可逆的，由定理2 1 知，算法2 1 可 在有限步终止。 在b l o s 中实现该算法的算符为s o p 【】( s u mo fp r o d u c t 的缩写) 用 m a t h m e t i c a 编程时把b l l 中的x + x - - - x 从b l l 中分出来，改为n x 哼x 能节 省大量的时间，因为用规则x + x _ x 时每次都要进行比较，如果匹配则作用， 而不用x + x - - ) x ，系统会利用固有的合并同类项功能，得出积项的整数倍，最 后用一次规则r l * x x 作用则实现了每一次都用规则x + x - - - x 的功能。 算法2 2 ( 求函数的积之和范式) 1 2 1 输入布尔函数任一表迭式e x p r 输出布尔函数的积之和范式n o f m $ o p r 1 用算法2 1 把e x p r 化成积之和式s o p r 2 求s o p r 的变量集s ( 其中x i 与x ：看成同一变元x i 的两个形式) 3 对s o p r 的每一项与s 比较，如积项中缺少变元一则用血，竹：j 乘 上该积项，并用该项替代原积项直到该项的变元与s 一致。 4用分配律展开s o p r ，用幂等律消去重复积项得积之和范式 n o r m s o p r 。 在b l o s 中求积之和范式的算符为n o r m s o p 【】，使用形式为 n o r m s o p e x p r 】 例2 1 已知七元布尔函数f = ( ( a + bc ) 7 ( cd 7 + ab + e ，) ) 7 + ( fg 7 + ca ) ，b ，用b l o s 中的算符求： 1 ) f 的积之和式； 2 ) f 的积之和范式。 解：i ) i n i 】：置s o p ( ( a + bc ) 7 ( cd 7 + ab + e 7 ) ) 7 + ( f9 7 + ca7 ) 7b 7 】 o u t 1 ：= a + bc + d ea + deb7+a gb 7+ea 7 c 7 1 4 +eb 7c7+gb 7c7+ab 7f + b 7c 7 f 7 o u t 1 为f 的积之和式。该例在c p u 为c e l e r o n33 3 a ，内存6 4 m 的兼容机上 运行时间可忽略不计。 2 ) 1 1 3 2 】：= n o r m s o p ( ( a + bc ) ( cd 7+ab + e 7 ) ) 7 + ( fg7 +ca7 ) b 7 o u t 2 】：= ahcdefg + bcdefg8 + acdefgb ，+ cdefga b ，+ abdef gc 7 +bdefga c + adef gb 。c 7+def ga 。b c + abce f gd + bc efb a d7+ac ef gb d + ab ef b c 7 d + bef ga c d + ae r gb c d + efga b c d + abcd f ge + bcdfga e + acd f gb e + abd f gc e + ad f g b 7 c 7 e + df ga 7 b c 7e7+abcf gd 7 e7 + bcf ga d e +acfgb d e + ab f gc d 。e + afgb c d e 7 + fg 7 b c 7 d e7+abcdegf + bcdeg8 f + n cdegb f + cdeea b f + abdegc f + bde ga c f + adegb c f + deg8 b c f + 8bce gd f + bceg 8 7 d 7 f7+ac e gb d 7 f 7 + abegc ， d 7 f + be ga c 7d f + aegb c d f 7+ ega b 7c 7 d 7 r + abcd ge f + bc dga e f + acd gb e f + abdgc e f + adgb c e f + dg b c 7 e f7+abc gd e r + bcga 7 d 7b 7 f +acgb 7 d e f + abgc d e 7 f7+agb c d e f + ga b c 7 d 7e f7+abcdef9 7 + bcdef a g 7+acdof b g + c def a 。b g + a bd efc g + bdef a c g + ad ef b c g 7+defa 7 b c g + abcefd 7 g + bc efa d g7+acefb 7 d g + ab efc 7 d g + befa c 7 d g + efb 7 c 7 d 7 g + efa b 7 c 7 d g + abcd fe 7 g7 + bcd fa 7 e g + acdf b e g + abd fc e g + dfb c e g + abcrd e g7 + bcfa d 7 e g + ac f b d e g + abf c 7 d e g + afb 7 c 7 d 7 e g + bcdef g7 + bcdea f g + acdeb 7f g + cd ea b + f g + abdec f g + bdea c f g + adeb 7 c 7 f b + dea b 7c f g + ab ced fg7 + bcea d f 7 g 7 + aceb 7 d 7 r 7 g 7+ab ec d f g + bea 7 c d 7 f 7 g + aeb c d f g7 +ea b 7c 7 d 7 f 7 g + ab cde f g + bcd