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

《离散数学复习提纲(1-457章)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2006年12月离散数学复习提纲16离散数学复习提纲第一章命题逻辑1．（PQ）（QR）的主合取范式和主析取范式。2．试求下列公式的主析取范式：（1）；（2）（an:）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）ÙQ0010001100100102006年12月离散数学复习提纲1611100因此公式（2）为恒假。（1）真值

2、表PQRP®QQ®RP®R（（P®Q）Ù（Q®R））®（P®R）00011110011111010101101111111000101101011111010011111111因此公式（3）为恒真。4．┐QÙ（P→Q）蕴涵┐P（an:法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）

3、（（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））Ú（Ø

4、PÙ（ØQÚØR））=（PÚ（QÙR））ÚØ（PÚ（QÙR））=1）6．用形式演绎法证明：{}蕴涵2006年12月离散数学复习提纲16(an:证明：（1）规则P（2）规则Q（1）（3）规则P（4）规则Q（3）（5）规则Q（2）（4）（6）R®S规则P（7）P®S规则Q（5）（6）)7．用形式演绎法证明：（蕴涵A（an:、证明：(改()（1）A规则D（2）A∨B规则Q（1）（3）规则P（4）规则Q（2）（3）（5）D规则Q（4）（6）规则Q（5）（7）规则P（8）E规则Q（6）（7）（9）规则Q（1）（8））8．┐（P∧┐Q），┐Q∨R，┐R蕴涵┐P（an:（1）┐Q∨R（2

5、）┐R（3）┐Q（4）┐（P∧┐Q）（5）┐P∨Q（6）┐P）9．某案涉及甲、乙、丙、丁四个，根据已有线索，已知：（1）若甲、乙均未作案，则丙、丁也均未作案；（2）若丙、丁均未作案，则甲、乙也均未作案；（3）若甲与乙同时作案，则丙与丁有一人且只有一人作案；（4）若乙与丙同时作案，则甲与丁同时作案或同未作案。办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？（an:解：对问题中的四个简单命题用P1，P2，P3，P4分别表示甲，乙，丙，丁作案，则办案人员的推理如下：2006年12月离散数学复习提纲16前提：1)ØP1ÙØP2®ØP3ÙØP42)ØP3ÙØP4®ØP1Ù

6、Ø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≥

7、y,消去（x）(F(x)（y）G(y,x))中的量词，并讨论其真值。2．所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生是很有风度。请用谓词逻辑中的推理理论证明上述推理。（个体域：所有人的集合）3．设数，小于，将“不存在最小的数。”符号化。（an:）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）=