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

离散数学复习提纲命题逻辑1．（PQ）（QR）的主合取范式和主析取范式。2．试求下列公式的主析取范式：（1）；（2）（an:）3．用真值表判断下列公式是恒真？恒假？可满足？（1）（PP）Q（2）（PQ）Q（3）（（PQ）（QR））（PR）(an:解：真值表PQPPP（PP）Q00101011001000111000因此公式（1）为可满足。)真值表PQPQ（PQ）（PQ）Q00100011001001011100因此公式（2）为恒假。真值表PQRPQQRPR（（PQ）（QR））（PR）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．利用基本等价式证明下列命题公式为恒真公式。（（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））（（QR）1）=QPQR=（QQ）PR=1PR=1（（PQ）（P（QR）））（PQ）（PR）=（（PQ）（P（QR）））（P（QR））=（P（QQR））（P（QR））=（P（QR））（P（QR））=1）6．用形式演绎法证明：{}蕴涵(an:证明：（1）规则P（2）规则Q（1）（3）规则P（4）规则Q（3）（5）规则Q（2）（4）（6）RS规则P（7）PS规则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）┐R （3）┐Q （4）┐（P∧┐Q） （5）┐P∨Q （6）┐P）9．某案涉及甲、乙、丙、丁四个，根据已有线索，已知：若甲、乙均未作案，则丙、丁也均未作案；若丙、丁均未作案，则甲、乙也均未作案；若甲与乙同时作案，则丙与丁有一人且只有一人作案；若乙与丙同时作案，则甲与丁同时作案或同未作案。办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？（an:解：对问题中的四个简单命题用P1，P2，P3，P4分别表示甲，乙，丙，丁作案，则办案人员的推理如下：前提：1)P1P2P3P42)P3P4P1P23)P1P2(P3P4)(P3P4)4)P3P4(P1P2)(P1P2)结论：P1。(P1P2P3P4)(P3P4P1P2)(P1P2(P3P4)(P3P4))(P3P4(P1P2)(P1P2))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．设数，小于，将“不存在最小的数。”符号化。（an:）4．利用一阶逻辑的基本等价式，证明：（x）（y）（F（x）G（y））=（x）F（x）（y）G（y）(an:xy（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) （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为：定义域D={-2，3，6}；F（x）：x3；G（x）：x5。在解释I下求公式(x)（F（x）G（x））的真值。（an:(x)（F（x）G（x））=（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},试消去下列公式中的量词。（x）P(x)∧（x）Q(x)（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．设全集有下列子集A=B=C={求1）2）3）（an:）4．设集合，试求：1）A×B2）3）（an:）5．一个年级170人中，120名学生学英语，80名学生学德语，60名学生学日语，50名学生既学英语又学德语，25名学生既学英语又学日语，30名学生既学德语又学日语，还有10名学生同时学习三种语言。试问：有多少名学生这三种语言都没有学习？（an:解：设E为全集，A为学英语学生的集合，B为学德语学生的集合，C为学日语学生的集合。由公式，|ABC|=|A|+|B|+|C|-|AB|-|BC|-|AC|+|ABC|可得：|ABC|=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）}。写出R1和R2的关系矩阵，并画出R1和R2的关系图；判断它们是否为等价关系，是等价关系的求A中各元素的等价类。（an:）R1为等价关系等价类M1={a,b}，M2={c,d}R2不为等价关系7．集合，R是集合A上的关系，，求，并分别画出它们的关系图。（an:它们的关系图：）8．设集合，R为A上的整除关系，（1）画出偏序集（A，R）的哈斯图；（2）写出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集的上界、下界、最小上界、最大下界。（an:（1）半序集（A，R）的哈斯图如下所示：2412623（2）集合A中的最大元是24，无最小元，极大元是24，极小元是2与3。（3）集合B的上界是12与24，无下界，最小上界是12，无最大下界。）9．设集合，试画出偏序集的哈斯图，并写出A的最大元，最小元，极大元和极小元。（an:（A，）的哈斯图为：ebcdaa为A的极小元，也是最小元；e为A的极大元，也是最大元。）11．设R是集合A上的二元关系，证明：R是传递的，当且仅当t（R）=R。（an:证明：若R是传递的，又有RR，对于任何包含R的传递关系，都有，所以R满足传递闭包定义中的全部条件，即t（R）=R。反之，若t(R)=R，由传递闭包含定义中的条件1可得R是传递的。）12．设集合上的关系则R在A上构成的等价类是？（an:）13．设集合A=，为A上的二元关系，则是？（an:{（1，1），（1，2），（1，3），（2，1），（2，2），（2，3），（3，1），（3，2），（3，3）}）14．设R是一个二元关系，设S={<a,b>|存在某个C，使<a,c>∈R且<c,b>∈R}，证明R是一个等价关系，则S也是一个等价关系。（an:1、证明：

（1）∵R是自反，

∴若有x∈A就有＜x，x＞∈R

∴＜x，x＞∈S

∴S是自反的。

（2）因有＜a，b＞∈S

且存在c，使＜a，c＞∈R且＜c，b＞∈R

∵R是对称的

∴＜c，a