北科大 离散数学习题解答汇总.docx

《北科大 离散数学习题解答汇总.docx》由会员分享，可在线阅读，更多相关《北科大 离散数学习题解答汇总.docx（108页珍藏版）》请在三一办公上搜索。

1、北科大 离散数学习题解答汇总第一章习题 1 填空题 a+b=a，当且仅当b=0。 假。 2。 P(QR) P为真且Q为假。 4。 永假式；永真式。 T.F，T.F N222F；M0M1M2M3或(M00M01M10M11)。 (10) P。 2选择题 C C C C C C D C A C 3.判断下列语句是否是命题，若是试将其符号化。 是。P 是。P 是。P 是。P 是。P 不是。 是。令P：太阳出来，Q：天下雨，R：阴天，S：温度下降 则原命题可表示为：PQ(RS) 不是。 不是。 是。令P：我给你写了信，Q：信在路上丢了， 则原命题可表示为：PQ 4试做出下列公式的填表 (P)(Q)=A

2、 P T T F F Q T F T F A F F F T A=(PQ)(PQ) P T T F F Q T F T F A T F F F A=(P(QR) P T T T T F F F F Q T T F F T T F F R T F T F T F T F A T F T T T F F F A=(PQ)R) P T T T T F F F F Q T T F F T T F F R T F T F T F T F A T F T T T T T T 注：该题公式与等值，故真值表相同。 A=(P(Q)UQ) P Q A T T F F T F T F T T F F (6)A=(P

3、Q)(RS) P T T T T T T T T F F F F F F F F Q T T T T F F F F T T T T F F F F R T T F F T T F F T T F F T T F F S T F T F T F T F T F T F T F T F A T T T T T F F F T F F F T F F F (7)A=(P)Q)(Q)R) P Q R A T T T T T T F T T F T T T F F T F T T F F T F T F F T T F F F F A =(P(QR)(PQ)(PR) P Q R A T T T T F

4、 F F F T T F F T T F F T F T F T F T F F T T F F F F F 5联结词“”和“”有下列等式关系 ）(1)PQ=T (2) PQ=T(TP)(TQ) (1) 证明：T(TP)(TQ)T(T(TPTQ)T(PQ)=PQ (2) 同理可证 6证明下列公式对是等价的。 (1) 证明 PQ(TQTP) 证明：右 (Q(P)Q(P)(P)QPQ=左 (2) 证明 (PQ)R)(PR)(QR) 证明 ：利用“”关于“”的分配律有 左(PR)(QR)右 (3) 证明 (P)(Q)(R)(R(QP) 证明： 左(P)(Q)(R)(PQ)(R) (R)(QP)(R(

5、QP)右 证明 (P)Q)R)(P(Q)R) 证明 左(P)Q)R)(P(Q)R右 证明 (PQ)(RQ)(PR)Q) 证明 ： 左(PQ)(RQ)(PR)Q) (PR)Q)(PRQ)右 证明 (PQ)(PQ)(PQ) 证明：左(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PP)(PQ)(QP)(QQ) (PQ)(PQ)(PQ)(PQ)右 证明 (P(PQ)(Q(PR)(PQ)(P(QR)(PQ)(PR)证：左(P(QR)(Q(PR) (P(QR)(QPR) T 右 (PQ)(P(QR)(PQ)(PR) (PQ)(P(QR)(P(QR)(PQP)(PQ)(QR)(P(QR)P)(P(QR

6、)(QR)TTT(P(QR)(QR)T 所以 左右 证明(PQ)(RQ)(PR)Q 证：左(PQ)(RQ)(PR)Q (PR)Q(PR)Q右 证明(PQAC)(APQC)(A(PQ)C 证明：右(A(PQ)(QP)C (A(PQ)(QP)C(A(PQ)(QP)CA(PQ)(QP)C(AP)(AQ)(QC)(PC)(APQC)(APPC)(AQQC)(AQPC)(A(PQC)TT(AQP)C) 证明(P(QR)(Q(PR) 证：左(P(QR)(Q(PR) (Q(PQ)=右 7略 8化简下面的命题公式 A(A(BB)A(AF)=AA=T (ABC)(ABC)(AA)(BC) T(BC)BC (AB

7、)(BA)C(AB)(BA)C TCC (PQ)(QP)R(PQ)(QP)R TRR 9解：当ACBC时 未必有AB 因为当C=F时 对任何命题公式A与B 恒有ACBC 10解：若AB 则必有AB 因为当AB为永真公式时 AB11设三元联结词f定义如下： 也是永真公式。 e1 T T T T F F F F e2 T T F F T T F F e3 T F T F T F T F f(e1,e2,e3) F T T T F F T T 解 由f的定义，不难看出 Pf(P,P,P)PQf(f(P,P,P),f(P,P,P),f(Q,Q,Q)因为,是功能完备的，所以联结词f是最小完备的。 由于

8、PQf(P,P,f(Q,Q,Q)PQf(P,P,Q)所以由于PQPQf(P,P,P)Q f(f(f(P,P,P),f(P,P,P),f(P,P,P),f(f(P,P,P),f(P,P,P),f(P,P,P),f(Q,Q,Q)12.解：首先，将公式(PQ)PQ)(QP)化简成与之等价的公式： 原式(PQ)(PQ)(QP) (PQ)(PQ)(PQ) PQ 从而该公式所表达的含义为“我今天没课，但也没法去阅览室。” 13判断下列公式是永真公式、永假公式还是其他。 解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) 因为它的主析取范式没含有所有的极小项。因此，他是一个可满足式。 (PQ)Q)(QR)

9、Q)(PQ)Q)(RQ)Q) (PQ)Q(RQ)Q 因此，它是一个重言式。 (QP)P)(PR)(QPP)(PR)=F 因此，它是一个矛盾式。 (PQ)R)(PQ)R) (PQ)R)(PQ)R)(PQ)R)(PQ)R) T因此，它是一个重言式。 (PQ)R)(P(QR)(PQ)R)(P(QR) (PR)(QR)(PQ)(PR)(PRPQ)(PRPR)(QRPQ)(PRPR)T因此，它是一个重言式。 (6)(PQ)R)(R(PQ) (PQR)(RPQ)(RPQ)(RPQ) 因此他是一个永假式。 (7)(PQ)R)(PQ)R) (PQ)(PQ)R)(PR)(QR) (PQR)(PQR)(PQR)(

10、PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) 因此他是可满足式。 (PQ)(QR)(Q(PR) (PQ)(QR)(Q(PR) (PQR)(PQR) 因此它是一个重言式 14.求下列公式的主吸取范式及主合取范式： 解：(1) (PQ)(PR) (PQ)(PR)(PR)(PR) (PQP)(PQR)(PQ)(PR) (PQ)(PQR)(PPR)(PQR) (PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) 这便是该公式的主吸取范式。 主合取范式为。 (PQR)(PQR)(PQR)(PQR) (PQ)QR (PQ)QR (P

11、Q)Q)R R(QR)(QR) (PQR)(PQR)(PQR)(PQR) 这便是公式的主合取范式。 主析取范式为(PQR)(PQR)(PQR)(PQR)。 (PR)(PQ) (PR)(PQ)(PQ) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR)(PQR) 这便是该公式的主合取范式。 主析取范式为(PQR)(PQR)(PQR)。 (P(QR)(P(QR) (P(QR)(P(QR) (PP)(PQR)(PQR)(QRQR) (PQR)(PQR)m111m000 这便是该公式的主析取范式。 主合取范式为M001M010M011M100M101

12、M110 (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(P(QR)(P(QR) (PQR)(P(QR)(QR) (PQR)(PQR)(PQR) M100M001M101 这便是该公式的主合取范式。 主析取范式为m000m101m011m110m111(PQR)(PQR)(PQR)(PQR)(PQR)(6)略 (7) P(PQ)(QP)P(PQ)(QP)P(PQP)(QQP)P(PQ)(PQ)(PQ)(PQ)m10m11m00这便是该公式的主析取范式 主合取范式为M01PQ (PQ)R)(PQ)R)(PQ)R(PR)(QR)(PQR)(PQR)(PQR)(PQR) (PQR)(P

13、QR)(PQR)m100m010m000这便是该公式的主析取范式 主合取范式为M001M011M101M110M111(PQR)(PQR)(PQR)(PQR)(PQR)(QP)R(QP)R(QP)R(QR)(PR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)M010M110M000这便是该公式的主合取范式 主析取范式为M001M011M100M101M111 (PQR)(PQP)(PQR)(PQP)(PQP) 16.试证下列蕴函关系. (PQ) 证：因为(PQ)(PQ）(PQ)(PQ)(PQ)T 所以QPQ 证：利用真值表法 令 A=Q)(PQ),z则公式A的真值表

14、为 P T T F F Q T F T F QPQ. (Pq),qR,RP 证：利用真值法：设公式(Pq),qR,R均为T。 则R为F，由qR为T，知q为T，从而q为F。 再由(Pq)为T知：Pq为F。以及q为F知：P为F。 因此，P为T。即 (Pq),qR,RP p(qR),(ST)P,STqR )P,ST均为真。 证：设公式p(qR),(ST由ST真及(ST再由p(qR)P真知P真。 )真及P真知qR真 )P,STqR 因此p(qR),(STPQ,(PQ)(RS)SR )(RS)真。由PQ真可推出PQ真。 证：设PQ真，(PQ再由(PQ)(RS)真，可推出RS真，即SR真。 )(RS)SR

15、 )R,(QS)S )R,(QS)均为真 因此，PQ,(PQ(QRPQ，(QR证：设PQ，由(QR)R真QR真且R真QR真且R假 Q真。再PQ真QP真。从而P真。 再由(PS)真SP真SP真PS真 从而S真。 因此，该蕴涵关系成立 (9) (P(QR)(PQ)(PR) 证： (P(qR)(PQ)(PR) (PqR)(Pq)(PR) (PqR)(Pq)(PR) (PqR)(PPR)(qPR) (PqR)(PqR) (PqR)(PqR)T 因此， FB= FC= 20.解：因为A的主合取范式为M001M100M010 所以A的主析取范式为m000m011m101m110m111 即A 21.证：因

16、为,不是完备的，所以,不是最小完备联结同集. 因为，不是完备的，所以，不是最小完备联结同集. 22证：因为V均不是完备的，例如公式P不可由它们单独表示，所以，它们都不是最小完备联结同集. 23 .证：由命题1.37得知.是完备的.且联结词不能由联结词表示，所以，.是最小完备联结词集。 Q=(PQ),所以,也是最小完备联结词。 由因为 PCC24.利用CP规则证明： (1)P(QR),(RS)T,STW(PQ)W 证：PQ P (2)P T,(1),I1 (3)P(QP) P (4)QR T,(2),(3),I11 (5)Q T,(1),I2 (6)R T,(4),(5),I11 (7)RST

17、P (8)RST T (7) E (9)RST T (8) E (10)ST T,(6),(9),I11 (11)STW P (12)W T,(10),(11),I11 (13)(PQ)W C P (1).(12) (2) PQ,QP,RSPS 证：(1)P P (2) PQ P (3) QR P (4)RS P (5)PQ T (2) (6) QR T (3) (7)PR T,(5),(6),I13 (8)PS T,(4),(7,I13 (9)S T,(1),(8),I11 (10) PS C P (1) (9) PQP 证： (1)(3)PQPPT,(1),(2),I11 T,(1),(3

18、),I9CP(1),(4)(2)PQ(4)PQ(5)P(PQ)P(QR),QS,(TS),Q(PT)QT 证： (1)QPPT(2),ET,(1),(3)IPT,(4),(6),IT,(7)T(8),ICP,(1),(9)(2)QS(3)QS(4)S(5)(TW)S(7)(TW)(8)TW(9)T(10)QT(6)S(TW)T(5),E(PQ)R(PQ)R 证： (1)PQ(2)P(3)PQPT(1)I1T(2)I3(4)(PQ)RP(5)RT(3),(4)I11(6)PQRCP(1),(5)(PQ)(Rs),(ST)WPW证：P P PQ TI (PQ)(RS) P RS TI11 R T.

19、I1 RT TI3 (RT)W P W T. PW CP. 3I11 (PQ)R,(RS)W,7X(S7W)P(QX) 证 P P Q Q PQ T.CP (PQ)R P R T. (PS)W P R7SW TE 7X(S7W) P 7(SW)X TE 7SWX TE RX TI13 X T. QX CP P(QX) CP 25解：由条件、分别有下列命题公式 AC，BC，CAB 求它们的合取式得 I11 I11 (AC)(BC)(CAB) (AC)(BC)(CAB)(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)(ABC) M000M011M100M1

20、10M111 m001m010m101 (ABC)(ABC)(ABC) 所以，立项方案有三种； 第一种：C上，A、B不上； 第二种：B上，A、C不上； 第三种：A、C上，B不上。 26解：令P：营业员A作案. Q：营业员B作案. R:：营业员A提供正确证词. S：作案时间为营业时间. T：货柜上了锁. 则侦察结果可写成如下的命题公式 PQ QS，RT RS，T 推理如下：T P RT P TR T(2)E R T(1)、(3) QS P RS P SQ T(5)E (7)I13 RQ T(6)、(8)I11 Q T(4)、PQ P (10)I P T(9)、 所以作案者为A。 27.解：令P：

21、文件系统加锁 Q：新消息将被排成队 R：系统正常运行 S：新消息被送入缓冲区 则符号化为PQ，PR，QS，PS，S 28.解：令A2为A获得第二名，A3为A获得第三名， B2为B获得第二名，B5为B获得第五名， C2为C获得第二名，C3为C获得第三名， D1为D获得第一名，D4为D获得第四名， E4为E获得第四名，E5为E获得第五名。 依据条件：甲猜对一半(A2B5)(A2B5)在真值指派f下为真， 乙猜对一半(C3E4)(C3E4)在真值指派f下为真， 丙猜对一半(C2D4)(C2D4)在真值指派f下为真， 丁猜对一半(B2A3)(B2A3)在真值指派f下为真， 戊猜对一半(D1E5)(D1

22、E5)在真值指派f下为真， 从而在真值指派f下 公式 G=(A2B5)(A2B5)(C3E4)(C3E4)(C2D4)(C2D4)(B2A3)(B2A3)(D1E5)(D1E5)为真。 另外，一个人只能获得一个名次，所以还应有在真值指派f下 A2A3,B2B5,C2C3,D1D4,E4E5均为假.又设并列名次，所以，在真值指派f下 A2B2,A2C2,B2C2,A3C3,D4E4,B5E5为假 利用上述条件，化简公式G 由(A2B5)(A2B5)(A2A3)(B2A3)(A2B5B2A3)(C3E4)(C3E4)(C2D4)(C2D4)(C3E4C2D4)(C3E4C2D4)得G=(C3E4C

23、2D4)(C3E4C2D4)(D1E5)(D1E5)(A1B5B2A3D1E5)(C3E4C2D4)(C3E4C2D4)(A1B5B2A3D1E5C3E4C2D4)因此，第一名为D，第二名为C，第三名为A，第四名E，第五名为B。 29.解：令P表示该矿样为铁；Q表示该矿样为铜；R表示该矿样为锡。 由条件知有一人的判断都正确，所以， (PQ)(PR)(PR)(P(QR)(PR) (PR)(PQR)为真。 由条件知，有一人的判断对一半，所以 (PQ)(PQ)(PR)(PQ)(PR)(PR) (PQ)(PQ)(PR)(PR)(PR)(PR) (PQR)(PQR)(PR)(PR) (PQR)(PQR)

24、为真。 由条件知，有一人的判断全错，所以 (PQ)(PR)(PR) (P(QR)(PR) (PR)(PQR)为真 从而 (PR)(PQR)(PQR)(PQR)(PR)(PQR)为真，求出的主合取范式为 (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)从而它的主析取范式为 (PQR)(PQR)为真 又因为矿样只能为一种矿石，所以QR为假 PQR为真，即P为真 因此，该矿样为铁。 从而，甲是普通队员 乙是见习生 丙是专家 30解：令A.B.C.D分别表示派A.B.C.D出差 则条件为ACD ( 2 ) 为 ( 3 ) CD 将条件合成为 求该公式的主析取范式 首先求主合取范式 原式 (

25、 CD） M0011M0110M0111M1000M1011M1100M1110M1111 从而 主析取范式为 m0000m0001m0010m0100m0101m1001m1010m1101 因为派三个人出差 所以 为真。因此 符合条件的派法有三种： 第一种：派B和D出差， 第二种：派A和D出差， 第三种：派A和C出差。 31 解：由题意得 G(pqr)(pqr)(rqr)(pqr) 这是主析取范式 ，从而主合取范式为 GM000M010M101M111 (pqr)(pqr)(pqr)(rqr)32 解：设三个按扭分别A，B，C表示，P，Q，R表示按纽A，B，C。 G表示会场电铃响。 则G(

26、pqr)(pqr)(pqr)(pqr) 33 解：令A表示执行下载，根据条件构成A的真值表如下： ETTTTTTTTNTTTTFFFFDOTTTFFFTTFFTFTFTFAFFFF TTTFFFFFFFFFTTTTFFFFTTFFTTFFTTFTTTFTTTFTTTFT执行下载的主合取范式为 (ENDO)(ENOO)(ENDO)(ENDO)(ENDO)第二章习题 1 填空 A(x)，B(y) x(C(x)A(x) x(A(x)B(y) xy(F(x)F(y)H(x,y) $x(F(x)G(x) T y(P(x,y)Q(y,z)，P(x,y)Q(y,z)，P(x,y) $!x(Q(x)P(x)

27、$!x(Q(x)P(x) y,x和z x(Q(x)R(y)，$x(Q(x)Z(x)，$x(Q(x)R(x)Z(x) 2选择题 B B A B C C B B B D C A 3下列哪些是谓词公式 解：公式均为谓词公式。 4在谓词逻辑中将下列命题符号化 有些汽车比所有火车都跑得慢； 解：令A(x)：x是汽车，B(x)：x是火车，C(x,y)：x比y跑得慢。 符号化为$x(A(x)(y(B(y)C(x,y) 会叫的狗未必会咬人； 解：令A(x)：x会叫，B(x)：x是狗，C(x)：x会咬人 符号化为$x(A(x)B(x)C(x) 存在最小自然数 解：令A:x是自然数，B：x 小于y 符号化为$x(

28、A(x)y(A(y)B(y,x) 对于每个实数都存在比它大的有理数 解：令A:x是实数，B:x是有理数，R：x 比y大 符号化为x(A(x)$y(B(y)R(y,x) 每个自然数都有唯一的后继 解：令A:x是自然数，B：x 是y的后继 符号化为x(A(x)$!y(A(y)B(y,x)） 没有以0为后继的自然树 解：令A:x是自然数，B：x 是y的后继 符号化为$x(A(x)B(0,x) 存在唯一的偶实数 解：令A:x是偶数，令B:x是素数 符号化为$!x(A(x)B(x) (8)没有即是奇数也是偶数的数 解：令A:x是奇数，令B:x是偶数 符号化为$x(A(x)B(x) 天下乌鸦一般黑 解：令

29、A:x是乌鸦，令B:x是黑的 符号化为x(A(x)B(x) 一个数是素数当且仅当它只能被1和它自身整除 解：A(x):x是素数;.B(x,y):x被y整除;.C(x,y):x与y相等;D(x):x是实数; 符号化为：x(A(x)$y(D(y)B(x,y)(C(y,1)C(y,x) 5、利用所给定命题和谓词，将下列诸命题符号化。 P表示“今天天气好”；Q表示“入学考试准时进行”； A表示“c是考生”：B(c)表示“c提前进入考场”； C表示“c取得良好成绩”;E表示“e1=e2”。 如果今天天气不好，就一定有些考生不能提前进入考场， 符号化为：P$x(A(x)B(x) 如果所有考生提前进入考场，

30、那么入学考试可以准时进行。 符号化为：x(A(x)B(x)Q 并非所有提前进入考场的考生都能取得良好成绩。 符号化为：(x(A(x)B(x)C(x) 又且仅有一个提前进入考场的考生未取得良好成绩。 符号化为：$!x(A(x)B(x)C(x) 或：(A(x)B(x)C(x)(A(y)B(y)C(y)E(x,y) 7、将下列命题符号化，要求只是用全称量词。 有些有理数是整数，但并非所有有理数都是整数。 解：令A: x是有理数，B: x是整数; 符号化为：(x(A(x)B(x)(x(A(x)B(x) (2)有些素数是偶数。有些素数是奇数 解：令A(x)：x是素数。B(x):x是偶数。C(x)：x是奇

31、数。 符号化为x(A(x)B(x)x(A(x)C(x) 6.将下列命题符号化，要求只使用存在量词 (1)有些人是大学生，但并非所有人都是大学生 解：令：A(x):x是人,B(x):x是大学生 符号化为$x(A(x)B(x)$x(A(x)B(x) (2)所有整数都是有理数 解：令A(x):x是整数。B(x):x是有理数 符号化为$x(A(x)B(x) 8设个体域为a,b，请消除以下谓词中的量词 (1)x(P(x)Q(x) 解：原式(p(a)q(a)(p(b)q(b) (2)(x)($y)(R(x,b) 解：原式($yR(a,b)($yR(b,b) (R(a,a)R(a,b)(R(b,a)R(b,

32、b) (3)($y)(x)R(x,y) 解：原式(x)(R(x,a)(x)(R(x,b) (R(a,a)R(b,a)(R(a,b)R(b,b) 9.若A(x)表示x是整数;B(x)表示x是偶数; C(x)表示x是奇数;D(x)表示x是素数 E(x)表示x能整除y. 试用日常用语叙述下列命题。 x(B(X)A(X) 解：所有的偶数都是奇数。 $X(A(X)C(X) 解：有些奇数是奇数。 X(E(2.X)B(X) 解：所有被2 整除的数均是偶数。 $X(C(X)D(X) 解：有些奇数是素数。 $X(C(X)D(X)X(C(X)D(X) 解：有些奇数十素数，但并非所有奇数都是素数。 10.将命题“并非E1中的每个数都小于或等于E2中的每个数”分别按下面所要求的形式表达出来： (1) 出现全称量词，不出现存在量词 解:令A(X,Y)表示“X属于Y” B(X,Y)表示“XY” 则XYAX,(E)B(Y,E)B(X,Y) 12出现存在量词，不出现全称量词 解：令A(X,Y)表示“X属于Y” B(X，Y)表示“XY” 则$X$YAX，(E)A(Y，E)B(X，Y) 1211.指出下列各式的自由变元和约束变元，并确定量词的辖域 ($X)(P(X)R(X)S(X)X(P(X)Q(X) 解：所有变元均为约束变元 量词