《离散数学复习提纲(1-457章)》由会员分享，可在线阅读，更多相关《离散数学复习提纲(1-457章)（16页珍藏版）》请在金锄头文库上搜索。
1、2006 年 12 月离散数学复习提纲 1离散数学复习提纲离散数学复习提纲第一章 命题逻辑1 （PQ）（QR）的主合取范式和主析取范式。2试求下列公式的主析取范式：（1）；（2）)()(PQQPP)(RQQPP（an: )()()()(:) 1PQQPQPPPQQPP原式解QPPPQPPQP)()()()()(QPPQQP)()()(QPQPQP)()(:)2RQQPPRQQPP解)()()()(RQPRQPRQPRQPRQP）)()()(RQPRQPRQP3用真值表判断下列公式是恒真？恒假？可满足？ （1） （PP）Q （2）（PQ）Q （3） （PQ）（QR） ）（PR） (an: 解：
2、（1）真值表P QP PP （PP）Q0 01 0 10 11 0 01 00 0 11 10 0 0因此公式（1）为可满足。 ) （2）真值表P QPQ （PQ） （PQ）Q0 01 0 00 11 0 01 00 1 02006 年 12 月离散数学复习提纲 21 11 0 0因此公式（2）为恒假。 （3）真值表P Q RPQ QR PR （PQ）（QR） ）（PR）0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 1 0 11 0 1 0 1 1 11 1 0 1 0 0 11 1 1 1 1 1 1因此公式（3）为恒
3、真。4Q（PQ）蕴涵 P 法 1：真值表法 2：若Q（PQ）为真，则 Q，PQ 为真，所以 Q 为假，P 为假，所以P 为真。法 3：若P 为假，则 P 为真，再分二种情况：若 Q 为真，则Q（PQ）为假 若 Q 为假，则 PQ 为假，则Q（PQ）为假 根据 ，所以 Q（PQ）蕴涵 P。 ） 5利用基本等价式证明下列命题公式为恒真公式。 （PQ）（QR） ）（PR） （PQ）（P（QR） ） ）（PQ）（PR） （an: 1、证明： （PQ）（QR） ）（PR）=（PQ）（QR） ）（PR）=（PQ）（QR） ）（PR） =（PQ）（QR）PR =（PQ）P ）（QR）R） =（1（QP ）
4、）（QR）1）= QPQR =（QQ） P R= 1 P R = 1 （PQ）（P（QR） ） ）（PQ）（PR）=（PQ）（P（QR） ） ）（P（QR） ）=（P（Q QR） ）（P（QR） ）=（P（QR） ）（P（QR） ）=1）2006 年 12 月离散数学复习提纲 36用形式演绎法证明：蕴涵SRRQQP,SP (an: 证明： （1） 规则 P QP （2） 规则 Q （1） QP （3） 规则 P RQ（4） 规则 Q（3） RQ （5） 规则 Q（2） （4） RP （6）RS 规则 P （7）PS 规则 Q（5） （6） )7用形式演绎法证明：（蕴涵 AEFDDCBA)(),
5、()E（an: 、证明：(改()()(),()FDFDBABA为为（1）A 规则 D （2）AB 规则 Q（1）（3） 规则 P)()(DCBA（4） 规则 Q（2） （3）DC （5）D 规则 Q（4） （6） 规则 Q（5）FD（7） 规则 P EFD)(（8）E 规则 Q（6） （7）（9） 规则 Q（1） （8） ）EA 8（PQ） ，QR，R 蕴涵 P （an: （1）QR （2）R （3）Q （4）（PQ） （5）PQ （6）P） 9某案涉及甲、乙、丙、丁四个，根据已有线索，已知： （1）若甲、乙均未作案，则丙、丁也均未作案； （2）若丙、丁均未作案，则甲、乙也均未作案； （3）若
6、甲与乙同时作案，则丙与丁有一人且只有一人作案； （4）若乙与丙同时作案，则甲与丁同时作案或同未作案。 办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？ （an: 解：对问题中的四个简单命题用 P1，P2，P3，P4 分别表示甲，乙，丙，丁作案，则2006 年 12 月离散数学复习提纲 4办案人员的推理如下： 前提：1) P1P2P3P4 2) P3P4P1P2 3) P1P2(P3P4)(P3P4) 4) P3P4(P1P2)(P1P2) 结论：P1。(P1P2P3P4) (P3P4P1P2) ( P1P2(P3P4)(P3P4) ( P3P4(P1P2)(P1P2) P1 不是永
7、真式，比如： P1 取假，P2 取真，P3 取假，P4 取真时，上式为假 所以 P1 不是前提的有效结论， 所以甲是作案者的结论是错误的)课后习题： p8：1，5 p19：7 p23：6，7，8 p39：4 p47：4，5第二章 谓词逻辑1设个体域 D=1，2，5，F（x）：x2，G（x,y）：xy, 消去 （x）(F(x)（y）G(y,x) 中的量词，并讨论其真值。2所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生是很有风 度。请用谓词逻辑中的推理理论证明上述推理。 （个体域：所有人的集合）3设数，小于，将“不存在最小的数。 ”符号化。是xxM: )(xyxL: ),(y
8、（an: ）),()()()()(yxLyMxMyx4利用一阶逻辑的基本等价式，证明： （x） （y） （F（x）G（y） ）=（x）F（x）（y）G（y） (an: xy（F（x）G（y） ）=x（F（x）y G（y） ） = x（F（x）y G（y） ）= x（F（x） ）y G（y）= xF（x）y G（y） = xF（x）yG（y）)5 （x） （F(x) A(x)） ， （x） （A(x)B(x)， （x） B(x)蕴涵 （x） F(x) （an: （1）x B(x)2006 年 12 月离散数学复习提纲 5（2）B(c) （3）x（A(x)B(x)） （4）A(c)B(c) （5）
9、A(c) （6）x（F(x) A(x)） （7）F(c) A(c) （8）F(c) （9）x F(x)）6符号化下列命题并推证其结论： 没有不守信用的人是可以信赖的，有些可以信赖的人是受过教育的人，因此，有些受 过教育的人是可守信用的。 （个体域：所有人的集合） （an: 令 M(x)：x 是守信用的；J(x)：x 是受过教育的；D(x)：x 是可以信赖的 前提：x（M(x)D(x)） ， （x D(x) J(x)）有效结论：x（J(x) M(x)） 证明：1） （x D(x)J(x)）前提 2）x D(x)J(y)代替规则 3）x D(x)合取 4）D(c)EI 规则 5）J(y)合取 6）
10、zJ(z)UG 规则 7）J(c)UI 规则 8）x（M(x) D(x)）前提规则 9） x（M(x) D(x)） 等价 10） x（M(x) D(x)）等价 11）M(c) D(c)UI 规则 12）M(c)等价 13）M(c) J(c)合取 14）x（J(x) M(x)）EG 规则)7在一阶逻辑中，构造下面的证明：前提：，F(a) 结论:（an: 1)x(F(x)G(x)2) F(a)G(a) 3) F(a) 4)G(a)5) G(x)8设解释 I 为： （1）定义域 D=-2，3，6； （2）F（x）：x3； G（x）：x5。 在解释 I 下求公式(x)（F（x）G（x） ）的真值。 （
11、an: ( x)（F（x）G（x） ）2006 年 12 月离散数学复习提纲 6=（F（-2）G（-2） ）（F（3）G（3） ）（F（6）G（6） ）=（10）（10）（01）= 1）9不存在能表示成分数的无理数。有理数都能表示成分数。因此，有理数都不是无理数。 （an: F(x)：x 为无理数，G(x)：x 为有理数，H(x)：x 能表示成分数）10 设个体域为集合a, b, c, 试消去下列公式中的量词。 (1) （x） P(x)（x）Q(x) (2) （x） （ P(x) Q(x)） 课后习题： p59：1，2 p62：3，6 p65：2，3 p72：1，4 p75：1 p79：2，3第三章 集合论1设A，是偏序集，A=1，2，3，4，5，6，8，是整除关系，请画出A， 的哈斯图。写出 A 中的极大元，极小元和最大元，最小元。2设 A=1，2，3，求 A 上所有等价关系。3设全集有下列子集 A= B=,NE 10, 8 , 2 , 1,50|2NnnnC=
