离散数学（本）模拟试题
一、填空题(共20分)
1．设全集E＝{1，2，3，4，5}，A＝{1，5}，B＝{1，2，3，4}，C＝{2，5}，求(A∩B)∪～C＝，ρ(A)∩ρ(C)＝ .
2．若关系R具有自反性，当且仅当在关系矩阵中，主对角线上元素；若关系只具有对称性，当且仅当关系矩阵是 .
3．设P：2+2＝4，Q：3是奇数；将命题“2+2＝4，当且仅当3是奇数．”符号化，其真值为 .
4．表达式中谓词的定义域是{a，b，c}，将其中的量词消除，写成与之等价的命题公式为 .
二、单项选择题(选择一个正确答案的代号，填入括号中。共14分)
1．下面关于集合的表示中，正确的是( )．
A．φ＝0 B．φ∈{φ}
C．φ∈φ D．φ∈{a，b}
2．设R1，R2是集合A＝{1，2，3，4}上的两个关系，其中R1＝{(1，1)，(2，2)，(2，3)，(4，4)}，R2＝{(1，1)，(2，2)，(2，3)，(3，2)，(4，4)}，则R2是R1的( )闭包．
A．自反 B．反对称
C．对称 D．以上都不是
3．设半序集(A，≤)上关系只的哈斯图如下图所示，若A的子集B＝{2，3，4，5}，则元素6为B的( )．
A．下界 B．上界
C．最小上界 D. 最大下界
4．设命题公式则G是( )．
A．恒假的 B．恒真的
C．可满足的 D．以上都不对
6．对于公式，下面的改名中，正确的是( )。
三、计算题(共50分)
1．化简下式：
((A∪B∪C)∩(A∪B))一((A∪(B—C))∩A) (9分)
2．试画出集合A＝{1，2，3，4，5，6}在半序关系“整除”下的哈斯图，并分别求出：
(1)集合A的最大元、最小元、极大元和极小元；
(2)集合B＝{2，3，6}的上界、下界、最小上界、最大下界．(11分)
3．设公式G的真值表如下，试求出G的主析取范式和主合取范式． (12分) P Q R G
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
4．设解释I为：
(1)定义域D＝{-2，3，6}；
(2)F(x)：x≤3
G(x)：x＞5
在解释I下求公式的真值． (8分)
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．令P ：今天下雪了，Q ：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（ ） A ．P→Q B ．P ∨Q C ．P ∧Q
D ．P ∧Q
2．下列命题公式为重言式的是（ ） A ．Q→（P ∧Q ） B ．P→（P ∧Q ） C ．（P ∧Q ）→P D ．（P ∨Q ）→Q 3．下列4个推理定律中，不．
正确的是（ ） A ．A ?（A ∧B ） B ．（A ∨B ）∧A ?B
C ．（A→B ）∧A ?B
D ．（A→B ）∧B ? A
4．谓词公式?x(P(x)∨?yR(y))→Q(x)中量词x ?的辖域是（ ）
A ．))()((y yR x P x ?∨?
B ．P （x ）
C ．(P(x)∨?yR(y))
D ．P(x), Q(x)
5．设个体域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)
6．下列选项中错误．．的是（ ） A ．??? B ．?∈? C ．??{?}
D ．?∈{?}
7．设A={a,b,c,d}，A 上的等价关系R={
的划分是（ ） A ．{{a},{b, c},{d}} B ．{{a, b},{c}, {d}} C ．{{a},{b},{c},{d}}
D ．{{a, b}, {c,d}}
12．设A={a, b, c}，R是A上的二元关系，R={
A．反自反的B．反对称的
C．可传递的D．不可传递的
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．任意两个不同的小项的合取为________________式，全体小项的析取式必为________________式。
17．公式?x(P(x)→Q(x,y)∨?zR(y, z))→S(x)中的自由变元为________________，约束变元为________________。
18．设集合M={x|1≤x≤12,x被2整除，x∈Z},N={x|1≤x≤12,x被3整除，x∈Z}，则M∩N=________________，M∪N=________________。
19．设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},
g={<1,2>,<2,3>,<3,3>}，则f g=________________，g f=________________。
20．设A={a,b,c}，R是A上的二元关系，且给定R={
三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题
8分，共30分）
26．集合A={a, b, c, d, e}上的二元关系R为
R={
（1）写出R的关系矩阵；
（2）判断R是不是偏序关系，为什么？
27．利用真值表判断公式（（P∨Q）∧（Q→R））→（P∧R）是否为重言式。
29．求下列公式的主析取范式和主合取范式：（P→Q）∧（Q→R）
30．设A为54的因子构成的集合，R?A×A，?x,y∈A, xRy?x整除y。画出偏序集
五、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）
31．设R是A上的一个自反关系，证明：R是一个等价关系，当且仅当若
五、应用题（本大题共2小题，第34小题8分，第35小题7分，共15分）
34．构造下面推理的证明。
如果今天是星期六，我们就要到颐和园或圆明园去玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。
离散数学试题八
一、单项选择题(本大题共8小题，每小题2分，共16分)
1.设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为[ ]
A.p→q
B.q→p
C.p→┐q
D.┐p→q
2.设解释I如下，个体域D={a,b},F(a,a)=(b,b)=0,F(a,b)=F(b,a)=1，在解释I下，下列公式中真值为1的是[ ]
A.VxヨyF(x,y)
B.ヨxVyF(x,y)
C.VxVyF(x,y)
D.┐ヨxヨyF(x,y)
3.对于任意集合X,Y,Z，则[ ]
A.X∩Y=X∩Z=>Y=Z
B.X∪Y=X∪Z=>Y=Z
C.X－Y=X－Z=>Y=Z
D.X⊕Y=X⊕Z=>Y=Z
4.下面等式中唯一的恒等式是[ ]
A.(A∪B∪C)-(A∪B)=C
B.A⊕A=A
C.A-(B×C)=(A-B)×(A-C)
D.A×(B-C)=(A×B)-(A×C)
二、填空题(本大题共10小题，每空3分，共24分)
5.含n个命题变项的重言式的主合取范式为_________________________。
6.设个体域为整数集合Z，命题Vxヨy(x+y=3)的真值为___________。
7.设R={<{1},1>，<1,{1}>，<2,{3}>，<{3},{2}>}，则ranR=_____________。
三、简答题(本大题共8小题，每小题5分，共40分)
8.设p：2+2=4，q=3+3=7，4+4=8，求下列个复合命题的真值。
(1)(p∧q)←→r
(2)(p←→r)←→(q←→r)
(3)(p∨┐q)→(q→r)
(4)┐q→(p←→r)
(5)(p∨q)→(┐p∧q∧r)18.求公式Vx(┐ヨyF(x,y)→ヨzG(x,z))的前束范式。
9.设A={{a,{b}},c,{c},{a,b}}，B={{a,b},{b}}，计算
(1)A∩B
(2)A⊕B
(3)P(B)
四、证明题(本大题共4小题，每小题5分，共20分)
10.在命题逻辑中构造下面推理的证明。
前提：p→s，q→r，┐r，p∨q
结论：r
离散数学试题十
一、选择（每题3分，共24分）
1. 设为上关系，关系图如下，则具有性质（）。
A.自反性
B.反自反性
C.对称性
D.传递性
2. 下列运算正确的是（）。
A． B. C．D．
3. 设个体域为有理数集，则以下谓词公式中为假的是（）。
A. B．
C． D.
4. 下列各式中，不正确的有（）。
A． B．
C． D．二、计算与证明题
5．（每小题4分共20分），为上关系，关系矩阵为，
(1) 画出关系图。
(2) 求，。
(3) 求，，。
(4) 指出具有的性质。
(5) 是偏序关系吗？能否画出哈斯图？
6．（每小题5分共15分）已知命题公式，
(1) 构造真值表。
(2) 求主析取范式。
(3) 求主合取范式。
7．（每小题6分共12分）将下列语句翻译成谓词公式。
(1) 并非所有的人都聪明。
(2) 某些汽车比所有的火车慢。
《离散数学试题1套》
一、选择题（每题3分，共30分） 1. 下列语句中，( )是命题。 A. 请把门关上 B. 地球外的星球上也有人
C. x + 5 > 6
D. 下午有会吗？
2. 命题公式﹁B→﹁A 等价于( ) A. ﹁A ∨﹁B B. ﹁(A ∨B) C. ﹁A ∧﹁B D. A→B
3. 设I 是如下一个解释：D ＝{a,b},
0 1 0 1b) P(b,a) P(b,b) P(a,),(a a P ，则在解释I 下取真值为1的公式是( ).
A. ?x ?yP(x,y)
B. ?x ?yP(x,y)
C. ?xP(x,x)
D. ?x ?yP(x,y)
4. 下列说法正确的是 ( ).
A ．若C A ∈?∈则及C
B B A B ．若
C A ??∈则及C B B A C ．若C A ∈∈?则及C B B A
D ．若C A ?∈?则及C B B A
5． 下列说法错误的是 ( ).
A ．)(}{ΦP ∈Φ
B ．})({ΦP ?Φ
C ．}{)(Φ?ΦP
D ．})({)(ΦP ∈ΦP
6．设} 2} {1 {1} {，，，Φ=A ，P(A)为A 的幂集，则P(A)的元素个数为( ).
A ．3
B ．6
C ．7
D ．8
7. 集合A 的一个划分，确定A 的元素间的关系为( ).
A ．全序关系
B ．等价关系
C ．偏序关系
D ．拟序关系
二、填空题（每题3分，共24分） 1. 设S(x)∶x 是大学生；K(x)∶x 是运动员。则命题：“有些运动员不是大学生”的 符号化为 .
2. 已知命题公式G ?(?P →Q)∧R ，则G 的主析取范式是 .
3. 将公式化为等价的前束范式: ?xF(x)∧??xG(x)? .
4. 设} 4 3 2 1 {，，，=A ，A A R ??，},|,{R b a b a b a R ∈<><=，， 则domR= ，ranR= .
5. 设A 为非空集合，P(A)为A 的幂集，则对于P(A)中的二元运算：?⊕，
，求运算 ⊕ 的幺元 ，运算? 的幺元 .
6. 设} 5 4 3 2 1 {，，，，=A ，A A R ??，} 2 2 4 3 2 1 {><><><=，，，，，R
求)(R r = ，)(R s =
三、计算题（每题6分，共18分）
1. 设集合} b {
，a A =，P(A)为A 的幂集，求笛卡尔积A A ?P )(.
2. 设} 24 12 8 6 4 3 2 1 {，，，，，，，=A ，}/|{整数，=><=x y y x R ，试求：
(1) 作出〈A ，R 〉的哈斯图
(2) 求A 的最大元、最小元、上界、下界
四、证明题（共28分）
1. (5分)在命题逻辑中构造下面推理的证明：
前提：p→┐q, ┐r ∨q, r ∧┐s 结论：┐p
2．(5分)证明：(?x )(H (x )→M (x ))，(?x )H (x )?(?x )M (x )
2. (5分)设A={1，2，3，4}，关系)A A ()A A (R ????，
}A d ,c ,b ,a |,,,{R ∈+=+>><><<=，c b d a d c b a ，证明：R 是等价关系
计算机应用专业 《离散数学》试题B
2005年3月
一、填空题 (每小题3分，本题共15分)
1 设R 是集合A 上的等价关系，则R 所具有的关系的三个特性是_______________________________________________________.
2. 设命题公式()G P Q R =?→?→，则公式G 的合取范式是_____________________。
3. 设A 是集合，且A = {1, 2}，则A 上的全关系A 2 =
_____________________________________________________.
二、选择题 (每小题3分，本题共15分)
1 在由3个元素组成的集合上，可以有 ( ) 种不同的关系。
(A)3
(B)8
(C) 9
(D) 512
3 设命题公式()G P Q =?→，H Q P =→?，则G 与H 的关系是( )。
(A)G H ? (B)H G ? (C)G H = (D)以上都不是.
4 已知命题()GP Q R =∧?∨?，则所有使G 取真值为1的解释是 ( )。
(A)(0, 0, 0), (0, 0, 1), (1, 0, 0);
(B) (0, 1, 0), (1, 0, 1), (1, 1, 0);
(C) (1, 0, 0), (1, 0, 1), (1, 1, 0); (D) (1, 1, 0), (1, 0, 1), (1, 1, 1).
5 设I 是如下一个解释：D = {a, b}，(,)(,)(,)(,)
1010
P a a P a b P b a P b b ，则在解释I 下
取真值的公式是 ( ).
(A) (,)x y Px y ??
. (B) (,)x y Px y ??. (C) (,)x P x x ?. (D) (,)x y Px y ??. 三、计算题 (本题共60分)
1. (本题12分)设集合A ＝{1, 2, 3}，A 上的关系R ＝{(1, 1),(1, 2),(2, 2),(3, 2),(3, 3)},
(1) 画出R 的关系图； (2) 写出R 的关系矩阵.
(3) 问R 具有关系的哪几种性质(自反、对称、传递、反对称). 2. (本题12分) 设集合A ＝{1, 2, 3, 4, 6, 8, 12}，R 是A 上的整除关系，
(1) 画出半序集(A, R)的哈斯图；
(2) 写出A 的子集{2, 4, 6, 8}的上界，下界，最小上界，最大下界； (3) 写出集合A 的最大元，最小元，极大元，极小元。
. (本题12分)试判断命题公式(()())()P Q Q R P R →∧→→→的公式类型。
5. (本题12分)设一阶逻辑公式
((,)(()()))G x y P x y z Q z R x =???→?→
试将G 化成与其等价的前束范式。
离散数学试题六
一、单项选择题 (本大题共8小题，每小题2分，共16分)
1.设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为 [ ]
A.p→q
B.q→p
C.┐q→p
D.┐p→q
2.下面4个推理定律中，不正确的为 [ ]
A.A=>(A ∨B) (附加律)
B.(A ∨B)∧┐A=>B (析取三段论)
C.(A→B)∧A=>B (假言推理)
D.(A→B)∧┐B=>A (拒取式)
3.若X是Y的子集，则一定有[ ]
A.X不属于Y
B.X∈Y
C.X真包含于Y
D.X∩Y=X
4.设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是[ ]
A.自反、对称、传递的
B.自反、对称、反对称的
C.对称、反对称、传递的
D.只有对称性
二、填空题(本大题共10小题，每空3分，共30分)
5.设个体域D={1,2}，命题Vxヨy(x+y=3)的真值为___________。
6.公式p→(q→r)在联结词全功能集{┐，∧}中等值形式之一为___________________。
7.设A={φ}，B={φ,{φ}}，则P(A)∩P(B)=___________。
8.设A={2,3,4}，B={4,5,6}，R是从A到B的关系，且xRy<=>x与y互质，那么R=____________________。
三、简答题(本大题共8小题，每小题5分，共40分)
10.用等值演算法求公式((p∨q)∧(p→q))←→(q→p)的主合取范式与主析取范式。
11.在个体域D={a,b,c}消去公式Vx(F(x)∧ヨyG(y))的量词。
12.设R是自然数集合N上的关系，且xRy<=>x+2y=10。
(1)求dom R；
(2)说明R具有的性质(自反、反自反、对称、反对称、传递)。
13.设偏序关系R的关系图如右所示，
(1)画出R的哈斯图；
(2)求出该偏序集的极大，极小、最大、最小元。
四、证明题(本大题共3小题，共20分)
14.在一阶谓词逻辑中构造下面推理的证明。
前提：Vx(F(x)∨G(x))，Vx(F(x)→H(x))，
结论：Vx(┐H(x)→G(x))。
数理系离散数学模拟试卷
一．选择题（每题1分，共10分）
1．判断下列语句哪一个是命题：（）。
A．请把门关上！ B．你喜欢鲁迅的作品吗？
C．我在说谎 D．雪是黑色的。
2．命题公式P→(Q→P)为（）。
A．重言式 B．可满足式 C．矛盾式 D．等价式
3．若个体域为整数域，下列公式中（）为假。
A．?x?y(x+y=0) B．?y?x(x+y=0)
C．?x?y(x+y=0) D．┐?y?x(x+y=0)
4．设A，B，C为任意三个集合，下列命题正确的是（）。
A．若A∪B=A∪C，则B=C B．若A∩B=A∩C，则B=C
C．若~A∪B=E，则A?B D．若A－B=?，则A=B
5．设R和S是集合A上的关系，若R和S是传递的，则（）。
A．R∩S是传递的 B．R∪S是传递的
C．R·S是传递的 D．以上都不对
二．填空题（每空2分，共30分）
1．设P：王华是一班的学生；Q：王华是二班的学生。则：
命题“王华要末是一班的学生要末是二班的学生”符号化为____________。
2．谓词公式?x P(x)→?x Q(x)∨?yR(y)的前束范式为：______________________________。
3．设A={a,b,c,d}，R={
则t(R)= _______________________________________________________；
s(R)= _______________________________________________________。
5．根据右图所示哈斯图，写出该偏序关系R的集合表达式，
R＝____________________________________________________；
子集{2,3,4,5}的上界是__________，下界是_______________。三．求（（P∨Q）→R）→ P的主析取范式和主合取范式。（共10分）
1
2
4 5
3
四. 已知个体域为人类集合，给定谓词：
F(x):x喜欢步行；G(x):x喜欢骑自行车；H(x):x喜欢乘汽车。
请将下列命题符号化，并进行推理证明（共12分）
每个喜欢步行的人都不喜欢骑自行车。每个人或者喜欢骑自行车或者
喜欢乘汽车。有的人不喜欢乘汽车。所以有的人不喜欢步行。
五．设集合A={1,2,3}，R1，R2，R3均为A上二元关系，试分别画出下列每个关系的关系图并判断各个关系的性质。（共9分）
R1={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,3>}
R2={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}
R3={<1,3>}
六．已知R是A上的等价关系，设关系S={
离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设Ｐ：他去旅游 Ｑ：他有时间 则命题公式为Ｐ→Ｑ
3．请将语句“有人不去工作”翻译成谓词公式． 设Ａ（x）:x是人 Ｂ（x）：去工作 则谓词公式为?x（A(x)∧－B（x）) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习 则谓词公式为?x（A（x）∧B（x）） 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A-B)；（2）(A∩B)；（3）A×B． 解： （1）（A-B）＝{{1}，{2}} （2）（A∩B）＝{1，2} （3）A×B＝ {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2．设A={1，2，3，4，5}，R={
离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：
((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19
D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项：
A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标：
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f
2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（ A ）． 选择一项： ， A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 . 答案已保存 满分 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（ D ）． ) 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 < 题目3 答案已保存 满分 标记题目 题干 ； 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 ， D. 17 题目4 答案已保存 满分 标记题目 … 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 ~ C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分 " 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 … B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 ^ 满分 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： % A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 《 答案已保存 满分 标记题目 题干 “教学活动资料”版块是课程学习平台右侧的第（ A ）个版块． 、 选择一项： A. 6 B. 7 C. 8 D. 9 @ 题目8 答案已保存 满分 标记题目 题干 ( 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项： 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 一、单项选择题（共 10 道试题，共 100 分。） 1. 设集合A = {1, a }，则P(A) = ( D )． A. {{1}, {a}} B. { ,{1}, {a}} C. {{1}, {a}, {1, a }} D. { ,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A}，则R的性质为（C ）． A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( C )． A. {a，{a}} A B. {1，2} A C. {a} A D. A 4. 设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}， 则h =（ A ）． A. f?g C. f?f D. g?g 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的（ C ）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )． 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上的整除关系，则偏序集上的元素5是集合A的（ C ）． A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10，则其幂集的元素个数为（ A ）． 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ． 2．设给定图G(如右由图所示)，则图G的点割集是 { f }，{ e,c} ． 3．设G是一个图，结点集合为V，边集合为E，则 G的结点度数之和等于边数的两倍． 4．无向图G存在欧拉回路，当且仅当G连通且不含奇数度结 点． 5．设G= 8．结点数v与边数e满足e=v - 1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。” 2．如下图所示的图G存在一条欧拉回路． 答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。 3．如下图所示的图G不是欧拉图而是汉密尔顿图． 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 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) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 电大离散数学本形考任 务 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} A B ==，P(A)-P(B )={{3},{1,3},{2,3},{1,2,3}}，A B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} x∈ y y > <那么R－1＝{<6,3>,<8,4>}． x = ∈ 2 , , x , {B A y 5．设集合A=｛a, b, c, d｝，A上的二元关系R={离散数学形考任务1-7试题及答案完整版
离散数学期末试题及答案完整版
离散数学模拟试卷和答案
204电大离散数学,形考任务2
离散数学期末试卷及答案
离散数学期末试卷A卷及答案
离散数学模拟试题及答案
2018国家开放大学离散数学本形考任务答案
离散数学试卷及答案
离散数学考试试题(A、B卷及答案)
电大离散数学本形考任务完整版
相关主题
文本预览