离散数学课堂习题及答案

1.1 命题及其表示法

1.下列陈述句中，（ ）不是命题。

A.2013年国庆节是星期天。 B.火星上有生物。 C.月球距离地球近。 D.上海是大城市。 2.下列命题中，（ ）是复合命题。

A.江山代有人才出。 B.我花开时百花杀。 C.春江水暖鸭先知。 D.万紫千红总是春。 3.下列命题中，（ ）是原子命题。

A.燕子飞回南方，春天来了。 B.天才是炼成的，而不是天生的。 C.暮春三月，江南草长。 D.哥白尼指出地球绕太阳转。 4.下列命题中，（ ）是原子命题。

A.王芳与王菲是姐妹。 B.王芳与王菲是三好学生。 C.王芳与王菲持有驾照。 D.王芳与王菲喜欢早睡早起。 5.下列命题中，（ ）是原子命题。

A.数学是科学的皇后，而数论是数学的皇后。 B.数学使人精细，逻辑使人善辩。 C.较大的偶数都可表示为两个素数的和。 D.数学是一种语言，也是一种工具。 6.判断一个语句是否为命题，首先看它是否为 陈述句 ，然后再看它是否具有唯一的 真值 。

1.C 2.B 3.D 4.A 5.C 6.陈述句，真值

1.2 命题联结词

1.命题“如果我休假，我将去美丽的黄山旅游。”的否定可表示为 2.命题“每个学生都要考试。”的否定可表示为 3.命题“1既不是素数也不是合数。”的否定可表示为 4.命题“如果我是你，那么太阳从西边出。”的真值为 5.命题“如果时间倒流，那么我们将长生不老。”的真值为 6.命题“2是偶数或3是奇数。”的否定可表示为（ ）。

A.2不是偶数或3不是奇数。 B.2不是偶数且3不是奇数。 C.2不是偶数或3是奇数。 D.2不是偶数且3是奇数。

7.设P:中国地处亚洲。Q:大熊猫产在中国。R:太阳从西边升起。求下列复合命题的真值。（1）(P?Q)→R （2）（R→(P∧Q))?┐P （3）┐R→(┐P∨┐Q∨R) （4）(┐P↑Q)↓(Q↑┐R)

8.命题“我善良、正直、勤奋、感恩、有责任、有尊严，所以我幸福。”的否定可表述 。 1.我休假且我不将去美丽的黄山旅游。 2.有的学生不要考试。 3.1是素数或合数。

4.1或T 5.1或T 6.B

7.（1）0或F （2）0或F （3）0或F （4）0或F

8.我善良、正直、勤奋、感恩、有责任、有尊严，并且我不幸福。

1.3 命题公式及其真值表

1.命题公式(P→Q)∧((Q→R)→(P→R))的类型为（ ）。 A 重言式 B 矛盾式 C 可满足式 D 不确定 2.命题公式(P→Q)→R的类型为（ ）。

A 重言式 B 矛盾式 C 可满足式 D 不确定

3.命题公式((P∧Q)∨(P∧R)∨(Q∧R))?((P∨Q)∧(P∨R)∧(Q∨R))的类型为（ ）。 A 重言式 B 矛盾式 C 可满足式 D 不确定

4.设P：它占据空间。Q：它有质量。R：它不断变化。S：它是物质。命题“占据空间的，有质量的而且不断变化的叫做物质。”翻译为 。命题“占据空间的有质量的叫做物质，而且物质是不断变化的。”翻译为 。 5.命题公式┐(P∧Q)→R的成真赋值为 。 6.命题公式（P∨Q∨R)?┐R的成真赋值为 。 7.翻译下列命题

（1）辱骂和恐吓决不是战斗。

（2）我们要做到德、智、体、美全面发展，为祖国建设而奋斗。 （3）上海到北京的D27次列车是下午五点半或六点开。 （4）如果你有时间，那就陪我去度假。

（5）如果爸爸和妈妈不同意，那我就不去探险。 （6）喝酒不开车，开车不喝酒。 1.C 2.C 3.A

4.(P∧Q∧R)? S，((P∧Q)? S)∧ (S→R) 5.001，011，101，110，111 6.010，100，110

7.（1）P∨Q，其中P：辱骂不是战斗。Q：恐吓不是战斗。 （2）(A∧B∧C∧D)? P，其中

A：我们要做到德育发展。B：我们要做到智育发展。C：我们要做到体育发展。 D：我们要做到美育发展。P：我们为祖国建设而奋斗。 （3）P?Q，其中P：上海到北京的D27次列车是下午五点半开。

Q：上海到北京的D27次列车是下午六点开。

（4）P→Q，其中P：你有时间。Q：你陪我去度假。

（5）(┐P∨┐Q)→┐R，其中P：爸爸同意。Q：妈妈同意。R：我去探险。 （6）(P→┐Q)∨(Q→┐P)，其中P：喝酒Q：开车

1.4 逻辑等价

1.化简命题公式A∨(┐A∨(B∧┐B)) ? 。 2.化简命题公式((A→B)?(┐B→┐A))∧C? C 。 3.化简命题公式(A∧B∧C)∨(┐A∧B∧C) ? 。

4.已知三元命题公式A(P1,P2,P3)是重言式，则A(┐P1,┐P2,┐P3)是 重言 式；A(┐P1,P2,P3)是 式。

5.已知三元命题公式A(P1,P2,P3)是矛盾式，则A(┐P1,┐P2,P3)是 矛盾

式；A(P1,P2,┐P3)是 式。

6.由三个命题变元能组成 个不等价的命题公式。

7.已知A是B的充分条件，B是C的必要条件，D是B的必要条件，A是D的 条件。 8.设P与Q是命题变元，则德·摩根律可表示为 ；吸收律可表示为 。 9.下列语句中，（ ）正确。

A．若P∧R?Q∧R，则P?Q B．若P∨R?Q∨R，则P?Q

C．若P→R?Q→R，则P?Q D．若P?R?Q?R，则P?Q 10.下列式子中，（ ）不正确。

A．┐(P↑Q)?┐P↓┐Q B．┐(P↓Q)?┐P↑┐Q

C．┐(P?Q)? ┐P?┐Q D．P?Q?┐P?┐Q

1. T或1 2.C 3.B∧C 4.重言式或永真式，重言式或永真式 5.矛盾式或永假式，矛盾式或永假式 6.22 7.充分

8. ┐(P∧Q)?┐P∨┐Q，┐(P∨Q)?┐P∧┐Q；P∧(P∨Q)?P，P∨(P∧Q)?P 9.D 10.C

3

1.5 联结词的全功能集合

1.下列式子中，（ ）不正确。

A.P→(Q→R)?(P→Q)→(P→R) B.P→(Q→R)?(P→Q)→R C.P→(Q→R)?Q→(P→R) D.P→(Q→R)?(P∧Q)→R 2.下列语句中，（ ）不正确。

A.若P?Q，R?S，则P∧R?Q∧S。 B.若P?Q，P?R，则P?Q∧R。 C.若P?Q，R?Q，则P∧R?Q。 D.若P?Q，Q?R，则P?R。 3.如果P?Q，则下列式子中，（ ）成立。

A.┐P?┐Q B.┐Q?┐P C.P?┐Q D.┐P?Q

4.如果A∨B?A∨C，┐A∨B?┐A∨C，则B?C。其对偶命题为 。 5.命题公式P↓┐Q的对偶式可表示为 或 。

6.已知命题公式┐P→┐Q，其逆换式是为 ；其反换式是为 ；其逆反式是为 。 1.B 2.C 3.B

4.如果A∧B?A∧C，┐A∧B?┐A∧C，则B?C。 5.P↑┐Q，┐P∨Q

6.┐Q→┐P； P→Q；Q→P

1.6 蕴含与对偶

1.仅用联结词↓表达下列命题公式┐P? ；P∨Q? ；P∧Q? 。

2.命题联结词 、 、 、 、 、 的运算均满足交换律。

3.列举六个命题最小全功能集合为 ， ， ， ， ， 。 4.仅用联结词↓表达命题公式P→Q? ； 仅用联结词↑表达命题公式P→Q? 。 5.试证明{┐,→}，{┐,?}，{↑}，{↓}均是最小全功能集合。 6.下列式子中（ ）不正确。 A．┐(P↑Q)?┐P↓┐Q B．┐(P↓Q)?┐P↑┐Q

C．P∧(Q?R)?(P∧Q)?(P∧R) D．P∨(Q?R)?(P∨Q)?(P∨R)

1.P↓P；(P↓Q)↓(P↓Q)；(P↓P)↓(Q↓Q) 2. ∧、∨、?、↑、↓、?

3. {┐，∧}，{┐，∨}，{↑}，{↓}，{┐，→}，{┐，?} 4.P↑(Q↑Q)；((P↓P)↓Q)↓((P↓P)↓Q)

5.例1.6.1已证明{┐，∨}是最小全功能集合。

由于P∨Q?┐P→Q，即仅用联结词┐与→就可表示┐与∨，故{┐，→}是最小全功能集合。

由于P∨Q?┐(┐P∧┐Q) ?┐(┐P?Q)，即仅用联结词┐与?就可表示┐与∨，故{┐，?}是最小全功能集合。

由于┐P?P↑P，所以P∨Q? (P↑P)↑(Q↑Q)，即仅用联结词↑就可表示┐与∨，故{↑}是最小全功能集合。

由于┐P?P↓P，所以P∨Q? (P↓P) ↓(Q↓Q)，即仅用联结词↓就可表示┐与∨，故{↓}是最小全功能集合。 6.D

1.7 命题公式的范式

1.命题公式(P→(Q∧R))∧(┐P? (┐Q∧┐R))的主合取范式为（ ）。 A．↖(0,7) B．↖(1,2,3,4,5,6) C．?(0,7) D．?(1,2,3,4,5,6)

2.命题公式(P→(Q∧R))∧(┐P? (┐Q∧┐R))的主析取范式为（ ）。 A．↖(0,7) B．↖(1,2,3,4,5,6) C．?(0,7) D．?(1,2,3,4,5,6) 3.命题公式(P→(Q∧R))∧(┐P? (┐Q∧┐R))的类型为（ ）。 A．重言式 B．矛盾式 C．可满足式 D．不确定

4.命题公式P∨(┐P∧┐Q∧R)∨(P∧┐R)的主合取范式为（ ）。 A．↖(1,4,5,6,7) B．↖(0,2,3) C．?(1,4,5,6,7) D．?(0,2,3)

5.命题公式P∨(┐P∧┐Q∧R)∨(P∧┐R)的主析取范式为（ ）。 A．↖(1,4,5,6,7) B．↖(0,2,3) C．?(1,4,5,6,7) D．?(0,2,3) 6.命题公式P∨(┐P∧┐Q∧R)∨(P∧┐R)的类型为（ ）。 A．重言式 B．矛盾式

C．可满足式 D．不确定

7.命题公式┐P∧(P∨┐Q∨R)∧(┐P∨┐Q)的主合取范式为（ ）。 A．↖(2,4,5,6,7) B．↖(0,1,3) C．?(2,4,5,6,7) D．?(0,1,3)

8.命题公式┐P∧(P∨┐Q∨R)∧(┐P∨┐Q)的主析取范式为（ ）。 A．↖(2,4,5,6,7) B．↖(0,1,3) C．?(2,4,5,6,7) D．?(0,1,3) 9.命题公式┐P∧(P∨┐Q∨R)∧(┐P∨┐Q)的类型为（ ）。 A．重言式 B．矛盾式 C．可满足式 D．不确定

表1.7.6 P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A(P,Q,R) 0 0 0 0 1 1 1 1 B(P,Q,R) 1 0 1 1 0 0 1 1 C(P,Q,R) 1 1 0 0 0 0 1 0 10.关于命题公式┐(P∧Q)? (Q∧R)的范式，下列结论中（ ）正确。 A．只有主合取范式。 B．既有主合取范式又有主析取范式。 C．只有主析取范式。 D．既没有主合取范式又没有主析取范式。

11.已知三元命题公式A(P,Q,R)，B(P,Q,R)，C(P,Q,R)的真值表如表1.7.6所示，它们的最简形式分别表示为A(P,Q,R)? ，B(P,Q,R)? ，C(P,Q,R)? 。

1.D 2. A 3. C 4. D 5. A 6.C 7. C 8. B 9. C 10.B

11.P；(┐P∨Q∨┐R)；(┐P∧┐Q)∨(P∧Q∧┐R)

1.8 命题逻辑的推理理论

1.前提┐P∨Q，┐Q∨P，┐R的有效结论是（ ）。题目好像有问题 A．Q B．┐P C．P∨Q D．┐Q→R 2.前提S→┐Q，S∨R，┐R，┐P?Q的有效结论是（ ）。 A．P B．R C．┐P D．┐S 3.下列命题公式中，（）不是前提P,P→Q的有效结论。 A．P∨Q B．P∨┐Q C．┐P∨Q D．┐P∨┐Q 4.证明下列各式。

（1）P∨Q，P→R，Q→S?S∨R （2）P→(Q→R)，S∨P，Q?S∨R

（3）R→┐Q，R∨S，S→┐Q，P→Q?┐P （4）S→┐Q，S∨R，┐R，┐P?Q?P

（5）┐(P→Q)→┐(R∨S)，(Q→P)∨┐R，R?P?Q

（6）P→(Q∧R)，┐Q∨S，(E→┐F)→┐S，Q→(P∧┐E)?Q→E

5.对下面的每一组前提，写出可能导出的有效结论及所应用的推理规则。

（1）若甲获胜，则乙失败；若丙获胜，则乙也获胜；若甲不获胜，则丁不失败；而丙获胜。 （2）如果我设计的程序运行通过，那么我很兴奋。如果我很兴奋，那么笑容是灿烂的，歌

声是燎亮的。而我很想哭还很想骂人。 6.构造下列推理的证明。

若x是实数，则它不是有理数就是无理数。若x不能表示成分数，则它不是有理数。x是实数且不能表示成分数。所以x是无理数。 1.？ 2.A 3.D

4.（1）①P→R P

②Q→S P

③P∨Q→R∨Q T，①，I14 ④Q∨R→S∨R T，②，I14

⑤P∨Q→S∨R T，③④合取，I10 ⑥P∨Q P

⑦S∨R T，⑤⑥合取，I7

（2）①P→(Q→R) P

②Q→(P→R) T，①，E17 ③Q P

④P→R T，②③合取，I7 ⑤S∨P P

⑥┐S→P T，⑤，E11

⑦┐S→R T，④⑥合取，I10 ⑧S∨R T，⑦，E11 （3）①R∨S P

②R→┐Q P ③S→┐Q P

④┐Q T，①②③合取，I11 ⑤P→Q P

⑥┐P T，④⑤合取，I8 另外，用归谬法证明

①P P（附加） ②P→Q P

③Q T，①②合取，I7 ④R→┐Q P ⑤R∨S P ⑥S→┐Q P

⑦┐Q T，④⑤⑥合取，I11 ⑧0 T，③⑦合取，E10

（4）①S∨R P

②┐R P

③S T，①②合取，I9 ④S→┐Q P

⑤┐Q T，③④合取，I7 ⑥┐P? Q P

⑦(┐P→Q)∧(Q→P) T，⑥，E12 ⑧┐P→Q T，⑦，I1

⑨P T，⑤⑧合取，I8 （5）①(Q→P)∨┐R P

②R P

③Q→P T，①②合取，I9 ④┐(P→Q)→┐(R∨S) P

⑤(R∨S) →(P→Q) T，④，E15 ⑥R∨S T，②，I2

⑦P→Q T，⑤⑥合取，I7 ⑧(Q→P)∧(P→Q) T，③⑦合取，I16 ⑨P? Q T，⑧，E12 （6）用CP规则证明

①Q P（附加） ②┐Q∨S P

③S T，①②合取，I9 ④(E→┐F)→┐S P

⑤┐(E→┐F) T，③④合取，I7 ⑥┐(E∨┐F) T，⑤，E11 ⑦E∧F T，⑥，E7 ⑧E T，⑦，I1

5.（1）设A：甲获胜。B：乙获胜。C：丙获胜。D：丁获胜。

前提：A→┐B，C→B，┐A→D，C ①A→┐B P

②B→┐A T，①，E15 ③C→B P

④C→┐A T，②③合取，I10 ⑤┐A→D P

⑥C→D T，④⑤合取，I10 ⑦C P

⑧D T，⑥⑦合取，I7 结论：D，丁获胜。

（2）设A：我设计的程序运行通过。 B：我很兴奋。

C：笑容是灿烂的。 D：歌声是燎亮的。 前提：A→B，B→(C∨D)，┐C，┐D

①A→B P ②B→(C∨D) P

③A→(C∨D) T，①②合取，I10

④┐C P ⑤┐D P

⑥┐C∧┐D T，④⑤合取，I16 ⑦┐(C∨D) T，⑥，E7

⑧┐A T，③⑦合取，I8 结论：┐A，我设计的程序运行没通过。

6.设P：x是实数。Q：x是有理数。R：x是无理数。S：x能表示成分数。 前提：P→(┐Q→R)，┐S→┐Q，P，┐S 结论：R

①P P ②P→(┐Q→R) P

③┐Q→R T，①②合取，I10 ④┐S→┐Q P

⑤┐S→R T，③④合取，I10 ⑥┐S P

⑦R T，⑤⑥合取，I7

2.1 个体与谓词

1.命题“李明是王芳和王菲的教练。”的个体为（ ）。

A．李明 B．王芳，王菲

C．王菲 D．李明，王芳，王菲

2.命题“5＋6＝11。”的个体为（ ）。

A．11 B．5，6 C．5 D．5，6，11

3.命题“长江和黄河都流经安徽境内。”的个体为 ，谓词为 ，该谓词刻画了个体的 ，且其真值为 。 4.命题“九华山是著名的佛教圣地。”的个体为 ，谓词为 。该谓词刻画了个体的 。 5.翻译下列命题。

（1）上海不是中国的最大城市。

（2）外星人曾访问过地球且今天是雨天。 （3）如果王芳和王菲是朋友，那么2＋5＝6。 （4）王菲是优秀共产党员或三好学生。

（5）太阳从东方升起，当且仅当地球绕太阳转。

（6）王菲是计算机学院老师，他生于1968年，他是教授或博导。 （7）中国地大物博，人口众多，是发展中国家。 1.D 2.D

3.长江，黄河，安徽；?和?流经?境内；关系；0或F 4.九华山；是著名的佛教圣地；性质 5.（1）┐P(a)，

其中P：是中国的最大城市 a：上海 （2）P(a)∧Q(b)，

其中P：访问过地球 a：外星人 Q：是雨天 b：今天

（3）P(a,b)→Q(2,5,6)，

其中P：?和?是朋友 Q：?＋?＝? a：王芳 b：王菲 （4）P(a)∨Q(a)，

其中P：是优秀共产党员 Q：是三好学生 a：王菲 （5）P(b)?Q(a,b)，

其中P：从东方升起 Q：?绕?转 a：地球绕 b：太阳 （6）P(a)∧Q(a)∧(R(a)∨S(a))，

其中P：是计算机学院老师 Q：生于1968年 R：是教授 S：是博导 a：王菲 （7）P(a)∧Q(a)∧R(a)，

其中P：地大物博 Q：人口众多 R：是发展中国家 a：中国

2.2 命题函数与量词

1.令F(x)：x是金属。G(y)：y是液体。H(x,y)：x可以溶解在y中。则命题“任何金属可以溶解在某种液体中。”可翻译为（ ）。

A．?x(F(x)∧?y(G(y)∧H(x,y))) B．?x?y(F(x)→(G(y)→H(x,y)))

C．?x(F(x)→?y(G(y)∧H(x,y))) D．?x(F(x)→?y(G(y)→H(x,y)))

2.令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))) 3.设F(x,y):x有y。M(x)：x是人。G(x)：x是缺点。则F(x,y)称为 ，x与y称为 ；M(x)与G(x)称为 ，x称为 。命题“每个人都有缺点。”翻译为 。 4.设P(x)：x是人。Q(x)：x犯错误。命题“没有不犯错误的人，每个人都犯错误。”在全总个体域上翻译为 ，取人类集合为论域翻译为 。

5.设P(x)：x是人。Q(x)：x聪明。命题“尽管有人聪明，但未必一切人都聪明。”在全总个体域上翻译为 ，取人类集合为论域翻译为 。

6.令F(x)：x是汽车。G(y)：y是火车。H(x,y)：x比y快。命题“有些汽车比某些火车快。”可翻译为 。命题“有些汽车比所有火车快。”可翻译为 。命题“所有汽车比所有火车快。”可翻译为 。命题“所有汽车比某些火车快。”可翻译为 。 7.翻译下列命题

（1）计算机专业的学生都要学离散数学。 （2）每个人都要学习和工作。

（3）并非一切推理都能用计算机完成。 （4）任何自然数都有唯一的一个后继数。 （5）是金子都闪光，但闪光的未必是金子。 （6）每个实数的平方都不小于0。

（7）凡是实数，不是大于0就是等于0或小于0。

22

（8）对于所有的实数x与y，均有x＋y?2xy。

（9）有的自然数既是质数又是合数，没有自然数既不是质数又不是合数。 （10）每个人恰有一个最好的朋友。

（11）有位美国人游览过中国每个城市的各个景点。 （12）这只大红书柜摆满了那些唐朝时期的古书。 （13）有些大学生不钦佩歌星。 （14）所有运动员都钦佩某些教练。

(15)没有一位女同志既是国家选手又是家庭妇女。 1.C 2.B

3.二元谓词；个体变量；一元谓词；个体变量；?x(M(x)→G(x)) 4. ┐?x(P(x)∧┐Q(x))∧?x(P(x)→Q(x))； ┐?x┐Q(x)∧?x Q(x)) 5. ?x(P(x)∧Q(x))∧┐?x(P(x)→Q(x))；?xQ(x)∧┐?xQ(x)) 6. ?x?y(F(x)∧G(y)∧H(x,y))；?x(F(x)∧?y(G(y)→H(x,y)))； ?x(F(x)→?y(G(y)→H(x,y)))；?x(F(x)→?y (G(y)∧H(x,y))) 7.（1）?x(P(x)→Q(x))，

其中P(x)：x是计算机专业的学生。 Q(x)：x要学离散数学。 （2）?x(M(x)→(P(x)∧Q(x))，

其中M(x)：x是人。P(x)：x要学习。Q(x)：x要工作。 （3）┐?x(P(x)→?y(Q(y)∧F(x,y))，

其中P(x)：x是推理。 Q(x)：x是计算机。F(x,y) ：x能由y完成。 （4）取论域：自然数集

?x?y?z(F(x,y)∧(F(x,z)→(y＝z)))， 其中F(x,y)：y是x的后继。

（5）?x(P(x)→Q(x))∧?x(Q(x)∧┐P(x))，

其中P(x)：x是金子。Q(x)：x闪光。 （6）?x(P(x)→┐F(f(x),0)，

其中P(x)：x是实数。f(x)：x的平方。F(x,y)：x小于y 。 （7）?x(P(x)→(B(x)∨C(x)∨D(x)))

其中P(x)：x是实数。B(x)：x大于0。C(x)：x等于0。D(x)：x小于0。

22

（8）?x ?y((P(x)∧P(y))→(x＋y?2xy))，

其中P(x)：x是实数。

（9）?x(P(x)∧Q(x)∧R(x))∧┐?x(P(x)∧Q(x)∧┐R(x))

其中P(x)：x是自然数。Q(x)：x是质数。R(x)：x是合数。 （10）取论域：人类集合

?x?y?z(F(x,y)∧(F(x,z)→(y≠z)))， 其中F(x,y) ：y是x的最好朋友。

（11）?x(P(x)∧?y (Q(y)→?z(R(z)→F(x,y,z)))，

其中P(x)：x是美国人。Q(x)：x是中国城市。R(x)：x是景点。

F(x,y,z)：x游览过y的z 。

（12）A(a)∧B(a)∧C(a)∧F(a,b)∧P(b)∧Q(b)∧R(b)，

其中A(x)：x是大的。B(x)：x是红的。C(x)：x是书柜。

P(y)：y是唐朝时期的。Q(y)：y是古老的。R(y)：y是书。 F(x,y)：x摆满了y 。 a：这只 b：那些

（13）?x(P(x)∧?y (Q(y)→┐F(x,y))，

本文来源：https://www.bwwdw.com/article/mpl2.html