第3章布尔代数与逻辑函数化简

第三章布尔代数与逻辑函数化简3.1基本公式和法则3.2逻辑函数的代数法化简3.3卡诺图化简第一页，编辑于星期六：二十点四十五分。一、基本公式

逻辑常量运算公式逻辑变量与常量的运算公式0

·

0

=

00

·

1

=

01

·

0

=

01

·

1

=

10

+

0

=

00

+

1

=

11

+

0

=

11

+

1

=

10–1律重叠律互补律还原律0+A=A1+A=11·A=A0·A=0A+A=AA·A=A

3.1基本公式和规则第二页，编辑于星期六：二十点四十五分。二、基本定律

(一)

与普通代数相似的定律

交换律

A+B=B+AA·B=B·A结合律(A+B)+C=A+(B+C)(A·B)·C=A·(B·C)分配律

A(B+C)=AB+AC

A+BC=(A+B)(A+C)普通代数没有！利用真值表逻辑等式的证明方法

利用基本公式和基本定律第三页，编辑于星期六：二十点四十五分。111111111100

例1

证明等式A+BC=(A+B)(A+C)解：真值表法公式法右式=(A+B)(A+C)用分配律展开=AA+AC+BA+BC=A+AC+AB+BC=A(1+C+B)+BC=A·1+BC=A+BC0000ABCA+BC(A+B)(A+C)000001010011100101110111=左式第四页，编辑于星期六：二十点四十五分。

(二)

逻辑代数的特殊定理

吸收律A+AB=A

A+AB=A(1+B)=A

第五页，编辑于星期六：二十点四十五分。0011111011011100A+BA·BA

B0011001000011100A·BA+BA

B

(二)

逻辑代数的特殊定理

吸收律

A+AB=A

推广公式：思考：(1)若已知

A+B=A+C，则

B=C吗？

(2)若已知

AB=AC，则B=C吗？

推广公式：摩根定律

(又称反演律)第六页，编辑于星期六：二十点四十五分。三、重要规则

(一)

代入规则

A

A

A

A均用代替A均用代替B均用C代替利用代入规则能扩展基本定律的应用。

将逻辑等式两边的某一变量均用同一个逻辑函数替代，等式仍然成立。第七页，编辑于星期六：二十点四十五分。例2

证明解这是两变量的求反公式，若将等式两边的B用B+C代入便得到这样就得到三变量的摩根定律。第八页，编辑于星期六：二十点四十五分。变换时注意：(1)不能改变原来的运算顺序。(2)反变量换成原变量只对单个变量有效，而长非

号保持不变。可见，求逻辑函数的反函数有两种方法：利用反演规则或摩根定律。原运算次序为

(二)

反演规则

对任一个逻辑函数式

Y，将“·”换成“+”，“+”换成“·”，“0”换成“1”，“1”换成“0”，原变量换成反变量，反变量换成原变量，则得到原逻辑函数的反函数。第九页，编辑于星期六：二十点四十五分。

(三)

对偶规则

对任一个逻辑函数式

Y，将“·”换成“+”，“+”换成“·”，“0”换成“1”，“1”换成“0”，则得到原逻辑函数式的对偶式

Y

。

对偶规则：两个函数式相等，则它们的对偶式也相等。

应用对偶规则可将基本公式和定律扩展。变换时注意：(1)

变量不改变

(2)不能改变原来的运算顺序A+AB=AA·(A+B)=A

第十页，编辑于星期六：二十点四十五分。四、基本公式应用1.证明等式例3用公式证明解第十一页，编辑于星期六：二十点四十五分。2.逻辑函数不同形式的转换

逻辑函数的形式是多种多样的，一个逻辑问题可以用多种形式的逻辑函数来表示，每一种函数对应一种逻辑电路。逻辑函数的表达形式通常可分为五种：与或表达式、与非-与非表达式、与或非表达式、或与表达式、或非-或非表达式。第十二页，编辑于星期六：二十点四十五分。例4

将函数与或表达式转换为其它形式。解(1)与非-与非式。将与或式两次取反，利用摩根定律可得(2)与或非式。首先求出反函数然后再取反一次即得与或非表达式

_____CABACAABF+=+=第十三页，编辑于星期六：二十点四十五分。(3)或与式。

将与或非式用摩根定律展开，即得或与表达式如下：(4)或非-或非式。将或与表达式两次取反，用摩根定律展开一次得或非-或非表达式第十四页，编辑于星期六：二十点四十五分。图3–1同一逻辑的五种逻辑图第十五页，编辑于星期六：二十点四十五分。一、逻辑函数及其表示方法

逻辑函数描述了某种逻辑关系。常采用真值表、逻辑函数式、卡诺图和逻辑图等表示。1.真值表列出输入变量的各种取值组合及其对应输出逻辑函数值的表格称真值表。列真值表方法(1)按

n位二进制数递增的方式列出输入变量的各种取值组合。(2)分别求出各种组合对应的输出逻辑值填入表格。3.2逻辑函数的代数法化简第十六页，编辑于星期六：二十点四十五分。00000111011101111111011110110011110101011001000111100110101000101100010010000000YDCBA输出变量输入变量4个输入变量有24

=16种取值组合。第十七页，编辑于星期六：二十点四十五分。2.逻辑函数式表示输出函数和输入变量逻辑关系的表达式。又称逻辑表达式，简称逻辑式。逻辑函数式一般根据真值表、卡诺图或逻辑图写出。

(1)找出函数值为1的项。(2)将这些项中输入变量取值为1的用原变量代替，取值为0的用反变量代替，则得到一系列与项。(3)将这些与项相加即得逻辑式。真值表逻辑式例如

ABC1000111100110101000100100100YCBA011010001111

逻辑式为第十八页，编辑于星期六：二十点四十五分。3.逻辑图运算次序为先非后与再或，因此用三级电路实现之。由逻辑符号及相应连线构成的电路图。

根据逻辑式画逻辑图的方法:将各级逻辑运算用相应逻辑门去实现。例如画的逻辑图反变量用非门实现与项用与门实现相加项用或门实现第十九页，编辑于星期六：二十点四十五分。例1图示为控制楼道照明的开关电路。两个单刀双掷开关

A和

B分别安装在楼上和楼下。上楼之前，在楼下开灯，上楼后关灯；反之，下楼之前，在楼上开灯，下楼后关灯。试画出控制功能与之相同的逻辑电路。(1)

分析逻辑问题，建立逻辑函数的真值表11YAB0000110110(2)根据真值表写出逻辑式解：方法：找出输入变量和输出函数，对它们的取值作出逻辑规定，然后根据逻辑关系列出真值表。设开关A、B合向左侧时为0状态，合向右侧时为1状态；Y表示灯，灯亮时为1状态，灯灭时为0状态。则可列出真值表为第二十页，编辑于星期六：二十点四十五分。(3)画逻辑图

与或表达式(可用2个非门、

2个与门和1个或门实现)异或非表达式(可用1个异或门和1个非门实现)设计逻辑电路的基本原则是使电路最简。第二十一页，编辑于星期六：二十点四十五分。二、逻辑函数式化简的意义与标准

化简意义使逻辑式最简，以便设计出最简的逻辑电路，从而节省元器件、优化生产工艺、降低成本和提高系统可靠性。不同形式逻辑式有不同的最简式，一般先求取最简与-或式，然后通过变换得到所需最简式。第二十二页，编辑于星期六：二十点四十五分。最简与-或式标准(1)乘积项(即与项)的个数最少(2)每个乘积项中的变量数最少用与门个数最少与门的输入端数最少

最简与非式标准(1)非号个数最少(2)每个非号中的变量数最少用与非门个数最少与非门的输入端数最少

第二十三页，编辑于星期六：二十点四十五分。如直接由该函数式得到电路图，则如图3-3所示。图3-3F原函数的逻辑图第二十四页，编辑于星期六：二十点四十五分。

但如果将函数化简后其函数式为F=AC+B

只要两个门就够了，如图3-4所示。图3–4函数化简后的逻辑图第二十五页，编辑于星期六：二十点四十五分。三、代数化简法

运用逻辑代数的基本定律和公式对逻辑式进行化简。并项法

运用，将两项合并为一项，并消去一个变量。

任何两个相同变量的逻辑项，只有一个变量取值不同(一项以原变量形式出现，另一项以反变量形式出现)，我们称为逻辑相邻项(简称相邻项)。如果函数存在相邻项，可利用吸收律，将它们合并为一项，同时消去一个变量。第二十六页，编辑于星期六：二十点四十五分。

解令

解利用等幂律，一项可以重复用几次。第二十七页，编辑于星期六：二十点四十五分。其中与其余四项均是相邻关系，可以重复使用。解所以第二十八页，编辑于星期六：二十点四十五分。吸收法

运用A+AB

=A和，消去多余的与项。第二十九页，编辑于星期六：二十点四十五分。消去法

运用吸收律

，消去多余因子。第三十页，编辑于星期六：二十点四十五分。配项法通过乘或加入零项进行配项，然后再化简。例1

化简例2

化简第三十一页，编辑于星期六：二十点四十五分。综合灵活运用上述方法

[例]化简逻辑式解：

应用[例]化简逻辑式解：

应用应用AB第三十二页，编辑于星期六：二十点四十五分。[例]化简逻辑式解：

应用用摩根定律第三十三页，编辑于星期六：二十点四十五分。作业：书P691(3)，2(1)(4)，3(2)(3)，4(1)(4)，5(2)(6)(8)第三十四页，编辑于星期六：二十点四十五分。代数化简法

优点：对变量个数没有限制。缺点：需技巧，不易判断是否最简式。

卡诺图化简法优点：简单、直观，有一定的步骤和方法易判断结果是否最简。

缺点：适合变量个数较少的情况。一般用于四变量以下函数的化简。一、代数化简法与卡诺图化简法的特点3.3卡诺图化简第三十五页，编辑于星期六：二十点四十五分。二、卡诺图化简的基本原理例解第三十六页，编辑于星期六：二十点四十五分。n个变量有2n种组合，可对应写出2n个乘积项，这些乘积项均具有下列特点：包含全部变量，且每个变量在该乘积项中(以原变量或反变量)只出现一次。这样的乘积项称为这n个变量的最小项，也称为n变量逻辑函数的最小项。1.最小项的定义三、逻辑函数的标准式——最小项

第三十七页，编辑于星期六：二十点四十五分。

一个变量A有2个最小项：二个变量AB有4个最小项：三个变量ABC有8个最小项：第三十八页，编辑于星期六：二十点四十五分。

任何形式的逻辑式都可以转化为标准与-或式，而且逻辑函数的标准与

-

或式是唯一的。

2.逻辑函数的最小项表达式

每一个与项都是最小项的与

-

或逻辑式称为标准与

-

或式，又称最小项表达式(不一定由全部最小项组成)。第三十九页，编辑于星期六：二十点四十五分。例如是最小项表达式。而不是最小项表达式，而是一般式。

最小项表达式具有唯一性。任何逻辑函数的最小项表达式只有一个。第四十页，编辑于星期六：二十点四十五分。3.由一般式获得最小项表达式(1)代数法。对逻辑函数的一般式采用添项法，例如第四十一页，编辑于星期六：二十点四十五分。(2)真值表法。将原逻辑函数A、B、C取不同值组合起来，得其真值表，而该逻辑函数是将F=1那些输入变量相或而成的，如表3-4所示。

表3–4某逻辑函数的真值表第四十二页，编辑于星期六：二十点四十五分。如何编号？如何根据输入变量组合写出相应最小项？例如

3变量逻辑函数的最小项有23=8个将输入变量取值为1的代以原变量，取值为0的代以反变量，则得相应最小项。

简记符号例如

1015m5m44100ABC111110101100011010001000最小项ABCm7m6m5m4m3m2m1m0输入组合对应的十进制数765432104.最小项的编号第四十三页，编辑于星期六：二十点四十五分。5.最小项的基本性质

(1)

对任意一最小项，只有一组变量取值使它的值为1，

而其余各种变量取值均使其值为0。三变量最小项表110000000111101000000110100100000101100010000100100001000011100000100010100000010001100000001000ABCm7m6m5m4m3m2m1m0ABC(2)

不同的最小项，使其值为1的那组变量取值也不同。(3)

对于变量的任一组取值，任意两个最小项的乘积为0。(4)

对于变量的任一组取值，全体最小项的和为1。第四十四页，编辑于星期六：二十点四十五分。如何将逻辑式转化为标准与-或式呢

？[例]

将逻辑式化为标准与或式。(3)利用A+A=A，合并掉相同的最小项。0000m00001m11100m121101m131111m15=m0+m1+m12+m13+m15=∑m(0,1,12,13,15)解：(1)利用摩根定律和分配律把逻辑函数式展开为与或式。AB+(2)利用配项法化为标准与或式。第四十五页，编辑于星期六：二十点四十五分。(一)

卡诺图的构成

四、逻辑函数的卡诺图表示法1.相邻最小项

两个最小项中只有一个变量互为反变量，其余变量均相同，称为相邻最小项，简称相邻项。相邻最小项重要特点：两个相邻最小项相加可合并为一项，

消去互反变量，化简为相同变量相与。例如ABC+ABC=AB第四十六页，编辑于星期六：二十点四十五分。

将n变量的2n个最小项用2n个小方格表示，并且使相邻最小项在几何位置上也相邻且循环相邻，这样排列得到的方格图称为n个变量最小项卡诺图，简称变量卡诺图。2.卡诺图及其构成方法第四十七页，编辑于星期六：二十点四十五分。变量取0的代以反变量取1的代以原变量AB二变量卡诺图0101000110110001AB0101m0m1m2m3ABAAB

BABABABAB四变量卡诺图01

3

245

7

61213

15

14891110三变量卡诺图ABC01000111

10

m6m7m4m2m3m0m5001m1ABCD00011110000111

10以循环码排列以保证相邻性第四十八页，编辑于星期六：二十点四十五分。变量取0的代以反变量取1的代以原变量ABCD00011110000111

1001

3

245

7

61213

15

14891110ABCD相邻项在几何位置上也相邻卡诺图特点：循环相邻性同一列最上与最下方格相邻同一行最左与最右方格相邻第四十九页，编辑于星期六：二十点四十五分。如何写出卡诺图方格对应的最小项？

已知最小项如何找相应小方格？

例如

原变量取1，反变量取0。1001？ABCD0001111000011110

第五十页，编辑于星期六：二十点四十五分。

(二)

用卡诺图表示逻辑函数

(1)求逻辑函数真值表或者标准与-或式或者与-或式。

(2)

画出变量卡诺图。

(3)

根据真值表或标准与

-

或式或与

-

或式填图。基本步骤用卡诺图表示逻辑函数举例

已知标准与或式画函数卡诺图

[例]

试画出函数Y=∑m(0,1,12,13,15)的卡诺图解：(1)画出四变量卡诺图(2)填图逻辑式中的最小项m0、m1、m12、m13、m15对应的方格填1，其余不填。ABCD0001111000011110

0

1324576

12

13

151489

11

10

11

111

第五十一页，编辑于星期六：二十点四十五分。已知真值表画函数卡诺图[例]

已知逻辑函数Y的真值表如下，试画出Y的卡诺图。解：(1)画3变量卡诺图。ABCY00010010010101101001101011011110ABC0100011110

6

7

5

4

2

31

0m0m2m4m6

1

1

1

1(2)找出真值表中Y=1对应的最小项，在卡诺图相应方格中填1，其余不填。第五十二页，编辑于星期六：二十点四十五分。已知一般表达式画函数卡诺图解：(1)将逻辑式转化为与或式(2)作变量卡诺图找出各与项所对应的最小项方格填1，其余不填。[例]已知，试画出Y的卡诺图。AB+ABCD0001111000011110(3)根据与或式填图

11111111

1

1AB对应最小项为同时满足A=1，

B=1的方格。BCD对应最小项为同时满足B=1，C=0，D=1的方格AD对应最小项为同时满足A=0，D=1的方格。第五十三页，编辑于星期六：二十点四十五分。五、用卡诺图化简逻辑函数

化简规律2

个相邻最小项有

1个变量相异，相加可以消去这

1个变量，化简结果为相同变量的与；

4个相邻最小项有2个变量相异，相加可以消去这2个变量，化简结果为相同变量的与；

8个相邻最小项有3个变量相异，相加可以消去这3个变量，化简结果为相同变量的与；……

2n个相邻最小项有

n个变量相异，相加可以消去这

n个变量，化简结果为相同变量的与。消异存同

第五十四页，编辑于星期六：二十点四十五分。ABCD000111100001111011例如2个相邻项合并消去

1个变量，化简结果为相同变量相与。ABCD+ABCD=ABDABCD000111100001111011例如2个相邻项合并消去

1个变量，化简结果为相同变量相与。ABCD+ABCD=ABDABCD0001111000011110例如1111ABCD+ABCD+ABCD+ABCD=ACD+ACD=AD4个相邻项合并消去2个变量，化简结果为相同变量相与。8个相邻项合并消去3个变量A11111

111第五十五页，编辑于星期六：二十点四十五分。画包围圈规则包围圈必须包含2n个相邻1方格，且必须成方形。先圈小再圈大，圈越大越是好；1方格可重复圈，但须每圈有新1；每个“1”格须圈到，孤立项也不能掉。同一列最上边和最下边循环相邻，可画圈；同一行最左边和最右边循环相邻，可画圈；四个角上的1方格也循环相邻，可画圈。注意ABCD+ABCD+ABCD+ABCD卡诺

图化

简法

步骤画函数卡诺图

将各圈分别化简对填1的相邻最小项方格画包围圈将各圈化简结果逻辑加

第五十六页，编辑于星期六：二十点四十五分。m15

m9

m7

m6

m5

m4

m2

m0解：(1)画变量卡诺图[例]用卡诺图化简逻辑函数Y(A,B,C,D)=∑m(0,2,4,5,6,7,9,15)ABCD0001111000011110(2)填卡诺图11111111(3)画包围圈abcd(4)将各图分别化简圈2个可消去

1个变量，化简为3个相同变量相与。Yb=BCD圈4个可消去

2个变量，化简为2个相同变量相与。孤立项Ya=ABCDYc=

AB循环相邻

Yd=

AD(5)将各图化简结果逻辑加，得最简与或式第五十七页，编辑于星期六：二十点四十五分。解：(1)画变量卡诺图[例]用卡诺图化简逻辑函数Y(A,B,C,D)=∑m(0,2,5,7,8,10,12,14,15)ABCD0001111000011110(2)填卡诺图11111111(4)求最简与或式Y=1消1个剩3个(3)画圈消2个剩2个4个角上的最小项循环相邻第五十八页，编辑于星期六：二十点四十五分。找

AB

=11,C

=

1

的公共区域找

A

=

1,

CD

=

01

的公共区域找

B

=

1,

D

=

1

的公共区域解：(1)画变量卡诺图ABCD0001111000011110(2)填图11(4)化简(3)画圈[例]用卡诺图化简逻辑函数0011m30100m411111111要画吗？Y=第五十九页，编辑于星期六：二十点四十五分。[例]化简第六十页，编辑于星期六：二十点四十五分。[例]已知函数真值表如下，试用卡诺图法求其最简与或式。ABCY00010011010001111001101011011111注意：该卡诺图还有其他画圈法可见，最简结果未必唯一。解：(1)画函数卡诺图ABC01000111

101

1

1

111(3)化简(2)画圈Y=1

1

1

111ABC0100011110第六十一页，编辑于星期六：二十点四十五分。六、其它逻辑形式的化简1.与非逻辑形式

所谓与非式，就是全由与非门实现该逻辑，前面讲逻辑函数相互变换时已讲过，将与或式两次求反即得与非式。第六十二页，编辑于星期六：二十点四十五分。第六十三页，编辑于星期六：二十点四十五分。

2.或与逻辑形式

首先从卡诺图上求其反函数，其方法是圈“０”方格，然后再用摩根定律取反即得或与式。

例求的反函数和或与式。第六十四页，编辑于星期六：二十点四十五分。

总结如下：在卡诺图上圈“0”方格，其化简结果：变量为0→原变量；变量为1→反变量，然后变量再相“或”起来，就得每一或项，最后再将每一或项“