离散数学复习提纲(1-457章)

2006年12月离散数学复习提纲1离散数学复习提纲第一章命题逻辑1．（PQ）（QR）的主合取范式和主析取范式。2．试求下列公式的主析取范式：（1）))()((PQQPP；（2）)))((RQQPP（an:))()(())()((:)1PQQPQPPPQQPP原式解QPPPQPPQP)()()())(())((QPPQQP)()()(QPQPQP)))((()))(((:)2RQQPPRQQPP解)()()()(RQPRQPRQPRQPRQP)()()(RQPRQPRQP）3．用真值表判断下列公式是恒真？恒假？可满足？（1）（PP）Q（2）（PQ）Q（3）（（PQ）（QR））（PR）(an:解：（1）真值表PQPPP（PP）Q00101011001000111000因此公式（1）为可满足。)（2）真值表PQPQ（PQ）（PQ）Q001000110010010111002006年12月离散数学复习提纲2因此公式（2）为恒假。（3）真值表PQRPQQRPR（（PQ）（QR））（PR）00011110011111010101101111111000101101011111010011111111因此公式（3）为恒真。4．┐Q（P→Q）蕴涵┐P法1：真值表法2：若┐Q（P→Q）为真，则┐Q，P→Q为真，所以Q为假，P为假，所以┐P为真。法3：若┐P为假，则P为真，再分二种情况：①若Q为真，则┐QÙ（P→Q）为假②若Q为假，则P→Q为假，则┐Q（P→Q）为假根据①②，所以┐Q（P→Q）蕴涵┐P。）5．利用基本等价式证明下列命题公式为恒真公式。（（PQ）（QR））（PR）（（PQ）（P（QR）））（PQ）（PR）（an:1、证明：（（PQ）（QR））（PR）=（（PQ）（QR））（PR）=（（PQ）（QR））（PR）=（PQ）（QR）PR=（（PQ）P）（（QR）R）=（1（QP））（（QR）1）=QPQR=（QQ）PR=1PR=1（（PQ）（P（QR）））（PQ）（PR）=（（PQ）（P（QR）））（P（QR））=（P（QQR））（P（QR））=（P（QR））（P（QR））=1）6．用形式演绎法证明：{SRRQQP,,}蕴涵SP(an:证明：2006年12月离散数学复习提纲3（1）QP规则P（2）QP规则Q（1）（3）RQ规则P（4）RQ规则Q（3）（5）RP规则Q（2）（4）（6）RS规则P（7）PS规则Q（5）（6）)7．用形式演绎法证明：（EFDDCBA)(),()蕴涵AE（an:、证明：(改()()(),()FDFDBABA为为)（1）A规则D（2）A∨B规则Q（1）（3）)()(DCBA规则P（4）DC规则Q（2）（3）（5）D规则Q（4）（6）FD规则Q（5）（7）EFD)(规则P（8）E规则Q（6）（7）（9）EA规则Q（1）（8））8．┐（P∧┐Q），┐Q∨R，┐R蕴涵┐P（an:（1）┐Q∨R（2）┐R（3）┐Q（4）┐（P∧┐Q）（5）┐P∨Q（6）┐P）9．某案涉及甲、乙、丙、丁四个，根据已有线索，已知：（1）若甲、乙均未作案，则丙、丁也均未作案；（2）若丙、丁均未作案，则甲、乙也均未作案；（3）若甲与乙同时作案，则丙与丁有一人且只有一人作案；（4）若乙与丙同时作案，则甲与丁同时作案或同未作案。办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？（an:解：对问题中的四个简单命题用P1，P2，P3，P4分别表示甲，乙，丙，丁作案，则2006年12月离散数学复习提纲4办案人员的推理如下：前提：1)P1P2P3P42)P3P4P1P23)P1P2(P3P4)(P3P4)4)P3P4(P1P2)(P1P2)结论：P1。(P1P2P3P4)(P3P4P1P2)(P1P2(P3P4)(P3P4))(P3P4(P1P2)(P1P2))P1不是永真式，比如：P1取假，P2取真，P3取假，P4取真时，上式为假所以P1不是前提的有效结论，所以甲是作案者的结论是错误的)课后习题：p8：1，5p19：7p23：6，7，8p39：4p47：4，5第二章谓词逻辑1．设个体域D={1，2，5}，F（x）：x≤2，G（x,y）：x≥y,消去（x）(F(x)（y）G(y,x))中的量词，并讨论其真值。2．所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生是很有风度。请用谓词逻辑中的推理理论证明上述推理。（个体域：所有人的集合）3．设是xxM:)(数，xyxL:),(小于y，将“不存在最小的数。”符号化。（an:))),()()()()((yxLyMxMyx）4．利用一阶逻辑的基本等价式，证明：（x）（y）（F（x）G（y））=（x）F（x）（y）G（y）(an:xy（F（x）G（y））=x（F（x）yG（y））=x（F（x）yG（y））=x（F（x））yG（y）=xF（x）yG（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）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)），（xD(x)∧J(x)）有效结论：x（J(x)∧M(x)）证明：1）（xD(x)∧J(x)）前提2）xD(x)∧J(y)代替规则3）xD(x)合取4）D(c)EI规则5）J(y)合取6）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）：x3；G（x）：x5。在解释I下求公式(x)（F（x）G（x））的真值。（an:(x)（F（x）G（x））2006年12月离散数学复习提纲6=（F（-2）G（-2））（F（3）G（3））（F（6）G（6））=（10）（10）（01）=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，2p62：3，6p65：2，3p72：1，4p75：1p79：2，3第三章集合论1．设〈A，〉是偏序集，A={1，2，3，4，5，6，8}，是整除关系，请画出〈A，〉的哈斯图。写出A中的极大元，极小元和最大元，最小元。2．设A={1，2，3}，求A上所有等价关系。3．设全集,NE有下列子集A=}10,8,2,1{B=},50|{2NnnnC={},,6,2|{},,20,3|{NniinDNnnnni且且整除可以被求1）)(DCA2）)(CAB3）DBA)(~（an:}32,16,8,7,6,5,4,3{)(;)(};10,8,2,1{)(DBABCABDCA）4．设集合},,{},1,0{cbaBA，试求：1）A×B2）BA23）AA)(（an:)};,1(),,1(),,1(),,0(),,0(),,0{(cbacbaBA),1,1(),,0,1(),,1,0(),,0,0(),,1,1(),,0,1(),,1,0(),,0,0{(2bbbbaaaaBA)},1,1(),,0,1(),,1,0(),,0,0(cccc)}1},1,0({),1},1({),1},0({),1,(),0},1,0({),0},1({),0},0({),0,{()(AA）5．一个年级170人中，120名学生学英语，80名学生学德语，60名学生学日语，50名学生2006年12月离散数学复习提纲7既学英语又学德语，25名学生既学英语又学日语，30名学生既学德语又学日语，还有10名学生同时学习三种语言。试问：有多少名学生这三种语言都没有学习？（an:解：设E为全集，A为学英语学生的集合，B为学德语学生的集合，C为学日语学生的集合。由公式，|ABC|=|A|+|B|+|C|-|AB|-|BC|-|AC|+|ABC|可得：|ABC|=120+80+60-50-30-25+10=165所以，这三种语言都没有学习的学生为170-165=5人。）6．A={a，b，c，d}，R1，R2是A上的关系，其中R1={（a，a），（a，b），（b，a），（b，b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。（1）写出R1和R2的关系矩阵，并画出R1和R2的关系图；（2）判断它们是否为等价关系，是等价关系的求A中各元素的等价类。（an:）R1为等价关系等价类M1={a,b}，M2={c,d}R2不为等价关系7．集合},,{cbaA，R是集合A上的关系，)},(),,(),,{(cbabbaR，求)(),(),(RtRsRr，并分别画出它们的关系图。（an:)}.,(),,(),,(),,(),,(),,{()()};,(),,(),,(),,{()()};,(),,(),,(),,(),,(),,{()(cbbbcaabbaaaRtbccbabbaRscbabbaccbbaaRr它们的关系图：）8．设集合}24,12,8,6,4,3,2{A，R为A上的整除关系，（1）画出偏序集（A，R）的2006年12月离散数学复习提纲8哈斯图；（2）写出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集}12,6,3,2{B的上界、下界、最小上界、最大下界。（an:（1）半序集（A，R）的哈斯图如下所示：（2）集合A中的最大元是24，无最小元，极大元是24，极小元是2与3。（3）集合B的上界是12与24，无下界，最小上界是12，无最大下界。）9．设集合AIedecebeadacabaRedcbaA)},(),,(),,(),,(),,(),,(),,{(},,,,,{