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输入与门表达式：F2 = In1 · In2 （共1个2输入与门）

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

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

(2) 证明与非门的情况

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

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

∴ 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。

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 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 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.

A1B1 A2B2 Z1 00 01 11 10 1 1 1 A1B1 A2B2 Z2 00 01 11 10 1 1 1 00 01 11 10 00 01 11 10

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

74x14 A74x10 74x00

BY

ABY

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)

∴ 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是自对偶函数