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

第三章 逻辑代数基础 （Basis of Logic Algebra）

1．知识要点

逻辑代数（Logic Algebra ）的公理、定理及其在逻辑代数化简时的作用；逻辑函数的表达形式及相互转换；最小项（Minterm ）和最大项（Maxterm ）的基本概念和性质；利用卡诺图（Karnaugh Maps）化简逻辑函数的方法。

重点：

1．逻辑代数的公理（Axioms ）、定理（Theorems ），正负逻辑（Positive Logic, Negative Logic）的概念与对偶关系（Duality Theorems）、反演关系（Complement 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 complement of WX +YZ is W ′+X ′Y ′+Z ′. Yet both functions are 1 for WXYZ = 1110. How can both a function and its complement be 1 for the same input combination? What’s wrong here?

The mistake is that the original operation priority has been changed. The complement 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

3.4 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

3.5 Write the canonical sum and product for each of the following logic functions:

∑(3) F =∑

(1) F =

X,Y

(1,2) (1,2,5,6)

(2) F =

∏

A,B

(0,1,2)

A,B,C,D

(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 n -input 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 sum-of-products expression for each of the following logic functions. Indicate the distinguished 1-cells in each map.

∑(3) F =∑

(1) F = (1)

F =

X,Y,Z

(1,3,5,6,7)

W,X,Y,Z

(1,4,5,6,11,12,13,14)

∏ (4) F =∏

(2) F =

A,B,C,D A,B,C

(4,5,6,13,15)

(1,2,6,7)

∑

X,Y,Z

(1,3,5,6,7)

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

F =

∏

A,B,C,D

(4,5,6,13,15)

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

F = (4)

F =

∑

W,X,Y,Z

(1,4,5,6,11,12,13,14)

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

∏

A,B,C

(1,2,6,7)

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 n -input AND gate can be replaced by n 1 2-input AND gates. Can the same statement be made for NAND gates? Justify your answer.

(1) 证明与门的情况 考察：

2输入与门表达式：F 2 = In1 · In2 （共1个2输入与门）

3输入与门表达式：F 3 = In1 · In2 · In3 = F2 · In3 （共2个2输入与门） 则n 输入与门表达式：

F n = In1 · In2 · In3 · ... Inn = Fn -1 · Inn （比F n -1增加1个2输入与门） ∴ n 输入与门可以用n -1个2输入与门来实现。

(2) 证明与非门的情况

考察三输入与非门的实现：

用一个3输入与非门实现：F 3 = (In1 · In2 · In3) ' = (In1 · In2 )' + In3' 用2个2输入与非门实现：G 3 = ((In1 · In2) ' · In3) ' = In1 · In2 + In3' ∵ F 3 ≠G 3

∴ n 输入与非门不可以用n -1个2输入与非门来实现。

3.10 Rewrite the following expression using as few inversions as possible (complemented 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 switching-algebra variables . Then AB = 0 and A +B = 1 implies that A = B ′. (2) Let X and Y be switching-algebra expressions . Then XY = 0 and X +Y = 1 implies that X = Y ′.

(1)

(2)

3.12 What is the logic function of a 2-input 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 logic-gate types that can realize any logic function is called a complete set of logic gates. For example, 2-input AND gates, 2-input OR gates, and inverters are a complete set, because any logic function can be expressed as a sum of products of variables and their complements, and AND and OR gates with any number of inputs can be made from 2-input gates. Do 2-input NAND gates form a complete 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 X3-1 is a possible symbol for a 4-input, 2-output 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 X3-1 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。

3.15 Write logic expressions for the Z 1 and Z 2 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

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系列的图来选择器件，逻辑电路图如下：

74x00

Y

Y

D

3.16 A self-dual logic function is a function F such that F =F Which of the following functions are self-dual? (1) F = X

(2) F =

X , Y , Z

(1,2,5,7)

(3) F = X ′YZ ′+XY ′Z ′+XY

(1) F = X = FD ∴ F 是自对偶函数

(2) ∵ F = ∑ X,Y,Z (1,2,5,7)

∴ F D = ∏ 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)

∴ F D = ∏ X,Y,Z (0,1,3,5) = ∑ X,Y,Z (2,4,6,7) = F

∴ F 是自对偶函数