离散数学(第7讲习题课1)

《离散数学(第7讲习题课1)》由会员分享，可在线阅读，更多相关《离散数学(第7讲习题课1)（29页珍藏版）》请在装配图网上搜索。

1、1离散数学离散数学习题课（一）习题课（一）DISCRETE MATHEMATICSDISCRETE MATHEMATICS第一章第一章 小结小结命题命题 命题的解释命题的解释 原子命题、复合命题原子命题、复合命题 逻辑联结词（、逻辑联结词（、）命题公式命题公式 公式的解释公式的解释 永真式永真式(重言式重言式)永假式永假式(矛盾式，不可满足公式矛盾式，不可满足公式)可满足式可满足式命题公式的等价命题公式的等价 替换定理替换定理 对偶式对偶式 对偶原理对偶原理 基本等价式基本等价式2范式范式 句节、子句、短语、析取范式、合取句节、子句、短语、析取范式、合取范式范式 极小项极小项-主析取范式主析取

2、范式 极大项极大项-主合取范式主合取范式 命题公式的蕴涵命题公式的蕴涵 基本蕴含（关系）式基本蕴含（关系）式 推理规则推理规则 P P规则（称为前提引用规则）规则（称为前提引用规则）规则（逻辑结果引用规则）规则（逻辑结果引用规则）规则（附加前提规则）规则（附加前提规则）一、基本概念一、基本概念二、基本方法二、基本方法1 1、应用基本等价式及置换规则进行等价演算、应用基本等价式及置换规则进行等价演算2 2、求主析取（主合取）范式的方法、求主析取（主合取）范式的方法1 1）等价变换法）等价变换法2 2）真值表技术法）真值表技术法 主合取范式主合取范式-在命题公式的真值表中，使公式取值在命题公式的真

3、值表中，使公式取值0 0时的解释所对应的时的解释所对应的全部极大项的合取式全部极大项的合取式。主析取范式主析取范式-在命题公式的真值表中，使公式取值在命题公式的真值表中，使公式取值1 1时的解释所对应的时的解释所对应的全部极小项的析取式全部极小项的析取式。3 3、推理的各种方法、推理的各种方法（1 1）直接法）直接法（2 2）利用）利用CPCP规则规则（3 3）反证法）反证法 4 4、消解法、消解法3析取析取-P Q PQ 0 0 0 0 1 1 1 0 1 1 1 14注：汉语中的注：汉语中的“或或”有时与有时与有相同有相同含义，称含义，称可兼或可兼或（相容或）；有（相容或）；有时与时与不可

4、兼或不可兼或（排斥或，记为（排斥或，记为）有相同含义。有相同含义。排斥或排斥或 用真值表表示用真值表表示:P Q P Q 0 0 0 0 1 1 1 0 1 1 1 0联结词联结词表示析取。两个命题表示析取。两个命题P P和和Q Q析取为一析取为一个新的命题个新的命题PQPQ（读作（读作P P或或Q Q）。）。PQPQ为为真，当且仅当真，当且仅当P P或或Q Q至少有一个为真。用真值至少有一个为真。用真值表表示表表示:例：我上街去书店或去看电影例：我上街去书店或去看电影 两种可能可以同时为真两种可能可以同时为真例：我坐第三排五号或第四排五号例：我坐第三排五号或第四排五号。两种可能不能两种可能不

5、能同时为同时为真真,又不能同时为假，只有一又不能同时为假，只有一种是真，所以应是异或（排斥或）。种是真，所以应是异或（排斥或）。注：教室里有注：教室里有3030或或4040人（人（或不是做联结词，而是指大约人数或不是做联结词，而是指大约人数）561、下列语句中哪些是命题？是命题的句子中哪些是简单命题？下列语句中哪些是命题？是命题的句子中哪些是简单命题？（1 1）请快开门！）请快开门！A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（2 2）你去哪里？）你去哪里？A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不

6、是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（3 3）这房间可真热呀！）这房间可真热呀！A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（4 4）x+y10 x+y10。A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（5 5）苹果树和梨树都是落叶乔木。）苹果树和梨树都是落叶乔木。A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题三、典型例题三、典型例题7（6 6）2

7、2是质数或合数。是质数或合数。A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（7 7）豆沙包是由面粉和红小豆做成的。）豆沙包是由面粉和红小豆做成的。A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（8 8）吃一堑，长一智。）吃一堑，长一智。A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单命是命题而且是简单命题题（9 9）n n是偶数当且仅当它能被是偶数当且仅当它能被3 3整除。（整除。（n n为一固定的

8、自然数）为一固定的自然数）A.A.不是命题不是命题B.B.是命题但不是简单命题是命题但不是简单命题C.C.是命题而且是简单是命题而且是简单命题命题（1 1）A A；（；（2 2）A A；（；（3 3）A A；（；（4 4）A A；（；（5 5）B B；（；（6 6）B B；（；（7 7）C C；（；（8 8）B B；（；（9 9）B B。82 2、上题中语句（上题中语句（5 5）（9 9）为命题，如下所示：）为命题，如下所示：（5 5）苹果树和梨树都是落叶乔木。）苹果树和梨树都是落叶乔木。（6 6）2 2是质数或合数。是质数或合数。（7 7）豆沙包是由面粉和红小豆做成的。）豆沙包是由面粉和红小

9、豆做成的。（8 8）吃一堑，长一智。）吃一堑，长一智。（9 9）n n是偶数当且仅当它能被是偶数当且仅当它能被3 3整除。（整除。（n n为一固定的自然数）为一固定的自然数）9103 3、设设p p：星期六天气好，：星期六天气好，q q：我去公园玩。将下列命题：我去公园玩。将下列命题符号化。符号化。（1 1）只要星期六天气好，我就去公园玩。）只要星期六天气好，我就去公园玩。（2 2）只有星期六天气好，我才去公园玩。）只有星期六天气好，我才去公园玩。（3 3）除非星期六天气好，否则我不去公园玩）除非星期六天气好，否则我不去公园玩。（1 1）pqpq（2 2）qpqp或或 pp q q（3 3）q

10、pqp或或 pp q q 11表表1 p1 p (qp)(qp)的真值表的真值表表表2(pq)(2(pq)(qq p)p)的真值表的真值表p qp (qp)0 0 1 0 00 1 0 1 01 0 1 0 01 1 1 0 0p qp pq qpqpqqq p p(pq)(pq)(qq p)p)0 0111110 1101111 0010011 100111p qpq0 0100 1101 0001 111（1 1）为矛盾式；（）为矛盾式；（2 2）为重言式；（）为重言式；（3 3）为可满足式；）为可满足式；12（1 1）p pq q，其中，其中，p p：2 22 24 4，q q：地球静止

11、不动，真值为：地球静止不动，真值为0 0。（2 2）p pq q，其中，其中，p p：2 22 24 4，q q：地球运动不止，真值为：地球运动不止，真值为1 1。（3 3）p pq q，其中，其中，p p：地球上有树木，：地球上有树木，q q：人类能生存，真值为：人类能生存，真值为1 1。（4 4）p pq q，其中，其中，p p：地球上有水，：地球上有水，q q：是无理数，真值为：是无理数，真值为1 1。136 6、设设A A与与B B均为含均为含n n个命题个命题变元变元的公式，判断下列命题是否为真的公式，判断下列命题是否为真？（1 1）为假；（）为假；（2 2）为真；（）为真；（3 3

12、）为真；（）为真；（4 4）为假；（）为假；（5 5）为假；（）为假；（6 6）为假；（）为假；（7 7）为真。）为真。147 7、证明、证明P(QR)P(QR)(PQ)R(PQ)R证明：证明：P(QR)P(QR)P(QR)P(QR)（蕴涵式）（蕴涵式）P(P(QR)QR)（蕴涵式）（蕴涵式）(PP Q)R (Q)R (结合律结合律)(PQ)R(PQ)R(De Morgan(De Morgan定律定律)(PQ)R(PQ)R（蕴涵式）（蕴涵式）158 8、试证明、试证明(P(QR)(P(P(QR)(P Q Q R)R)P P证明：证明：(P(QR)(P(P(QR)(P Q Q R)R)P(QR)

13、(P(QR)(Q Q R)R)（分配律）（分配律）P(QR)P(QR)(QR)(QR)(De Morgan(De Morgan定律定律)PTPT（矛盾律）（矛盾律）P P(同一律同一律)169 9、证明、证明 (P(PQ)Q)(P(PQ)Q)(P(PQ)Q)(P(PQ)Q)(P(PQ)Q)(P(PQ)Q)(P PQ)Q)(De Morgan(De Morgan定律定律)(P(PQ)Q)P)P)(P(PQ)Q)Q)Q)（分配律）（分配律）(P(PP)P)(Q(QP)P)(P(PQ)Q)(Q(QQ)Q)(Q(QP)P)(P(PQ)Q)（矛盾律）（矛盾律）(QQP)P)(P PQ)Q)(De Mor

14、gan(De Morgan定律定律)(Q(QP)P)(P(PQ)Q)（蕴涵式）（蕴涵式）(P(PQ)Q)（等价式）（等价式）1010、G=G=()，求主析取和主合取范式。，求主析取和主合取范式。解：首先列出其真值表如下：解：首先列出其真值表如下：P Q R P Q R PQPQ（PQPQ）(PQ)RPQ)R0 0 00 0 01 10 00 00 0 10 0 11 10 01 10 1 00 1 01 10 00 00 1 10 1 11 10 01 11 0 01 0 00 01 11 11 0 11 0 10 01 11 11 1 01 1 01 10 00 01 1 11 1 11 1

15、0 01 117极大项极大项极小项极小项PQRPQRPPQRQRPPQRQRP PQ QR RP PQ QR RP PQ QR RP PQ QR RP PQ QR R主析取范式主析取范式=（P PQ QR R）（P PQ QR R）（P PQ QR R）（P PQ QR R）（P PQ QR R）主合取范式主合取范式=（PQRPQR）（PPQRQR）（PPQRQR）181111、用等价变换法求上题中的主析取和主合取范式、用等价变换法求上题中的主析取和主合取范式()（P PQQ）R R（P PQ Q）R R（P PRR）（QRQR）（P PRR（QQQQ）（QRQR（PPPP）（P PRRQ Q

16、）（P PRQRQ）（QRQRP P）（QRQRP P）（P PRRQ Q）（P PRQRQ）（QRQRP P）（主合取范式）主合取范式）()（P PQQ）R R（P PQ Q）R R（P PQQ（R RR R）（RR（PPP P）（QQQ Q）（P PQRQR）（P PQQR R）（RPRP）（RRP P）（P PQRQR）（P PQQR R）（RPRP（QQQ Q）（RRP P（QQQ Q）（P PQRQR）（P PQQR R）（RPRPQQ）（RPRPQ Q）（RRP PQQ）（RRP PQ Q）（主析取范式）（主析取范式）1912、将下面一段程序简化将下面一段程序简化If AB the

17、nIf AB then If BC then If BC then X X Else Else Y Y End EndElseElse If AC then If AC then Y Y Else Else X X End EndEndEnd 执行程序段执行程序段X X 的条件为的条件为(AB)(AB)（B B C)C)(ABAB)(AC)(AC)(A(A BCBC）If AIf A BC thenBC then Y Y Else Else X X End End执行程序段执行程序段Y Y的条件为的条件为(AB)(AB)(B C)(B C)(AB(AB）（AC)AC)AA BCBC201313

18、、如如果果今今天天是是星星期期一一，则则要要进进行行离离散散数数学学或或数数据据结结构构两两门门课课程程中中的的一一门门课课的的考考试试；如如果果数数据据结结构构课课的的老老师师生生病病，则则不不考考数数据据结结构构；今今天天是是星星期期一一，并并且且数数据据结结构构的的老老师师生生病病。所所以以今今天天进进行行离离散散数数学的考试。学的考试。解：设解：设P P：今天是星期一；：今天是星期一；Q Q：要进行离散数学考试；：要进行离散数学考试；R R：要进行数据结构考试；：要进行数据结构考试；S S：数据结构课的老师生病；：数据结构课的老师生病；则则PQPQ R R，SSR R，PSPSQ Q。

19、证证:PS PS S S ,I ,I S SR R R R ,I ,I P P ,I ,I PQ PQ R R Q Q R R ,I,I Q Q ,I,I 211414、一一位位计计算算机机工工作作者者协协助助公公安安人人员员审审查查一一件件谋谋杀杀案案，警警方方掌掌握握的的线索如下；线索如下；（1 1）会计张某或邻居王某谋害了厂长。）会计张某或邻居王某谋害了厂长。（2 2）如果会计张某谋害了厂长，则谋害不能发生在半夜。）如果会计张某谋害了厂长，则谋害不能发生在半夜。（3 3）如果邻居王某的证词是正确的，则谋害发生在半夜。）如果邻居王某的证词是正确的，则谋害发生在半夜。（4 4）如果邻居王某的

20、证词不正确，则半夜时屋里灯光未灭。）如果邻居王某的证词不正确，则半夜时屋里灯光未灭。（5 5）半夜时屋里灯光灭了，且会计张某曾贪污过。）半夜时屋里灯光灭了，且会计张某曾贪污过。计算机工作者用他的数理逻辑知识，很快推断出谋害者是谁？计算机工作者用他的数理逻辑知识，很快推断出谋害者是谁？请问请问:谁是谋害者？怎样推理发现他？谁是谋害者？怎样推理发现他？22解：设解：设P P：会计张某谋害了厂长：会计张某谋害了厂长 Q Q：邻居王某谋害了厂长：邻居王某谋害了厂长 N N：谋害发生在半夜。：谋害发生在半夜。O O：邻居王某的证词是正确的。：邻居王某的证词是正确的。R R：半夜时屋里灯光灭了。：半夜时屋

21、里灯光灭了。A A：会计张某曾贪污过。：会计张某曾贪污过。上述案情有如下命题公式：上述案情有如下命题公式：（1 1）PQ PQ （2 2）PPN N （3 3）ON ON （4 4）OOR R （5 5）RARA23问题是需求证：问题是需求证：PQPQ，PPN N，ONON，OOR R，RA RA？证：证：RA PRA P R T R T，I I OOR PR P O T O T，I I，E E ON P ON P N T N T，I I P PN PN P P TP T，I,EI,E PQ P PQ P Q T Q T，I I PQPQ，PPN N，ONON，OOR R，RA RA Q Q

22、结论是：邻居王某谋害了厂长。结论是：邻居王某谋害了厂长。241515、证明下面论述的有效性。、证明下面论述的有效性。在意甲比赛中，假如有四只球队，其比赛情况如下：在意甲比赛中，假如有四只球队，其比赛情况如下：如如果果国国际际米米兰兰队队获获得得冠冠军军，则则ACAC米米兰兰队队或或尤尤文文图图斯斯队队获获得得亚亚军军；若若尤尤文文图图斯斯队队获获得得亚亚军军，国国际际米米兰兰队队不不能能获获得得冠冠军军；若若拉拉齐齐奥奥队队获获得得亚亚军军，则则ACAC米米兰兰队队不不能能获获得得亚亚军军；最最后后，国国际际米米兰兰队队获获得得冠冠军军。所所以，拉齐奥队不能获得亚军。以，拉齐奥队不能获得亚军。

23、解：设解：设P P：国际米兰队获得冠军；：国际米兰队获得冠军；Q Q：ACAC米兰队获得亚军；米兰队获得亚军；R R：尤文图斯队获得亚军；：尤文图斯队获得亚军；S S：拉齐奥队获得亚军；：拉齐奥队获得亚军；则原命题可符号化为：则原命题可符号化为：PQPQ R R，RRP P，SSQ Q，P PS S25 （S S）P P（附加前提）（附加前提）S T,S T,E,E S SQ PQ P Q T,Q T,I,I PQ PQ R PR P P P P P Q Q R T,IR T,I R T,R T,I,I R RP PP P P T,IP T,I P PP(P(F)F)T,E T,E结论：拉齐奥

24、队不能获得亚军结论：拉齐奥队不能获得亚军1616、若、若n n是偶数，并且是偶数，并且n n大于大于5 5，则，则m m是奇数。只有是奇数。只有n n是偶数，是偶数，m m才大于才大于6 6。n n是大于是大于5 5，所以，若，所以，若m m大于大于6 6，则，则m m是奇数。是奇数。解：设解：设p p：n n是偶数，是偶数，q:n q:n大于大于5,5,r:m r:m是奇数是奇数,s:m s:m大于大于6.6.前提前提:(pq)r,sp,q:(pq)r,sp,q结论结论：srsr26证明证明:q P q P sq sq 扩充法则扩充法则 （关键）（关键）spsp P P(spsp)()(sq

25、sq)T)TIIs(ps(pq q)T)TI I(p(pq q)r P)r Psr Tsr TI I1717、习题一、习题一 1414题题解：解：由题设由题设 p p：A A去，去，q q：B B去，去，r r：C C去，去，s s：D D去去则满足条件的选派应则满足条件的选派应满足满足如下范式：如下范式：（pp（r r s s）（qrqr）（rsrs）（ppq q r s r s）（ppq qr rs s）（ppqrqrs s）（pqpqr rs s）（ppq qr rs s）（ppqqrsrs）（pqpqr rs s）（pqpqr rs s）27共有八个极小项，但根据题意，需派两人出差，所

26、以，只有其中共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：三项满足要求：（ppq qr rs s），（），（ppqqrsrs），（），（pqpqr rs s）即有即有三种方案：三种方案：A A和和C C去或者去或者A A和和D D去或者去或者B B和和D D去。去。1818、习题、习题1818解：根据给定的条件有下述命题：解：根据给定的条件有下述命题：P P：珍宝藏在东厢房：珍宝藏在东厢房Q Q：藏宝的房子靠近池塘：藏宝的房子靠近池塘R R：房子的前院栽有大柏树：房子的前院栽有大柏树S S：珍宝藏在花园正中地下：珍宝藏在花园正中地下T T：后院栽有香樟树：后院栽有香樟树

27、M M：珍宝藏在附近：珍宝藏在附近根据题意，得出：根据题意，得出：（QQP P）（RPRP）QQ（RSRS）（TMTM）？28（Q QP P）（R RP P）QQ（R RS S）（T TM M）PP（R RP P）（R RS S）（T TM M）RR（R RS S）（T TM M）SS（T TM M）S S 即珍宝藏在花园正中地下即珍宝藏在花园正中地下1919、习题、习题2121（2 2）解：根据给定的条件有下述命题：解：根据给定的条件有下述命题：P P：现场无任何痕迹：现场无任何痕迹Q Q：失窃时，小花在：失窃时，小花在OKOK厅厅R R：失窃时，小英在：失窃时，小英在OKOK厅厅S S：失窃时，小胖在附近：失窃时，小胖在附近T T：金刚是偷窃者：金刚是偷窃者M M：瘦子是偷窃者：瘦子是偷窃者则根据案情有如下命题公式：则根据案情有如下命题公式：PP，QRQR，S S P P，Q TQ T，S S R R，R MR M29 P P P P S SP PP P S TIS TI SSR PR P R TIR TI QR P QR P Q TI Q TI QT P QT P T TI T TI即即 金刚是偷窃者金刚是偷窃者