离散数学习题集.doc

离散数学课外习题集编者：金鹏时间：2008-5-6目录：第一章一、 选择题1. 由n个命题变元组成不等值的命题公式的个数为（）A.2n B.2n C.n2 D.2. 设P：我将去镇上，Q：我有时间命题“我将去镇上，仅当我有时间时”符号化为（）A.P®Q B.Q®P C.P «Q D.ØQÚØP3. 下列各组公式中，哪组是互为对偶的？（）A.P,P B.P, ØP C.A,(A*)* D.A,A（其中P为单独的命题变元，A为含有联结词的命题变元）4. 设P：我们划船，Q：我们跑步命题“我们不能即划船又跑步”符号化为（）A. ØpÙØQ B. ØPÚØQ C. Ø(P«Q) D.P«ØQ5. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）A. 2是偶数或-3不是负数 C. 2是奇数或-3不是负数C．2不是偶数且-3不是负数 D. 2是奇数且-3不是负数6. 设P：张三可以作这件事，Q：李四可以作这件事命题“张三或李四可以做这件事”符号化为（）A.PÚQ B.PÚØQ C.P«Q D. Ø(ØPÚØQ)7. 下列语句中哪个是真命题？（）A.我正在说谎。

B.严禁吸烟C.如果1+2=3，那么雪是黑的 D.如果1+2=5，那么雪是黑的8. 下面哪个联结词运算不可交换？（）A.Ù B.® C.Ú D.«9. 命题公式(PÙ (P®Q)) ®Q是（）A.矛盾式 B.蕴含式 C.重言式 D.等值式10. 下面哪个命题公式是重言式？（）A.(P®Q)Ù(Q® P) B.(PÙQ)®PC.(ØPÚQ)ÙØ(ØPÙØQ) D.Ø(PÚQ)11. 下列哪一组命题公式是等值的？（）A. ØPÙØQ,PÚQ B.A®(B®A),ØA®(A®ØB)C.Q®(PÚQ),ØQÙ (PÚQ) D.ØAÚ (AÙB),B12. P®Q的逆反式是（）A.Q®ØP B. P ®Ø Q C. ØQ®P D. ØQ®ØP13. ØP®Q的逆反式是（）A.Q®ØP B. P ®Ø Q C. Q®ØP D.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.Q®ØP B.ØP®ØQ C.ØQ®ØP D.P®ØQ18. 下面哪一个命题公式是重言式？（）A.P®(QÚR) B.(PÚR)Ù(P®Q)C.(PÚQ) « (QÚR) D.(P®(Q®R)) ®((P®Q) ®(P®R))19. 下列哪个命题公式不是重言式？（）A.Q®(PÚQ) B.(PÙQ)®PC.Ø(PÙØQ) Ù(ØPÚQ) D.(P®Q)«(ØPÚQ)20. 重言式的否定式是（）A.重言式 B.矛盾式 C.可满足式 D.蕴含式21. 下面哪一个命题是假命题？（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不惟一C.如果2是奇数，那么一个公式的析取范式惟一D.如果2是奇数，那么一个公式的析取范式不惟一22. 下面哪一组命题公式不是等值的？（）A.Ø(A®B),AÙØB B.Ø(A«B),(AÙØB)Ú(ØAÙB)C.A®(BÚC),ØAÙ(BÚC) D. A®(BÚC),(AÙØB)®C23. 命题公式P®QÙR的对偶式为（）A.P®(QÚR) B. PÚ (QÚR)C.ØPÚ (QÙR) D.ØPÙ (QÚR) 24. 命题公式P®(Q¯R)是（）A.重言式 B.可满足式 C.矛盾式 D.等值式25. P«ØQÛ（）A.ØP® (P®ØQ) B.(ØPÚQ)Ú (ØQÚP)C.(ØPÚØQ)Ù(ØQÚP) D.(ØPÚØQ)Ù(QÚP)26. 命题公式Ø(PÙQ)®R的主析取范式中含极小项的个数为（）A.8 B.3 C.5 D.027. 命题公式Ø(PÙQ)®R的主析取范式中含极大项的个数为（）A.0 B.3 C.5 D.828. 命题公式Ø(PÙQ)®R的成真赋值为（）A.000,001,110 B.001,011,101,110,111C.全体赋值 D.无29. 如果AÞB成立，则以下各种蕴含关系哪一个成立？（）A.BÞA B.ØAÞØB C.ØBÞØA D.ØAÞB二、 填空题1. 下列句子中，是命题的有 (1).我是教师。

2).禁止吸烟！(3).蚊子是鸟类动物4).上课去！(5).月亮比地球大2. 设P：我生病，Q：我去学校(1).命题“我虽然生病但我仍去学校”符号化为 2).命题“只有在生病的时候，我才不去学校”符号化为 3).命题“如果我生病，那么我不去学校”符号化为 3. 设P：我有钱，Q：我去看电影1).命题“如果我有钱，那么我就去看电影”符号化为 2).命题“虽然我有钱，但我不去看电影”符号化为 3).命题“当且仅当我有钱时，我才去看电影”符号化为 4. 对于下列各式，是永真式的有 1).(PÙ(P®Q))®Q(2).P®(PÚQ)(3).Q®(PÙQ)(4).(ØPÙ(PÚQ))®Q(5).(P®Q) ®Q 5. (PÙ(PÚQ)) ®RÛ 6. P®(P®Q) 7. 对于下列各式(1).(ØPÙQ)Ú(ØPÙØQ)可化简为 2).Q®(PÚ(PÙQ)) 可化简为 3).(ØPÚQ)«(ØQ®ØP)ÙP可化简为 。

8. 命题公式PÚ(QÙØR)的成真赋值为 ，成假赋值为 9. 若 且 则称X是公式A的子公式10. 写出表中各列所定义的命题联结词PQP ① QP ② Q1110100101010001 11. 由n个命题变元可组成 个不等值的命题公式 12. 用两种形式写出P­Q的对偶式 ① ， ② 13. 两个重言式的析取是 ① ，一个重言式与一个矛盾式的析取是 ② 14. A、B为两个命题公式，AÛB当且仅当 ① ，AÞB当且仅当 ② 15. 设P、Q为两个命题公式，德●摩根律可表示为 ① ，吸收率可表示为 ② 16. 设命题公式A中仅含有联结词Ø，Ù，Ú，若 得到公式A*，则A*称为A的对偶式 17. 公式(PÚQ) ®R的只含联结词Ø，Ù，Ú的等值式为 ① ，它的对偶式为 ② 18. 命题公式AÛ(PÙQÙR)­0，则其对偶式A*Û 19. 在命题演算中，一个蕴含式与它的 ① 式是等值的，它的 ② 式与它的 ③ 是不等值的。

20. 公式ØP®Q的反换式为 ① ，逆反式为 ② 21. 任意两个不同极小项的合取为 ① 式，全体极小项的析取式必为 ② 22. 命题公式Ø(P®Q)的主析取范式为 ① ，主合取范式的编码表示为 ② 23. 已知公式A(P,Q,R)的主合取范式为M0ÙM3ÙM5，它的主析取范式为（写成编码形式） 24. 命题公式Ø(P«Q)的主析取范式为 ① ，其编码表示为 ② ，主合取范式的编码表示为 ③ 25. 对于前提：S®ØQ，SÚR，ØR, ØP«Q，其有效结论为 26. 对于前提：(PÙQ) ®R，ØRÚS, ØS，其有效结论为 三、 判断题1. “王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”2. 凡陈述句都是命题3. 语句3x+5y=0是一个命题4. 命题“两个角相等当且仅当它们是对顶角“的值为15. 语句“x+y=4”是个命题6. 命题“十减四等于五”是一个原子命题7. 命题“如果1+2=3，那么雪是黑的”是真命题。

8. (P®(QÙR))是一个命题演算的命题公式，其中P、Q、R是命题变元9. (P®(QÙR®ØQ))是一个命题公式，其中P、Q、R是命题变元10. 若A：张明和李红都是三好学生，则ØA：张明和李红都不是三好学生11. 若A：张明和李红都是运动员，则ØA：张明和李红不都是运动员12. 若P：每一个自然数都是偶数，则ØP：每一个自然数都不是偶数13. 若P：每个自然数都是偶数，则ØP：每个自然数不都是偶数14. 如果AÛB，则AÙCÛBÙC，AÚCÛBÚC15. 如果AÙCÛBÙC，则AÛB16. 联结词“¯”是可结合的17. 联结词“­”是可结合的18. 联结词“¯”是可交换的19. 联结词“­”是可交换的20. 联结词“®”是满足交换律21. “学习有如逆水行舟，不进则退”设P：学习如逆水行舟，Q：学习进步，R：学习退步则命题符号化为PÙ(ØQ®R)22. P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：P® (ØQ®R)23. 设P、Q是两个命题，当且仅当P、Q的真值均为1时，P«Q的值为124. 命题公式(PÙ(P®Q))®Q是矛盾式25. 命题公式(PÙ(P®Q))®Q是重言式。

26. 联结词Ù与Ú不是相互可分配的27. 在命题的演算中，每个最小联结词组至少有两个联结词28. 命题联结词集{Ø,«}是最小联结词集29. 命题联结词集{Ø,Ù,Ú}是最小联结词集30. 命题联结词集{Ù,®}是最小联结词集。