（电路与系统专业论文）近代数字理论中的特殊运算及其应用研究[电路与系统专业优秀论文].pdf

近代数字理论中 的特殊 运算及其应用研究 摘要 作为二值数字电 子学的基 础， 传统的数字理论- 布尔代数中 基于与或非三种基本运 算的代数系统的研究早己 成熟。 为了 开拓新的数字元件及新一代数字电路， 人们一 直十分 重视有关 代数 理论的研究， 从 而形 成了 近代数 字 理论。 本 文的 主要内 容是围 绕着近代数 字 理论中的特殊运算展开的。 . 首先，通过与普通代数相对比，引入了近代数字理论中的各种特殊运算一 布尔减、 布尔除运算:布尔差分、 布尔微分及布尔积分;以 及模减、 模除、 模指数等 运算。 在此基 础上， 提出了 基于布尔四则运算的 代数系统， 包括各种新的 完备集、函 数的 规范展开式 及 化简、各种规范展开式之间的相互转换等。 其 次 ， 介 绍 了 基 于 模四 则 运 算 的 多 值 模 代 数 系 统: 由 模 加、 模 减、 模 乘、 模 除 等 组 成 的各种模运算完备集的构成、函数展开、图 形表示及其化简等。 此外，还讨论了 特殊运算- - 布尔差分、 布尔微分及布尔积分等的理论计算以 及在故障 检测中的应用。 关键词:近代数字理论 特殊运算 规范展开式 化简 故障检测 浙江大学硕士学位论文 近 代数字 理论中 的 特殊 运算 及其 应用 研究 a b s t r a c t a s a b a s i s o f t h e b i n a r y v a l u e d i g i t a l e l e c t r o n i c , t h e t r a d i t i o n a l d i g i t a l t h e o r y - - - - b o o l e a n a l g e b r a i c s y s t e m w h i c h i s b a s e d o n a n d , o r , n o t o p e r a t i o n s - - - -h a s a l r e a d y b e e n d e v e l 叩e d . i n o r d e r t o d e v e l o p n e w e l e c t r o n i c d e v i c e s a n d e l e c t r i c c i r c u i t , i t h a s b e e n p a i d a l o t o f a t t e n t i o n t o s t u d y c o n c e r n e d a l g e b r a i c t h e o r y a n d f o r m e d t h e m o d e r n d i g i t a l t h e o r y . t h i s d i s s e r t a t i o n i s g o i n g t o d i s c u s s t h e s p e c i a l o p e r a t i o n s i n t h e m o d e r n d i g i t a l t h e o r y . f i r s t l y , t h i s d i s s e r t a t i o n i n t r o d u c e s t h e s p e c i a l o p e r a t i o n s i n c o m p a r i s o n w i t h t h e b a s i c a l g e b r a- 一b o o l e a n s u b t r a c t i o n , b o o l e a n d i v i s i o n ; b o o l e a n d i f f e r e n t i a l a n d i n t e g r a l c a l c u l u s ; m o d u l a r s u b t r a c t i o n , m o d u l a r d i v i s i o n , m o d u l a r e x p o n e n t a n d s o o n . o n t h e b a s e , i t i s p r o p o s e d s o m e o f n e w a l g e b r a i c s y s t e m s o n b o o l e a n f o u r a r i t h m e t i c o p e r a t i o n s , w h i c h i n c l u d e s o m e n e w c o m p l e t e s e t s , t h e l o g i c a l f u n c t i o n s e x p a n s i o n s a n d t h e i r m i n i m i z a t i o n , t h e t r a n s f o r m b e t w e e n t h e s t a n d a r d e x p a n s i o n s e t c . t h e n , m u l t i - v a l u e d m o d u l a r a l g e b r a i c s y s t e m s w e r e s u r v e y e d o n m u l t i - v a l u e d m o d u l a r f o u r a r i t h m e t i c o p e r a t i o n s i n t h i s d i s s e r t a t i o n , w h i c h i n c l u d e s o m e n e w c o m p l e t e s e t s，t h e l o g i c a l f u n c t i o n s e x p a n s i o n s , t h e i r m i n i m i z a t i o n a n d s o o n i n a d d i t i o n , t h i s d i s s e r t a t i 血 d i s c u s s e s b o o l e a n d i f f e r e n t i a l , i n t e g r a l c a l c u l u s a n d t h e i r a p p l i c a t i o n t o d e t e c t i o n o f d i g i t a l c i r c u i t f a u l t s. k e y w o r d s : m o d e r n d i g i t a l t h e o r y , s p e c i a l o p e r a t i o n , a l g e b r a i c s y s t e m , e x p a n s i o n , m i n i m i z a t i o n , d e t e c t i o n o f d i g i t a l c i r c u i t f a u s t a n d a r d i t s 浙江大学 硕士学位论文 近代数字理论中的 特殊运算及其 应用 研究 布尔代数的提出是为了用数学方法解决复杂的语言和思维逻辑问 题。并被广泛应用于 解决开关电路和数字逻辑电路的分析与设计。 为了开拓新的 数字元件及新一代数字电 路， 一方面人们对这一传统的二值代数理论进行了 深入的 研究， 取得了 新的 进展。另一方面， 将二值代数理论拓展到了多值，从而形成了 近代数字理论。 夸 1 . 1 引言 1 8 4 9年， 英国数学家乔治 布尔 ( g e o r g e b o o l e ) 首先提出了 描述客观事物逻辑关系 的数学方法一一布尔代数。但直到 1 9 3 8年才由美国麻省理工学院的研究生香农 ( s h a n o n ) 开始应用于开关电路的分析设计中。 后来，由 于 布尔代数被广 泛地应用于解决二 值的开关电路和数字逻辑电路的 分析与设 计上， 所以 也把布尔代数叫做开关代数或逻辑代 数 ， 21 。 二值布尔代数是分析设计由门电路、 触发器、中小规 模集成电 路等基本单元电路构成 的 二 值逻 辑电 路的 数学 工 具， 其 基础是 cc 1 采用二值的数字信号伯，n: z .采用与、或、非三种基本运算 ( 与、 或、非完备集) : 3 .采用以函数的最小项展开为基础的最小 化表达式; 上述传统的 ( 二值) 数字理论 布尔代数中 基于与、 或、 非三种荃本运算的代数理 论的研究早已成熟。 为了 开拓新的数字元件及新一代数字电 路， 人们一直十分重视有关代 数 理 论 的 研 究 ， 从 而 形 成了 近 代 数 字 理 论 h . m 这 一 理 论 的 研 究 主 要 集 中 在以 下 几 个 方 面: 1 .二值代数理论 ( 布尔代数) 的进一步完善 a .布尔代数中的 特殊运算及特殊函数的研究。 除了 基本运算布尔加( 或运算) 、布尔乘 ( 与运算) 运算以 及模加( 异或运算) 及模乘( 与 运算) 运算外， 通过与普通代数的对比， 引入 了多种特殊运算， 如布尔减、布尔除、 布尔差分、 布尔积 分、 模减、 模除等特殊运算。 通 过对这些特殊运算及各种特殊函数的 研究，以 期进一步完善布尔代数理论; h . 布尔代数中 除与、 或、非 代数系 统外 基于不 同运 算 完备 集的 各 种 代数系统的 研究。 如与一 或一 非代数系统、与一 异或代数系 统、或 一 符合代数系统等; c 布尔代数中有关谱技术的研究。如基于各种正交变换的 数字谱技术及其应用. 2 多值代数理论的 研究。 在布尔代数中 信号 仅取两个 值， 而在多 值逻 辑中 信号 可 取多 个分立 值， 从而 提高了 传 浙江大学 硕士学 位论文 近代教字理论中 的特f * i a- 算及其应用 研究 输线和集成电路的信息密度， 可减少数字系统的 连线数及提高集成电路芯片的集成度。 正 因如此， 多值逻辑及多值逻辑电 路的 研究受到重视。 而作为多值逻辑电 路分析设计的数学 工 具各种多 值代数系统的 研究业已 成为近代数字理论的一个重要研究方向; 3 有关应用方面的研究。 二值、多值代数理论在诸如数字逻辑电 路的分析、设计及故障检测等方面获得了 广泛 的 应用。 尤其是多值逻辑，由 于多 值信号较二值信号含有更多的信息量， 有望在新一代计 算机中 得到应用。 又如， 基于各种正交变换的数字谱技术在信号处理及信息传输等方面的 应用。因此有关代数理论的应用 研究是一项有实际意 义的工作。 然而， 尽管近代数字理论取得了 喜人的进展。 但仍然有许多领域需要进行深入的 探讨 和研究。 众所周知，在普通代数中存在加、减、乘、除四则运算，而在布尔代数中却只有布尔 加( 或 运算 ) 及 布尔 乘( 与 运算) 运算。 因 此特殊 运算 - 一布尔减 运算与 布尔除 运算引 入fa l 引 起了 人们的关注， 也完善了 对布尔四则 运算的讨论。 布尔四则运算 布尔加、 减、 乘、 除及异或、 符合及非运算可构成的各种新的完备集。 然而迄今为止， 对任意逻辑函 数在各 种新的完备 集中的 规范展开式、 规范展开式 之间的相互转换及各种规范展开式的化简等问 题的 研究还很不充分; 在普通代数中还存在导数、 微分和积分等运算， 对应地在布尔代数 中引入了 特殊运算 布尔差分、 布尔微分及布尔积分等运算， 但其理论研究 ( 特别是布 尔积分) 及在数字电路的故障检测、非冗余电路等中的应用仍有待与进一步的探索。 又 如在多值 代数理 论的 研究中 ，各 种多 值 代数系 统的 研究也 有待 进一步的 深入。如多 值模代数系统中除了模加( 异或运算) 及模乘( 与运算) 运算外， 对各种特殊模运算模 减、 模除、 模指数运算及其性质的研究及各种模运算完备集的 构成、 展开、图形表示及其 化简等均需深入探讨. 基于以 上原因， 本硕士论文将就近代数字理论中的 特殊运算 及其应用进行进一步研究。 以期深入对各种特殊运算、 性质及其应用的认识。 进一步完善布尔代数中基于不同 运算 完 备集的 各种代数系统:丰富多值代数理论中多 值模代数系统的 各种模运算完备集的 构成、 展开、图形表示及其化简等方面的理论。 1 . 2 布尔代数中的运算 布尔代数的 提出是为了 用数学方法解决复杂的 语言和思维逻辑问 题。 其应用和发展的 基础是只有两种状态的电 路 开关电 路， 并被广泛应用于解决开关电 路和数字逻辑电路 的分析与设计。 布尔代数中作为引 入三个最基本运算 与、 或、非)的公理以 及由 此推导 得到的基本定理及规则都是根据开关电路的 特性导出的。 为了 解决复杂的逻辑问 题， 还用 与、 或、 非 运算定义了异或、同 或等复合逻辑运算. 下面先简要介绍布尔基本运算， 再扼 要讨论 少 l 种 特殊 运算la 浙江大 学硕士学拉论文 近代数字理论中的特脚邑 算及其应用研究 1 . 2 . 1 基本运算 客观事物的 各种逻辑关系中， 最基本的逻辑关系有三种: 与逻辑、 或逻辑以 及非逻辑。 而其它的复杂逻辑关系可由这三种基本逻辑关系组合而成。 据此， 在布尔 二值逻辑) 代 数中引入了 三种基本的 逻辑运算: 与运算、 或运算以 及非运算。 与、 或、 非 运算构成完备 集， 即任意逻辑函数均可由此三种基本运算表示成 规范 展开形式 最小项表达式或最大 项表达式。 但必须注意的是: 尽管二值逻辑代数中和普 通代数一样， 用字母或符号表示 变 量， 但是， 该变量不代表具体数值大小， 而只代表两种截然不同的 状态， 开关的断开和闭 合、电平的高与低，是与非、真与 假等. 在二值代数的研究中， 人们就设想直接引 用普通代数 ( 本文是指包含实数常量、 实数 变量以及连结 它们的各种运算， 如加、 减、 乘、 除、 指数、 导数等所构成的代数系 统， 各 运算的 优先级多符合传统的规定)中的 算术运算。 加法与乘法是二种最基本的 算术运算， 但对于 变量取值域( 0 , 1 ) 的二值情况， 普通加法会发生 超出取值域的困 难。为此引入模2 加的概念， 并常用由作模2 加的运算符。 而对于乘法不必施以 模2 限 制， 但也可以 称它为 模2 乘。 r e e d 与m u l l e r r 证明了 模2 乘运算与模2 加运算能组成完备集， 即任何二值函 数 均可由 此二种基本运算 表示成规范展开形式 r e e d - m u l l e r 展开式 ( 相当于普通代数中 的泰勒展开) 。建立在模加和模乘二种基本运算上的代数系统被称为模代数系统。必须注 意的是: 模代数系统中的 变量取值具有数值大小。 事实 上在二值情况下 模2 加及模2 乘分 别为 二值逻辑代数中的 异 或运算 及与 运算， 因 此该 二值 情况 下的模 代数 系统即 为 逻 辑代数 中的与 一 异或代数系统。 研究表明，以与一 异或表示的函数所对应的电 路特别 具有容易测试的优点。因此对它 的研究一直受到重视， 并且把它引 人到多值逻辑的 研究中。 文献( 1 3 1 证明了 对于任何基为 质数的多值逻辑， 模代数系统 均是适用的， 且模加与模乘二种基本 运算仍组成完备 集， 可 用于表示任何函数。 为 叙述方便，本文把二值逻辑代数的与 运算、 或运算以 及二值情况下的 模代数系统中 模2 加 ( 异 或运算) 及模2 乘 ( 与 运算) 运算称为 基本运算。表1是其真值表。由 表可知， 逻辑意义 上的与、 异成运算从数值运算角度看分别是二值情 况下的模2 加及模2 乘运算。 表1 与、或、 异或运算真值表 a b a十b ae b b 0 0 八uo 10/ 才 b 0 0 oi 1 0 1或/ l与 1 . 2 . 2 特殊运算 除了基本运算或运算 ( 也称布尔加) 、与运 i 1 逻辑意义 数值运算模2 加 算 ( 也称布尔乘) 运算以 及模2 加及模2 乘运算外， 通过与普通代数的对比，引入了多种 特殊运算， 如布尔减、 布尔除、 布尔差分、 布尔积分、 模减、 模除等特殊 运算。从而进一 步完善了布尔代数理论: 众所周知，在普通代数中 存在加、减、 乘、除四则运算，而在布尔代数中 却只有布尔 浙江大学硕士学 往论文 近代数字理论中的 特殊运算及其应用 研究 加( 或 运 算 ) 及 布 尔 乘( 与 运 算 ) 运 算 。 因 此 特 殊 运 算 一 一 布尔 减 运 算 与 布 尔 除 运 算 引 入 阁 ， 引 起了 人们的关 注， 也完善了对布尔四则运算的 讨论。 布尔四 则运算 布尔加、 减、 乘、 除及异或、 符合及非运算可构成的 各种新的完备集. 迄今为止， 对任意逻辑函数在各种新 的完备集中的规范展开式、 规范展开式之间的相互转换及各种规范展开式的化简等问 题的 研究还很t,充分; 在普通代数中 还存在导 数、 微分和积分等运算， 对应地在布尔 代数中也 引入了 特殊运算 一 一 布尔差分、 布尔微分及布尔积分等运算， 但其理论研究 ( 特别是布尔 积分) 及在数字电 路的故障检测、 非冗余电 路、 图 像处理等方面的 应用仍有待进一步的 探 索。 研究表明， 以 异或( 模2 加) 及与( 模2 乘) 运算表示的函 数所对应的电路特别具有容易 测试的 优点， 因 此对二值情况下的 模代数系统 ( 与异或代数系 统) 研究一直受到 重视，并 且把它扩展到多值逻辑的研究中， 建立了以 模乘和模加运算为基本运算的多 值模代数系 统。 在二值代数的研究中， 人们就设 想直接引用普通代数中的 算术运算。同样地在普通代 数中 存在加、 减、 乘、 除四 则 运算， 而在多 值 模代数中 却只 有模 加及模乘 运算。 对各 种特 殊模 运算 模减、 模除、 模指数等运算及其性质的研究，以 及由 模加、 模减、 模乘、 模 除等组成的各种模运算完备集的 构成、 函数展开、图形表示及其化简等间题的 研究尚需深 入。 对子 模代数系 统的 各方面应用如故障检测、 可靠性分析、 图 象信号处理等也在不断推 广，并有待深入探讨。 1 . 3论文研究的主要内 容及章节安排 近代数字理论的 研究领 域十分宽 广， 本文将就近代数字理论中的 特殊运算、 各种完备 集、函数展开、图形表示及其化简及其应用等问 题。 主要内 容归 纳为以 下几个方面: 1 、近代数字 理论中的 特殊运算 特殊运算 布尔减、 布尔除 运算; 布尔差分、 布尔微分及布尔积分运算;以 及模减、 模除、 模指数等运算及其性质的 研究。以 期深入对各种特殊运算、 性质的认识; 2 、基于布尔四则运算的代数系 统 布尔四则 运算 布尔加、减、乘、除及异或、 符合及非运算可构成的各种新的 完备 集; 任意逻辑函数在各种新的完备集中的规范展开式、 规范展开式之间 的相互转换及各种 规范展开式的 化简等问 题的研究， 进一步完警布尔代数中 4于不同 运算完备集的各种代数 系统。 3 ,基于 模四则 运算的多值模代数系统 多值模代数中却只有模加及模乘运算。 对各种特殊模运算 一 一- 模减、 模除、 模指数等 运算及其性 质的 研究， 以 及由 模加、 模减、 模乘、 模除 等组 成的 各 种模运算 完备集的构 成、 函 数展开、 图 形 表示 及其化简等问 题的 研究。 丰富多 值代 数理论中 多 值模代数系统的 各 种 模运算完备集的构成、 展开、图形表示及其化简等方面的 理论。 浙江大学硕士学位论文 近代数字理论中的特殊运算及其应用研究 4 、布尔微积分的计算及其应用 布尔代数中特殊运算 布尔差分、 布尔微分及布尔积分等运算， 但其理论研究 ( 特 别是布尔积分) 及在数字电路的故障检测、 非 冗余电 路等中的 应用仍有待与进一步的 探索。 在章节安排上， 本论文在第一章对近代数字理论研究的 领域及 近代数字理论中主要的 特殊运算的研究情况作了阐述，并提出了 本文研究的内容。 论文将在第二章具体介绍 近代数字理论中的主要特殊运算的定义、性质等。 论文的第三章中将讨论基于布尔四则运算一 一布尔加、 减、 乘、 除 及异或、 符合及非 运算的代数系统: 各种新的完备集: 任意逻辑函 数在各 种新的完备集中 的规范展开式、 规 范展开式之间的相互转换及各种规范展开式的化简等问题。本章的内 容是本论文的 重点。 本论文将在第四 章中 对名 种 特殊模 运算 - 一 模减、 模除、 模指数 运算构成的 各 种模运 算完备集、函数的规范展开、图形表示及其化简等内容。 在第五 章中 讨论特殊 运算 一 目 布尔 差分、 布 尔傲分 及 布尔 积分等 运算的 性质， 特别是 布尔积分的理论研究， 进一步完善布尔微积分理论。 同 时简要介绍在数字电 路的故障检测、 非冗余电路、图像处理等方面的 应用。 论文的最后一章是结论与 展望。 浙i x 大学硕士学 位论丈 近代男 二 字理论中的 特殊运葬及共应用 研究 在二值布尔代数中与 运算被称为布尔乘运算， 或运算被称为布尔加运算， 而在普通代 数中有加、 减、 乘、 除四则 运算以 及乘方、 开方、 导数、 微分和积分等多种运算，在布尔 代数中是否存在其余的相应运算? 有何性质? 这些将在第一节和第三节中予以介绍. 在二值 代数的 研究中 ， 人们 就设 想直 接引 用普 通代数中 的 算术运算。 加法 与乘法是 二 种最基本的 算术运算， 但对于变量取值域( 0 , i ) 的二值情况， 普通加法会发生超出取值域 的困难， 为此引入模z 加的 概念。 而对于乘法不必施以 模2 限制。 将模2 加、 模2 乘概念 扩展到多值逻辑的研究中 ， 建立了以 模r 乘和模r 加 运算为基本运算的多值模代数系统。 普通代数中 除了二种算术 运算 加法与乘法外， 还引 入了它们的算术逆运算 减法和 除法运算， 构成了 加、 减、 乘、 除四 则运算。 那么多 值模代数中却与模加及模乘运算相对 应的逆运算是否存在?是否存在其余的 运算?有何性质? 这些将在第二节予以 讨论。 本章 通过与 普通 代数的对比， 引 入了 多 种 特殊运算tsa z i ， 如布 尔减、 布尔除、 布尔 差 分、 布尔积分、 模减、 模除、 模指 数等运算等特殊运算。 并对各种特殊运算的性质进行了 研究，从而进一步完善了布尔代数理论。 2 . 1 布尔 减与布尔除运算及布尔四则运算 众所周知， 在普 通 代数中 存在加、 减、 乘、 除四 则 运算， 而 在 布尔代数中 却只 有 布尔 加( 或运算) 及布尔乘( 与 运算) 运算。 有学者通过与 普通代数的四则运算相比 较， 将布尔减 和 布 尔 除 运 算 引 入了 布 尔 代 数 系 统 川， 引 起了 人 们的 关 注。 特 殊 运 算 布 尔 减 与 布尔 除 运算的引入及其性质的 研究， 完善了 对布尔四则运算的讨论。 2 . 1 . 1布尔减、布尔除运算的定义 利用 幂 级 数 展 开 对 二 元 逻辑 函 数的 全 部1 6 个 函 数几一 关 ， 的 真 值表( 见 表2 . i . i ) 进 达儿 a b五 厂 石 石 人 石 f a f f t. f l f 2 f f a f s 0 a bb . 4 由丑 . 4 十 b a十 b a (db ab i 行 分 析 可 知 (8, ， ， 1 6 个 函 数 中 还 有4 个 a i a i f i i f 3 未 定 义 而f z 与 f 4 、 f l 气 z 分 浙江大 学硕士学 位论丈 近代数字理论中的特殊运算及其应用研究 别相类似， 应属于同一种函数。 通过与普通代数中减、 除运算的比较， 用三个 最基本运 算 与、或、非) 分别定义这两种函数为布尔减及布尔除; 布 尔 减 :a 一 b0 a 厉，b - a = 元b .( 2 . 1 . 1 ) 布尔除:a 令 b 会 a 十 b. 上述定义中的符号 “ 十 、 一 么+ ” b + a - a + b. t 2 . 1 . 2 己 不是普 表2 . 1 . 2布尔 加、 减、 乘、 除运算真值表 通代数中的四则运算符号， 而是表示与之相对应 的布尔加 ( 或) 、布尔减、布尔乘 ( 与)和布尔 除运算 ( 真值表见表2 . 1 . 2 ) . a ba+b a一b a b a二b 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 1 2 . 1 . 2布尔减与布尔除的基本公式与性质 一与常量0 . 1 有关的性质 a一0二a a一1 二0 滋+0=1 a+1 二a 0 一a二0 1 一 a=a o +a=才 1 +a=1 二 与单变量有关的性质 a一a=0 a+a二1 a一a=a a+a= a a-a=a a-a= a 三.与多变量有关的性质 1 .交换律关系 布 尔减及布尔除 不满足 交换律， 即a 一 b# b - a , a = b *b + a， 但满足以 下 关系: a一b= a=b= b一a b- - a a一b一c=a一c一b a+b : - c=a+ c=b 2 .结合律关系 布尔减及布尔除不满足结合律， a一 b 一 c二 ( a 一 b ) ( a 一 c ) a + b = c二 ( a = b ) + ( a + c ) s .分配律关系 布尔减及布尔除满足结合律: 但满足以一 f 关系: a 一 b 一 c= a 一 ( b 十 c ) a = b + c= a + ( b + c ) 浙江大学硕士学位论文 近代数字理论中的持殊 运算及其应用研究 a ( b 一 c ) = a b 一 a c 反演规则 a一b=a+b a + ( b + c ) = ( a 十 b ) + ( a + c ) a+b二a一b .f ( a , b ， 一， 0 , 1 ; + ， 一 ，. ， 干 , 0 ) , 0 ) = f ( a , b , , 1 , 0 ; , + , + ， 二0 1 0 ) ) 对偶规则 如果两个逻辑式相等， 则 将式中 所有的“ 。 ” 跟“ 十” 交换、 “ + ” 跟 “ 一 ” 四五 u 0”跟 “ e”交换、. 4 1, 跟 + 1 ”交换得到的对偶式必定相等。例如， a ( b 一 c ) = a b 一 a c必 有a + ( b + c ) = ( a + b ) + ( a + c ) 。 交换、 根据 上述公式最直接的 证明 方法就是利用布尔减、除运算的定 义。也可利用真值表证 明。由于存在对偶规则，以 上诸式只要证明 其中一半的公式， 其余公式可有对偶规则 予以证明。 六.一 、+ 、非 运算构成完各集 下 面列出与本文推导有关的公式: 1 一 a= a , 0 一 a = o , a b 二 a 一 b , 0 -. a= a , 1 + a= 1 , a十 b= a - - b , a 一 b 一 c= a 一 ( b 十 c ) a + b - c= a + ( b c ) 2 . 1 . 3 布尔四则运算的基本规则及其变换表 一布尔四则运算的基本规则 布尔加 0 +0=0 0 +1 二1 1 +0 =1 1 +1 =1 布尔减 0一0=00 一1 =0 1 一0=11 一1 =0 布尔乘 0 . 0 =0 0 . 1 =0 1 . 0=0 1 . 1 =1 布尔除 0 - 0=1 0 +1 二0 1 +0 =1 1 +1 =1 二.布尔运算变换表: 布尔四则运算之间的变换如表2 t3 所示。 浙江大学硕士学 位论丈 近代数字理论中的特殊运算及其应用研究 表2 . 1 . 3 布尔 运算变 换表 由 该 表 可 知 布 尔 减 和 非 运 算 、 布 尔 除内 容 形 式 一 和非运算均构成完备集。 一 一卞一 -b一一b一刀b a=a二a月 a十b a一b a一b a一b a b a b a.b一一材 讨一间 a b a : - b a十b 忿二产 - . 山 a十b a+b a+b 2 . 2多 值模减、 模除运算及模四则运算 由于基于二值模代数系统的电 路具有容易 测试的 优点， 因此对于它的研究一直受到重 视。文献 1 1 , 1 2 , 1 5 把二值模代数推广到多值逻辑， 文献( 1 3 证明了 模代数适用于任何 模为质数( 素数) 的多 值逻辑， 且模加与模乘运算构成完备集， 任惫质数为模的多 值逻辑函 数具有相应的规范展开式。 文献 1 6 3 提出了 模减与模除运算， 并指出它们适用于任何模为 质数的模代数系统。 针对多值模代数的研究中 缺乏对模为合数的模减、 模除 运算以 及模为 合数时任意多值逻辑函数的展开式的讨论 文献( 1 7 3 提出 与讨论了 模为合数的 模减、 模除 运算，并推导出模为4 时任意单变量函数的展开式，以 补充对模代数系统的研究. 研究表明， 以 异或( 模2 加) / 与( 模2 乘) 运算表示的函数所对应的电 路特别具 有容易 测试的优点， 因此对二值情况下的 模代数系 统 ( 与异或代数系统) 研究一直受到重视， 并 且把它扩展到多值逻辑的研究中， 建立了以 模乘和模加运算为基本运算的多值模代数系 统。 在二值代数的 研究中， 人们就设想直接引用普通代数中的算术运算。 在普通代数中加 法与乘法是 二种最基本的 算术 运算， 但对于 变量取值域( o , 1 ) 的 二值情况， 普通加法会发 生超出取值域的困 难， 为此引 入模2 加的 概念， 并常用由作模2 加的运算符。 而对于 乘法 不必施以模2 限 制， 但也可以 称它为 模2 乘。 r e e d 与m u l l e r r 证明了 模2 乘运算与 模2 加运算能组成完备集，即任何二值函数均可由 此二种基本运算表示成规范展开形式 r e e d - m u l l e r 展开式 ( 相当于 普通代数中的 泰勒展开) 。1 9 2 4 年b e r n s t e i n 将二值模代数 ( 与、 异或代数) 扩展到多值领域中， 将模2 加、 模2 乘概念扩展到多值逻辑中 ，对应地引 入了 模r 加和模r 乘运算。 在后续者的努力下， 建立了以 模r 加和模r 乘运算为基本运算 的传统的多值模代数系统。 必须注意的是: 模代数系 统中的变量取值具有数 值大小的 意义。 事实上，当r = 2 时 ( 二值情况) 模r 加和模r 乘运算即为 模a 加及模2 乘 ( 分别为二值 逻辑代数中的异或运算及与运算) ， 相应的多值模代数系统即退化为二值情况下的 模代数 系统。 针 对多 值 模代 数中 缺 乏 模 减、 模 除 的问 题， 吴 训 威 在1 9 9 5 年 提出了 两 种 特 殊 模 运 算 一 一模为质数的模减、 模除运算，从而完善了多值模四则运算， 然而缺乏模为 合数的 模减、 浙江大学 硕士学位论文 近代数字理论中的特殊运算及其应用研究 模除 运算。 王伶俐提出了 类质数的 概念， 在此基础上提出了 模为任惫大于等于2 的正整数 ( 含质数和合数) 的模减、 模除运算， 从而进一步完善了 模四则运算。 但有关研究还需进一 步深入。如模减、 模除的 性质、是否构成新的完备集、 展开式如何、怎样化简等。 在普通代数中除了二种算术运算响 一- 加法与乘 法外， 还引入了 它们的算术逆运算 减法和除法运算。构成了加、减、 乘、除四则运算。 那么多值模代数中却与模r 加及模r 乘运算相对应的逆运算是否存在? 有何性质? 这些 将在这是本节所要讨论的问 题。 2 . 2 . 1 模为质数时多 值模减、模除运算 is ) 一，模乘和模加运算 传统的多值模代数系统的基本运算是模乘和模加运算， 它们分别定义如下: 模 r t f z : x y a x y ) , d 模 r 加 运 算 : x eb y 0- ( x + 刃 m od ( 2 . 2 . 1 ) 以r = 3 的三值逻辑为例， 模3 加及模3 乘可定 义为如表2 表2 . 2 . 1 ( 2 . 2 . 2 ) 2 . 1 . 模 3 加及模 3 乘 而任意多值函数均可表示成规范展 开一一r e e d - - m u l l e r 展开式. 模代数的建立是在加法与乘法二种运 算的 基础上仿照普通代数进行的， 但在普 通代数中具有加、减、 乘、 除四 种运算。 鉴此，有学者引入了减法与除法。以此完 + m o d 30 1 2.m o d 3 0 1 2 o 1 2 0 1 2 1 2 0 2 0 1 0 1 2 000 0 1 2 0 2 1 善对模代数系统的研究。本小节的讨论将适用于任何基为质数的 模代 数系统。 二. 模减和模除运算 1 模减运算 在r 值 模 代 数中 减 法 运 算 遇 到 的 困 难 是 出 现 负 数， 即 超 出 正 摊 数 的 取 值 域e , , e , 二 o . 1 , 2 ， 。封。 借鉴模r 加的取模方法， 习 通过加上r 的整数倍消除负数，使之回到取 值域内，由 此可提出 模减的定义， 但由 于减法为加法的逆运算，因此亦可由已 有的 模加， 模乘运算来定 义. 定 理2 . 1对 于 确 定 的 n , k 尽， 则 可 找 到 唯 一 的 ， 尽， 使 满 足m 9 n = k 。 证明若有某 m满足 mon = k，则在该式二边模加 ( r一 1 ) . :后有 m e 9 r n = k e$ ( ， 一 1 ) n， 因 r n = 0 ， 故 有m= k e) ( r 一 l n ， 显 然 此。 是 唯 一 确 定 的。 证毕。 由定理2 , 1 可得出 如下定义: 定 义2 . 1若二 。 n - k , m , n , k e 尽， 由 于 对 给 定 的n , k ， 式 中。 为 唯 一 的 ， 因 此 浙江大学 硕士学位论文功 近代数字理论中 的特殊运葬及其应用研究 可 记为m= k on， 且定 义它为k ( 被减数 ) 与n ( 减数) 模r 减 运算。 2 .模除运算 在r 值代数中除法运算遇到的困 难是出 现分数，即 超出了 原整数取值域。由 于除法为 乘法逆运算，故可从讨论模 r 乘出发来定义模 r除， 引 理1若m 1 = 0 , m , l e 尽， 则m , 1 中 至 少 有 一 个为 零. 证明 因r 为质数， 故m , 1 的算术乘积不可能为r 的倍数， 则当m 1 = 0 即m , 1 的算 术乘积必为零时，m 1 = 0 中至少有一个为零。证毕。 引 理2若m , - / = m 2 m l , m 2 1 1 e 尽， 且1 x 0 ， 则 必有二 : = m 2 , 证明 对 等 式 两 边 模r 减 去m 2 d 有 m , d o m 2 . 1 = 0 即 m , 9 m , ) 1 二 0 由 刊 x 0 ， 据 引 理1 有 m , 9m 2 = 0， 注 意 到m m : 的 算 术 差 不 可 能 为士 r 。 而 必 为 零， 故m , = m 2 。 证毕。 推论1若m , * m , ， 则 只 要1 x 0 ， 必 有m , # m 2 1 推论2 设m i 1 , 2 , . - , r 一 1 ) ， 即m , 1 # 0 . 则m i 的 模r 乘可作成 矩形乘 积表， 如 表2 . 2 . 2 所示。由引理1 知表中每个元素均非零， 且由推论1 间知表2 . 2 . 2 中每一行或列 内不存在二个相同的 元素， 因 此表中每一行或每一列中的( r - 1 ) 个元素必是1 , 2 , ， r - 1 的某一种排列。 以 表2 . 2 . 2 为例， 表中的模3 乘法表中的 非零部分呈现推论2 的 这一特性。 表2 . 2 . 2 。 与i 的 模r 乘积表 推 论3 m , n e 1 , 2 , . . . , r 一 1 1 对 于 给 定 的 ，总能找到唯一的 l e ( 1 , 2 , . . . , r 一 1 ) ，使满足m 1 = n , 此推论可扩展到n =0的情况， 此 时有i =d o m 义 1 2 ” 一( r - 1 ) i 2 ( r - 1 ) n, 1 n1 2. “二n , a - u n 2 1 n 2 2 . . . . . . . . . n 2 tr - u n( , - , ) , n a - us 0 0 n a - u c - u 定义2 . 2 如m 1 = n ，n , l e , ， m e 1 , 2 , . . . , r - 1 ， 则由 于 对于n 及非零m , ! 是 唯一的， 因 此可记1 = n l m， 且定 义它为 n ( 被除数) 与m ( 除数) 的模r 除运算。 即有 n o ，- ( n 十 m ) ,， l # 。 定理 2 . 2 在基为 质数的 模代数系统中， 只要m#0。则 n / m总可整除得到l ，使 i e e , ， 且 满 足m 1 = n . 由 于n 乃由: 与i 的 算 术 乘 积 取 模所 得， 因 此 应 存 在 某自 然 数k . 浙江大学 硕士学 位论丈 近代数字理论中的持殊运算及其应用研究 使n + k r 及为。 与z 的 算 术乘，即 被。 算 术整除. 2 . 2 . 2 模为合数时多值模减、模除运算 定义2 . 3 对于一个整数变量i 取模r 运算就是找到一个整数m ， 使得i 十 m r = j ， 其中 e , j 6 尽， 尽6 1 , 2 ， 一， r 一 1 记 作( 1 ) , = j 。 由 模为质数的模减定义中 可知， 模r 减运算是模r 加运算的逆运算。 在上述定义中对m ， n，k并未提出 特殊要求， 因此模r 减运算的定义不仅适用于r 为质数， 同样也适用于r 为合数 的多值逻辑系统。模减运算的引入使模代数系统的变量域扩展至负数。 模为合数的模减定 义如下: 定 义2 . 4若m 由 n = k , m , n , k e 耳， 由 于 对 给 定 的n , k ， 式中。 为 唯一 的 ， 因 此 可记为m二 k e3n ， 且定义它 为k( 被减数) 与n( 减数 ) 模r 减 运算。 定 义2 . 5在多 值 模r 代 数 系 统中 ， 当 且 仅 当 不 存 在 非 零 整 数b e 0 , 1 , 2 , ， 二 ， r 一 1 ) 使得a e 0 , 1 , 2 , . . . , r 一 1 有a b = 0 时称a 为类质数，否则 称a 为 非类质数。 显然0 对所有的 模代数系统均为非类质数， 而1 对所有的 模代数系统均为类质数 当 r 为质数时，由 质数的性质可知，i ,。 r - 1 均为类质数.当r 为合 数时可根据定义2 . 4 予以确定。 例如r = 4 时，1 , 3 为类质数， 0 , 2 为非类质数. 又如。9 时，1 , 2 , 4 , 5 , 7 , 8 为 类质数， 0 , 3 , 6 为非类质数. 定 义2 . 6 若m l - n , m , n , l e 0 , 1 , 2 , . . . , r 一 1 ) ， 且i 为 类 质数，则 可定义i = n 白m 为n ( 被除数) 与m ( 除数) 的模r 除 运算。即有 ” o m- ( n + m ) m m ，其中 i 为 类 质 数 根据上述讨论可知， 在多 值模r 代数系统中， 只有类质数才可作模除运算的除 数。由 于r 为质数时，只有0 为非类质数， 1 , 2 -。r -1 均为 类质数， 所以除0 以 外均可作模 除运算的除数， 上述给出的定义 不仅适用于r 为 合数， 也适用于r 为 质数的多 值逻辑系统。 2 . 2 . 3多值模四则运算 模为 质 数 的多 值 模 代数中 的 模 减， 模 除 运算 定 义， 将 模 减 与 模 除 运 算 从 二 值 逻 辑 扩展 到部分多值逻辑。 在此荃础上， 将模减与模除运算从模为质数的多值模代数系统进一步扩 展到 模为 合数的多 值模代数系 统。 从 而进 一步完善了 对模代 数系统的四 则 运算研究。 表2 . 2 . 3、 表22 4 分 别 给出了r 二 3( 质数 和r 二 4 合数)时 模四 则 运算的 真 值表 .应该 指出 ， 尽管表2 . 2 . 3、 表2 . 2 . 4 显 示 ， 在三 值逻 辑与四 值逻 辑中 ， 在a ob有定 义的 地方 a e ) b 与a 8的值相同 ， 但是一般而言在r为 其他值时不存在类似的关系， 浙江大学硕士学位论文 近代数字理论中的 特殊运算及其应用研究 表2 . 2 . 3 r ，3( 质数) 时 模 4 则 运界 的真值表表 表2 . 2 . 4 r 二4( 合数)时 模四则 运算的 真值表 a由 b ao b a - b a b 0八u 八u内 a 由b acb a b ae)b 八幽u 0l02 0 0 0 3 八ucu .月，1月j 1勺山，j 八u气 .己，月 1 0 引c 月1咭.主八u， ，”u 八卜，山 ，勺山 nu，山 1，凡 ，月产了 ，石n nu.1，飞ji“ 2，山2，山内、 几乙n 刀-nl，01，乙0 a一n八u八vlll， 卜u， in汽 印、八u.t. 0 1