华南理工大学网络教育学院
《离散数学》练习题参考答案
第一章命题逻辑
一填空题
（1）设：p：派小王去开会。q：派小李去开会。则命题：
“派小王或小李中的一人去开会”可符号化
为：(p∨?q) ∧ (?p∨q) 。
（2）设A，B都是命题公式，A?B，则A→B的真值是T。
（3）设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题：
“刘平不但不聪明，而且不用功”可符号化为：p∧q。
（4）设A , B 代表任意的命题公式，则蕴涵等值式为
A → B??A∨B。
（5）设，p：径一事；q：长一智。在命题逻辑中，命题：
“不径一事，不长一智。”可符号化为：? p→?q 。
（6）设A , B 代表任意的命题公式，则德?摩根律为
?（A ∧ B）??A ∨?B）。
（7）设，p：选小王当班长；q：选小李当班长。则命题：“选小王或小李中的一人当班长。”可符号化为：(p∨?q) ∧ (?p∨q) 。（8）设，P：他聪明；Q：他用功。在命题逻辑中，命题：
“他既聪明又用功。”可符号化为：P∧Q 。
（9）对于命题公式A，B，当且仅当 A → B 是重言式时，称“A蕴含B”，并记为A?B。
（10）设：P：我们划船。Q：我们跑步。在命题逻辑中，命题：“我们不能既划船又跑步。”可符号化为：? (P∧Q) 。（11）设P , Q是命题公式，德·摩根律为：
?（P∨Q）??P∧?Q）。
（12）设P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。”可符号化为：?P→Q。
（13）设p：小王是100米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑冠军。”可符号化为：
p∨q。
（14）设A，C为两个命题公式，当且仅当A→C为一重言式时，称C可由A逻辑地推出。
二．判断题
1.设A，B是命题公式，则蕴涵等值式为A→B??A∧B。（?）
2.命题公式?p∧q∧?r是析取范式。（√）
3.陈述句“x + y > 5”是命题。（?）
4.110 (p=1,q=1, r=0)是命题公式((?(p∧q))→r)∨q 的成真赋值。（√）
5.命题公式p→(?p∧q) 是重言式。（?）
6.设A，B都是合式公式，则A∧B→?B也是合式公式。（√）
7.A∨(B∧C)?( A∨B)∨(A∨C)。（?）
8.陈述句“我学英语，或者我学法语”是命题。（√）
9.命题“如果雪是黑的，那么太阳从西方出”是假命题。（?）
10.“请不要随地吐痰！”是命题。（?）
11.P →Q ??P∧Q 。（?）
12.陈述句“如果天下雨，那么我在家看电视”是命题。（√）
13.命题公式（P∧Q）∨（?R→T）是析取范式。（?）
14.命题公式(P∧?Q)∨R∨ (?P∧Q) 是析取范式。（√）
三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。
1．设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。”
可符号化为（2）。
（1）P→Q
（2）Q → P
（3）? Q →? P
（4）Q ∨?P
2．(1 ) 明年国庆节是晴天。
(2 ) 在实数范围内，x+y〈3。
(3 ) 请回答这个问题！
(4 ) 明天下午有课吗？
在上面句子中，是命题的只有(1 ) 。
3．命题公式A与B是等值的，是指(4 ) 。
（1）A与B有相同的命题变元
（2）A?B是可满足式
（3）A→B为重言式
（4）A?B为重言式
4．(1 ) 雪是黑色的。
(2 ) 这朵花多好看呀！。
(3 ) 请回答这个问题！
(4 ) 明天下午有会吗？
在上面句子中，是命题的是(1 ) 。
5．设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。”
可符号化为（2）。
（1）Q→P
（2）P → Q
（3）? Q →? P
（4）Q ∨?P
6．设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。”
在命题逻辑中可符号化为（3）。
（1）Q→P（2）P→Q
（3）?P→Q（4）Q∨?P
7．(1 ) 现在开会吗？
(2 ) 在实数范围内，x+y >5。
(3 ) 这朵花多好看呀！
(4 )离散数学是计算机科学专业的一门必修课。
在上面语句中，是命题的只有(4 ) 。
8．设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游。”
可符号化为（1）
（1）P→Q （2）Q → P
（3）? Q →? P （4）Q ∨?P
9．下列式子是合式公式的是（2）。
（1）（P∨→Q）（2）?（P→（Q∨R））
（3）（P ?Q）（4）∧Q→R
10．（1）1＋101＝110 （2）中国人民是伟大的。
（3）全体起立！（4）计算机机房有空位吗？
在上面句子中，是命题的是（2）。
11．设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功。”
在命题逻辑中可符号化为（3）。
（1）P ∧Q（2）P→Q
（3）P∨?Q（4）P∧?Q
12．(1 ) 如果天气好，那么我去散步。(2 ) 天气多好呀！
(3 ) x=3。(4 ) 明天下午有会吗？
在上面句子中(1 ) 是命题。
13．设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为（4）。
（1）P ∨Q（2）P→Q
（3）P∧?Q（4）P∧Q
四、解答题
1．设命题公式为（?p→q）→（q→?p）。
（1）求此命题公式的真值表；
（2）给出它的析取范式；
（1）
p q ﹁p ﹁p→q q→﹁p （?p→q）→（q→?p）T T F T F F
T F F T T T
F T T T T T
F F T F T T
（2）（?p→q）→（q→?p）
?﹁（?p→q）∨（q→?p）
?﹁（p∨q）∨（?q∨?p）
?（﹁p∧﹁q）∨?q∨?p
2．设命题公式为（p → q）∧（p ∨ r）。
（1）求此命题公式的真值表；
（2）给出它的析取范式；
（1）
p q r p→q p∨r （p → q）∧（p ∨ r）
T T T T T T
T T F T T T
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T F F
（2）（p → q）∧（p ∨ r）
?（?p∨q）∧（p ∨ r）
?((?p∨q)∧p )∨((?p∨q)∧r)
?((?p∧p ) ∨(q∧p))∨((?p∧r) ∨(q∧r))
? (q∧p)∨(?p∧r) ∨(q∧r)
3．设命题公式为(?Q∧（P→Q）)→?P。
（1）求此命题公式的真值表；
（2）求此命题公式的析取范式；
(1)
P Q ﹁Q P→Q ﹁P ﹁Q ∧（P→Q）(﹁Q∧（P→Q）)→﹁P T T F T F F T T F T F F F T F T F T T F T F F T T T T T
(2)
解：(?Q∧（P→Q）)→?P
?(?Q∧（﹁P∨Q））→?P
?﹁(?Q∧（﹁P∨Q））∨?P
?（﹁?Q∨﹁（﹁P∨Q））∨?P
?Q∨（P∧﹁Q）∨?P
4．完成下列问题
求命题公式（P∧（Q→R））→S的析取范式。
解：（P∧（Q→R））→S
?（P∧（﹁Q∨R））→S
?﹁（P∧（﹁Q∨R））∨S
?（﹁P∨﹁（﹁Q∨R））∨S
?﹁P∨（﹁﹁Q∧﹁R）∨S
?﹁P∨（Q∧﹁R）∨S
5．设命题公式为（P ∧（P→Q））→Q。
（1）求此命题公式的真值表；
（2）求此命题公式的析取范式；
（1）
P Q P→Q P ∧（P→Q）（P ∧（P→Q））→Q
T T T T T
T F F F T
F T T F T
F F T F T （2）
解：（P∧（P→Q））→Q
?（P∧（﹁P∨Q））→Q
?﹁（P∧（﹁P∨Q））∨Q
?（﹁P∨﹁（﹁P∨Q））∨Q
?﹁P∨（﹁﹁P∧﹁Q）∨Q
?﹁P∨（P∧﹁Q）∨Q
6．设命题公式为（（P ∨ Q）∧?P）→Q。
（1）求此命题公式的真值表；
（2）给出它的析取范式；
（1）
P Q P∨Q﹁P（P∨Q）∧﹁P（（P∨Q）∧﹁P）→Q
T T T F F T T F T F F T F F F T F T F T T T T T
（2）
解：（（P ∨ Q）∧?P）→Q
?﹁（（P ∨ Q）∧?P）∨Q
?（﹁（P ∨ Q）∨（﹁﹁P））∨Q
?﹁P∨﹁Q）∨P∨Q
?T
7．用直接证法证明
前提：P∨Q，P→R，Q→S
结论：S∨R
证明：1）P∨Q P
2）﹁P→Q T 1）E
3）Q→S P
4）﹁P→S T 2）3）I
5）﹁S→P T 4）E
6）P→R P
7）﹁S→R T 5）6）I
8）S∨R T 7）E
8．用直接证法证明
前提：P→ (Q∨R)，S→?Q，P，S。
结论：R
证明：1）P→ (Q∨R) P
2）P P
3）(Q∨R) T 2）3）I
4）S→?Q P
5）S P
6）?Q T 4）5）I
7）R T 3）6）E
第二章谓词逻辑
一填空题
（1）若个体域是含三个元素的有限域{a，b，c}，则
?xA(x)?A(a) ∨ A(b) ∨ A(c)
（2）取全总个体域，令F(x)：x为人,G(x)：x爱看电影。则命题“没有不爱看电影的人。”可符号化为___?(?x(F(x) ∧ G(x)))____。
（3）若个体域是含三个元素的有限域{a，b，c}，则
?xA(x)?A(a) ∧ A(b) ∧ A(c) 。
（4）取全总个体域，令M(x)：x是人,G(y)：y是花, H(x,y)：x喜欢y。则命题“有些人喜欢所有的花。”可符号化为?x(M(x)∧(?y(G(y)→H(x,y))))。（5）取个体域为全体人的集合。令F(x)：x在广州工作,G(x)：x是广州人。
在一阶逻辑中，命题“在广州工作的人未必都是广州人。”可符号化为_______﹁?x(F(x)→ G(x))_____。
（6）P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题：
“每个学生都要参加考试”可符号化为：?x(P(x) →Q(x))。
（7）M(x)：x是人，B(x)：x勇敢。则命题“有人勇敢，但不是所有的人都勇敢”谓词符号化为 ____?x(M(x)∧ B(x)) ∧﹁?x(M(x) →B(x))_______。（8）P(x)：x是人，M(x)：x聪明。则命题“尽管有人聪明，但不是一切人都聪明”谓词符号化为 ______?x(P(x)∧ M(x)) ∧﹁?x(P(x) →M(x))___。（9）I(x)：x是实数，R(x)：x是正数，N(x)：x是负数。在谓词逻辑中，命题：“任何实数或是正的或是负的”可符号化为：?x(I(x) →(R(x) ∨ N(x))。（10）P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题：“每个学生都要参加考试”可符号化为：?x(P(x) →Q(x))。（11）令M(x)：x是大学生,P(y)：y是运动员, H(x, y)：x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为____?x(M(x)∧(?y(P(y)→H(x,y)))___。
二．判断题
1.设A，B都是谓词公式，则?x A??B也是谓词公式。（√）
2.设c是个体域中某个元素，A是谓词公式，则A(c)??xA(x)。（?）
3.?x?yA(x,y)??y?xA(x,y) 。（√）
4.?x?yA(x,y)??y?xA(x,y) 。（?）
5.取个体域为整数集，则谓词公式?x?y(x ? y = y ) 是假命题。（√）
6.(?x)（P(x)→Q(x)）? (?x)（?P(x) ∨Q(x)）。（√）
7.命题公式(P∧?Q∨ R) ∨ (?P∧Q) 是析取范式。（?）
8.谓词公式(?x)(A (x) → B(x, y)) ∧R(x) 的自由变元为x, y。（√）
9.（（?x）A（x）→B）?（?x）（A（x）→B）。（?）
10.R(x)：“x是大学生。”是命题。（?）
三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入
下列叙述中的内。
1．设F（x）：x是火车，G（x）：x是汽车，H（x，y）：x比y快。命题“某些汽车比所有火车慢”的符号化公式是(2) 。
（1）?y（G（y）→?x（F（x）∧H（x，y）））
（2）?y（G（y）∧?x（F（x）→H（x，y）））
（3）?x ?y（G（y）→（F（x）∧H（x，y）））
（4）?y（G（y）→?x（F（x）→H（x，y）））
2．设个体域为整数集，下列真值为真的公式是（3）。
（1）?y?x (x – y =2)
（2）?x?y(x – y =2)
（3）?x?y(x – y =2)
（4）?x?y(x – y =2)
3．设F（x）：x是人，G（x）：x早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是（4）。
（1）（?x）（F（x）→G（x））
（2）（?x）（F（x）∧G（x））
（3）（?x）（F（x）→G（x））
（4）（?x）（F（x）∧G（x））
5．下列式子中正确的是（1）。
（1）?（?x）P（x）?（?x）P（x）
（2）?（?x）P（x）?（?x）?P（x）
（3）?（?x）P（x）?（?x）?P（x）
（4）?（?x）P（x）?（?x）?P（x）
6．下面谓词公式是永真式的是b)。
a)P（x）→Q（x）
b)（?x）P（x）→（?x）P（x）
c)P（a）→（?x）P（x）
d)?P（a）→（?x）P（x）
5．设S（x）：x是运动员，J（y）：y是教练员，L（x，y）：x钦佩y。命题“所有运动员都钦佩一些教练员”的符号化公式是c) 。
a)?x（S（x）∧?y（J（y）∧L（x，y）））
b)?x?y（S（x）→（J（y）→L（x，y）））
c)?x（S（x）→?y（J（y）∧L（x，y）））
d)?y?x（S（x）→（J（y）∧L（x，y）））
6．下列式子是合式公式的是（2）。
（1）（P∨→Q）（2）?（P∧（Q∨R））
（3）（P ?Q）（4）∧Q→∧R
7．下列式子中正确的是（1）。
（1）?（?x）P（x）?（?x）P（x）
（2）?（?x）P（x）?（?x）?P（x）
（3）?（?x）P（x）?（?x）?P（x）
（4）?（?x）P（x）?（?x）?P（x）
四、解答题
1．构造下面推理的证明：
前提：? x F（x）→?y（（F（y）∨ G（y））→ R（y）），
? x F（x）。
结论：? x R（x）。
证明：
（1）? x F（x）→?y（（F（y）∨ G（y））→ R（y））前提引入
（2）? x F（x）前提引入
（3）?y（（F（y）∨ G（y））→ R（y））（1）（2）假言推理
（4）F（c）（2）EI
（5）F（c）∨ G（c）（4）附加
（6）（F（c）∨ G（c））→ R（c）（3）UI
（7）R（c）（5）（6）假言推理
（8）? x R（x）（7）EG
2．在一阶逻辑中构造下面推理的证明
每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令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）?x (?H（x）) 前提引入
（2）?H（c）（1）EI
（3）?x（G（x）∨H（x））前提引入
（4）G（c）∨H（c）（3）UI
（5）G（c）
（6）?x（F（x）→?G（x））前提引入
（7）F（c）→?G（c）（6）UI
（8）?F（c）
（9）?x (?F（x）) （8）EG
3．在命题逻辑中构造下面推理的证明：
如果他是理科学生，他必须学好数学。如果他不是文科学生，他必是理科学生。他没学好数学，所以他是文科学生。
令F(x)：x是理科学生，G(x)：x学好数学，H(x)：x是文科学生。
前提：?x（F（x）→G（x））, ?x（?H(x)→F（x））,
?x (?G（x）)
结论：?x (H(x))
证明
（1）?x（F（x）→G（x））前提引入
（2）?x (?G（x）) 前提引入
（3）?x (?F（x）) T（1）（2）I
（4）?x（?H(x)→F（x））前提引入
（5）?x (H(x)) T（3）（4）I
4．用直接证法证明：
前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x））
结论：（?x）（Q（x）∧R（x））。
推理：1) (?x)(C(x) →W(x) ∧R(x)) P
2) (?x)(C(x) ∧Q(x)) p
3) C(a) ∧Q(a) ES2)
4) C(a) →W(a) ∧R(a) US1)
5) C(a) T3)I
6) W(a) ∧R(a) T4)5)I
7) Q(a) T3)I
8) R(a) T6)I
9) Q(a) ∧R(a) T7)8)I
10) (?x)(Q(x) ∧R(x)) EG9)
第三章集合与关系
一填空题
（1）如果|A|＝n，那么|A×A|＝n2。A上的二元关系有____22n_____个。
（2）集合A上关系R的自反闭包r（R）=_______R?I____________。
（3）设集合A上的关系R和S，R={（1，2），（1，3），（3，2）}，S={（1, 3），（2，1），（3，2）}，则S?R={(1,2), (2,2), (2,3)} 。
（4）如果|A|＝n，那么|P(A)|＝2n。
（5）设集合A上的关系R和S，R={<1，2>，<2，1>，<3，4>，<4，3>}，S={<1，3>，<3，1>，<2，4>，<4，2>}，则R?S= {<1,4>, <2,3>, <3,2>, <4,1>} 。（6）设集合E={a, b, c}，E的幂集P(E)＝___________________________。（7）设R是定义在集合X上的二元关系，如果对于每个x, y∈X，______ ____ ____________ ，则称集合X上的关系R是对称的。（8）设关系R和S为，R={<1，2>，<3，4>，<2，2>}，S={<4，2>，<2，5>，<3，1>，<1，3>}，则R?S =______ ___ __ _______________。
（9）设R是定义在集合X上的二元关系，如果对于每个x, y∈X，______ ____ ____________ ，则称集合X上的关系R是自反的。
二．判断题
1．设A、B、C为任意的三个集合，则A×(B×C)=A×(B×C)。（×）2．设S，T是任意集合，如果S -T = ?，则S = T。（×）3．集合A={1,2,3,4}上的关系{<1,2>,<2,3>,<2,4>,<3,4>}是一个函数。（×）4．集合A={1，2，3，4}上的整除关系是等价关系。（×）5．集合A 的幂集P(A)上的包含关系是偏序关系。（√）6．设A={a, b, c}, R∈ A×A且R={< a, b>,< a, c>}, 则R是传递的。（√）6．设A，B是任意集合，如果B ≠?，则A – B ≠ A。（×）7．集合A={1,2,3}上的关系{<1,1>,<2,2>,<3,3>,<1,2>}是传递的。（√）8．集合A={1，2，3，4}上的小于关系是等价关系。（×）9．关系{
11．集合A={1,2,3}上的关系S={<1,1>,<1,2>,<3,2>,<3,3>}是自反的。（×）12．设X={1, 2, 3}, Y={a, b, c}。函数F={<1, a>,<2, c>,<3, b>}是双射。（√）13．集合A上的关系R的自反闭包r(R)=R∪I A。（√）14．集合A上的偏序关系R是自反的、对称的、传递的。（×）15.设A，B是任意集合，则A ⊕ B ＝(A-B) ∪(B-A)。（√）
三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入
下列叙述中的内。
1．设A={a，b，c}，B={a，b}，则下列命题不正确的是a) 。
a)A－B={a，b}
b)A∩B={ a，b }
c)A⊕B={c}
d)B?A
2．设A = {a, b, c, d}, A 上的关系R = {
a)R = {
b)R = {
c)R = {
d)R = {
3．对于集合{1, 2, 3, 4}上的关系是偏序关系的是a) 。
a)R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,3>,<2,4>,<3,3>,<3,4>,<4,4>}
b)R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<2,4>,<3,1>,<3,4>,<4,4>}
c)R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>, <2,1>,<3,1>,<3,3>,<4,1>,<4,4>}
d)R={<2,1>,<1,2>,<1,3>,<1,4>,<2,2>, <4,3>,<2,4>,<3,3>,<3,4>,<4,4>} 4．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下哪个关系是从A到B 的单射函数b) 。
a) f ={<1，7>，<2，6>，<3，5>，<1，9>，<5，10>}
b) f ={<1，8>，<2，6>，<3，7>，<4，9>，<5，10>}
c) f ={<1，7>，<2，6>，<3，5>，<4，6>}
d) f ={<1，10>，<2，6>，<3，7>，<4，8>，<5，10>}
5．设 A = {a, b, c}，要使关系{
a)R = {
b)R = {
c)R = {
d)R = {
6．设S={Φ，{1}，{1，2}}，则S的幂集P（S）有(4) 个元素（1）3 （2）6 （3）7 （4）8
7．设R为定义在集合A上的一个关系，若R是（2），则R为等价关系。
（1）反自反的，对称的和传递的（2）自反的，对称的和传递的
（3）自反的，反对称的和传递的（4）对称的，反对称的和传递的8．设S，T，M为任意集合，下列命题正确的是c) 。
a)如果S∪T = S∪M，则T = M
b)如果S-T = Φ，则S = T
c)S-T?S
d)S⊕S = S
9．设A = {a, b, c}，要使关系{
（1）R = {
（3）R = {
10．设A={1，2，3，4，5}，B={a，b，c，d，e}，以下哪个函数是从A到B 的入射函数b) 。
a)F ={<1，b>，<2，a>，<3，c>，<1，d>，<5，e>}
b)F={<1，c>，<2，a>，<3，b>，<4，e>，<5，d>}
c)F ={<1，b>，<2，a>，<3，d>，<4，a>}
d)F={<1，e>，<2，a>，<3，b>，<4，c>，<5，e>}
四、解答题
1．已知偏序集（A ，≦），其中A={a ，b ，c ，d ，e}，“≦”为{（a ，b ），
（a ，c ），（a ，d ），（c ，e ），（b ，e ），（d ，e ），（a ，e ）}∪I A 。
（1）画出偏序集（A ，≦）的哈斯图。
（2）求集合A 的极大元，极小元，最大元，最小元。 (1)
（2）集合A 的极大元是e ，极小元a ，最大元e ，最小元a 。
2．设R 是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除关系。
（1） 给出关系R ；（2）画出关系R 的哈斯图； （3）指出关系R 的最大、最小元，极大、极小元。
（1）R={<1,1>,<1,2> , <1,3>, <1,4>, <1,5>, <1,6>, <1,7>, <1,8>, <1,9>, <2,2>, <2,4>, <2,6>, <2,8>, <3,3>, <3,6>, <3,9>, <4,4>, <4,8>, <5,5>, <6,6>, <7,7>, <8,8>, <9,9>} (2)
e
d
a
b
c
4 5
1
2
3
7
6 8 9
（3）关系R 的无最大，最小元是1，极大元是8和9，极小元是1。
3．设R 是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。
（2） 给出关系R ； （2） 给出COV A
（3） 画出关系R 的哈斯图；
（4） 给出关系R 的极大、极小元、最大、最小元。
（1）R={<1,1>,<1,2> , <1,3>, <1,4>, <1,6>, <1,12>, <2,2>, <2,4>, <2,6>, <2,12>, <3,3>, <3,6>, <3,12>, <4,4>, <4,12>, <6,6>, <6,12>, <12,12>}
(2) COV A ={<1,2> , <1,3>,<2,4>, <2,6> <3,6> <4,12>, <6,6>, <12,12>} (3)
（4）关系R 的极大、最大元是12，极小元、最小元是1。
4 3
1
2
6 12
第五章代数结构
一填空题
（1）集合S的幂集P(S)关于集合的并运算“∪”的零元为____S___。
（2）集合S的幂集P(S)关于集合的并运算“∩”的零元为____φ____。
（3）集合S的幂集P(S)关于集合的并运算“∪”的么元为____φ______。（4）一个代数系统＜S, * ＞，其中S是非空集合。*是S上的一个二元运算，如果*在S上是封闭的，则称代数系统＜S, * ＞为广群。
二．判断题
1．含有零元的半群称为独异点。（?）2．运算“＋”是整数集I上的普通加法，则群
下列叙述中的内。
1．下列群一定为循环群的是e)。
e)
f)
g)
h)
2．运算“－”是整数集I上的普通减法，则代数系统
（1）结合律（2）交换律（3）有零元（4）封闭性
3．设I是整数集，N是自然数集，P（S）是S的幂集，“×，＋，∩”是普通的乘法，加法和集合的交运算。下面代数系统中（2）是群。
（1）
（1）
（2）
（3）
（4）
第七章图论
一填空题
（1）一个无向图G=（V，E）是二部图当且仅当G中无奇数长度的回路。（2）任何图(无向的或有向的)中，度为奇数的顶点个数为偶数。（3）设D是一个有向图，若D中任意一对顶点都是相互可达的，则称D是________双向连通的_______。
（4）既不含平行边，也不含环的图称为简单图。
（5）经过图中每条边一次且仅一次并的回路，称为欧拉回路。
（6）一棵有n个顶点的树含有_______n－1________边。
（7）设G =（V，E），G' =（V'，E'）是两个图，若V′= V且E′?E，称G'是G的生成子图。
（8）经过图中每个结点一次且仅一次的回路，称为哈密尔顿回路。
二．判断题
1．5个顶点的有向完全图有20条边。（√）2．连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。（?）3．图中的初级通路都是简单通路。（√）4．已知n (n≥2)阶无向简单图G有n – 1条边，则G一定为树。（?）5．n阶无向完全图K n的每个顶点的度都是n。（?）6．一个无向图是二部图当且仅当它没有奇数度的顶点。（?）7．任何图都有一棵生成树。（?）8．连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次。（?）9．图中的初级回路都是简单回路。（√）10．任一图G=（V，E）的顶点的最大度数必小于G的顶点数。（?）11．欧拉图一定是汉密尔顿图。（?）12．无向连通图G的任意两结点之间都存在一条路。（√）
第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数.
是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。
2016注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．令p : 今天下雪了，q :路滑，r :他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。 A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨? 2.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。 A. (()((),0))x P x L f x ?∧ B. (()((),0))x P x L f x ?→ C. ()((),0)xP x L f x ?∧ D. ()((),0)xP x L f x ?→ 3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。 A ．(()())x F x G x ?∧ B ． (()())x F x G x ??→? C ．(()())x F x G x ??∧ D ． (()())x F x G x ??∧? *4.下列命题公式不是永真式的是（ A ）。 A . ()p q p →→ B . ()p q p →→ C . ()p q p ?∨→ D . ()p q p →∨ 5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。 A. p q ∧ B. ()p q ?∧ C. p q ?∧? D. p q ?∧ 6．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ A ） A ．()(()())?→x R x Q x B ．()(()())?∧x R x Q x C ．()(()())x R x Q x ?∧ D ．(()())x R x Q x ?→ 7. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( C ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 8．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点， 则G 一共有（ C ）个顶点。
第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);
离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧?
答案： 令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y，都有x+y≥x。 答案： 令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化： 某些人对某些药物过敏。 答案：
令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式： 答案： 15. 证明： 答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明： 前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ?
离散数学（本）复习题 1.请给出公式G=（P→（Q→P））→（?P→（P→Q））的真值表。 2.设A={1，2，3，4，5，6}，其上一个划分为C={{1}，{2，4}，{3，5，6}}，请给出对应划分C的等价关系R C。 3.R，S是集合A上的两个关系。试证明下列等式： （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R （3）(R∪S)-1= R-1∪S-1 （4）(R∩S)-1= R-1∩S-1 4.设R是集合A上的关系，令 R+={(x, y)|x∈A，y∈A，并且存在n>0，使得xR n y}， 则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。 5.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。 6.设A={1，2，3，4，5，6，7，8，9}，R为A上的整除关系，请给出部分序集（A，R）的Hasse图。 7.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？ 8.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？ 9.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。 10.若R是等价关系，试证明R-1也是等价关系。 11.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值： a) (P∧(Q∧R))∨?((P∨Q)∧(R∨S)) b) (?(P∧Q)∨?R)∨(((?P∧Q)∨?R)∧S) c) (?(P∧Q)∨?R)∨((Q??P)→(R∨?S)) d) (P∨(Q→(R∧?P)))?(Q∨?S) 12.试将下列公式化成等价的前束范式： (1)?x(P(x)→?yQ(x，y))； (2)?x((??yP(x，y))→(?zQ(z)→R(x)))； (3)?x?y(?zP(x，y，z)∧(?uQ(x，u)→?vQ(y，v)))。 13.设S={G1，…，G n}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。 14.证明下面的等价式： (1) (?P∧(?Q∧R))∨(Q∧R)∨(P∧R)=R (2) P→(Q→P)=?P→(P→Q) (3) P→(Q∨R)=(P→Q)∨(P→R) (4) (P→Q)∧(R→Q)=(P∨R)→Q 15．找出下面公式的Skolem范式： (1)?(?xP(x)→?y?zQ(y，z))； (2)?x(?E(x，0)→(?y(E(y，g(x))∧?z(E(z，g(x))→E(y，z)))))。 16．G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n≤2 C，其中2m C表示 m m中取2的组合数。
常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={
1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
离散数学测试题 一．选择题（10*2） 1.设L (x )：x 是演员，J (y )：y 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老 师”符号化为( ) (A) ),()(y x A x xL →? (B) ))),()(()((y x A y J y x L x ∧?→? (C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧?? 2.令F(x):x 是有理数，G(x):x 是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为 （ ） A.?x(F(x)∧G(x))∧?x(G(x)→?F(x)) B.?x(F(x)→G(x))∧?x(G(x)∧?F(x)) C.?x(F(x)∧G(x))∧?x(G(x)∧?F(x)) D.?x(F(x)→G(x))∧?x(G(x)→?F(x)) 3．设R 是集合A={a,b,c,d}上的二元关系， R={
离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==， ，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，
一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是 ．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B.
离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群}
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P
02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={
5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集