离散数学习题集

离散数学课外习题集编者：金鹏时间：2008-5-6推荐精选目录：推荐精选第一章一、 选择题1. 由n个命题变元组成不等值的命题公式的个数为（）A.2nB.2nC.n2D.2. 设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）A.PQB.QPC.P QD.QP3. 下列各组公式中，哪组是互为对偶的？（）A.P,PB.P, PC.A,(A*)*D.A,A（其中P为单独的命题变元，A为含有联结词的命题变元）4. 设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）A. pQB. PQC. (PQ)D.PQ5. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）A. 2是偶数或-3不是负数C. 2是奇数或-3不是负数C2不是偶数且-3不是负数D. 2是奇数且-3不是负数6. 设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件事”符号化为（）A.PQB.PQC.PQD. (PQ)7. 下列语句中哪个是真命题？（）A.我正在说谎。B.严禁吸烟。C.如果1+2=3，那么雪是黑的。D.如果1+2=5，那么雪是黑的。8. 下面哪个联结词运算不可交换？（）A.B.C.D.9. 命题公式(P (PQ) Q是（）。A.矛盾式B.蕴含式C.重言式D.等值式10. 下面哪个命题公式是重言式？（）A.(PQ)(Q P)B.(PQ)PC.(PQ)(PQ)D.(PQ)11. 下列哪一组命题公式是等值的？（）A. PQ,PQB.A(BA),A(AB)C.Q(PQ),Q (PQ)D.A (AB),B12. PQ的逆反式是（）A.QPB. P QC. QPD. QP13. PQ的逆反式是（）A.QPB. P QC. QPD.P Q 14. 下列命题联结词集合中，哪一个是最小联结词组？（）A.,B.,C.D.,15. 下列联结词集合中，哪一个不是最小联结词组？（）A.,B.,C.,D.16. 已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（）A.充分条件B.必要条件C.充要条件D.A、B、C都不对17. P Q的反换式是（）A.QPB.PQC.QPD.PQ18. 下面哪一个命题公式是重言式？（）推荐精选A.P(QR)B.(PR)(PQ)C.(PQ) (QR)D.(P(QR) (PQ) (PR)19. 下列哪个命题公式不是重言式？（）A.Q(PQ)B.(PQ)PC.(PQ) (PQ)D.(PQ)(PQ)20. 重言式的否定式是（）A.重言式B.矛盾式C.可满足式D.蕴含式21.下面哪一个命题是假命题？（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一22.下面哪一组命题公式不是等值的？（）A.(AB),ABB.(AB),(AB)(AB)C.A(BC),A(BC)D. A(BC),(AB)C23. 命题公式PQR的对偶式为（）A.P(QR)B. P (QR)C.P (QR)D.P (QR)24. 命题公式P(QR)是（）A.重言式B.可满足式C.矛盾式D.等值式25. PQ（）A.P (PQ)B.(PQ) (QP)C.(PQ)(QP)D.(PQ)(QP)26. 命题公式(PQ)R的主析取范式中含极小项的个数为（）A.8B.3C.5D.027. 命题公式(PQ)R的主析取范式中含极大项的个数为（）A.0B.3C.5D.828. 命题公式(PQ)R的成真赋值为（）A.000,001,110B.001,011,101,110,111C.全体赋值D.无29. 如果AB成立，则以下各种蕴含关系哪一个成立？（）A.BAB.ABC.BAD.AB二、 填空题1. 下列句子中，是命题的有 (1).我是教师。(2).禁止吸烟！(3).蚊子是鸟类动物。(4).上课去！(5).月亮比地球大。2. 设P：我生病，Q：我去学校(1).命题“我虽然生病但我仍去学校”符号化为 。(2).命题“只有在生病的时候，我才不去学校”符号化为 。(3).命题“如果我生病，那么我不去学校”符号化为 。3. 设P：我有钱，Q：我去看电影。(1).命题“如果我有钱，那么我就去看电影”符号化为 。(2).命题“虽然我有钱，但我不去看电影”符号化为 。(3).命题“当且仅当我有钱时，我才去看电影”符号化为 。4.对于下列各式，是永真式的有 。(1).(P(PQ)Q推荐精选(2).P(PQ)(3).Q(PQ)(4).(P(PQ)Q(5).(PQ) Q5.(P(PQ) R 。6.P(PQ) 。7. 对于下列各式(1).(PQ)(PQ)可化简为 。(2).Q(P(PQ) 可化简为 。(3).(PQ)(QP)P可化简为 。8.命题公式P(QR)的成真赋值为 ，成假赋值为 。9.若 且 则称X是公式A的子公式。10. 写出表中各列所定义的命题联结词。PQP QP Q111010010101000111.由n个命题变元可组成 个不等值的命题公式。12.用两种形式写出PQ的对偶式 ， 。13.两个重言式的析取是 ，一个重言式与一个矛盾式的析取是 。14.A、B为两个命题公式，AB当且仅当 ，AB当且仅当 。15.设P、Q为两个命题公式，德摩根律可表示为 ，吸收率可表示为 。16.设命题公式A中仅含有联结词，若 得到公式A*，则A*称为A的对偶式。17.公式(PQ) R的只含联结词，的等值式为 ，它的对偶式为 。18.命题公式A(PQR)0，则其对偶式A* 。19.在命题演算中，一个蕴含式与它的 式是等值的，它的 式与它的 是不等值的。20.公式PQ的反换式为 ，逆反式为 。21.任意两个不同极小项的合取为 式，全体极小项的析取式必为 。22.命题公式(PQ)的主析取范式为 ，主合取范式的编码表示为 。23.已知公式A(P,Q,R)的主合取范式为M0M3M5，它的主析取范式为（写成编码形式） 。24.命题公式(PQ)的主析取范式为 ，其编码表示为 ，主合取范式的编码表示为 。25.对于前提：SQ，SR，R, PQ，其有效结论为 。26.对于前提：(PQ) R，RS, S，其有效结论为 。三、 判断题1. “王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（）2. 凡陈述句都是命题。（）3. 语句3x+5y=0是一个命题。（）4. 命题“两个角相等当且仅当它们是对顶角“的值为1。（）5. 语句“x+y=4”是个命题。（）推荐精选6. 命题“十减四等于五”是一个原子命题。（）7. 命题“如果1+2=3，那么雪是黑的”是真命题。（）8. (P(QR)是一个命题演算的命题公式，其中P、Q、R是命题变元。（）9. (P(QRQ)是一个命题公式，其中P、Q、R是命题变元。（）10. 若A：张明和李红都是三好学生，则A：张明和李红都不是三好学生。（）11. 若A：张明和李红都是运动员，则A：张明和李红不都是运动员。（）12. 若P：每一个自然数都是偶数，则P：每一个自然数都不是偶数。（）13. 若P：每个自然数都是偶数，则P：每个自然数不都是偶数。（）14. 如果AB，则ACBC，ACBC。（）15. 如果ACBC，则AB。（）16. 联结词“”是可结合的。（）17. 联结词“”是可结合的。（）18. 联结词“”是可交换的。（）19. 联结词“”是可交换的。（）20. 联结词“”是满足交换律。（）21. “学习有如逆水行舟，不进则退”。设P：学习如逆水行舟，Q：学习进步，R：学习退步。则命题符号化为P(QR)。（）22. P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：P (QR)。（）23. 设P、Q是两个命题，当且仅当P、Q的真值均为1时，PQ的值为1。（）24. 命题公式(P(PQ)Q是矛盾式。（）25. 命题公式(P(PQ)Q是重言式。（）26. 联结词与不是相互可分配的。（）27. 在命题的演算中，每个最小联结词组至少有两个联结词。（）28. 命题联结词集,是最小联结词集。（）29. 命题联结词集,是最小联结词集。（）30. 命题联结词集,是最小联结词集。（）31. 命题联结词集和是最小联结词集。（）32. A是命题公式，A与(A*)*互为对偶式。（）33. A是命题公式，A(A*)*。（）34. P是命题变元，P与P互为对偶式。（）35. 任一命题公式的主析取范式和它的主合取范式互为对偶式。（）36. 任一命题公式都可以表示成与其等值的若干极小项的析取式。（）四、 综合题1. 使用命题：P：这个材料有趣。Q：这些习题很难。R：这门课程让人喜欢。将下列句子用符号形式写出：(1). 这个材料有趣，并且这些习题很难。(2). 这个材料无趣，习题也不难，而且这门课程也不让人喜欢。(3). 如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。(4). 这个材料有趣，意味着这些习题很难，并且反之亦然。(5). 或者这个材料有趣，或者这些习题很难，并且两者恰具其一。2. 用符号形式写出下列命题：(1).假如上午不下雨，我去看电影，否则就在家里读书或者看报；(2).我今天进城，除非下雨；(3).仅当你走，我将留下；(4).一个数是素数当且仅当它只能被1和它自身整除。3. 判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。推荐精选(1).是无理数。(2).5能被2整除。(3).现在开会吗？(4).x+50。(5).这朵花真好看呀！(6).2是素数当且仅当三角形有三条边。(7).雪是黑色的当且仅当太阳从东方升起。(8).2000年10月1日天气晴好。(9).太阳系以外的星球上有生物。(10).小李在宿舍。(11).全体起立！(12).4是2的倍数或是3的倍数。(13).4是偶数且是奇数。(14).李明与王华是同学。(15).蓝色和黄色可以调配成绿色。4. 确定下列命题的真值：(1).“如果太阳从西边出来，那么地球自转”；(2).“如果太阳从东边出来，那么地球自转停止”；(3).“如果8+930，那么三角形有三条边”；(4).“如果疑问句是命题，那么地球将停止转动”。5. 判断下面语句是否是命题，若是，确定其真值：(1).喜马拉雅山比华山高；(2).如果时间静止不动，你就可以长生不老；(3).如果时间流失不止，你就可以长生不老；(4).伦敦是英国首都；(5).这盆茉莉花好香阿！6. 给命题变元P、Q、R、S分别指派真值为1、1、0、0，求下列命题公式的真值：(1).(PQ)R)(PQ)R)S)(2).(P(Q(RP)(QS)7. 设A*、B*分别是命题公式A和B的对偶式，判断下列各式是否成立，若不成立，请举例说明：(1).A*A(2).AB则A*B*(3).AB则A*B*(4).(A*)*A8. 命题联结词“”定义为PQ(PQ)(1).构造PQ的真值表；(2).证明、可以用仅含联结词的等值公式表示。9. 化简下列命题公式：(1).A(A(BB)(2).(ABC)(ABC)(3).(PQ)(QP)R(4).(AB)(BA)C10. 如果有ACBC，是否一定有AB?11. 如果有ACBC，是否一定有AB?12. 如果AB是否有AB？13. 用真值表判断下列各式是否为重言式：(1).(PQ)(QR)(PR)(2).(PQR)(PRQ)14. 设命题公式A的真值表如表所示，试求出A的主析取范式和主合取范式（用编码表示和公式表示）：推荐精选PQA11110101000115. 用等值演算法证明P(PQ) Q是重言式。16. 证明下列命题的等值关系：(1).(PQ)(RQ)(PR)Q(2).(PQAC)(APQC)(A(PQ)C(3).P(QP)Q(PR)(4).(PQ)(PR)P(QR)(5).(PQ)(PQ)(PQ)17. 求证下面命题的蕴含关系：(1).PQPQ(2).(P(QR)(PQ)(PR)18. 求下面各式的主析取范式与主合取范式，并写出相应的为真赋值。(1).(PQ)(PQ)(2).(R(QP)(PQR)(3).(PQ)Q)(QP)P)(4).(P(QR)(R(QP)(5).(PQ)(RP)(RQ)P19. 联结词f1，f2由表所示真值表定义，证明 f1，f2是最小联结词组。PQf1PP f1Q110110010110001120.设计一种简单的表决器，表决者每人座位旁边有一按钮，若同意则按下按钮，否则不按按钮，当表决结果超过半数时，会场电铃就会响，否则铃不响。试以表决人数为3人的情况设计表决器电路的逻辑关系。21. 证明时最小联结词组。22. 设计一加法器，实现两自然数相加的功能。23. 某勘探队有3名队员。有一天取得一块矿样，3人的判断如下：甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，时铁。经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。24. 观察下列推理过程，是否正确，结论是否有效，说明理由。(1).PQRP(2).PRTI(3).PP(4).RTI所以PQR，PR。25. 下列证明过程是否正确，若正确补足每一步推理依据，否则指出错误。(1).DA(2).D(3).A推荐精选(4).A(CB)(5).CB(6).C(7).B(8).DB26. 证明A(BC)，B(CD)A(BD)。27.用CP规则证明P(QR)，Q(RS)，PQS。28. 用推理规则说明AB,(BC)，AC是否能同时为真。29. 用推理规则说明(PQ)R，SU，RS，UW，WPQ。30. 用推理规则证明下列推理的正确性：如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。31. 用等值演算法证明P(PQ)是矛盾式。32. 用CP规则证明A(BC)，(EF)C，B(AS)BE。33. 用反证法证明(AB)(CD)，(BE)(DF)，(EF)，ACA。34. 用反证法证明AB，(BC)C，(AD)D。推荐精选第二章一、 选择题1. 谓词公式x(P(x)$yR(y)Q(x)中量词x的作用域是（）A. x(P(x)$yR(y)B.P(x)C. (P(x)$yR(y)D.P(x)，Q(x)2. 谓词公式x(P(x)$yR(y)Q(x)中变元x是（）A.自由变量B.约束变量C.既不是自由变量也不是约束变量D.既是自由变量也是约束变量3. 若个体域为整体域，下列公式中哪个值为真？（）A.x$y(x+y=0)B.$yx(x+y=0)C.xy(x+y=0)D.$x$y(x+y=0)4. 设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式$x(P(x)Q(x)在下面哪个论域中是可满足的？（）A.自然数集B.整数集C.实数集D.以上均不成立5. 设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可符号化为（）A.x(C(x)G(x)B.x(C(x)G(x)C.$x(C(x)G(x)D.$x(C(x)G(x)6. 设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为（）A.x(A(x)B(x)B.$x(A(x)B(x)C.$x(A(x)B(x)D.$x(A(x)B(x)7. 设Z(x)：x是整数，N(x)：x是负数，S(x,y)：y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式（）A.xy(Z(x)S(x,y)N(y)B.x$y(Z(x)S(x,y)N(y)C.xy(Z(x)S(x,y)N(y)D.x(Z(x)S(x,y)N(y)8. 令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有的火车慢”可表示为（）A.$y(G(y)x(F(x)H(x,y)B.$y(G(y)x(F(x)H(x,y)C.x$y(G(y)(F(x)H(x,y)D.$y(G(y)x(F(x)H(x,y)9. 设个体域A=a,b，公式xP(x)$xS(x)在A中消去量词后应为（）A.P(x)S(x)B.P(a)P(b)(S(a)S(b)C.P(a)S(b)推荐精选D.P(a)P(b)S(a)S(b)10. 在谓词演算中，下列各式哪个是正确的？（）A.$xyA(x,y)y$xA(x,y)B.$x$yA(x,y)$y$xA(x,y)C.$xyA(x,y)x$yA(x,y)D.xyA(x,y)yxA(x,y)11. 下列各式哪个不正确？（）A.x(P(x)Q(x)xP(x)xQ(x)B.x(P(x)Q(x)xP(x)xQ(x)C.$x(P(x)Q(x)$xP(x)$xQ(x)D.xP(x)Q)xP(x)Q12. 下面谓词公式哪个是前束范式？（）A.xy$z(B(x,y)A(z)B.x$yB(x,y)C.$xyx(A(x,y)B(x,y)D.x(A(x,y)$yB(y)13. 在谓词演算中：P(a)是xP(x)的有效结论，其理论根据是（）A.全称规定规则(US)B.全称推广规则(UG)C.存在规定规则(ES)D.存在推广规则(EG)二、 填空题1. 令R(x)：x是实数，Q(x)：x是有理数。(1) 命题“并非每个实数都是有理数”。其符号化为 。(2) 命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可表示为 。2.设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。3.设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有智能工作都能由计算机来做”符号化为 。4. 设Q(x)：x是偶数，P(x)：x是素数，则命题“存在惟一一个偶素数”可符号化为 ，“至多存在一个偶素数”可符号化为 。5.设Q(x)：x是奇数，Z(x)：x是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为 。6.设个体域为自然数集，P(x)：x是奇数，Q(x)：x是偶数，则命题“不存在既是奇数又是偶数的自然数”可符号化为 。7.设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数担不是整数”符号化分别为 ， ， 。8.xy(P(x,y)Q(y,z)$xP(x,y)中x的作用域为 ，y的作用域为 ，$x的作用域为 。9. 公式x(P(x)Q(x,y)$R(y,z)S(x)中自由变量为 ，约束变量为 。10. 取个体域为整数集，给定下列公式：(1).x$y(xy=0)(2).x$y(xy=1)(3)$x$y(xy=2)(4)xy$z(x-y=z)(5).x-y=-y+x(5).xy(xy=y)(7)x(xy=x)(8).$xy(x+y=2y)上面公式中，真命题的有 ，假命题的有 。*11.下列谓词公式(1).($xA(x)与xA(x)推荐精选(2).x(A(x)B(x)与xA(x)xB(x)(3).x(A(x)B(x)与xA(x)xB(x)(4).$xyD(x,y)与y$xD(x,y)中 是等值的。12. 对公式x(P(x)Q(x)，其中P(x):x=1，Q(x):x=2，当论域为1,2时，其真值为 ，当论域为0,1,2时，其真值为 。13.设个体域为A=a,b,c，消去公式xP(x)$xQ(x)中的量词，可得 。14. 下列各式(1).x(P(x)Q(x)(xP(x)$xQ(x)(2).(x(A(x)B(x)A(c)A(c)(3).(x(A(x)B(x)xB(x)$xA(x)(4).($x(P(x)Q(x)$xP(x)Q(x)其中 是永真式。15. 下列各式(1).$yxA(x,y)(2).$xyA(x,y)(3).x$y A(x,y)(4).$x$yA(x,y)它们之间存在着 的推理关系。可供选择的项有：A.(1)(2)；(2) (3)B.(2) (1)；(3) (4)C.(1) (3)；(4) (3)D.(4) (1)；(1) (3)E.(1) (3)；(2) (4)16.填上联结词：xP(x)xQ(x) x(P(x)Q(x)*17.只用联结词，表示以下的公式。(1).$x(P(x)Q(x)= ；(2).$x(P(x)yQ(y)= ；(3).y(xP(x)Q(y)= 。18. 给定下面谓词公式：(1).x(F(x)F(x)(2).xF(x)$xF(x)(3).(F(x)(yG(x,y)F(x)(4).x$yF(x,y)$xyF(x,y)(5).xF(x)$xF(x)(6).x(F(x)G(x)(xF(x)xG(x)(7).$x$yF(x,y)xyF(x,y)(8).x(F(x)G(x)(xF(x)xG(x)(9).(xF(x)xG(x)x(F(x)G(x)(10).xyF(x,y)yxF(x,y)(11).(xF(x)yG(y)yG(y)上面11个公式中，为重言式的有 ，为矛盾式的有 。19. 给定下列各公式：(1).($xF(x)yG(y)(F(u)zH(z)(2).$xF(y,x)yG(y)(3).x(F(x,y)yG(x,y)则 是(1)的前束范式， 是(2)的前束范式， 是(3)的前束范式。供选择的答案有$xyz(F(x)G(y)(F(u)H(z)xyz(F(x)G(y)(F(u)H(z)$xy(F(y,x)G(y)xy(F(z,x)G(y)xy(F(z,x)G(y)推荐精选x$y(F(x,z)G(x,y)xy(F(x,z)G(x,y)yx(F(x,z)G(x,y)yx(F(x,z)G(y)20.谓词公式xP(x)xQ(x)$yR(y)的前束范式为 。21.谓词公式x(P(x)Q(x,y)$zR(y,z)S(x)的前束范式为 。*22.谓词公式$x(yG(y,b)H(x)的前束范式为 。23. 在谓词逻辑中给出四个推理：(1).前提：x(F(x)G(x)，$yF(y)；结论：$yG(y)(2).前提：$x(F(x)G(x)；结论：yF(y)(3).前提：$xF(x)，$xG(x)；结论：$y(F(y)G(y)(4).前提：x(F(x)H(x)，H(y)；结论：x(F(x)以上四个推理中正确的有 。24. 在谓词逻辑中构造下面推理的证明：每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。命题符号化：F(x)：x喜欢步行；G(x)：x喜欢坐汽车；H(x)：x喜欢骑自行车。前提：x(F(x)G(x)，x(G(x)H(x)，$x(H(x)；结论：$x(F(x)。三、 判断题1.在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（）2.公式x(P(x)Q(x)R(y)中x的作用域为P(x)。（）3.同一谓词公式，指定不同的论域，其真值不一定相同。（）4.谓词公式xP(x)$y(P(y)是矛盾式。（）*5.x(P(x)Q(x)($xP(x)$xQ(x)为真。（）6.对公式$z(P(z)Q(x,z)M(z,y)R(z)中自由变量代入后，有$z(P(z)Q(a,z)M(z,b)R(z)（）7.xy(P(x)Q(y)$xP(x)yQ(y)（）*8.P(x)，Q(x)表示谓词，P表示命题，有x(P(x)P)$xP(x)P（）*9.x(A(x)B(x)xA(x)xB(x)（）*10.x(A(x)B(x)$xA(x)$xB(x)（）11.任意一个谓词公式都与一个前束范式等价。（）12.公式xP(x)$yQ(x,y)前束范式xy(P(x)Q(x,y)为（）13.公式$x($yP(x,y)($zQ(z)R(x)的前束范式为$x$y$z(P(x,y)Q(z)R(x)（）14. 下面的推理：条件：x(P(x)Q(x)，根据全称规定（US）有：P(a)Q(b)是正确的。（）15. 对公式$z(P(z)Q(x,z)M(z,y)R(z)中约束变量z改名后，得到的等价公式为：$t(P9t)Q(x,t)M(t,y)R(t)（）四、 综合题1. 用谓词和量词将下列命题符号化：(1).没有不犯错误的人；(2).尽管有人聪明，但未必一切人都很聪明；(3).每个计算机系的学生都学离散数学；(4).所有的人都学习和工作；(5).并非一切推理都能用计算机完成；(6).任何自然数都有惟一的一个后继数。*2.令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，L(x,y)表示“xy”，其中个体域为自然数集，用以上符号表示下列命题：推荐精选(1).没有x0当且仅当有这样的y，使得xy。(2).并非对一切x，都存在y，使得xy。(3).对任意的x，若x+y=x，当且仅当y=0。3.用谓词公式表示命题“”，并写出该命题的否定命题。*4.设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化：(1).并不是外语学的好的都是三好学生。(2).有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。5. 指出下列公式中量词每次出现的作用域，并指出个体变量是约束变量还是自由变量。(1).xy(R(x,y)L(y,z)$xH(x,y)(2).x(P(x)$xQ(x)(xP(x)Q(x)6. 设f,g,h是二元运算符号，E，L是二元谓词符号，考查的个体域为有理数集。给出解释如下：f(x,y)=xy；g(x,y)=x+y；h(x,y)=x2-y2；a=0；b=1；E(x,y):x=y；L(x,y):x1”；A(x)表示“x1”；B(x)表示“x是某个自然数的平方”。请在此基础上，求下面公式的真值：x(A(x)(A(a)B(x)(PxA(x)B(a)9. 下列各式翻译成自然语言，然后在不同的个体域中确定它们的真值：(1).x$y(xy=0)(2).$xy(xy=0)(3).x$y(xy=1)(4).$xy(xy=1)(5).x$y(xy=x)(6).$xy(xy=x)(7).xy$z(x-y=z)个体域分别为：实数集整数集正整数集非负实数集10. 设解释T如下：个体域为实数集R，元素a=0，函数f(x,y)=x-y，特定谓词F(x,y)为xy。根据解释T，下列哪些公式为真？哪些为假？(1).xF(f(a,x),a)(2).xy(F(f(x,y),x)(3).xyz(F(x,y)F(f(x,z),f(y,z)(4).x$yF(x,f(f(x,y),y)推荐精选11. 求下面谓词公式$x(X(x)y(X(y)(Y(x,z)Y(y,z)p)t(X(t)(Y(x,t)Y(y,t)在赋值(z;p;X(x);Y(x,y)=(2;1;x是自然数;x5，R(x)：x7。根据解释T，求下列各式的真值：(1).x(F(x)G(x)(2).x(R(x)F(x)G(5)(3).$x(F(x)G(x)13. 设A(x)是一个含有个体变量x的谓词公式，证明下面等值式成立：xA(x)$x(A(x)14. 设A(x)，B(x)均为含有自由变量x的任意谓词公式，证明：x(A(x)B(x)xA(x)xB(x)15.证明：xy(G(x)H(y)xG(x)xH(x)。16.设G(x)，H(x)分别是谓词公式，试证明xG(x)$xH(x)$x(G(x)H(x)17.下列公式是否成立，成立则证明，不成立，则举例说明之。(1).x$yA(x,y)$x$yA(x,y)(2).$xA(x)$xB(x)$x(A(x)B(x)18.下面公式是否是永真式？说明理由。(1).(A$xB(x)$x(AB(x)(2).$x(A(x)B(x)(xA(x)$xB(x)19.下面的公式是否是永真式？是则证明之，不是，请举出反例：(1).$xyA(x,y)y$xA(x,y)(2).($xA(x)$xB(x)$x(A(x)B(x)20.下面公式是否有效，对有效的公式加以证明，对无效的公式加以反驳。(1).x(P(x)Q(x)(xP(x)xQ(x)(2).(xP(x)xQ(x)x(P(x)Q(x)21.航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明：这个人一定不是航海家。22指出下列推理中的错误：(1).xF(x)G(x)前提引入F(y)G(y)US(2). x(F(x)G(x)前提引入F(a)G(b)US(3). F(x)G(x)前提引入$y(F(y)G(y)EG(4). F(x)G(c)前提引入$x(F(x)G(x)EG(5). F(a)G(b)前提引入$x(F(x)G(x)EG(6). $x(F(x)G(x)前提引入$y(H(y)R(y)前提引入F(c)G(c)ESF(c)化简H(c)R(c)ESH(c)化简F(c)H(c)合取$x(F(x)H(x)EG23.试找出下列推理过程中的错误，写出正确的推导过程，说明理由：x(P(x)Q(x)条件P(y)Q(y)全称规定(US)$xP(x)条件推荐精选P(y)存在规定(ES)Q(y)由条件$xQ(x)存在推广(EG)24.下面推理是否是一个有效的推理，为什么？x$yQ(x,y)条件$yQ(a,y)全称规定(US)Q(a,b)存在规定(ES)xQ(x,b)全称推广(UG)$yxQ(x,y)存在推广(EG)25.下面推广是否正确，若有错，请指出：x(A(x)B(x)x(A(x)B(x)X(A(x)B(x)$x(A(x)B(x)($xA(x)$xB(x)$xA(x)$x(B(x)$xA(x)xB(x)$xA(x)xB(x)26.用谓词演算推理规则证明：x(P(x)(Q(y)R(x)，xP(x)Q(y)$x(P(x)R(x)27改正下面证明中的错误：前提：x($y(S(x,y)M(y)$z(P(z)R(x,z)；结论：$zP(z)xy(S(x,y)M(y)。证明过程：x($y(S(x,y)M(y)$z(P(z)R(x,z)；P$y(S(b,y)M(y)$z(P(z)R(b,z)US$zP(z)P(附加前提)z(P(z)T,EP(a)USP(a)R(b,a)T,Iz(P(z)R(b,z)UG$z(P(z)R(b,z)T,E$y(S(b,y)M(y),T,Ly(S(b,y)M(y)T,Ey(S(b,y)M(y)T,Exy(S(x,y)M(y)UG$zP(z)xy(S(x,y)M(y)CP推荐精选第三章一、 选择题1. 对任意集合A、B、C，下述论断正确的是（）A.若AB，BC，则ACB.若AB，BC，则ACC.若AB，BC，则ACD.若AB，BC，则AC2. 设A-B=，则有（）A.B=B.BC.ABD.AB3. 设P=x|(x+1)24，Q=x|x2+165x，则下列选项正确的是（）A.PQB.PQC.QPD.Q=P4. 设A=1,2,3,4,5,6,7,8，下列选项正确的是（）A.1AB.1,2,3AC.4,5AD.A5. 下列个选项错误的是（）A.B.C.D.6. 设A=x|x3-x=0，B=x|x2-40,xZ，C=x|y=2x-1，D=x|x+y=5,xy=6，则有（）A.A=BB.A=CC.C=DD.C=A7.在0 之间填上正确的符号。A.=B.C.D.8. 设M=x|f1(x)=0，N=x|f2(x)=0，则方程f1(x)f2(x)=0的解为（）A.MNB.MNC.MND.M-N9. 设A=a,a，下列选项错误的是（）A.aP(A)B.aP(A)C.aP(A)D.aP(A)10. 设A=，B=P(P(A)，下列选项错误的是（）A.BB.BC.BD.,P(A)11. 幂集P(P(P()为（）A.,B.,C.,D.,*12.空集的幂集P()的基数是（）推荐精选A.0B.1C.3D.413.集合A=1,2,10上的关系R=|x+y=10,xA,yA，则R的性质为（）A.自反的B.对称的C.传递的，对称的D.反自反的，传递的14.设A=a,b,c上的关系如下，有传递性的有（）A.1=,B.2=,C.3=,D.4=15.设R和S是集合A上的任意关系，则下列命题为真的是（）A.若R和S是自反的，则RS也是自反的B.若R和S是反自反的，则RS也是反自反的C.若R和S是对称的，则RS也是对称的D.若R和S是传递的，则RS也是传递的16.若R和S是集合A上的两个关系，则下述结论正确的是（）A.若R和S是自反的，则RS也是自反的B.若R和S是对称的，则RS也是对称的C.若R和S是反对称的，则RS也是反对称的D.若R和S是传递的，则RS也是传递的17.设A=1,2,3,4,5，=|ij,i,jA，则的性质是（）A.对称的B.自反的C.反对称的D.反自反、反对称、传递的18.设集合A=a,b,c，R是A上的二元关系，R=,，那么R是（）A.反自反的B.反对称的C.可传递的D.不可传递的19.设R和S是集合A上的等价关系，则RS的对称性（）A.一定成立B.一定不成立C.不一定成立D.不可能成立20.设R和S是非空集合A上的等价关系，下述各式是等价关系的为（）A.(AA)-RB.R2C.R-SD.r(R-S)21.集合A上的关系R是相容关系的必要条件是（）A.自反、反对称的B.反自反、对称的C.传递、自反的D.自反、对称的22.设R是集合A上的偏序关系，是R的逆关系，则R是（）A.偏序关系B.等价关系C.相容关系D.都不是23.设集合A中有4个元素，则A上的不同的等价关系的个数为（）A.11个B.14个C.15个D.17个二、 填空题1.设M=1x12，x被2整除，xZ，N=x|1x12，x被3整除，xZ，则MN= ，MN 。2. 设全集U=1,2,7的子集为A=偶数，B=奇数，C=3的倍数，则AB= ，= ，= ,BC= 。3. 设集合A=x|3，xZ，B=x|x=2k，kZ，C=1,2,3,4,5。(1).AC= (2).(AB)C= (3).BB= (4).A(C-B)= 4. 设I为整数集合，A=x|x230，xI，B=x|x是素数，x20，C=1,3,5。(1).(AB)C= 推荐精选(2).(B-A)C= (3).(C-A)(B-A)= (4).(BC)-A= 5. 设全集U=1,2,3,