一章逻辑代数基础

第一章逻辑代数基础§1.0数字逻辑基础知识§1.0数字逻辑基础知识模拟信号与数字信号模拟信号模拟信号是在时间和幅值上都连续变化的信号，例如温度、压力、磁场、电场等物理量通过传感器变成的电信号，如图所示。模拟电路

对模拟信号进行传输、处理的电子线路称为模拟电路。§1.0数字逻辑基础知识模拟信号与数字信号数字信号数字信号是在时间和幅值上都不连续，并取一定离散数值的信号，通常是由数字0和1，也可以说是由低电平电信号和高电平电信号组成的信号，如图所示。数字电路对数字信号进行传输、处理的电子线路称为数字电路。§1.0数字逻辑基础知识数字电路数字电路的特点有：以二值数字逻辑为基础，所处理的数字信号只有0和1两种取值，即只要处理两种电平，因此易于用电路来实现高电平、低电平允许有一定的取值范围，因此电路抗干扰能力强；数字电路不仅能完成数值运算，而且能进行逻辑判断和运算，这在控制系统中是不可缺少的凡是可以区分两种状态的物体就可以记录数字信号，信息便于长期存储，便于计算机处理§1.0数字逻辑基础知识数字电路数字电路的类型组合逻辑电路：逻辑门组成时序逻辑电路：触发器组成数字电路研究的主要任务对给定电路输入和输出之间的逻辑关系进行分析按照要求设计一个性能合适的电路运用的主要数学工具是逻辑代数，也叫布尔代数或开关代数，因而数字电路也叫逻辑电路表达电路功能的主要方式是真值表、逻辑函数表达式、波形图等§1.0数字逻辑基础知识数字技术与数字系统数字技术数字信号和模拟信号之间可以相互转换，模拟信号经过取样、量化转换为数字信号的过程称为模数转换。数字技术就是为了适应和满足不同的应用需要，通过转换电路把模拟信号变成由0和1组成的数字信号，然后由数字系统对数字信号进行存储、运算、处理、变换、合成等。数字系统输入和输出都是数字信号而且具有存储、传输、处理信息能力的系统称为数字系统。一台微型计算机就是一个典型的最完善的数字系统。§1.0数字逻辑基础知识数制与代码数制：多位数码中每一位的构成方法以及从低位到高位的进位规则称为数制。常用的数制有十进制、二进制、十六进制和八进制。基数：数制的基数就是在该数制中可能用到的数码个数。（例十进制的基数是10，数码为0~9；二进制的基数是2，数码是0、1）位权：在某一数制的数中，每一位的大小都对应着该位上的数码乘上一个固定的数，这个固定的数就是这一位的权数。权数是一个幂，如等。§1.0数字逻辑基础知识数制与代码十进制基数是10，数码为0~9，逢十进一表达式

3

3

13×１０２＝3００3×１０１＝3０1×１００＝1

＝331同样的数码在不同的数位上代表的数值不同。§1.0数字逻辑基础知识数制与代码二进制基数是2，数码为0、1，逢二进一表达式用电路的两个状态---开关来表示二进制数，数码的存储和传输简单、可靠。位数较多，使用不便；不合人们的习惯，往往只在机器内部使用§1.0数字逻辑基础知识数制与代码十六进制基数是16，数码为0~9、A~F，逢十六进一表达式八进制基数是8，数码为0~7，逢八进一表达式§1.0数字逻辑基础知识数制与代码数制转换十—二进制转换整数：除2取余倒记法小数：乘2取整正记法§1.0数字逻辑基础知识数制与代码数制转换二—十六进制转换§1.0数字逻辑基础知识数制与代码数制转换二—八进制转换§1.0数字逻辑基础知识数制与代码代码用以表示十进制数码、字母、符号等信息的一定位数的二进制数称为代码。编码建立二进制代码与字母、符号及十进制数码的一一对应的关系称为编码。常见编码二—十进制码（BCD码）ASCII码§1.0数字逻辑基础知识数制与代码BCD码用四位二进制数表示0~9十个数码，即为BCD（BinaryCodedDecimal）码。有权码

无权码：不满足上述关系式的编码称无权码四位二进制数最多可以有16种不同组合，不同的组合便形成了一种编码。常见的BCD码有有权码：8421码、5421码、2421码无权码：余3码、Gray码§1.0数字逻辑基础知识常用的BCD码十进制数8421码5421码2421码余3码Gray码000000000000000110000100010001000101000001200100010001001010011300110011001101100010401000100010001110110501011000101110000111601101001110010010101701111010110110100100810001011111010111100910011100111111001101权842154212421二进制数8421码5421码2421码余3码Gray码000000000001111100102223001133302010044417010152601106340111745100085510019661010771011858110096981101791110811119§1.0数字逻辑基础知识二进制数的算术运算数值运算当两个二进制数码表示两个数量大小时，它们之间可以进行加、减、乘、除运算。运算过程遵照逢二进一的原则例：1100011

100010001011

101101100001011110111§1.0数字逻辑基础知识二进制数的算术运算原码以最高位作为符号位，正数为0，负数为1反码将二进制数中各位的0改为1、1改为0补码正数的补码和它的原码相同；负数的补码可以通过将原码除符号位之外的数值位逐位求反，然后在最低位上加1得到两数相减可用它们的补码相加来完成§1.1逻辑代数概述§1.1.1逻辑变量和逻辑函数逻辑变量逻辑代数中的变量称为逻辑变量输入逻辑变量：逻辑条件输出逻辑变量：逻辑结果逻辑变量的值二值逻辑中逻辑变量的取值只有0和1两种可能，即“真”和“假”逻辑值不表示数值的大小，只表示两种对立的逻辑状态，如电位的高低、开关的开合等，称为状态赋值逻辑变量的基本运算是指逻辑值之间的逻辑运算§1.1.1逻辑变量和逻辑函数逻辑函数逻辑函数是描述逻辑变量之间逻辑关系的函数如果对应于输入逻辑变量A、B、C、…的每一组确定值，输出逻辑变量Y就有唯一确定的值，则称Y是A、B、C、…的逻辑函数。记为

f反映Y和A、B、C、…之间的因果关系，即“条件”与“结果”的关系自变量和函数的值都只能取0或1逻辑函数与自变量的关系由有限个基本逻辑运算（与、或、非）决定§1.1.1逻辑变量和逻辑函数逻辑函数逻辑函数相等和相反设有两个逻辑函数输入变量均为A、B、C、…，且对应于输入变量的任何一组取值，，则称两个逻辑函数相等。若两个逻辑函数相等，则它们的真值表一定相同；反之，若两个函数的真值表完全相同，则这两个函数一定相等。如果对应于输入变量的任何一组取值，，则称这两个逻辑函数互为反函数。§1.1.2逻辑运算基本逻辑运算逻辑与（AND）只有决定事物结果的全部条件同时具备时，结果才会发生，也叫逻辑乘，运算结果称为逻辑积AB电源开关A开关B灯断断灭断合灭合断灭合合亮00ABY0110110001规定：开关合为逻辑“1”，开关断为逻辑“0”

灯亮为逻辑“1”，灯灭为逻辑“0”§1.1.2逻辑运算基本逻辑运算逻辑或（OR）在决定事物结果的诸多条件中，只要有任何一个满足结果就会发生，也叫逻辑加，运算结果称为逻辑和开关A开关B灯断断灭断合亮合断亮合合亮00ABY0110110111规定：开关合为逻辑“1”，开关断为逻辑“0”

灯亮为逻辑“1”，灯灭为逻辑“0”A电源B§1.1.2逻辑运算基本逻辑运算逻辑非（NOT）只要条件具备结果不会发生，而条件不具备时结果一定发生，也叫逻辑求反开关A灯断亮合灭规定：开关合为逻辑“1”，开关断为逻辑“0”

灯亮为逻辑“1”，灯灭为逻辑“0”A电源AY0110§1.1.2逻辑运算基本逻辑运算§1.1.2逻辑运算复合逻辑运算与非（NAND）由与运算和非运算组合而成，条件都具备时结果不会发生00ABY0110111110§1.1.2逻辑运算复合逻辑运算或非（NOR）由或运算和非运算组合而成，在决定事物结果的诸多条件中，只要有任何一个满足结果就不会发生00ABY0110111000§1.1.2逻辑运算复合逻辑运算异或（XOR）异或是一种二变量逻辑运算，当两个变量取值相同时逻辑函数值为0；当两个变量取值不同时逻辑函数值为100ABY0110110110§1.1.2逻辑运算复合逻辑运算同或（XNOR）同或是异或的求反运算，当两个变量取值相同时逻辑函数值为1；当两个变量取值不同时逻辑函数值为000ABY0110111001§1.1.2逻辑运算复合逻辑运算§1.1.2逻辑运算逻辑运算的规律在一个逻辑运算表达式中逻辑非的优先级最高，逻辑与的优先级其次，逻辑或的优先级最低逻辑运算表达式中有括号时，应先做括号内的运算逻辑运算表达式中有取非符号时，先做“非”号下表达式的运算，再进行求反运算§1.1.3逻辑函数表达形式逻辑函数的表示形式真值表由逻辑函数输入变量（n个）的所有可能取值组合（个）及其对应的输出函数值所构成的表格直观地反映了变量取值组合和函数值的关系，便于把一个实际问题抽象为一个数学问题真值表具有唯一性0101BYA0011输入0001输出

与逻辑真值表§1.1.3逻辑函数表达形式逻辑函数的表示形式逻辑函数表达式由逻辑变量和逻辑运算符连接起来所构成的式子称为逻辑表达式，逻辑表达式可以有多样性逻辑表达式描述了逻辑变量与逻辑函数间的逻辑关系，是实际逻辑问题的抽象表达逻辑函数表达式通常采用“与或”的形式，即乘积项相加，如若表达式的乘积项中包含了所有输入变量的原变量或反变量，则这一项称为最小项，上式中每一项都是最小项§1.1.3逻辑函数表达形式逻辑函数的表示形式逻辑图将逻辑函数表达式中的各逻辑运算关系，用对应的逻辑符号和连线表示出来，就构成和逻辑函数相对应的逻辑图。波形图反映逻辑变量输入和输出波形变化规律的图形，也称为时序图。卡诺图§1.1.3逻辑函数表达形式各种表示方法之间的相互转换由真值表写逻辑表达式取出真值表中输出变量为1对应的那些输入变量取值的组合每组输入变量取值的组合对应一个乘积项，其中输入变量取值为1的以原变量形式出现，取值为0的以反变量形式出现将这些乘积项相加，即为真值表对应的逻辑表达式由逻辑表达式画真值表把各输入变量取值的所有组合状态逐一代入表达式，求出输出变量的值，列成表即可§1.1.3逻辑函数表达形式各种表示方法之间的相互转换由逻辑图写逻辑表达式从输入端到输出端逐级写出各个逻辑门符号对应的输出表达式由逻辑表达式画逻辑图把逻辑表达式中的逻辑运算符号分别用相应逻辑门电路的逻辑符号表示出来，再给予正确的连线即可§1.1.3逻辑函数表达形式各种表示方法之间的相互转换实际逻辑问题举例裁判判定电路：举重比赛，设有一名主裁判和两名副裁判，当主裁判和至少一名副裁判判定合格，运动员的动作方为成功。真值表Y

0

0

0

0

0

1

1

1

A

B

C

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

设A为主裁判，B、C为两名副裁判，判定合格为1，不合格为0。运动员的动作成功与否用变量Y表示，成功为1，不成功为0。§1.1.3逻辑函数表达形式各种表示方法之间的相互转换实际逻辑问题举例逻辑表达式逻辑图&

1YBCA§1.2逻辑代数的基本定理§1.2.1逻辑代数基本公式布尔恒等式0-1律等幂律互补律自反律交换律§1.2.1逻辑代数基本公式布尔恒等式结合律分配律反演律（摩根定理）上述基本公式可以用列真值表的方法加以验证定律中逻辑乘与逻辑加都成对出现只要用一种形式的电路（“与非”或者“或非”）就可以完成所有的逻辑功能§1.2.2其他常用逻辑恒等式常用公式吸收律冗余律§1.2.3逻辑代数基本定理代入定理定义在任何一个逻辑等式中，如果将等式两边出现的某变量都用一个函数代替，则等式依然成立

用途利用代入定理可以把前述基本公式和常用公式推广为多变量形式§1.2.3逻辑代数基本定理反演定理定义对于任一个逻辑函数，若将其中所有逻辑运算符“+”、“•”交换，逻辑常量“1”、“0”交换，所有逻辑变量取反，得到的结果是反函数注：不属于单个变量上的“非”号应保留不变用途用于求取一个已知逻辑函数的反函数§1.2.3逻辑代数基本定理对偶定理定义对于任一个逻辑式，若将其中所有逻辑运算符“+”、“•”交换，逻辑常量“1”、“0”交换，所有逻辑变量保持不变，得到的结果是对偶式。若两个逻辑式相等，则它们的对偶式也相等。用途可从已知的公式推导更多的运算公式；证明两个逻辑式相等可以通过证明它们的对偶式相等来完成§1.3逻辑函数的标准表达式和卡诺图§1.3.1逻辑函数的标准表达式逻辑函数的标准与或式最小项在n个逻辑变量的逻辑函数中，若m为包含n个因子的乘积项，而且这n个因子均以原变量或反变量的形式在m中出现一次，则称m为该组变量的最小项n个逻辑变量的逻辑函数有个最小项若两个最小项只有一个因子不同，则称这两个最小项具有（逻辑）相邻性§1.3.1逻辑函数的标准表达式逻辑函数的标准与或式最小项的重要性质在输入变量的任何一组取值下，必有且仅有一个最小项的值为1任意两个不同的最小项之积，其值恒为0输入变量的全体最小项之和，其值恒为1具有相邻性的两个最小项之和可以合并成一项并消去一对因子标准与或表达式（最小项之和，SOP）§1.3.1逻辑函数的标准表达式逻辑函数的标准或与式最大项在n个逻辑变量的逻辑函数中，若M为包含n个因子的和项，而且这n个因子均以原变量或反变量的形式在M中出现一次，则称M为该组变量的最大项n个逻辑变量的逻辑函数有个最大项若两个最大项只有一个因子不同，则称这两个最大项具有（逻辑）相邻性§1.3.1逻辑函数的标准表达式逻辑函数的标准或与式最大项的重要性质在输入变量的任何一组取值下，必有且仅有一个最大项的值为0任意两个不同的最大项之和，其值恒为1输入变量的全体最大项之积，其值恒为0具有相邻性的两个最大项之积可以合并成一项并消去一对因子标准或与表达式（最大项之积，POS）§1.3.1逻辑函数的标准表达式两种标准表达式之间的关系最小项和最大项之间的关系下标相同的最大项和最小项互补逻辑表达式的相互关系对于同一个逻辑问题，其逻辑函数的两种标准表达式之间存在以下关系§1.3.1逻辑函数的标准表达式将逻辑函数按照标准形式展开利用基本公式可以把任何一个逻辑函数化为最小项之和的标准与或表达式利用基本公式可以把任何一个逻辑函数化为最大项之积的标准或与表达式§1.3.2逻辑函数的卡诺图表示卡诺图的构成将n个变量的全部最小项各用一个小方块表示，并使具有逻辑相邻性的最小项在几何位置上也相邻地排列起来，所得到的图形叫做n变量最小项的卡诺图二变量卡诺图三变量卡诺图§1.3.2逻辑函数的卡诺图表示卡诺图的构成四变量卡诺图§1.3.2逻辑函数的卡诺图表示卡诺图的特点图形两侧自变量组成的二进制数所对应的十进制数大小是对应的最小项编号几何相邻的两个最小项仅有一个变量不同，即具有逻辑相邻性卡诺图具有循环邻接性，即处在任何一行或一列两端的最小项也具有逻辑相邻性§1.3.2逻辑函数的卡诺图表示逻辑函数在卡诺图上的表示将给定的逻辑函数按照最小项之和标准形式展开，在卡诺图上与这些最小项对应的方格内填入1，其余方格内填入0Y

0

0

0

0

0

1

1

1

A

B

C

0

0

0

0

0

1

0

1

0

0

1

1

1

0

0

1

0

1

1

1

0

1

1

1

裁判判定问题的真值表和卡诺图§1.4逻辑函数的化简§1.4.1逻辑函数的最简形式逻辑函数的不同表示形式同一个逻辑函数的几种表示形式与或式（积之和，SOP）或与式（和之积，POS）与或非式§1.4.1逻辑函数的最简形式逻辑函数的不同表示形式同一个逻辑函数的几种表示形式与非—与非式或非—或非式§1.4.1逻辑函数的最简形式逻辑函数化简的必要性同一函数的逻辑表达式有多种形式，或繁或简每个逻辑表达式对应一个逻辑电路图，因此一种逻辑功能可用多种逻辑电路来实现，简单的形式对应简单的电路，繁琐的形式对应复杂的电路为了用最少的器件和最少的连线实现逻辑功能，必须通过化简，找出最简逻辑表达式§1.4.1逻辑函数的最简形式逻辑函数的最简表示形式最简与或式包含的乘积项最少而且每个乘积项里的因子数也最少最简或与式包含的和项最少而且每个和项里的因子数也最少常用表达式一般都是与或式，便于用卡诺图表示以利于化简，且与或式可以转换为其他形式的逻辑式，故只讨论与或形式的化简问题§1.4.2代数化简法化简的目标消除与或式中多余的乘积项和每个乘积项中多余的因子代数化简法的原理利用逻辑代数的公式和定理化简逻辑表达式，化简的过程和结果便捷与否取决于对公式和定理掌握的熟练程度代数化简法的特点不受输入逻辑变量数目的束缚技巧性强，化简结果不明确§1.4.2代数化简法并项法利用公式合并乘积项并消去一个变量若两个乘积项中分别包含同一个因子的原变量和反变量，而其他因子都相同时，则这两项可以合并成一项，并消去互为反变量的因子§1.4.2代数化简法吸收法利用公式消去多余的乘积项如果某个乘积项是另外一个乘积项的因子，则这另外一个乘积项是多余的§1.4.2代数化简法消因子法利用公式消去多余的变量如果某个乘积项取反是另外一个乘积项的因子，则这个因子是多余的§1.4.2代数化简法消项法利用公式及消去冗余的乘积项若两个乘积项中分别包含同一个因子的原变量和反变量，而其他因子又是第三个乘积项的因子，则这第三个乘积项是可以消去的冗余项§1.4.2代数化简法配项法利用公式为某项配上能合并的项利用公式为某项配上所缺的变量，以便拆分后与其他项合并§1.4.3卡诺图化简法卡诺图化简法的原理具有相邻性的最小项可以合并消去互补的变量卡诺图化简的步骤将逻辑函数展开成标准与或表达式，即最小项之和的形式画出表示该逻辑函数的卡诺图找出可以合并的最小项并加以合并选取化简后的乘积项，得到最简与或式§1.4.3卡诺图化简法合并最小项的规则相邻的个最小项可围成一个卡诺圈，这个最小项可以合并成一项，并消去n对因子裁判判定问题的卡诺图§1.4.3卡诺图化简法选取化简后乘积项的规则乘积项应包含函数式中所有的最小项，即应覆盖卡诺图中所有的1值方格所用的乘积项数目最少，即可合并的最小项组成的卡诺圈的个数应尽可能少每个乘积项包含的因子最少，即可合并的最小项组成的卡诺圈的面积应尽可能大每个卡诺圈对应一个乘积项，其中的因子由左侧和上方取相同值的变量组成，取值为1的变量用原变量，取值为0的变量用反变量§1.4.3卡诺图化简法化简函数§1.4.3卡诺图化简法化简函数同一逻辑函数可能有多个最简表达式，即逻辑函数的化简结果不是唯一的§1.4.3卡诺图化简法化简函数卡诺图中填1方格可以被不同的卡诺圈圈用，但若某个卡诺圈中所有填1方格完全被包含在其它卡诺圈中，则该卡诺圈是冗余的§1.4.3卡诺图化简法

§1.4.4卡诺图运算卡诺图运算两个逻辑函数的运算只要将卡诺图上对应的方格进行逻辑运算即可巧妙地运用卡诺图运算可使一些逻辑函数化简的过程更为简单对某些特定目标函数的化简过程特别有效，如将逻辑函数化简成全部用“与非”电路或者“或非”电路构成的函数时§1.4.4卡诺图运算卡诺图运算规律