（电路与系统专业论文）数字理论的表格方法研究[电路与系统专业优秀论文].pdf

摘要 浙江大学博士学位论文 摘要 随着数字电路的设计规模和复杂程度的大大提高，传统的数字理论已不能很 好的满足需要，有必要对它做进一步的探讨和研究。近代数字理论正是对传统数 字理论的进一步研究，它不但大大扩展了数字理论的研究内容，而且还提出了很 多新的方法。本文结合近代数字理论中的成果，对数字理论中的表格方法做了一 个系统地研究。 近代数字理论引入了一些特殊运算及特殊函数，这是近代数字理论中的一个 重要内容。本文通过分析这些特殊运算及特殊函数的定义及其性质，对布尔差分 与布尔偏导数的性质做了进一步的研究，提出了它们与谱系数之间的关系，并在 详细讨论了布尔差分及布尔偏导数和特殊函数之间的关系后，提出了几个相应的 定理，并做了证明。这些关系和性质可以很方便的用于检测和判断特殊函数。 与一或一非代数系统是传统的布尔代数系统。本文系统地介绍了该代数系统中 各种表格表示方法，并对表格的各种表现形式及相应的性质做了详细的分析，同 时给出了真值表规模的压缩方法。文中对现有的各种表格方法做了系统的介绍， 并提出了用分解表计算一阶及n 阶布尔差分的方法，及利用该方法实现了检测特 殊函数的表格方法，并通过例子进行说明。对于含任意项的逻辑函数，我们提出 了相关任意项的概念及含任意项的表格表示，并结合实例实现了利用该表格计算 特殊运算及检测特殊函数的一系列表格方法，这些方法是对与或非代数系统中 的表格方法的完善和补充。 模代数系统由于其易于故障检测，便于逻辑综合等原因一直受到重视。本文 讨论了模代数系统中的积项表的表示方法及其相应的性质，并系统地介绍了现有 的表格方法，在此基础上提出了检测对称函数( 包括部分变量取反) 的表格方法 和计算r m 型逻辑函数布尔差分及偏导数的表格方法。模代数系统中的任意项比 与一或- 非代数系统中的更加复杂，我们对此进行了细致的分析和比较，提出了含 任意积项的表格表示，并结合实例给出了一系列利用含任意项的积项表的表格方 法。 或符合代数系统与模代数系统有着密切的关系，对它的研究也成为热点。 结合或一符合运算的性质，文中对和项表进行了详细的分析，得出了几个有用的 性质，并给予了证明。通过分析或符合代数系统中的特殊函数和特殊运算的性 质，并结合现有的表格方法，我们提出了计算o c 型逻辑函数布尔差分及布尔偏 导数的表格方法。 关键词： 表格方法，与或非代数系统， 模代数系统，或符合代数系统， 布尔差分， 特殊函数检测，分解表，真值表，积项表， 和项表 a b s t r a c t 浙江大学博士学位论文 a b s t r a c t a sd i g i t a lc i r c u i tg r o w sl a r g e ra n dt h ed e s i g nt a s kb e c o m e sm o r ec o m p l e x ， i r a d i t i o n a ld i g i t a lt h e o r yc a n tm e e tt l i er e q u i r e m e n t , a n dm u s tb es t u d i e df u r t h e r m o d e r nd i g i t a lt h e o n ，i st h ea n s w e rw h i c hr e s e a r c h st h et r a d i t i o n a ld i g i t a lt h e o r y f u r t h e r i tn o to r l ye x - t e - u d st h ec o n t e n t so fd i g i t a lt h e o r yg r e a t l y , b u ta l s op r o p o s e s m a n yn e wm e t h o d s c o m b i n c dw i t l lt h ep r o d u c t i o no fm o d e r nd i g i t a lt h e o r y , t a b u l a r m e t h o d so fd i g i t a lt h e o r ya r es y s t e m a t i c a l l yd i s c u s s e di nt h i sd i s s e r t a t i o n s o m es p e c i a ll o g i co p e r a t i o n sa n ds p e c i a ll o g i cf u n c t i o n sa r ei n t r o d u c e di n m o d e md i g i t a lt h e o r y , a n dt h e ya r ei m p o r t a n tc o n t e n t st h a tm o d c l - nd i g i t a lt h e o r y r e s e a r c h t h ed e f i n i t i o n sa n dc h a r a c t e r i s t i c so ft h e s cs p e c i a ll o g i co p e r a t i o n sa n d s p e c i a ll o g i cf u n c t i o n sa r ea n a l y z e di nt h i sp a p e r b a s e du p o nt h i s ，t h ec h a r a c t e r i s t i c s o fb o o l e a nd i f f e r e n c ea n db o o l e a np a r t i a ld e r i v a t i v ea r es t u d i e df a r t h e r , a n dt h e r e l a t i o n s h i p sb e t w e e nt h 锄a n ds p e c t r a le o e f f i c i e n t sa r cp r o p o s e d a f t e rd i e u s s e dt l i e r e l a t i o n s h i p sb e t w e e nb o o l e a nd i f f e r e n c ea n db o o l e a np a r t i a ld e r i v a t i v ea n ds p e c i a l l o g i cf u n c t i o n si nd e t a i l ，t h ep a p e rp r o p o s e ss e v e r a lt h e o r e m s ，a n dp r o v e st h e m t h e s e r e l a t i o n s h i p sa n dc h a r a c t e r i s t i c sc m a k et h ed e t e c t i o na n di u d g m e n tf o rs p e c i a l l o g i cf u n e t i o i l 8m o r ee o i l v c n i o n o e a n d - o r - n o ta l g e b r a i cs y s t e mi sat r a d i t i o n a lb o o l e a na l g e b r a i cs y s t e m t h i s d i s s e r t a t i o ni n t r o d u c e sa l lk i n d so ft a b u l a rm c t h o d sf o rf u n o t i o ne x p r e s s i o ni nt i i i s a l g e b r a i cs y s t e m ，a n dd i s c u s s e sa l lf o r m sa n dc h a r a c t e r i s t i e so f t a b u l a ri nd e t a i l a tt h e s a m et i m e ；t h ec o m p r e s s i o nm c t h o do f 劬t hv a l u et a b l ei sp r e s e n t e d a l le x i s t i n g t a b u l a rm e t h o d sa r ed i c u s s e ds y s t e m a t i c a l l yi nt h i st h e s i s a n dt h em e t h o d so f c a l c u l a t i n gf l r s t - o r d e ra n dn o r d e rb o o l c a nd i f f e r e n c eb yu s i n gd e c o m p o s i t i o nt u b u l a r a r ep r e s e n t e d b yu s i n gt h e s em e t h o d s ，t h et a b u l a rm e t h o d so fd e t e c t i n gs p e c i a ll o g i c f u n c t i o n sa r ep r o p o s e d , a n ds o m ee x a m p l e sp r o v et h em e t h o d s c o n s i d e r i n gt h e p a r t i a l l yd e s c r i b e dl o g i cf u n c t i o n , w ep r o p o s et h ee o n e e p t i o no fc o r r e l a t i v ea r b i t r a r y i t e r na n dt h et a b u l a rw i t ha r b i t r a r yi t e m b yu s i n gt h i st a b u l a r , as e r i e so ft a b u l a r m e t h o d so fc a l c u l a t i n gs p e c i a l o p e r a t i o n sa n dd e t e c t i n gs p e c i a ll o g i cf u n c t i o n sa r e p r e s e n t e di nt h i st h e s i s a n ds o m ee x a m p l e sa r cg i v e nt oe x p l a i n t h e s em c t h o d sw i l l c o m p l e m e n ta n dc o n s u m m a t et h et a b u l a rm e t h o d so f a n d - o r - n o ta l g e b r a i es y s t e m m o d u l a ra l g e b r a i cs y s t e mh a ss e v e r a la d v a n t a g e ss u c ha s e a s yt od e t e c t i o n ， c o n v e n i e n tf o rs y n t h e s i s ，s oi tb e c o m e sah o t s p o ti nd i g i t a lt h e o r yr e s e a r c h t h ep a p e r d i e u s s e se x p r e s s i o nf o r m sa n dc h a r a c t e r i s t i c so fp r o d u c ti t e mt a b u l a r , a n di n t r o d u c e s e x i t i n gt a b u l a rm e t h o d ss y s t e m a t i c a l l y b a s e du p o nt h e s e t h et a b u l a rm e t h o t i so f d e t e c t i n gs y m m e t r y ( i n c l u d i n gp a r t i a ln e g a t e dv a r i a b l e s ) a n dc a l c u l a t i n gb o o l e a n d i f f e r e n c ea n db o o l e a np a r t i a ld e r i v a t i v co fi 洲t v p cf u n e t i o na r ep r o p o s e dt h e a r b i t r a r yi t e mi nm o d u l a ra l g e b r a i cs y s t e mi sm o r ec o m p l i c a t e dt h a ni na n d - o r - n o t a l g e b r a i cs y s t e mb ya n a l y z e da n dc o m p a r e dc a r e f u l l y , t h ee x p r e s s i o nf o r mo ft a b u l a r i i a b s t r a c t 浙江大学博士学位论文 w i t l ia r b i t r a r yi t e mi sd i e u s s e d a n das e r i e so ft a b u l a rm e t h o d sf i l ep r e s e n t e di nt h i s t h e s i sb yu s i n gt h et a b u l a rw i t ha r b i t r a r yi t e m o r - c o i n c i d e n c ea l g e b r a i cs y s t e mh a so l o s er e l a t i o n s h i pw i t hm o d u l a ra l g e b r a i o s y s t e m ，8 0i ti sn e o e s s a r yt os t u d yt h i sa l g e b r a i cs y s t e mc o n s i d e r i n gt h ep r o p e r t i e so f c o i n e i d e n c eo p e r a t i o n ，t h ep a p e rd i s c u s s e ss u mt c r n lt a b u l a ri nd e t a i l , p r o p o s e s s c v c r a lp r a e t i e a le h a r a c t e r i s t i e s a n dv e r i f i e st h e m w ea l s 0a n a l y z et h ep r o p e r t i e so f b o o l e a nd i f f e r e n c ea n dp a r t i a ld c r i v a t i v ea n ds o m es p e c i a ll o g i of u 1 c t i o i l qi n o r - e o i i i c i d e a o ea l g e b r a i cs y s t e mi nt h i st h e s i s a n dg i v es o m et a b u l a rm e t h e 凼t o c a l c u l a t i n gb o o l e a np a r t i a ld e r i v a t i v ea n dd i f f e r e n c eo f o ct y p e1 0 cf u n c t i o n s k e yw o r d s ： t a b u l a rm e t h o d , a n d o r - n o ta l g e b r a i cs y s t e m ，m o d u l a ra l g e b r a i cs y s t e m ， o r - c o i n c i d e n c ea l g e b r a i cs y s t e m ，b o o l e a nd i f f e r e n c e ， b o o l e a np a r t i a ld e r v a t i v e ，d e t e c ts p e c i a lf u n c t i o n ，d e c o m p o s i t i o nt a b u l a r t r u t hv a l u et a b l e ，p r o d u c ti t e mt a b l e ，s u mi t e mt a b l e i 第1 章绪论浙江大学博士学位论文 第1 章绪论 与模拟信号相比，数字信号有着更为优越的性质，它不仅可以方便地进行高 性能传输，而且还能对其进行编码、存储、压缩、恢复，同时也可以借助计算机 强大的计算能力，利用数字信号处理方面的技术进行各种处理，因此数字信号的 应用范围正在不断扩大，而这也大大促进了数字电路的发展。现在市场上的电子 产品，有很大一部分都是数字的，从复杂的、集成了上亿个晶体管的c p u 到几 个晶体管组成的小小的门电路，琳琅满目，数不胜数。另一方面，随着半导体制 造技术的发展，集成电路的规模不断增大，如今已经发展到s o c 阶段，即可以 将复杂的系统集成在单个芯片上。系统芯片s o c 把许多功能相关的电路集成为 一个系统，这不仅仅降低了成本，同时在很大程度上提高了电路的性能。数字信 号的广泛使用，数字电路的高度集成化，给我们带来方便的同时，也不可避免的 引发了新的问题。电路的测试、设计、实现、优化等方面都比以往更加复杂，为 了更为有效的解决这些问题，有必要对数字电路的理论基础擞字理论，做进 一步的研究。表格方法作为数字理论分析的有力手段，对它的研究具有积极意义。 本章第一节介绍近代数字理论的研究背景；第二节介绍表格方法的一些概 述；第三节给出本文主要的研究重点及章节安排。 1 1 研究背景 布尔代数是一种特殊的代数系统，因为在布尔代数中，变量和函数仅取0 ， 1 两个值，因此布尔代数又称为开关代数，相应的布尔函数称为开关函数，变量 称为开关变量。布尔代数是数字电路的理论基础，因此与之相关的理论被称为数 字理论。随着半导体工艺的不断发展，集成电路的规模、速度和复杂程度大大提 高，这使得我们在设计电路时，面临着比以往更为严峻的问题。由于需要处理的 信号急剧增加，这无疑大大增加了函数的复杂性，分析、优化、计算这些复杂的 函数需要更为有效的手段，而传统的数字理论对这些复杂函数的处理不尽如人 意，在这样的背景下，许多学者对数字理论做了进一步的研究。通过这些研究， 不但完善了数字理论，而且使得数字理论更趋向于实用化，它不但能指导我们如 何设计电路，还能对电路的性能进行优化，达到更好的效果。下面，我们就近代 数字理论的研究内容和研究现状做一个简介。 第1 章绪论浙江大学博上学位论文 近代数字理论的研究主要包含以下几个方面： 1 扩展传统的布尔代数运算 1 - 1 8 1 传统的布尔代数只有几种常见的运算，与、或、非、异或、符合等，和其他 的代数系统相比，一些比较常见的运算但在传统布尔代数中却没有相应的定义， 因此需要对该代数系统的运算进行扩展，在布尔代数中给出这些运算相应的定 义，并研究这些运算的意义、性质和应用，使得布尔代数进一步完善。这方面的 研究开始得比较早，一些特殊的运算被逐步的补充到这个代数系统中，比如减法、 除法、幂运算、比较运算、布尔差分和闽值运算等等。这些运算的引入，使得表 达布尔函数的形式更加多样化，分析布尔函数的手段更加多元化，实现布尔函数 的方式更加简捷化。虽然这方面的研究工作开展的比较早，但关于这些运算的性 质和应用的研究却在不断地深入。 2 特殊函数的研究1 ”o 】 在布尔代数中，存在着一些特殊的函数。线性函数、闽值函数、双反函数、 自双反函数、对称函数、冗余函数、单调函数、互斥变量函数是布尔代数中比较 常用的特殊函数。这些特殊函数在电路的设计、优化、检测、函数分类方面都有 着重要的作用，因此对这些函数性质的分析，相关的检测技术和相互之间的关系 及其转换是近代数字理论的一个比较重要的研究内容。这方面的研究工作已取得 了一定的进展，但仍需进一步的深入研究。 3 函数特殊的展开形式 3 1 - - 4 2 j 传统的布尔代数只有基于与或非代数系统的展开形式，分别为最大项展开 和最小项展开，然而在布尔代数中还有其他的运算构成布尔代数的完备集，因此 必需考虑这些布尔代数对应的展开形式。现阶段主要研究的展开形式有基于与 异或的r m 展开，基于或符合的o c 展开，基于布尔减一布尔除一非的d o s 和s o d 展开。对于这些展开，我们研究的内容主要有： 第一、相应展开的标准形式。为了统一这些展开形式，为了更好的对这些展 开进行分析和研究，首先必需要给出这些展开的标准形式。现阶段，r m 展开、 o c 展开及d o s 和s o d 展开的标准形式都已给出，但对于其他的完备集还缺乏 研究。 第二、研究这几种展开之间的转换关系，也就是从一种标准化展开转换到另 一种标准化展开的方法，这其中包括代数方法、表格方法和图形方法。最小项展 开系数和b 系数( r m 展开) 之间的转换关系研究得比较充分，而有关d ，系数 ( o c 展开) 有关的转换也正在不断的完善当中。 第三、研究这些展开系数所代表的意义及其应用。我们对数字理论的研究的 第l 章绪论 浙江大学博士学位论文 最终目标是希望通过相应的研究可以使得布尔代数在电路的分析、设计、实现上 发挥更大的作用，所以针对这些特殊形式的展开要研究这些系数所代表的意义 以及这些展开的应用。比如，r m 展开在测试方面有着比较大的优势，并在函数 分类和逻辑优化方面有着自己突出的特点。 4 谱技术的研究4 “ 】 谱系数的引入为逻辑分析和逻辑设计提供了新的手段。通过正交矩阵把函数 值变换为谱系数，这与信号处理中的傅立叶变换相似。谱系数反映了逻辑函数的 频谱特性，利用谱系数可以更好的对布尔函数进行分类，并且在逻辑设计中有着 广泛的应用，比如阈值函数的设计、逻辑函数修改、对称函数检测等。这方面的 研究正在不断的深入，其中涉及到谱系数的计算方法，谱系数和其他标准展开系 数之间的转换方法，谱系数的应用等等。 5 多值逻辑的研究1 4 “5 2 】 多值逻辑是对二值逻辑的扩展。传统的布尔代数只能取0 ，1 两个值，随着 计算机处理信息能力的增加，对数据的传输速率有着越来越高的要求，为了更有 效地利用传输线路，提高信息的传输速率，我们就可以采用多值逻辑。在多值逻 辑中，可以用一个电平表示多个b “信息，这样信号的传输速率不变，然而信息 的传输速率却得到了加强。这方面也是近代开关理论的一个研究重点，其中包括 多值理论的研究，多值逻辑电路的设计等等。 6 绝热型电路的研究5 ”9 】 现在功耗已经成为集成电路中的一个重要问题，如何在设计的过程中降低功 耗是一个研究热点。传统的电路由于都是采用基于类似方波的信号，这些信号在 对电路的充放电过程中会导致大量的能耗消耗，这些功耗称为动态功耗，占整个 功耗的绝大部分。许多学者在降低动态功耗方面作了很多研究，从系统级到门级 都提出了许多相应的算法，比如遗传算法、模拟退伙算法，这些算法在降低功耗 方面能起到一定的作用。而绝热型电路和传统的电路不同，它使用正弦波的形式 来传递电路信号，由于正弦波使得电路在充放电过程中的能量消耗基本为0 ，因 此采用这种方法可以大大降低电路的动态功耗，甚至趋向于无功耗损失，这也是 绝热型电路的由来。这方面研究的主要内容有绝热理论的研究和绝热型电路的设 计。 第1 章绪论 浙江大学博上学位论文 1 2 表格方法概述 1 2 1 几种常见的基本表 表格是数字理论中经常使用的一种表示形式，与代数表达式及图形比较，表 格具有更好的可扩展性，易于操作，便于编程实现，应用广泛等一系列优点，因 此，在数字理论中，表格方法一直受到重视。 数字逻辑中有各种各样的表格，这些表格是实现表格方法的基础。不同的代 数系统有不同的表格，各种表格又有不同的表现形式。对这些表格的分析和掌握， 是实现表格方法的前提，只有对各种表格有深入的了解，才能在分析、设计逻辑 函数时充分发挥表格方法的优势，下面就对几种常见的表格做一个简单的介绍。 常见的表格主要有四种，分别是真值表叫l 、积项表、和项表和分解表 u s , s s 。真值表由函数变量的取值和与之对应的函数值组成，对应的是函数的最小 项和最大项展开：积项表由函数的积项和与之对应的所系数组成，对应的是函数 的r m 展开；和项表由和项和与之对应的4 系数组成，对应的是函数的o c 展开。 分解表比较特殊，它是由k 图与6 ，图转换而来，不同之处在于表中行和列不再 按二进制循环码顺序排列，而是按二进制大小从小到大排列。表11 到14 分别 列出了三变量函数的真值表、积项表、和项表及分解表。 表l l 真值表表1 2 积项表 表13 和项表 五如j ， o00 c 0 o ol q 0l0 c 2 0l1 c 3 l00 c 4 l01 c 5 l10 lll c 7 积项b 系数 l 钆 j ， b m l 屯 而而以 玉 屯 玉鼍b 5 工l 工2k 五x 2 墨以 表14 分解表 和项d 系数 + 工2 + 而以 + 心4 而+ 与d 2 玉d 3 0 2 + 屯比 l 以 屯d 6 o d 7 i 0l23 玉 4567 随着数字理论的发展，表格方法不仅仅局限于以上四种基本表，各种其他的 表格也得到了广泛的研究和应用。这些表格没有固定的格式，内容多样，能针对 4 第1 章绪论浙江大学博士学位论文 不同的问题，在分析、设计和实现函数方面都有着十分重要的作用。比如用表格 法用于检测特殊函数“9 - - ” ，用表格法计算特殊的布尔运算 1 & s l ，用表格法对函数 进行化简等等5 “”。随着这些研究的深入，表格法在整个数字理论中也将占到重 要的地位。 1 2 2 表格法研究的主要内容及面临的问题 表格方法研究的主要内容有以下几点： 1 ) 用表格表示函数 表格的表现形式是多种多样的，不但包括前面介绍的四种基本表格，还包括 它们的各种变形，比如降维表、1 值表、0 值表等等，因此函数通过表格表示也 有多种方法，在什么场合，采用哪种表示方法，是用好表格方法的第一步。 2 ) 降低表格的规模 虽然表格很方便扩展，也很容易使用，但它有一个问题，就是表格的大小随 着函数变量的增加成指数级增长，这大大限制了表格的使用，所以如何降低表格 的规模，减少运算时间，是表格方法必须研究的一个问题。现阶段降低表格的主 要方法有：降维法，特殊函数法，合并法，特殊函数值法。这些方法的使用可以 在一定程度上降低表格的规模，但仍需要进一步的研究。 3 ) 表格方法处理特殊函数 特殊函数在逻辑分析和设计时能起到很好的作用，因此我们需要尽可能的检 测特殊函数和特殊变量。表格方法在这方面具有一定的优势，它能很好的反映一 些特殊函数的性质，应用表格方法检测特殊函数具有很强的实用性。这方面虽然 已经有些学者做了一定的研究，但仍不够深入和全面。 4 ) 表格方法化简函数 函数化简足分析处理逻辑函数的重要步骤。随着函数变量的增加，函数复杂 程度的提高，函数化简也显得越来越难。代数方法和图形方法在这方面不如表格 方法，表格方法由于其可扩展性和易于编程实现等特点，在函数化简方面起到了 重要作用。这方面的研究开展的比较早，对于多值逻辑函数的化简也有一定的涉 及，但需要进一步的完善。 5 ) 表格方法计算特殊运算 特殊运算的引入能更好的分析、综合逻辑函数，但它们的计算却相对比较复 杂。表格方法在处理特殊运算时能结合特殊运算的特点，快速的得到运算结果。 关于这方面的研究也正在不断的完善当中。 第1 章绪论浙江大学博上学位论文 6 ) 表格方法在逻辑设计中的应用 表格方法在逻辑设计中还有着许多应用，比如用表格方法实现不同代数系统 之间的系数转换，表格方法用于基于数据选择器的逻辑设计等等。这方面的研究 涉及的范围比较广，往往对于一个特定的问题，产生一种特定的表格方法，这体 现了表格的灵活性，有待于我们的进一步探索。 1 3 论文的研究重点及章节安排 本文结合近代数字理论中的成果，主要研究在数字理论中的表格方法及其应 用，研究重点及章节安排如下： 第二章介绍了布尔代数中的特殊运算及特殊函数，这是用表格方法研究的主 要内容。在本章中，对布尔减、布尔除、布尔差分、布尔偏导数和常见的特殊函 数做了详细的分析，在原有性质的基础上对它们做了进一步的深入研究，提出了 几个新的性质，并给予了证明。另外，文中对布尔差分和布尔偏导数与谱系数之 间的关系以及它们和特殊函数之间的关系做了详细的讨论，对此给出了相应的性 质，并做了证明。 第三章系统地介绍了在与或非代数系统中的表格方法。与或非代数系统是 传统的布尔代数系统，关于它的表格方法研究的比较充分。第一节首先介绍了真 值表的性质，接着对逻辑函数的表格法化简进行了系统的说明，包括单输出、多 输出函数及三值函数。第三节详细分析了真值表规模的压缩方法、然后对表格方 法在与或非代数系统的各种应用做了系统的阐述，给出了计算特殊运算及检测 各种特殊函数的表格方法。本章的最后提出了分解表的各种应用，引入了相关任 意项，并对提出了含任意项表格方法的各种应用。 第四章分析了表格方法在模代数系统中的应用。首先详细讨论了积项表的性 质，积项表规模的压缩方法，并给出了6 ，系数与q 系数转换的表格方法。然后 给出了表格方法在模代数系统中的各种应用，提出检测对称函数( 包括部分变量 取反) 及计算布尔差分与布尔偏导数的表格方法，最后对含任意项的r m 型逻辑 函数给出了表格表示及其各种应用。 第五章分析了或符合代数系统中的表格表示，详细分析了和项表的性质并给 出了相应的证明过程。接着详细讨论了表格方法在或- 符合代数系统中的各种应 用，提出了用于计算o c 型逻辑函数的布尔差分和布尔偏导数的表格方法，以及 用表格方法检测特殊函数和特殊变量。 第2 章布尔代数中的特殊运算及特殊函数 浙江大学博士学位论文 第2 章布尔代数中的特殊运算及特殊函数 随着近代数字理论研究的深入，在布尔代数中引入了许多新的内容，其中包 括一些特殊运算和特殊函数。特殊运算的引入是为了完善整个布尔代数系统，这 些特殊运算的加入主要是考虑到以下两个方面：一是传统的布尔代数运算种类比 较缺乏，一些在其他代数系统中比较常见的运算在布尔代数系统中却没有定义， 因此有必要在布尔代数中对这些比较常见的运算进行定义，布尔减、布尔除、比 较运算、幂运算、布尔差分、布尔偏导数等等属于这一类；另一方面根据布尔代 数自身的特点，定义的有别于其他代数系统的运算，比如闽运算。这些特殊运算 是近代数字理论中重要的组成部分，是布尔代数更加完善的保证。 在布尔代数中，特殊函数也是研究的重点。常见的特殊函数包括线性函数、 双反函数，自双反函数、阌值函数、对称函数，冗余函数、互斥变量函数等等。 由于这些特殊函数具有自身独特的性质，在分析、设计、实现相应的逻辑函数时， 能够起到相当大的作用，因此对这些特殊函数性质的研究、检测的方法、电路的 实现都必须有所重视。 本章第一节介绍布尔代数中的特殊运算布尔减、布尔除以及布尔差分和布尔 偏导数，第二节介绍一些特殊函数的定义及其性质，第三节介绍特殊函数与布尔 差分、布尔偏导数之间的关系。 2 1 布尔代数中的特殊运算 2 1 1 布尔减与布尔除运算“1 1 定义 布尔减 布尔除 a 一碰爿否 a 口垒a + b 表2 1 列出了布尔加、布尔减、布尔乘与布尔除的真值表。 表2 1 四种运算的真值表 一口a + ba bab a b o0000 l 0 l 100 0 lo1l 0 1 1ll01l 第2 章布尔代数中的特殊运算及特殊函数浙江大学博士学位论文 2 性质 布尔减和布尔除具有如下几方面的性质： 1 ) 与常量0 、l 有关的性质 a 一0 = a 0 一a = 0 a l = 0 0 = l0 a = aa l = a 2 ) 与单变量有关的性质 一a = 0a a = a a a = 1彳a = a 3 ) 交换律关系 布尔减与布尔除不满足交换律， 下关系： 一一a = a 4 a = a l a = a l a = 1 即爿一b b a ，a b b a ，但满足以 一一b = b a a b c = a c b 爿b = b a一口c = a c 曰 4 ) 结合律 布尔减与布尔除不满足结合律，但满足以下关系： a 一丑一c = ( 4 一b x a c )a 一口一c = 爿一( b + c ) 一b c = ( 爿口) + ( 爿c )彳b c = a ( 口，c ) 5 ) 分配律关系 a ( b c ) = a b - a c a + ( 占c ) = ( 彳+ 口) ( 一+ c ) 6 ) 反演定律 一一b = a 口一b = a b 7 ) 对偶规则 如果两个逻辑式相等，则将式中所有的“”跟“+ ”交换、“”跟“一” 交换、“0 ”跟1交换得到的对偶式也必定相等。 8 ) 一、非运算构成完备集 由于a + b = a b ，a bab ，故一、非运算构成完备集。 2 1 - 2 布尔差分与布尔偏导数m 1 布尔差分的定义 一阶布尔差分车y ( 一) 。，( i ) m 一 ( 2 1 ) 第2 章布尔代数巾的特殊运算及特殊函数浙江大学博士学位论文 二阶布尔差分 k 阶布尔差分 布尔偏导数的定义 一阶布尔偏导数 k 阶布尔偏导数 瓦d 2 ，f _ 厂a _ f ( x ，蝴一x , x i ) ( 2 2 ) 焉蛳栌厄x l , 刁( 2 3 ) 霎：誓：厂( ) 。，西 苏，出，7 。 分f & i & 2 缸i 2 布尔差分与布尔偏导数的性质 ( 1 ) 粤：，( 1 ) 。厂( o ) a x ( 2 ) ( 毛x - i ，x ，+ i 出： 盟：o ( 3 ) _ d f ：d f md x = 毒( 驯 c 。，掣= ，砉。砉。g 。考。砉 掣a x = 掣a x = 妻。砉 血m ( 6 ) 掣：7 挛。d f ；。孚_ d g d x ，d x ，d x i血，出， ( 7 ) 掣：掣 靠d x 7 考d x 。考d xg 。砉妾 。 ，。出，出 c s ，煎铲= 掣= ，。老。面d fg 。i d f a x a x 考 血出 血。癜 器= 器 ( 1 0 ) 婴：o 出。m 9 ( 2 4 ) ( 2 5 ) 第2 章布尔代数中的特殊运算及特殊函数浙江大学博上学位论文 ( 1 1 ) 蒜= i a f 。瓦a f 。瓦a 2 f ( 1 2 ) 霉：f ( o ，o ) 。厂( o ，1 ) 。，( 1 ，o ) 。，o ，1 ) o x , d x ， 燃砉= 考一o ，贿蒜- o 矾由于蒜2 善。考。去 =考。考。-d川f生ldx d xd x o 。o = 。证毕 ， ， ，l 出，j 推论2 1 设，( ) 为n 变量的逻辑函数，若誓：誓一一a ，f ：o ，则有 靠；积靠 型_ ：o ，m ：2 ，3 ，一，k 。 d ( ) 。 燃妄a x = 考乩贿焉a - o 戤1 x xi 跏丽a 2 f = 善。善。蕞d xd ( x ，j ，)苏，反，玉， = 砉d x 。考d x 。丢d x ( 剖= 。，。= 。证毕 ， ， ，i 出，j 叫燃筹= 考= 砉乩则有意篝2 - 矾老高= 砉。考。瓦a f 。丢( 纠。 丢( 矧。丢( 期。丢 每( 割 = 1 0 1 0 l o0 = 1 证毕 推论2 2 设厂( x i x n ) 舳姐艘鼬数诺毒2 毒一。毒- l 删有 1 0 第2 章布尔代数中的特殊运算及特殊函数浙江大学博士学位论文 生：0 如果肌为偶数 d ( x ，x 1 2 )【1 如果为奇数 脚果蒜一o ，蒜一o ，黜有焉- o 证明：根据二阶布尔差分的定义可得 。= 蒜= ( x l , x j , x k ) 。厩一x i 砌 故有： y x ，x i ) = f ( x ，z ，x i ) 根据，x j ，以的取值由上式可得 f ( o ，0 ，o ) = f o ，1 ，o ) ，f ( o ，o j ) = f ( 1 ，1 ，1 ) f ( o ，l ，o ) = f ( 1 ，0 ，o ) ，f ( o ，i j ) = f ( 1 ，o ，1 ) 类似的有 。= 瓦a ：而f = ，( ，以) 。几，一x i , 一x k ) 故有： f ( x ，x i ，xk ) = ，u ，xj ，xk ) 根据t ，z ，x k 的取值由上式可得 f ( o ，0 ，o ) = f ( o ，l 1 ) ，f ( o ，o 1 ) = f ( o ，l ，o ) f ( 1 ，0 ，o ) = f ( 1 ，l ，1 ) ，( 1 ，o j ) = f ( 1 ，1 ，o ) 根据上述诸式可得 f ( o ，0 ，o ) = f ( 1 ，0 ，1 ) ， f ( o ，0 ，1 ) = f ( 1 ，0 ，o ) f ( o ，1 ，0 ) = f o ，1 ，1 ) ，f ( o ，l ，1 ) = f ( 1 ，1 ，o ) 综合以上四式可得 f ( x ，x i ，x 1 ) = ，q ，xj ，x k ) 故有 瓦a 2 f 币= 厂( m ，) 。厩。- ) = 。 证毕 ( 1 7 ) 设- 厂( ) 为n 变量的逻辑函数，如果善： ：f ( o ，o ，以) 。，( 1 ，l ，) ， u j , “ 丽0 2 f 川z ，0 o ) 。几舯，则有鼍o x 叫。 o ) 。邝，删 盘班m 。 第2 章布尔代数中的特殊运算及特殊函数浙江大学博士学位论文 a 2 f 证明： 因为j ： = ，( o ，0 ，t ) o f ( o j ， ) o ( 1 ，0 ， ) o 厂( 1 j ，以) 珊班， = f ( o ，0 ，坼) o f ( u ，坼) 故有f ( o ，1 , x d = f o ，0 ，以) 令 分别为o ，l ，可得 f ( o ，1 ，o ) = f o ，0 ，o ) ，f ( o ，l ，1 ) = f o ，o ，1 )( 2 6 ) ；：姜：f ( x 1 , 0 , 0 ) 。厂( x j , 0 , 1 ) 。厂( j , o ) 。厂( 如1 ，1 ) ：f ( x s , 0 , 0 ) 。，( l ，1 ) 班f c r x 故有f ( x ，0 ，1 ) = 厂( ，1 ，o ) 令工分别为0 , 1 ，可得 f ( o ，o ，1 ) = f ( o ，l ，o ) ， f ( 1 ，0 3 ) = f o ，1 ，o ) ( 2 7 ) 由式( 2 6 ) 、( 2 ，7 ) 可得 f ( o ，0 ，1 ) = f ( 1 ，0 ，0 ) ，f o ，0 ，1 ) = f ( 1 ，1 ，o ) 综合上述两式可得： f ( o ，x j ，1 ，) = f o ，j ，o ) 因为鼍= ，( o , x j , o ) 。( o 叫，) 。m 删。们, x j , 1 ) = ( o ，一，o ) 0 ，( 1 ，j ，1 ) 证毕 3 布尔差分与谱系数的关系 定理2 1 设( j 。) 为n 变量的完全定义的逻辑函数，则f 的一阶布尔差分 a f a x , = o 的充分必要条件是，的谱系数中下标含，的谱系数均为0 ，即有 ( 2 _ 。r 。；o = 。= 0 证明：因为a f d x , 2 0 ，可以得到，( ) = ，( 焉矗) ，因此可以得 到函数( 五x 。) 与厂( 而) 具有相同的谱系数，根据变量取反谱系数 的变换规则，我们可以得到以下等式： 2 - r , ，2 一_ ，。一，一2 一一 因此= 一一一= 0 必要性得证。 计算，( 王i ) 的谱系数川，根据谱系数的性质一i ，则含i 的谱系 数全部改变符号，即，( 而t ) 的谱系数，。】中含i 的谱系数为 - r , ，= _ ，。= 。，其余的谱系数不变。 因为= 一= 一= 0 ，所以( 玉) 的谱系数与，( 玉- ) 第2 章布尔代数中的特殊运算及特殊函数浙江大学瞎士学位论文 的谱系数完全相等，而谱系数是对函数的正交变换，可以得到： 厂( 1 矗) 2 f ( x l 毛。矗) ， 因此彤如= o充分性得证