数字电路——分析与设计 ：第2章 逻辑代数基础

1、2.1 概述2.1.1 事物的二值性 世界上的许多事物都具有完全不同的两种状态，这就是平时所说的事物的矛盾性。我们可以举出很多这类完全对立的、处于矛盾状态的例子，如表2.1所示。 7/17/20221北京理工大学 信息科学学院7/17/20222北京理工大学 信息科学学院2.1.2 布尔代数 “逻辑代数”是十九世纪的英国数学家乔治布尔(George Boole)在1847年首先创立的。 这是一种仅使用数值“1”和“0”的代数。注意，这里的“1”和“0”并不代表数量的大小，而是表示完全对立的两个矛盾着的方面。 正是由于布尔构造出了二值代数系统，所以很多教科书上又把逻辑代数称作“布尔代数”(Boo

2、lean Algebra)。 布尔代数在创建的初期仅仅是应用于研究概率的问题，由于时代和生产力水平的限制，当时的人们并没有认识到这一代数理论的巨大应用前景。 7/17/20223北京理工大学 信息科学学院美国贝尔实验室的科学家克劳迪香农(Claude Shannon)于1938年写出了他那具有革命性的硕士论文继电器和开关电路的一种符号分析（“A Symbolic Analysis of Relay and Switching Circuits”）时，人们才真正认识到布尔代数的实用价值。 香农把布尔代数应用到开关电路的分析和设计上，所以还有一些教课书上把“布尔代数”叫做“开关代数”（Switch

3、ing Algebra）。 7/17/20224北京理工大学 信息科学学院2.2 逻辑变量和逻辑函数 2.2.1 基本的逻辑运算和逻辑变量 所谓逻辑就是指事物的因果之间所应遵循的规律,最基本的逻辑关系可以归纳为“与”逻辑、“或”逻辑和“非”逻辑三种逻辑运算。 1.“与”逻辑开关A、B是串联相接的，只有当两个开关A、B全都闭合时，灯泡 F 才能点亮。 7/17/20225北京理工大学 信息科学学院2.“或”逻辑决定某个事件的所有条件全都具备时，这个事件才会发生的因果关系定义为“与”逻辑。开关A、B是并联相接的，所以只要两个开关A、B中有任何一个开关闭合、或者是二者全都闭合时，灯泡F就能点亮。 决

4、定某个事件的所有条件中只要有任意一个条件具备、或者是某几个条件同时具备、或者是全都具备时，这个事件就会发生的因果关系定义为“或”逻辑。7/17/20226北京理工大学 信息科学学院3.“非”逻辑当开关A闭合时灯泡F是熄灭的，而在开关A断开时，灯泡F才能点亮。 事件的发生与否和决定这个事件的条件是否具备的状态刚好相反的因果关系定义为“非”逻辑。一个变量X如果仅有两个可能的取值“0”或“1”，则称这种仅有0、1两个取值的变量为逻辑变量（以后简称为变量） 。 逻辑变量7/17/20227北京理工大学 信息科学学院可把表2.1所列举的那些完全对立的矛盾状态实例都用一个逻辑变量来描述。 7/17/202

5、28北京理工大学 信息科学学院7/17/20229北京理工大学 信息科学学院表2.1中对立矛盾的状态与逻辑变量取值的对应关系完全是人为定义的。可以把表中“0”和“1”的位置对调一下而不失所述问题的合理性和一般性 。 开关A、B的“闭合”作为逻辑“1”，“断开”作为逻辑“0”。 灯泡F的“点亮”作为逻辑“1”，“熄灭”作为逻辑“0” 。 这种反映因果逻辑关系的表叫做真值表。 对开关的“闭合”与“断开”、灯泡的“点亮”与“熄灭”作如下的逻辑规定：7/17/202210北京理工大学 信息科学学院真值表的结构特点：真值表的左栏列出的是表示条件的逻辑变量以及这些变量取值的所有可能的组合。 真值表的右栏填

6、入的是表示事件的逻辑变量以及它对应于各条件变量取值的逻辑运算结果。 7/17/202211北京理工大学 信息科学学院最基本的逻辑是“与”、“或”、“非”，与之相对应的也有三种基本的逻辑运算。 逻辑运算：1.“与”运算（逻辑乘法）F = AB “AB”叫做逻辑表达式，它表示逻辑变量A和B做“与”运算（也叫逻辑乘法运算） 。 运算符号“ ”叫做“与”运算符 。 其他形式的“与”运算符有：“”、“”和“&” 。 7/17/202212北京理工大学 信息科学学院“与”运算的含义是：只有当A、B全为“1”时，F 才为“1”；A、B中只要有一个为“0”或者二者都为“0”时，F 就为“0”。 “与”运算的规

7、则就是：00=0， 01=0， 10=0， 11=1。 “与”运算规则与普通乘法的规律相同，但是含义却不同。 我们采用符号“ ”作为“与”运算符，有时干脆省去“ ”而把 F = AB 写成 F = AB。 7/17/202213北京理工大学 信息科学学院2.“或”运算（逻辑加法）F = A+B “A+B”也是逻辑表达式，它表示逻辑变量A和B做“或”运算(也叫逻辑加法运算)。 运算符号“+ ”叫做“或”运算符 。 其他形式的“或”运算符有：“”、“”和“|”。 “或”运算的含义是：A和B当中只要有一个为“1”或者全为“1”时，F 就为“1”；只有当A、B全为“0”时，F 才为“0” 。 我们采用

8、符号“+ ”作为“或”运算符。 7/17/202214北京理工大学 信息科学学院“或”运算的规则是：0+0=0， 0+1=1， 1+0=1， 1+1=1 。 “或”运算规则的前3条与普通加法的规律相同，但是含义不同。 “或”运算规则的最后1条与普通加法的规律在形式上和含义上均不相同。在这里，1+12，且1+1(10)。 要注意：逻辑运算不是数值运算，逻辑运算是因果关系的逻辑判断。 7/17/202215北京理工大学 信息科学学院3.“非”运算上式表示逻辑变量F和A的取值相反，即A为“0”时F为“1”；而A为“1”时F为“0”。 “非”运算的运算规则就是：“非”运算是算术里所没有的。 读作“A非

9、”或者“A反”，有时也把“非”运算叫做求“补”运算，而把 读作“A补”。 在逻辑代数中，只有“与”运算、“或”运算和“非”运算这三种基本逻辑运算，没有其他的运算。逻辑变量的取值也只有“1”和“0”两种，而不能有其他的取值。这些是和普通代数不同的。 7/17/202216北京理工大学 信息科学学院在逻辑代数中也有逻辑运算的前、后优先次序：单变量上的“非”运算优先级最高。 “与”运算（逻辑“乘”）要优先于“或”运算（逻辑“加”）。 括弧“（ ）”内的运算要优先于括弧外的运算。 多变量上的“非”运算相当于加括弧。 例如： 的运算顺序是：先做 ，再做A+ ，最后再将所得结果与变量C相“与”。例如： 就

10、相当于 。7/17/202217北京理工大学 信息科学学院“与”、“或”、“非”这三种基本逻辑运算可分别由“与”门、“或”门和“非”门三种基本的逻辑门电路来实现。这三种基本门电路的逻辑符号如下所示 ：7/17/202218北京理工大学 信息科学学院2.2.2 逻辑函数 如果把“与”、“或”、“非”这三种基本逻辑运算组合成一个较为复杂的逻辑表达式，再把该逻辑表达式的运算结果（只能是“0”或“1”）赋予另一个逻辑变量，比如说F，于是就构成了一个逻辑函数。例如： F叫做逻辑因变量，即：逻辑函数。 F是逻辑自变量A、B、C、D的逻辑函数。 其中A、B、C、D叫做逻辑自变量，叫做逻辑表达式。7/17/2

11、02219北京理工大学 信息科学学院无论是逻辑自变量的定义域还是逻辑函数的值域都只能是“0”或“1”而不能是其它的取值。 逻辑函数是一个四变量的逻辑函数，可以抽象地记为： 四变量逻辑函数的四个变量A、B、C、D的取值组合总共有十六组（0000至1111）。 对于A、B、C、D四个变量的十六组取值都有一个确定的F取值（只能是“0”或“1”）与之对应。 逻辑函数和逻辑表达式与普通函数和算术表达式，有着本质的区别 。 7/17/202220北京理工大学 信息科学学院一般的多变量逻辑函数可以记为： 逻辑函数有时也被称作开关函数。 三种基本逻辑运算,即： 就是三个最基本的逻辑函数。前两个是两变量逻辑函数

12、；而最后一个是单变量逻辑函数。 逻辑函数的相等：若两个逻辑函数F和G的输入变量相同，而且对于任意的一组变量取值都有相同的函数值，则这两个函数相等，记作：F=G。换句话说，就是任何形式的两个逻辑函数，只要它们的真值表相同，则彼此相等。 7/17/202221北京理工大学 信息科学学院任何一个逻辑操作的过程，都可用一个具有若干个逻辑变量的逻辑函数来描述，并可用一个与此函数相对应的逻辑电路来实现。先看一个例子。 LK下K上220V 楼梯照明电路原理图用逻辑变量F代表电灯L，并规定F=1表示灯亮，而F=0则表示灯灭；再用逻辑变量A、B分别表示两个开关K上、K下的位置，并规定“1”表示向上扳，而“0”表

13、示向下扳。 7/17/202222北京理工大学 信息科学学院A、B叫做输入逻辑变量；F叫做输出逻辑变量。 A、B也叫逻辑自变量，而F也叫逻辑因变量或逻辑函数。 逻辑函数和真值表各自都能完全地描述一个逻辑操作的过程。 一个逻辑函数对应了一张真值表；而一张真值表也对应了一个（或若干个）逻辑函数。 逻辑函数叫做“同或”逻辑函数。 其特点是：当A、B相同时，函数F为“1”，否则F为“0”。通常是把输入逻辑变量(逻辑自变量)列在真值表的左边；而把输出逻辑变量(逻辑函数)列在真值表的右边。 7/17/202223北京理工大学 信息科学学院逻辑函数和逻辑电路是相互对应的。逻辑函数可以由逻辑电路来实现；而逻辑

14、电路也可以由逻辑函数来描述。 2.2.3 逻辑函数与逻辑电路的关系例如，上一节所提到的“同或”逻辑函数就可以用下面的逻辑电路来实现它。 FAB “同或”逻辑电路7/17/202224北京理工大学 信息科学学院反之，如果给出一个逻辑电路，就可以根据这个逻辑电路写出用于描述该逻辑电路输入信号（变量）和输出信号（变量）之间关系的逻辑函数。 例如，给出下面的逻辑电路图FAB “异或”逻辑电路可以写出描述该电路输出信号F与输入信号A、B之间关系的逻辑函数表达式为： 7/17/202225北京理工大学 信息科学学院逻辑函数叫做“异或”逻辑函数。 其特点是：当A、B相异时，函数F为“1”，否则F为“0”。2

15、.3 逻辑代数的基本运算规律 2.3.1 逻辑代数的基本定律1.逻辑代数公理逻辑代数公理（或者叫基本原理）是整个逻辑代数系统的基石，以这些公理为出发点，可以证明所有逻辑代数系统中的各种定律和定理。 7/17/202226北京理工大学 信息科学学院逻辑代数公理实际上是逻辑常数“1”和“0”的基本运算规则。这些运算规则可直接由“与”、“或”和“非”的运算定义得出。这些公理归纳于下表： 7/17/202227北京理工大学 信息科学学院根据逻辑代数的公理，可以推导出逻辑代数运算的一些基本定律。下表给出了这些基本定律。 2.逻辑代数的基本运算规律7/17/202228北京理工大学 信息科学学院证明上表所

16、示基本定律的最有效的方法就是使用真值表，即，分别作出等式两边逻辑表达式的真值表，然后检验其结果是否相同。 例如：证明上表中的反演律。为此分别作出两个等式的等号两边逻辑表达式的真值表，如表2.8和表2.9所示。 7/17/202229北京理工大学 信息科学学院从表2.8和表2.9知： 这就是著名的狄摩根(DeMorgan)定理。在逻辑代数的运算中经常会用到狄摩根定理，它是一个非常重要的定理。 也可以用代数的方法来证明表2.7所列出的逻辑代数基本定律。 例如：可以用摩根定理、还原律和分配律的6号公式去证明分配律的6号公式。证明过程如下： （还原律） （摩根定理） （分配律6号） （摩根定理） 7/

17、17/202230北京理工大学 信息科学学院作业1：2-8，2-9的（1）、（2）、（3）、（8）、（9）（还原律） 2.3.2 三个重要规则1.代入规则任何一个逻辑等式，如果将等式两边所出现的同一个逻辑变量都代之以同一个逻辑函数，则该逻辑等式仍然成立，这就是代入规则。代入规则也叫代入定理。 7/17/202231北京理工大学 信息科学学院(结合律,摩根定理) 这就是三个变量的摩根定理。同理可以证明n个变量的摩根定理，即： 例如:摩根定理是再令：代入后一个等式，于是得到： 现在令：代入前一个等式；(结合律,摩根定理) 7/17/202232北京理工大学 信息科学学院2. 反演规则 若两个逻辑函

18、数F和G的输入变量相同，而且F和G对于任意的一组输入变量取值都有相反的函数值，则称这两个函数互反（或叫互补），记作： 或 。 反演规则的内容如下： 对于任意的逻辑函数F，如果对其表达式做下述三种变换： 把原表达式中所有的“ ”运算符换成“+”运算符，同时把所有的“+”运算符换成“ ”运算符；把原表达式中所有的逻辑常量“0”换成逻辑常量“1”，而把所有的逻辑常量“1”换成逻辑常量“0”； 7/17/202233北京理工大学 信息科学学院把原表达式中所有的原变量换成反变量，再把所有的反变量换成原变量。 则若则反演规则实际上是反演律（摩根定理）在求逻辑函数F的反（补）函数时的一种推广。它提供了一种可

19、以由逻辑函数F的表达式（较复杂时）直接求出其反（补）函数的方法。 例如：可直接写出：若于是就得到了函数F的反函数F。例如：7/17/202234北京理工大学 信息科学学院例如：则而例如：则绝对不能打乱原表达式的运算顺序；不属于单变量上的非号应保持不变。在运用反演规则时必须注意以下两点： 若若 是F 的反函数，F 也是 的反函数。F和 互为反函数。 7/17/202235北京理工大学 信息科学学院3. 对偶规则 对偶式的概念：对于任意的逻辑函数F，如果对其表达式做下述三种变换： 把原表达式中所有的“ ”运算符换成“+”运算符，同时把所有的“+”运算符换成“ ”运算符； 把原表达式中所有的逻辑常量

20、“0”换成逻辑常量“1”，而把所有的逻辑常量“1”换成逻辑常量“0”； 原表达式中所有的原变量和反变量均保持不变。 则由此所得到的新逻辑表达式就是原逻辑函数F表达式的对偶式（对偶函数），记作：F。 7/17/202236北京理工大学 信息科学学院例如：若：则：若：则：若：则：若：则：F是F 的对偶式，F 也是F的对偶式。F 和F互为对偶式。 在求一个函数表达式的对偶式时也不能打乱原表达式的运算顺序 。 在一般情况下 。 7/17/202237北京理工大学 信息科学学院表2.7所列出的基本定律中，右边带撇的标号所对应的公式两边的表达式，都是左边不带撇的标号所对应的公式两边表达式的对偶式。 对偶规

21、则：如果两个函数相等，则它们的对偶函数（对偶式）也相等。即：若 则 。 运用对偶规则，使需要记忆和证明的公式数量减少一半。对偶规则给简化和变换逻辑函数带来方便。 7/17/202238北京理工大学 信息科学学院2.3.3 逻辑代数的基本定理7/17/202239北京理工大学 信息科学学院证明表2.10所列出定理的最根本方法就是利用真值表。 在利用逻辑代数的方法证明表2.10中各定理时要用到逻辑代数的公理、基本定律、已获证明的其他定理和三个重要规则。 （1）证明“合并定理”公式1：证明： （分配律）（互补律）（自等律）也可以利用逻辑代数的方法证明表2.10所列出的各定理。 7/17/202240

22、北京理工大学 信息科学学院（自等律）（2）证明“吸收定理”的公式2：证明： （自等律、分配律）（0-1律）（互补律）（3）证明“吸收定理”的公式3：证明： （吸收定理公式2）（分配律）（自等律）7/17/202241北京理工大学 信息科学学院(交换律、结合律)（4）证明“添加项定理”的公式4：证明： (互补律、自等律)(分配律)(分配律)(0-1律、自等律) 7/17/202242北京理工大学 信息科学学院(互补律)（5）证明表2.10的公式6：证明： (摩根定理)(还原律)(分配律)(自等律) (摩根定理)(添加项定理)将“对偶规则”分别运用于表2.10中的公式1公式6就可以分别证明表2.1

23、0中的公式1公式6。 7/17/202243北京理工大学 信息科学学院作业2：2-9的（4）、（5）、（6）、（7），2-10，2-117/17/202244北京理工大学 信息科学学院2.3.4 复合逻辑运算和复合逻辑门 复合逻辑运算就是将三种基本逻辑运算“与”、“或”、“非”按某种形式进行简单地组合所构成的一种新的逻辑运算。 用于实现这些复合逻辑运算的逻辑门电路，就叫做复合逻辑门，简称复合门。1.“与非”、“或非”、“与或非”运算 “与非”运算就是“与”运算和“非”运算的组合。用逻辑函数表示就是： ABF“与非”门逻辑符号7/17/202245北京理工大学 信息科学学院“或非”运算就是“或”

24、运算和“非”运算的组合。用逻辑函数表示就是： “或非”门逻辑符号ABCDFABF“与或非”运算就是“与”运算、“或”运算和“非”运算的组合。用逻辑函数表示就是： “与或非”门逻辑符号7/17/202246北京理工大学 信息科学学院2. “异或”（“异”）、“同或”（“同”）运算“异或”逻辑运算（有时简称“异”运算）和“同或”逻辑运算（有时简称“同”运算）是两个非常重要的复合逻辑运算。两个变量 “异或”运算的定义如下：（1）“异或”运算“”是“异或”的运算符号。根据两变量“异或”定义式，列出其真值表。“异或”运算含义：若两变量A、B的取值相异，则F 的取值为“1”；若两变量A、B的取值相同，则F

25、的取值为“0”。 7/17/202247北京理工大学 信息科学学院根据“异或”运算定义，逻辑常数“1”和“0”的“异或”基本运算规则如下： 3个变量的“异或”运算定义如下：n个变量的“异或”运算可依此类推。7/17/202248北京理工大学 信息科学学院“异或”运算具有如下的基本运算规律：“异或”运算符合交换律，即：“异或”运算符合结合律，即：“异或”运算具有分配律，即：利用真值表，再根据“异或”的定义，可证明“异或”的这些基本运算规律。 7/17/202249北京理工大学 信息科学学院“异或”运算的两个重要特性特性1：多变量“异或”运算的结果取决于这些变量中取值为“1”的变量个数，而与取值为

26、“0”的变量个数无关。若取值为“1”的变量个数是奇数，则“异或”的结果为“1”；若取值为“1”的变量个数是偶数，则“异或”的结果为“0”。多个变量相“异或”的本质就在于确定取值为“1”的变量个数是奇数个还是偶数个。多个逻辑常量相“异或”，其结果取决于逻辑“1”的个数，而与逻辑“0”的个数无关。若逻辑“1”的个数为奇数，则“异或”的结果为“1”；若逻辑“1”的个数为偶数，则“异或”的结果为“0”。7/17/202250北京理工大学 信息科学学院由特性1可得到如下推论：若（1 i n）则或：n个变量相“异或”的补函数就等于这n个相“异或”的变量中任意一个变量取反。 7/17/202251北京理工大

27、学 信息科学学院特性2：“异或”运算具有因果互换的关系。即，等式两边的逻辑变量可以互相交换位置而仍然保持等式的成立。 例如：若成立，则或成立。“异或”运算的这种因果互换关系还可以推广到多个逻辑量（包括逻辑变量和逻辑常量）相“异或”的情形。 成立。例如：若成立，则或或或利用“异或”运算的特性1，可说明多个逻辑量“异或”运算的因果互换关系。7/17/202252北京理工大学 信息科学学院“异或”逻辑门及其逻辑符号“异或”运算可以由“异或”逻辑门来实现。“异或”门的逻辑符号如下图所示：ABFFABCD多个变量的“异或”，则可根据“异或”运算的结合律，利用多个“异或”门的级联来实现，如下图所示。 7/

28、17/202253北京理工大学 信息科学学院两个变量 “同或”运算的定义如下：（2）“同或”运算“”是“同或”的运算符号。根据两变量“同或”定义式，列出其真值表。“同或”运算含义：若两变量A、B的取值相同，则F 的取值为“1”；若两变量A、B的取值相异，则F的取值为“0”。 根据“同或”运算定义，逻辑常数“1”和“0”的“同或”基本运算规则如下： 00=1， 01=0， 10=0， 11=17/17/202254北京理工大学 信息科学学院3个变量的“同或”运算定义如下：F = ABCCn个变量的“同或”运算可依此类推。“同或”运算具有如下的基本运算规律：A0=；A1=A；AA=1；A=07/1

29、7/202255北京理工大学 信息科学学院“同或”运算符合交换律，即：AB=BA “同或”运算符合结合律，即：A(BC)=( AB)C“同或”运算具有分配律，即：A+(BC)=( A+B)( A+C) 利用真值表，再根据“同或”的定义，可证明“同或”的这些基本运算规律。 7/17/202256北京理工大学 信息科学学院7/17/202257北京理工大学 信息科学学院“同或”运算的两个重要特性特性1：多变量“同或”运算的结果取决于这些变量中取值为“0”的变量个数，而与取值为“1”的变量个数无关。若取值为“0”的变量个数是偶数，则“同或”的结果为“1”；若取值为“0”的变量个数是奇数，则“同或”的

30、结果为“0”。 多个变量相“同或”的本质就在于确定取值为“0”的变量个数是偶数个还是奇数个。 多个逻辑常量相“同或”，其结果取决于逻辑“0”的个数，而与逻辑“1”的个数无关。若逻辑“0”的个数为偶数，则“同或”的结果为“1”；若逻辑“0”的个数为奇数，则“同或”的结果为“0”。 7/17/202258北京理工大学 信息科学学院由“同或”运算的特性1可得到如下推论：或：n个变量相“同或”的补函数就等于这n个相“同或”的变量中任意一个变量取反。若F = A1A2AiAn， （1 i n）则= A1A2An；= A1A2An；A1A2AiAn7/17/202259北京理工大学 信息科学学院特性2：“

31、同或”运算具有因果互换的关系。即，等式两边的逻辑变量可以互相交换位置而仍然保持等式的成立。 例如：若 AB=C 成立，则 AC=B“同或”运算的这种因果互换关系也可以推广到多个逻辑量（包括逻辑变量和逻辑常量）相“同或”的情形。 例如：若 ABCD=1 成立，则 A1CD=B或 1BCD=A或 ABC1=D 成立。或 AB1D=C利用“同或”运算的特性1，可说明多个逻辑量“同或”运算的因果互换关系。或 BC=A 成立。7/17/202260北京理工大学 信息科学学院“异或”与“同或”之间的关系设有n个逻辑变量A1，A2，An，若F是将这n个逻辑变量相“异或”而构成的逻辑函数；G是将这n个逻辑变量

32、相“同或”而构成的逻辑函数，即： ； G= A1A2，An 则当n为偶数时： 或 。也就是说，此时逻辑函数F 和逻辑函数G 互为反函数（或互为补函数）；而当n为奇数时：F = G。也就是说，此时逻辑函数F 和逻辑函数G 相同。 两变量的“同或”函数是两变量的“异或”函数的反函数。AB = AB或7/17/202261北京理工大学 信息科学学院“同或”逻辑门及其逻辑符号“同或”运算可以由“同或”逻辑门来实现。“同或”门的逻辑符号如下图所示：在两个变量的“同或”运算中，只要有一个变量取反，则“同或”运算就变为“异或”运算，反之亦然。 AB =或= A “同或”运算亦称之为“异或”非运算。ABFAB

33、FABF7/17/202262北京理工大学 信息科学学院两个变量构成的“同或”和“异或”函数是一对特殊的逻辑函数。它们不仅互为反函数，而且还互为对偶函数。即： 不但 AB = AB或而且 = AB 或 (AB)= 运用对偶规则，可以从表2.13的左栏所列公式推导出右栏所列公式，反之亦然。 在求对偶式时，除了前面提到的三个变换以外，还要加上第四个变换，即：把所有的“ ”运算符换成“”运算符，同时把所有的“”运算符换成“ ”运算符。 在运用反演规则时，除原先的三个变换以外，也需加上第四个变换，即：把所有的“ ”、“”互换。 7/17/202263北京理工大学 信息科学学院3.逻辑运算符号的完备性

34、“与”、“或”、“非”是三种基本的逻辑运算，由它们可以组成任何逻辑函数。所以说“”、“+”、“”是一组逻辑功能完备的逻辑运算符。 “与非”运算、“或非”运算以及“与或非”运算各自都是功能完备的复合逻辑运算符。 “与”、“或”、“非”这三种基本逻辑运算均可用“或非” 运算来单独地完成，并可用相应的“或非”门来实现。 7/17/202264北京理工大学 信息科学学院“或”“非”ABA+B“与”A“0”BAB“0”A ABAB B或者A“0”7/17/202265北京理工大学 信息科学学院作业3：2-12的（1）、（3）、（4）、（5）、（8）、（9），2-14，2-17，2-19，2-21同理：“

35、与”、“或”、“非”这三种基本逻辑运算均可用“与非” 运算来单独地完成，并可用相应的“与非”门来实现。 同理：“与”、“或”、“非”这三种基本逻辑运算均可用“与或非” 运算来单独地完成，并可用相应的“与或非”门来实现。 7/17/202266北京理工大学 信息科学学院2.4 逻辑函数的两种标准形式一个逻辑函数可以归纳出五种主要的形式。它们是：“与或”表达式（先“与”后“或”的表达式）；“或与”表达式（先“或”后“与”的表达式）；“与非-与非”表达式；“或非-或非”表达式；“与或非”表达式。例如函数：7/17/202267北京理工大学 信息科学学院7/17/202268北京理工大学 信息科学学院

36、“与或”式和“或与”式是较为常用的表达式形式。同一种类型的逻辑表达式, 其形式也不是唯一的。例如F 的“与或”表达式： 在一个逻辑函数的众多的表达式中，有两种标准的表达式形式。它们实际上是特殊的“与或”式和“或与”式。 7/17/202269北京理工大学 信息科学学院2.4.1 最小项和最大项1.最小项（标准积或规范积）由A、B、C 三个逻辑变量所构成的乘积项（“与”项）中，有一类特殊的乘积项，它们是： 这8个乘积项（“与”项）有如下三个特点：每一项都是由三个逻辑变量相“与”而构成，即每项都有三个“因子”。 每个逻辑变量都是每一项的一个“因子”。7/17/202270北京理工大学 信息科学学院

37、在每一个乘积项中，每个逻辑变量或以原变量（A、B、C）的形式、或以反变量（ ）的形式出现一次。 这8个乘积项（“与”项）就称为三逻辑变量A、B、C的“最小项”。 n个变量的最小项是n个变量相“与”（乘积），其中每一个变量都以原变量的形式或反变量的形式出现、且仅出现一次。 对于n个变量来说，最小项的个数总共有2n个。当n=3（三个变量）时，最小项有23=8个。 7/17/202271北京理工大学 信息科学学院7/17/202272北京理工大学 信息科学学院最小项的性质性质1：对于任意的一个最小项，只有一组变量的取值使得它的值为“1”，而在变量取其它各组值时，这个最小项的值都是“0”。最小项不同，

38、使得它的值为“1”的那一组变量的取值也不同。使得某一个最小项的值为“1”的那组变量取值，就是该最小项中的原变量取“1”、反变量取“0”而组成的二进制数。 n代表最小项中变量的个数，常省略之 通常用符号 来表示最小项。 i代表最小项的编号，它是使最小项的值为“1”的变量取值的等效十进制数。 7/17/202273北京理工大学 信息科学学院性质2：任意两个不同的最小项的乘积（相“与”）恒为“0”。 性质3：全体最小项之和（相“或”）恒为“1”。 例如：7/17/202274北京理工大学 信息科学学院n变量最小项也具有同样的三个性质: 每一个最小项仅和一组变量取值相对应，只有在该组取值下这个最小项的

39、值才为“1”，而在其它的取值下它都为“0”。 n个变量的任意两个不同最小项的乘积（相“与”）恒为“0”，即： n个变量的全体最小项之和（相“或”）恒为“1”，即： 7/17/202275北京理工大学 信息科学学院2.最大项（标准和或规范和）由A、B、C 三个逻辑变量所构成的和项（“或”项）中，有一类特殊的和项，它们是： 每一项都是由三个逻辑变量相“或”而构成，即每项都有三个“加数”。 每个逻辑变量都是每一项的一个“加数”。 这8个和项（“或”项）有如下三个特点：7/17/202276北京理工大学 信息科学学院在每一个和项中，每个逻辑变量或以原变量（A、B、C）的形式，或以反变量（ ）的形式出现

40、一次。 这8个和项（“或”项）就称为三逻辑变量A、B、C的“最大项”。 n个变量的最大项是n个变量相“或”（和），其中每一个变量都以原变量的形式或反变量的形式出现、且仅出现一次。 对于n个变量来说，最大项的个数总共有2n个。当n=3（三个变量）时，最大项有23=8个。 7/17/202277北京理工大学 信息科学学院7/17/202278北京理工大学 信息科学学院最大项的性质性质1：对于任意的一个最大项，只有一组变量的取值使得它的值为“0”，而在变量取其它各组值时，这个最大项的值都是“1”。最大项不同，使得它的值为“0”的那一组变量的取值也不同。使得某一个最大项的值为“0”的那组变量取值，就是

41、该最大项中的原变量取“0”、反变量取“1”而组成的二进制数。n代表最大项中变量的个数，常省略之。 j代表最大项的编号，它是使最大项的值为“0”的变量取值的等效十进制数。 通常用符号 来表示最大项。 7/17/202279北京理工大学 信息科学学院性质2：任意两个不同的最大项的和（相“或”）恒为“1”。 性质3：全体最大项之积（相“与”）恒为“0”。 例如：7/17/202280北京理工大学 信息科学学院n变量最大项也具有同样的三个性质: 每一个最大项仅和一组变量取值相对应，只有在该组取值下这个最大项的值才为“0”，而在其它的取值下它都为“1”。 n个变量的任意两个不同最大项的和（相“或”）恒为

42、“1”，即： n个变量的全体最大项之积（相“与”）恒为“0”，即： 7/17/202281北京理工大学 信息科学学院3.最小项与最大项的关系 变量相同且编号相同的最小项和最大项之间，存在着互补的关系。即： 7/17/202282北京理工大学 信息科学学院7/17/202283北京理工大学 信息科学学院2.4.2 标准表达式和真值表1.两种标准表达式最小项之和式是由若干个最小项相“加”（相“或”）而构成，它也叫标准“与或”式。 例如：(1)最小项之和式7/17/202284北京理工大学 信息科学学院【例2.1】 把 展开为最小项之和式。 解：任何一个逻辑函数表达式都可以被展开成唯一的最小项之和式

43、；换句话说，用最小项之和这种形式可以表达任何一个逻辑函数。 7/17/202285北京理工大学 信息科学学院解：【例2.2】将 展开成最 小项之和式。 7/17/202286北京理工大学 信息科学学院最大项之积式是由若干个最大项相“乘”（相“与”）而构成，它也叫标准“或与”式。例如：(2)最大项之积式7/17/202287北京理工大学 信息科学学院解：【例2.3】把 展开为最大项之积式。 7/17/202288北京理工大学 信息科学学院解：【例2.4】将 展开成最大项之积式。 7/17/202289北京理工大学 信息科学学院任何一个逻辑函数表达式都可以被展开成唯一的最大项之积式；换句话说，用最

44、大项之积这种形式可以表达任何一个逻辑函数。 最小项之和式和最大项之积式是逻辑函数的两种标准表达式。 7/17/202290北京理工大学 信息科学学院2.真值表与标准表达式最小项之和式或者最大项之积式与真值表之间具有一一对应的关系，知道了一个就可以求出另一个。 例如：只有当ABC的取值为“011”、“101”和“110”时，函数F 的值才为“1”；而当ABC的取值为其它值时，F 的值为“0”。列出函数F 的真值表7/17/202291北京理工大学 信息科学学院例如：只有当ABC的取值为“000”、“011”、“101”和“110”时，函数G的值才为“0”；而当ABC的取值为其它值时，G的值为“1

45、”。列出函数G 的真值表。7/17/202292北京理工大学 信息科学学院函数F 的最小项之和式，实际上就是由真值表中F =1的各行相应的变量取值所对应的最小项相“或”而构成。 函数G 的最大项之积式，实际上就是由真值表中G =0的各行相应的变量取值所对应的最大项相“与”而构成。 在写各最小项时，应分别将各F =1的那一行所对应的变量取值中“1”代以原变量，而“0”代以反变量，再把这些变量（原变量和反变量）相“乘”（相“与”），从而构成一个最小项；同样，在写各最大项时，应分别将各F =0的那一行所对应的变量取值中“0”代以原变量，而“1”代以反变量，再把这些变量（原变量和反变量）相“加”（相“

46、或”），从而构成一个最大项。 7/17/202293北京理工大学 信息科学学院解：【例2.5】已知函数F 的真值表如表2.19所示。试写出F 的最小项之和式和最大项之积式。 函数F 的最小项之和式为： 函数F的最大项之积式为：7/17/202294北京理工大学 信息科学学院3.两种标准表达式之间的关系某个函数的最大项之积式中的最大项的编号正好是该函数的最小项之和式中的最小项编号中未包含的号码，反之亦然。 设：任意给定一个n变量的逻辑函数F，它的最小项之和式为： 因为全体最小项之和为“1”，即：7/17/202295北京理工大学 信息科学学院所以，逻辑函数F 的最小项之和 中所不包含的那些最小项

47、的 “和”就构成了逻辑函数F 的反函数 的最小项之和式，即：所以：7/17/202296北京理工大学 信息科学学院知道了逻辑函数F 的两种标准表达式之间“项号互补”的关系规律以后，就可以很容易地由一种标准表达式推出另一种标准表达式。 【例2.6】已知函数 ,试写出F 的最大项之积式。解：根据两种标准表达式所含项的编号在0 24-1的范围内互补的规律知： 7/17/202297北京理工大学 信息科学学院作业4：2-25，2-26，思考2-27，2-307/17/202298北京理工大学 信息科学学院2.5 逻辑函数的代数化简法2.5.1 化简逻辑函数的意义及化简方法一个逻辑函数可以归纳出五种主要

48、的形式。例如函数：7/17/202299北京理工大学 信息科学学院实现“与或”表达式AABC实现“或与”表达式ACBA实现“与非-与非”表达式AABC实现“或非-或非”表达式ACBA实现“与或非”表达式ABAC7/17/2022100北京理工大学 信息科学学院(a)AABC(b)ACBCAB(c)ACBCABCAABBC7/17/2022101北京理工大学 信息科学学院首先讨论如何将一个“与或”表达式化为最简“与或”表达式。这是因为：任何一个逻辑函数表达式都能展开成一个“与或”表达式；从一个最简“与或”表达式，可以很容易地得到“与非-与非”、“与或非”等形式的表达式；只要掌握了“与或”表达式的

49、化简方法，利用对偶式，就不难化简“或与”表达式。 最简“与或”表达式的标准：首先，表达式中乘积项（“与”项）的个数应该是最少的；其次，在满足上述条件的前提下，要求每一个乘积项中所含的变量个数最少。 7/17/2022102北京理工大学 信息科学学院乘积项的个数最少，就意味着电路中所用到的“与”门个数最少、所用“或”门的输入端子个数最少（“或”门的规模最小）； 每个乘积项中所含的变量个数最少，就意味着每个“与”门所含输入端子个数最少（“与”门的规模最小）。 在以后的化简中，均假定原变量（如A，B，C，）和反变量（如 ）都已经存在。 化简逻辑函数的常用方法:代数化简法。卡诺图化简法。 系统化简法：

50、也叫Q-M法，或称列表法。 7/17/2022103北京理工大学 信息科学学院2.5.2 代数化简法1.“与或”表达式的化简例如：(1)并项利用 “合并定理” 和“互补律” ，将两项合并为一项，同时消去一个“因子”（变量）。 7/17/2022104北京理工大学 信息科学学院7/17/2022105北京理工大学 信息科学学院(2)消项利用 “吸收定理” 和“添加项定理” ，消去多余的项。 例如：7/17/2022106北京理工大学 信息科学学院7/17/2022107北京理工大学 信息科学学院(3)消元例如：利用 “吸收定理” ,消去多余的“因子”。 7/17/2022108北京理工大学 信息

51、科学学院(4)配项例如：(1)利用 “互补律” ，把它代入逻辑函数式中作配项用，然后再消去更多的项。 7/17/2022109北京理工大学 信息科学学院例如：(2)利用 “重叠律” ，在逻辑函数式中重复写一项，有时可以得到更简单的结果。 7/17/2022110北京理工大学 信息科学学院例如：(3)利用“添加项定理” 和“重叠律” ，在逻辑函数式中先添项、再消项，有时也能得到更简单的结果。 7/17/2022111北京理工大学 信息科学学院注意到此处F1的化简形式与上述(1)中F1的化简形式不一样，但它们都是的最简“与或”式，这可以用真值表加以证明。这也说明“与或”表达式的最简形式，在某些情况

52、下是不唯一的。7/17/2022112北京理工大学 信息科学学院【例2.7】求 的最简“与或”式。 解：7/17/2022113北京理工大学 信息科学学院2.“或与”表达式的化简最简“或与”式的标准是“或项”（“和”项）最少、每个“或项”所含的变量个数最少。 利用对偶式化简“或与”式会更方便。现示意如下： F（“或与”式）（“与或”式）F（最简“或与”式）求对偶式（最简“与或”式）求对偶式化简7/17/2022114北京理工大学 信息科学学院【例2.9】求逻辑函数的最简“或与”式。解：（1）求 ： （2）化简 ： 7/17/2022115北京理工大学 信息科学学院3.其他类型逻辑表达式的化简“

53、与非与非”表达式的最简标准是：表达式的“非”号最少，（不计算单个变量上的“非”号，即假定原变量和反变量都已存在）；其次，每个“非”号下的变量个数最少（单个变量除外）。 用“求反加非”和反演律将已化简的最简“与或”式变换为最简“与非与非”表达式。 （3）求 ，即F： （1）最简“与非与非”表达式 7/17/2022116北京理工大学 信息科学学院解：（1）求函数F之最简“与或”式： 【例2.10】用最少的“与非”门实现 。 （2）把F之最简“与或”式“求反加非”变换为最简“与非与非”式： BDAD7/17/2022117北京理工大学 信息科学学院（2）最简“或非或非”表达式 “或非或非”表达式的

54、最简标准是：表达式的“非”号最少，（不计算单个变量上的“非”号，即假定原变量和反变量都已存在）；每个“非”号下的变量个数最少（单个变量除外）。 用“求反加非”和反演律将已化简的最简“或与”式变换为最简“或非或非”表达式。 解：【例2.11】用最少的“或非”门实现 。 （1）求函数F之反函数F ： 7/17/2022118北京理工大学 信息科学学院（2）求函数F之最简“与或”式：（3）求函数F之最简“或与”式：（4）求函数F之最简“或非或非”式：DBAD7/17/2022119北京理工大学 信息科学学院（3）最简“与或非”表达式 “与或非”表达式的最简标准和“与或”表达式的最简标准完全一样。即，

55、“与”项的个数最少；每个“与”项所含变量的个数最少。 对F 之最简“与或”式“求反”，即可得到F 之最简“与或非”式。 7/17/2022120北京理工大学 信息科学学院逻辑函数表达式的常用变换方法：F 之最简“与或”式 F 之最简“与非与非”式 求反加非F 之最简“与或”式 F 之最简“或与”式 反演F 之最简“或与”式 F 之最简“或非或非”式 求反加非F 之最简“或与”式 F 之最简“与或”式 反演F 之最简“与或”式 F 之最简“与或非”式 加一非7/17/2022121北京理工大学 信息科学学院作业5：2-31，2-33的（2）、（4），2-34的（1）、（3），2-35的（2），（

56、3）7/17/2022122北京理工大学 信息科学学院2.6 逻辑函数的卡诺图化简法2.6.1 卡诺图（K图）“逻辑相邻” 项：例如：AB+AB=A， ABCD+ABCD=ABC。 任意两个变量个数相同的最小项，如果组成它们的各个变量（原变量或反变量）中,只有一个变量互补（互反）而其余变量均相同（同为原变量或反变量）时，就称这两个最小项是逻辑相邻的最小项，简称“逻辑相邻项”或“相邻项”。 ABC+ABC=BC， 7/17/2022123北京理工大学 信息科学学院1.卡诺图的构成与特点把逻辑相邻的最小项所对应的小方块按几何位置相邻排列在一起，就得到了一个n变量最小项的方块图表示。这种最小项的方块

57、图表示方法是由美国人卡诺（Karnaugh）首先提出的，所以称之为卡诺图（Karnaugh Map），简称K图。 7/17/2022124北京理工大学 信息科学学院三变量卡诺图的构成7/17/2022125北京理工大学 信息科学学院二变量卡诺图 ；四变量卡诺图；五变量卡诺图 7/17/2022126北京理工大学 信息科学学院K图具有如下特点： n变量的K 图有2n个小方格，每个小方格代表一个最小项。 变量按行、列分成两组，每组变量的取值（编码）不是按自然二进制数码顺序排列而是按格雷码（循环码）的顺序排列。K 图上位于水平方向中心轴或垂直方向中心轴两侧对称的小格所代表的最小项在逻辑上是相邻的。所

58、以位于K 图上任何一行或一列两端上的小方格所代表的最小项是逻辑相邻的，即它们相互之间仅有一个变量互补。对于五变量的情形，要把“A=1”的卡诺图看成是重叠在“A=0”的卡诺图上。7/17/2022127北京理工大学 信息科学学院三变量卡诺图的几种画法（形式）7/17/2022128北京理工大学 信息科学学院变量次序对卡诺图小格标号的影响7/17/2022129北京理工大学 信息科学学院2.逻辑函数的卡诺图表示将所有最小项所对应的小方格里都填写“1”，而其余的小方格里都填写“0”。任何一个逻辑函数都等于其卡诺图上填“1”的那些小方格所对应的最小项之和。 （1）逻辑函数为最小项之和式7/17/202

59、2130北京理工大学 信息科学学院由函数的最大项之积式填写K图时，应将卡诺图上编号与表达式中最大项编号相同的小方格里都填写“0”，而其余的小方格里都填写“1”。任何一个逻辑函数都等于编号与其卡诺图上填“0”的那些小方格的编号相同的最大项之积。 （2）逻辑函数为最大项之积式7/17/2022131北京理工大学 信息科学学院最小项与最大项的名称来源相对于填“1”来讲，m7只占了编号为7的一个小格；而M7却占据了除7号小格以外的所有小方格。这就是最小项和最大项名称的由来。 卡诺图也证明了最小项和最大项的互补关系。 7/17/2022132北京理工大学 信息科学学院若卡诺图上的某个小方格所代表的最小项

60、，在真值表里所对应的函数F 取值为“1”，则该小方格里填“1”;否则就填“0”。（3）逻辑函数为真值表的形式7/17/2022133北京理工大学 信息科学学院将“与或”式中所有“与项”在卡诺图中所覆盖的区域内的所有小方格都填“1”（已经填过“1”的小格除外），其余都填“0”。（4）逻辑函数为一般“与或”式7/17/2022134北京理工大学 信息科学学院将“或与”式中所有“或项”在卡诺图中所覆盖的区域内的所有小方格都填“0”（已经填过“0”的小格除外），其余都填“1”。 （5）逻辑函数为一般“或与”式7/17/2022135北京理工大学 信息科学学院先将这些表达式变换为“与或”式或者“或与”式