第三章-逻辑代数基础-作业题(参考答案).doc

第三章 逻辑代数基础
(Basis of Logic Algebra)
1.知识要点
逻辑代数(Logic Algebra)得公理、定理及其在逻辑代数化简时得作用;逻辑函数得表达形式及相互转换;最小项(Minterm)与最大项(Maxterm)得基本概念与性质;利用卡诺图(Karnaugh Maps)化简逻辑函数得方法。
重点:
1.逻辑代数得公理(Axioms)、定理(Theorems),正负逻辑(Positive Logic, Negative Logic)得概念与对偶关系(Duality Theorems)、反演关系(plement Theorems)、香农展开定理,及其在逻辑代数化简时得作用;
2.逻辑函数得表达形式:积之与与与之积标准型、真值表(Truth Table)、卡诺图(Karnaugh Maps)、最小逻辑表达式之间得关系及相互转换;
3.最小项(Minterm)与最大项(Maxterm)得基本概念与性质;
4.利用卡诺图化简逻辑函数得方法。
难点:
利用卡诺图对逻辑函数进行化简与运算得方法
(1)正逻辑(Positive Logic)、负逻辑(Negative Logic)得概念以及两者之间得关系。
数字电路中用电压得高低表示逻辑值1与0,将代数中低电压(一般为参考地0V)附近得信号称为低电平,将代数中高电压(一般为电源电压)附近得信号称为高电平。以高电平表示1,低电平表示0,实现得逻辑关系称为正逻辑(Positive Logic),相反,以高电平表示0,低电平表示1,实现得逻辑关系称为负逻辑(Negative Logic),两者之间得逻辑关系为对偶关系。
(2)逻辑函数得标准表达式
积之与标准形式(又称为标准与、最小项与式):每个与项都就是最小项得与或表达式。
与之积标准形式(又称为标准积、最大项积式):每个或项都就是最大项得或与表达式。
逻辑函数得表达形式具有多样性,但标准形式就是唯一得,它们与真值表之间有严格得对应关系。
由真值表得到标准与得具体方法就是:找出真值表中函数值为1得变量取值组合,每一组变量组合对应一个最小项(变量值为1得对应原变量,变量值为0得对应反变量),将这些最小项相或,即得到标准与表达式。
由真值表得到标准积得具体方法就是:找出真值表中函数值为0得变量取值组合,每一组变量组合对应一个最大项(变量值为1得对应反变量,变量值为0得对应原变量),将这些最大项相与,即得到标准积表达式。
每个真值表所对应得标准与与标准积表达方式就是唯一得。
(3)利用卡诺图化简逻辑函数
卡诺图就是真值表得图形表示,利用卡诺图对逻辑函数进行化简得原理就是反复使用公式AB+AB′=A,对应到卡诺图上,即为相邻得小方格可以合并。通常:
2个相邻得方格可以合并,并可消去1个变量;4个相邻得方格可以合并,并可消去2个变量;8个相邻得方格可以合并,并可消去3个变量……
在相邻方格合并得过程中,通常采用画圈得方法进行标记。
利用卡诺图化简,圈1得结果就是得到最简与得表达式,圈0得结果就是得到最简积得表达式。
利用卡诺图化简得步骤(以最简与为例):
① 填卡诺图;
② 找出全部质主蕴含项;
③ 找到奇异1单元,圈出对应得质主蕴含项;
④ 若未圈完所有1方格,则从剩余得主蕴含项中找出最简得;
⑤ 写出各圈所对应得与项表达式(取值发生变化得变量不写,取值无变化得变量保留,取值为0写反变量,取值为1写原变量)。
⑥ 将所得到得与项相或,即为化简结果。
化简得原则就是:圈1不圈0,1至少圈1次,圈数越少越好,圈越大越好。
(4)利用卡诺图对逻辑函数进行运算
利用卡诺图可以完成逻辑函数得逻辑加(或)、逻辑乘(与)、反演(非)、异或等运算。进行这些运算时,要求参加运算得两个卡诺图具有相同得维数(即变量数相同)。
① 卡诺图相加
两函数做逻辑加(或)运算时,只需将卡诺图中编号相同得各相应方格中得0、1按逻辑加得规则相或,而得到得卡诺图应包含每个相加卡诺图所出现得全部1项。
② 卡诺图相乘
两函数做逻辑乘(与)运算时,只需将卡诺图中编号相同得各相应方格中得0、1按逻辑乘得规则相与,所得到得卡诺图中得1方格,就是参加相乘得卡诺图中都包含得1格。
③ 反演
卡诺图得反演(非),就是将函数F得卡诺图中各个为1得方格变换为0,将各个为0得方格变换为1。
④ 卡诺图异或
两函数做异或运算,只需将卡诺图中编号相同得各相应方格中得0、1按异或运算得规则进行运算,所得到得卡诺图中得1方格,就是进行异或运算得卡诺图中取值不同得方格。
2.Exercises
3、1 Prove theorems (X+Y)(X+Z) = X+Y·Z using perfect induction、
If X = 0, Left = (0+Y)(0+Z) = Y·Z Right = 0+ Y·Z = Y·Z ∴ Left = Right
If X = 1, Left = (1+Y)(1+Z) = 1·1 = 1 Right = 1+ Y·Z = 1 ∴ Left = Right
3、2 According to DeMorgan’s theorem, the plement of WX+YZ is W′+X′Y′+Z′、 Yet both functions are 1 for WXYZ = 1110、 How can both a function and its plement be 1 for the same input bination? What’s wrong here?
The mistake is that the original operation priority has been changed、
The plement of WX+YZ should be (W′+X′)(Y′+Z′)
3、3 Use the theorems of switching algebra to simplify each of the following logic functions:
(1) F = WXYZ(WXYZ′+WX′YZ+W′XYZ+WXY′Z)
(2) F = AB+ABC′D+ABDE′+ A′BC′E+A′B′C′E
(3) F = MRP+ QO′R′+MN+ONM+QPMO′
(1) F = W·X·Y·Z·(W·X·Y·Z'+W·X'·Y·Z+W'·X·Y·Z+W·X·Y'·Z)
= W·X·Y·Z·W·X·Y·Z'+ W·X·Y·Z·W·X'·Y·Z+ W·X·Y·Z·W'·X·Y·Z+ W·X·Y·Z·W·X·Y'·Z
= 0
(2) F = A·B·(1+C'·D+D·E') + A'·C'·E·(B+B') = A·B + A'·C'·E
(3) F = M·R·P + Q·O'·R' + M·N + Q·P·M·O' = M·P·R + Q·O'·R' + M·P·Q·O' + M·N = M·P·R + Q·O'·R' + M·N
34 Write the truth table for each of the following logic functions:
(1) F = AB′+B′C+CD′+CA′
(2) F = (A′+B+C′)(A′+B′+D)(B+C+D′)(A+B+C+D)
(3) F = AB+AB′C′+A′BC
(4) F = XY′+YZ+Z′X
(1)
A
B
C
D
F
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
1
0
1
0
1
1
0
1
1
1
1
1
0
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
0
(2)
A
B
C
D
F
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
(3)
A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
1
(4)
X
Y
Z
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1

3、5 Write the canonical sum and product for each of the following logic functions:
(1) F = (2) F =
(3) F = (4) F = A′B+B′C+A
(1) F = ∑X,Y (1,2) = X'·Y+X·Y' (标准与)
= ∏X,Y (0,3) = (X+Y)·(X'+Y') (标准积)
(2) F = ∏A,B (0,1,2) = (A+B)·(A+B')·(A'+B) (标准积)
= ∑A,B (3) = A·B (标准与)
(3) F = ∑A,B,C,D (1,2,5,6) = A'·B'·C'·D + A'·B'·C·D' + A'·B·C'·D + A'·B·C·D' (标准与)
= ∏A,B,C,D (0,3,4,7,8,9,10,11,12,13,14,15)
= (A+B+C+D)·(A+B+C'+D')·(A+B'+C+D)·(A+B'+C'+D')·(A'+B+C+D)·(A'+B+C+D')·(A'+B+C'+D) (A'+B+C'+D')·(A'+B'+C+D)·(A'+B'+C+D')·(A'+B'+C'+D)·(A'+B'+C'+D') (标准积)
(4) F = A'·B+B'·C+A = A'·B·(C+C')+(A+A')·B'·C+A·(B+B')·(C+C')
= A'·B·C+A'·B·C'+A·B'·C+A'·B'·C+A·B·C+A·B·C'+A·B'·C+A·B'·C'
= A'·B·C+A'·B·C'+A·B'·C+A'·B'C+A·B·C+A·B·C'+A·B'C' (标准与)
F = A'·B+B'·C+A = A+B+C (标准积)
3、6 If the canonical sum for an ninput logic function is also a minimal sum, how many literals are in each product term of the sum? Might there be any other minimal sums in this case?
若某函数得标准与也就是最小与,说明其卡诺图中得1都不相邻,无法合并。
此时,标准与 = 最小与 = 完全与,其与式中得乘积项必有n个变量,无法化简。
3、7 Using Karnaugh maps, find a minimal sumofproducts expression for each of the following logic functions、 Indicate the distinguished 1cells in each map、
(1) F = (2) F =
(3) F = (4) F =
(1)
F =

00
01
11
10
0

1

1
1
1
1
1

Z
XY

F = X·Y+Z (图中灰色块为奇异1单元)
(2)
F =

00
01
11
10
00

0

01

0
0

11

0

10

0

CD
AB

F = B+ A·D'+A'·C·D (图中灰色块为奇异1单元)
(3)
F =

00
01
11
10
00

1
1

01
1
1
1

11

1
10

1
1

YZ
WX

F = XY’+XZ’+W’Y’Z+WX’YZ (图中灰色块为奇异1单元)
(4)
F =

00
01
11
10
0

0
0

1
0

0

C
AB

F = AB’+B’C’+A’BC (图中灰色块为奇异1单元)
3、8 Prove that (X+Y) (X′+Z) = XZ + X′Y without using perfect induction、

3、9 Show that an ninput AND gate can be replaced by n-1 2input AND gates、 Can the same statement be made for NAND gates? Justify your answer、
(1) 证明与门得情况
考察:
2输入与门表达式:F2 = In1 · In2 (共1个2输入与门)
3输入与门表达式:F3 = In1 · In2 · In3 = F2 · In3 (共2个2输入与门)
则n输入与门表达式:
Fn = In1 · In2 · In3 · 、、、 Inn = Fn1 · Inn (比Fn1增加1个2输入与门)
∴ n输入与门可以用n1个2输入与门来实现。
(2) 证明与非门得情况
考察三输入与非门得实现:
用一个3输入与非门实现:F3 = (In1 · In2 · In3)' = (In1 · In2 )' + In3'
用2个2输入与非门实现:G3 = ((In1 · In2) ' · In3) ' = In1 · In2 + In3'
∵ F3 ≠G3
∴ n输入与非门不可以用n1个2输入与非门来实现。
3、10 Rewrite the following expression using as few inversions as possible (plemented parentheses are allowed):
B′C + ACD′ + A′C + EB′ + E(A+C)(A′+D′)

3、11 Prove or disprove the following propositions:
(1) Let A and B be switchingalgebra variables、 Then AB = 0 and A+B= 1 implies that A = B′、
(2) Let X and Y be switchingalgebra expressions、 Then XY = 0 and X+Y = 1 implies that X = Y′、
(1)

(2)

3、12 What is the logic function of a 2input XNOR gate whose inputs are tied together? How might the output behavior differ from a real XNOR gate? Give the answer based on the point of view of switching algebra、
F = A⊙B = A·B + A'·B' 可见,当输入A与B相同时,输出F为1,否则为0。
若A = B,则 F = A⊙A = A·A + A'·A' = A + A' = 1 (T3', T5) 可见,无论输入A为0或1,F恒等于1。
3、13 Any set of logicgate types that can realize any logic function is called a plete set of logic gates、 For example, 2input AND gates, 2input OR gates, and inverters are a plete set, because any logic function can be expressed as a sum of products of variables and their plements, and AND and OR gates with any number of inputs can be made from 2input gates、 Do 2input NAND gates form a plete set of logic gates? Prove your answer、
2输入与非门可以构成逻辑门得完备集。
如下图所示,1个与非门可构成1个非门,1个与非门加1个非门可构成1个与门,2个非门加1个与非门可构成1个或门,从而可构成“与、或、非”完备集。

3、14 Some people think that there are four basic logic functions, AND, OR, NOT, and BUT、 Figure X31 is a possible symbol for a 4input, 2output BUT gate、 Invent a useful, nontrivial function for the BUT gate to perform、 The function should have something to do with the name (BUT)、 Keep in mind that, due to the symmetry of the symbol, the function should be symmetric with respect to the A and B inputs of each section and with respect to sections 1 and 2、 Describe your BUT’s function and write its truth table、

Figure X31 logic circuit of exercise 3、14
【注】图中得符号不就是两个“与门”符号,而就是BUT门得首字母“B”。
关于BUT得描述可以有多种,须满足输入A与B对称(可互换),部分1与部分2对称(可互换)。比如:当A1与B1同时为1,但A2与B2不同时为1时,Z1为1,其她情况Z1为0。当A2与B2同时为1,但A1与B1不同时为1时,Z2为1,其她情况Z1为0。
A1
B1
A2
B2
Z1
Z2
0
0
0
0
0
0
0
0

0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
1
1
0
1
1
1
0
0
1
0
1
1
0
1
1
0
1
1
1
0
1
0
1
1
1
1
0
0
3、15 Write logic expressions for the Z1 and Z2 outputs of the BUT gate you designed in the preceding exercise, and draw a corresponding logic diagram using AND gates, OR gates, and inverters、

Z1 = A1·B1·A2' + A1·B1·B2'
= ( (A1·B1·A2')' · (A1·B1·B2')' )' (与非与非结构)
Z2 = A2·B2·A1' + A2·B2·B1'
= ( (A2·B2·A1')' · (A2·B2·B1')' )' (与非与非结构)
参照教材中74系列得图来选择器件,逻辑电路图如下:
A1
B1
A2
B2
74x14
74x10
74x00
Y1
Y2

3、16 A selfdual logic function is a function F such that F =FD Which of the following functions are selfdual?
(1) F = X (2) F = (3) F = X′YZ′+XY′Z′+XY
(1) F = X = FD ∴ F就是自对偶函数
(2) ∵ F = ∑X,Y,Z (1,2,5,7)
∴ FD = ∏X,Y,Z (0,2,5,6) = ∑X,Y,Z (1,3,4,7) ≠ F
∴ F不就是自对偶函数
(3) ∵ F = X’YZ’ + XY’Z’ + XY = X’YZ’ + XY’Z’ + XY(Z+Z’) = ∑X,Y,Z (2,4,6,7)
∴ FD = ∏X,Y,Z (0,1,3,5) = ∑X,Y,Z (2,4,6,7) = F
∴ F就是自对偶函数