µÚÈýÕ Âß¼­´úÊý»ù´¡ ×÷ÒµÌâ(²Î¿¼´ð°¸) ÏÂÔØ±¾ÎÄ

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ÊÇ×Ô¶Ôżº¯Êý