.
一、选择题：（每题2’）
1、下列语句中不是命题的有（）。
A．离散数学是计算机专业的一门必修课。B．鸡有三只脚。
C．太阳系以外的星球上有生物。D．你打算考硕士研究生吗?
2、命题公式A与B是等价的，是指（）。
A．A与B有相同的原子变元B．A与B都是可满足的
C．当A的真值为真时，B的真值也为真D．A与B有相同的真值
3、所有使命题公式P∨(Q∧?R)为真的赋值为（）。
A．010，100，101，110，111 B．010，100，101，111
C．全体赋值D．不存在
4、合式公式?(P∧Q)→R的主析取范式中含极小项的个数为（）。
A．2 B．3 C．5 D．0
5、一个公式在等价意义下，下面哪个写法是唯一的（）。
A．析取范式B．合取范式C．主析取范式D．以上答案都不对
6、下述公式中是重言式的有（）。
A．(P∧Q) → (P∨Q) B．(P?Q) ? (( P→Q)∧(Q→P))
C．?(P →Q)∧Q D．P →(P∧Q)
7、命题公式(?P→Q) →(?Q∨P)中极小项的个数为（），成真赋值的个数为（）。
A．0 B．1 C．2 D．3
8、若公式(P∧Q)∨(?P∧R) 的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为（）。
A．m001∧m011∧m110∧m111B．M000∧M010∧M100∧M101
C．M001∧M011∧M110∧M111D．m000∧m010∧m100∧m101
9、下列公式中正确的等价式是（）。
A．?(?x)A(x) ? (?x)?A(x) B．(?x) (?y)A(x, y) ? (?y) (?x) A(x, y)
C．?(?x)A(x) ? (?x)?A(x) D．(?x) (A(x) ∧B(x)) ? (?x) A(x) ∨(?x) B(x)
10、下列等价关系正确的是（）。
A．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) B．?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x)
C．?x ( P(x) →Q ) ??x P(x) → Q D．?x ( P(x) →Q ) ??x P(x) → Q
11、设个体域为整数集，下列真值为真的公式是（）。
A．?x?y（x·y=1）B．?x?y（x·y=0）C．?x?y（x·y=y）D．?x?y（x+y=2y）
12、设S={?,{1},{1,2}}，则有（）?S。
A．{{1,2}} B．{1,2 } C．{1} D．{2}
13、下列是真命题的有（）。
A．{a}?{{a}} B．{{?}}∈{?,{?}} C．?∈{?,{?}} D．{?}∈{?,{?}}
14、设S={?,{1},{1,2}}，则2S有（）个元素。
A．3 B．6 C．7 D．8
15、已知幂集的基数|ρ( A)|=2048，则集合A 的基数|A|为（ ）。
A ．11
B ．12
C ．10
D ．9
16、设A={1，2，3}，则A 上的二元关系有（ ）个。
A ． 23
B ． 32
C ．23?3
D ．32?2
17、设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}}
18、设R ，S 是集合A 上的关系，则下列说法正确的是（ ）。
A ．若R 、S 是自反的，则R ?S 是自反的
B ．若R 、S 是反自反的，则R ?S 是反自反的
C ．若R 、S 是对称的，则R ?S 是对称的
D ．若R 、S 是传递的，则R ?S 是传递的
19、集合A 上的相容关系R 的关系矩阵M(R)的对角线元素（ ）。
A ．全是1
B ．全是0
C ．有的是1，有的是0
D ．有的是2
20、设集合 A={1，2，3}，A 上的关系R={<1,1>，<1,2>，<2,2>，<3,3>，<3,2>}，则R 不具备（
）
。 A ． 自反性 B ． 传递性 C ． 对称性 D ． 反对称性
21、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为（如图所示），
则R 具有（ ）性质。
A ．自反性、对称性、传递性
B ．反自反性、反对称性
C ．反自反性、反对称性、传递性
D ．自反性
22、设S={1，2，3}，R 为S 上的关系，其关系图为
则R 具有（ ）的性质。
A ．自反、对称、传递
B ．什么性质也没有
C ．反自反、反对称、传递
D ．自反、对称、反对称、传递
23、设A={1, 2, 3}，B={a, b}，下列各二元关系中是A 到B 的函数的是（ ）。
A ．R={<1,a>,<2,a>,<3,a>}
B ．R={<1,a>,<2,a>,<2,b>,<3,a>}
C ．R={<1,a>,<2,b>}
D ．R={<2,a>,<2,b>}
24、设R 为实数集，映射f ：R →R ，f (x)= -x 2+2x-1，则f 是（ ）。
A ．单射而非满射
B ．满射而非单射
C ．双射
D ．既不是单射，也不是满射
25、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（）。
A．B．C．D．
26、N是自然数集合，定义f：N→N，f (x) = x mod 3（即x除以3的余数），则f 是（）。
A．满射不是单射B．单射不是满射
C．双射D．不是单射也不是满射
27、设S={?,{1},{1,2}}，则有（）?S。
A．{{1,2}} B．{1,2 } C．{1} D．{2}
28、集合A={x | x=2n∧n∈N }对（）运算封闭。
A．加法B．减法C．乘法D．|x－y|
29、设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（）。
A．?x ∈A，有x*Z=Z*x=Z B．Z ∈A，且?x ∈A有x*Z=Z*x=Z
C．Z ∈A，且?x ∈A有x*Z=Z*x=x D．Z ∈A，且?x ∈A有x*Z=Z*x=Z
30、下面偏序集（）能构成格。
31、在（）中，补元是唯一的。
A．有界格B．有补格C．分配格D．有补分配格。
32、下面四组数能构成无向简单图的度数序列的有（）。
A．(2, 2, 2, 2, 2) B．(1, 1, 2, 2, 3) C．(1, 1, 2, 2, 2) D．(1, 1, 3, 3, 3) 33、无向图结点之间的连通性，是结点集之间的一个（）。
A．连通关系B．偏序关系C．等价关系D．函数关系
34、已知图G的相邻矩阵为：
则G有（）。
A．5点，8边B．6点，7边C．5点，7边D．6点，8边
35、下列四组数为结点度序列，能构成无向图的是（）。
A．2, 3, 4, 5, 6, 7 B．1, 2, 2, 3, 4
C．2, 1, 1, 1, 2 D．3, 3, 5, 6, 0
36、下列几个图是简单图的有（）。
A．G1=(V1,E1)，其中V1={a, b, c, d, e}，E1={(a,b), (b,e), (e,b), (a,e), (d,e)}
B．G2=(V2,E2)，其中V2=V1，E2={
C．G3=(V3,E3)，其中V3=V1，E3={(a,b), (b,e), (e,d), (c,c)}
D．G4=(V4,E4)，其中V4=V1，E4={
37、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。
A．1 B．2 C．3 D．4
38、一棵树有2个4度结点，3个3数度结点，其余是树叶，则该树中树叶的个数是（）。
A．8 B．9 C．10 D．11
39、设图G是有6个顶点的连通图，总度数为20，则从G中删去（）边后使之变成树。
A．10 B． 5 C． 3 D． 2
40、下面那一个图可一笔画出（）。
41、在如下各图中（）欧拉图。
42、下图中既不是欧拉图，也不是哈密尔顿图的是（ ）。
43、在如下的有向图中，从V 1到V 4长度为3 的道路有（ ）条。
A ．1
B ．2
C ．3
D ．4
44、图 中 从v 1到v 3长度为3 的通路有（ ）条。
A ．0
B ．1
C ．2
D ．3
二、判断题（每题 1分）
1．)()())()((x xB x xA x B x A x ?∧??∧?。 （ Y ）
2．设A ，B ， C 是任意三个集合。
（1）若A ∈B 且B ?C ，则A ∈C 。 （ Y ） （2）若A ?B 且B ∈C ，则A ∈C 。
（ N ） （3）若A ∈B 且B ?C ，则A ?C 。 （ N ） （4）(A ⊕B)?C=(A ×C) ⊕ (B ×C)。
（
Y ） （5）A ⊕∪(B ⊕C)= (A ∪B)⊕(A ∪C)。 （ N ）
3．A ，B ，C 为任意集合，若A ∪B=A ∪C ，则B = C 。 （ N ）
4．可能有某种关系，既不是自反的，也不是反自反的。 （ Y ）
5．可能有某种关系，既是对称的，又是反对称的。 （ Y ）
6．设R 是实数集，R 上的关系S={
7．若集合A 上的关系R 是对称的，则R c 也是对称的。 （ Y ）
8．数集合上的不等关系（≠）可确定A 的一个划分 （ N ）
9．设集合A 、B 、C 为任意集合，若A×B = A×C ，则B = C 。 （ N ）
10．函数的复合运算“ ? ”满足结合律。
（ Y ） 11．集合A 上的恒等关系是一个双射函数。
（ Y ） 12．任何一个循环群必定是阿贝尔群。
（ Y ） 13．任何循环群必定是阿贝尔群，反之亦真。
（ N ） 14．设< A ，≤ >是偏序集，B ?A ，则B 的极大元b ∈B 且唯一。（ N ）
15．群是每个元素都有逆元的半群。 （ N ）
16．在代数系统< S , *> 中，若一个元素的逆元是唯一的，其运算*必是可结合的。
（ N ） 17．每一个有限整环一定是域，反之也对。 （ N ）
18．设
19．若平面图共有v 个结点，e 条边和r 个面，则v – e + r = 2。 （ N ）
20．任何有向图中各结点入度之和等于边数。 （ Y ）
21．若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。 （ N
） 22．一个图是平面图，当且仅当它包含与Ｋ3,3或Ｋ5在２度结点内同构的子图。 （ N
） 23．有割点的连通图可能是哈密尔顿图。 （ N ）
24．无多重边的图是简单图。 （ N ）
25．根树中最长路径的端点都是叶子。 （ N ）
26．在完全二叉树中，若有t 片叶子，则边的总数 e =2 t －1 。 （ N ）
27．群中可以有零元（对阶数大于1的群）。 （ N ）
28．任何循环群必定是阿贝尔群，反之亦真。 （ N ）
29．每一个链都是分配格。 （ Y ）
30．不可能有偶数个结点，奇数条边的欧拉图。 （ N ）
31．集合A 上的恒等关系是一个双射函数。 （ Y ）
32．设Q 为有理数集，Q 上运算 * 定义为),max(b a b a =*，则>*<，Q 是半群。（ Y ）
33．在完全二元树中，若有t 片叶子，则边的总数12-=t e 。 （ N ）
34．能一笔画出的图不一定是欧拉图。 （ Y ）
35．根树中最长路径的端点都是叶子。 （ N ）
36．命题公式(A ∧(A →B))→B 是一个矛盾式。 （ N ）
37．设R 是实数集，R 上的关系F={
38．设< A ，≤>是偏序集，B ?A ，则B 的极大元b ∈B 且唯一。 （ N ）
39．无多重边的图是简单图。 （ N ）
40．谓词公式?x P(x ) →?x Q(x )∨?y R(y )的前束范式是?x ?z ?y (P(x )→Q(z )∨R(y ))。（ Y ）
三、解答题（本题分4小题，共计35分）
1、试求))()((P Q Q P P ?∨??∧→→的主析取范式。
2、用真值表判断下列公式是永真式？永假式？可满足式？
（1）(P ∧?P)?Q
（2）?(P →Q) ∧Q （3）((P →Q)∧(Q →R))→(P →R)
解：（1）真值表：
因此公式（1）为可满足。
（2）真值表
因此公式（2）为永假式。
（3）真值表
因此公式（3）为永真式。
3、设个体域是D={2，3，6}，F(x):x≤3，G(x):x>5，消去公式?x(F(x)∧?yG(y))中的量词，并讨论其真值。 解：?x(F(x)∧?yG(y))? ?x(F(x))∧?yG(y)? (F(2)∧F(3)∧F(6))∧(G(2)∨G(3)∨G(6))
? F ∧T ?F
4、求下列公式的前束范式：
(1) ?xF(x)∧﹁?xG(x)
(2) (?xF(x,y)→?yG(y))→?xH(x,y)
5、通过求主析取范式判断下列命题公式是否等值：(P ∨Q)∧(?P ∨Q ∨R) 与
(P ∧(Q ∨R))∨(Q ∧(?P ∨R))。
解：(P ∨Q)∧(?P ∨Q ∨R)
? (P ∨Q ∨(?R ∧R))∧(?P ∨Q ∨R)
? (P ∨Q ∨?R)∧(P ∨Q ∨R)∧(?P ∨Q ∨R)
? M 1∧M 0∧M 4? M 0∧M 1∧M 4 ?∏(0,1,4)? ∑(2,3,5,6,7)
(P ∧(Q ∨R))∨(Q ∧(?P ∨R))
? (P ∧Q)∨(P ∧R)∨(?P ∧Q)∨(Q ∧R)
? (P ∧Q ∧R)∨(P ∧Q ∧?R)∨(P ∧Q ∧R)∨(P ∧?Q ∧R)
∨(?P ∧Q ∧R)∨(?P ∧Q ∧?R)∨(P ∧Q ∧R) ∨(?P ∧Q ∧R)
? (P ∧Q ∧R)∨(P ∧Q ∧?R)∨(P ∧?Q ∧R)∨(?P ∧Q ∧R)∨(?P ∧Q ∧?R)
? m 7∨m 6∨m 5∨m 3∨m 2? ∑(2,3,5,6,7)
由此可见 (P ∨Q)∧(?P ∨Q ∨R) ? (P ∧(Q ∨R))∨(Q ∧(?P ∨R))
6、设个体域为D={-2,3,6}，谓词3:)(≤x x P ，5:)(>x x G ，7:)(≤x x R ，求谓词公式的真值： )5())()((G x P x R x ∨→?
7、若集合A={a,{b,c}}的幂集为ρ(A)，集合B={?,{?}}的幂集为ρ(B)，求：ρ(A) ⊕ρ(B)。
解：ρ(A)= {?,{a},{{b,c}},{a,{b,c}} }
ρ(B)={?,{?},{{?}}, {{?,{?}} }
ρ(A) ⊕ρ(B)= {{a},{{b,c}},{a,{b,c}},{?},{{?}}, {{?,{?}} }
8、设集合A={2, 3, 4, 6, 8, 12, 24}，R 为A 上的整除关系，
(1) 画出偏序集
(2) 写出集合A 中的最大元、最小元、极大元、极小元；
(3) 写出A 的子集B={2, 3, 6, 12}的上界、下界、最小上界、最大下界。
9、集合S={1，2，3，4，5}，找出S 上的等价关系，此关系能产生划分{{1，2}，{3}，{4，5}}，并画出
关系图。
10、已知A ＝{a ，b ，c ，d }，A 上的关系R 定义为：R ＝{
11、已知A ＝{1，2，3，4，5}，A 上的关系R 定义为：
R ＝{<1,2>，<2,1>，<1,3>，<2,4>，<4,1>，<5,5>，<5,3>，<5,4>}，
求：r(R)，s(R)，t(R)。
12、集合}4,3,2,1{=A 上的关系R={<1,1>, <1,3>, <2,2>, <3,3>, <3,1>, <3,4>,<4,3>, <4,4>}，写出关系矩
阵M R，画出关系图并讨论关系R的性质。
13、设集合A={2, 3, 4, 6, 8, 12, 24}，R为A上的整除关系，画出偏序集
14、已知G={1,2,3,4,5,6}，×7为模7乘法。试说明
么？
15、一棵树T中，有3个2度结点，一个3度结点，其余结点都是树叶。
（1）T中有几个结点；
（2）画出具有上述度数的所有非同构的无向图。
16、设A={1，2，3，4，5}，A上的偏序关系如右图所示，
求：A的子集{3，4，5}和{1，2，3}的上界，下界，上确界和下确界。
17、求图中A到其余各顶点的最短路径，并写出它们的权。
18、设带权无向图如下，求其最小生成树T及该树的总权值。
19、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。
20、如下图所示的赋权图表示某七个城市v1,v2,……,v7及预先算出它们之间的一些直接通信线路造价，
试给出一个设计方案，使得各城市之间能够通信而且总造价最小。
四、写出对应下面推理的证明：（本题10分，1*10’=10’）
1、(A→B)∧(C→D)，B→E，D→F，￢(E∧F)，A→C?￢A
2、P∨W→R，R→S∨T，S→T，￢T∧Q?￢W
3、如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所
以，当小赵去看电影时，小李也去看电影。
v2
5
v6
v3
v5
v1
5
2
13
3
4
7
3
4、如果小张去看电影，则当小王去看电影时，小李也去。小赵不去看电影或小张去看电影。小王去看电
影。所以当小赵去看电影时，小李也去。
5、如果我学习（P），那么我数学不会不及格。如果我不热衷于玩扑克（R），那么我将学习。但我数学不
及格（Q）。因此我热衷于玩扑克。（注：请按括号中提示的字母翻译并进行论证。）
6、或者是天晴，或者是下雨。如果是天晴，我去看电影。如果我去看电影，我就不看书。所以，如果我
在看书，则天在下雨。
7、所有牛都有角，有些动物是牛；所以，有些动物有角。（P(x)：x是牛；Q(x)：x有角；R(x)：x是动物）
8、每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行
车。因而有的人不喜欢步行。（先将推理在一阶逻辑中符号化，随后验证其正确性）
五、解答题（本题10分，1*10’=10’）
1、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，
还有2人会打这三种球。而6个会打网球的人都会打另外一种球（指篮球或排球），求不会打这三种球的人数。
2、120名学生参加考试，这次考试有A、B和C共3道题，考试结果如下：12名学生3道题都做对了；
20名学生做对A和B；16名学生做对A和C；28名学生做对B和C；做对A题的有48名学生；做对B题的有56名学生；还有16名学生一道题也没做对。试求做对了C题的学生有多少名。
3、已知100个学生中有32人学数学，20人学物理，45人学生物，15人学数学和生物，7人学数学和物
理，10学物理和生物，30人这三门课一门也没学。问三门课程全部都学的学生人数是多少？
4、设A={a,b,c}，求A上所有的等价关系。
5、给定权1，4，9，16，25，36，49，64，81，100；构造一棵最优二叉树。
6、画出哈斯图：设B＝{a,b,c}，R={
7、偏序集
≤>
<,A的关系图如下图所示，
(1) 画出
≤>
<,A的哈斯图；
(2) 设B={b,c}，求B的所有上界、上确界，下界和下确界。
8、给定算式[(a+b)*c*(d+e)]－[f－g*h]，试用根树表示。
六、证明题：（本题10分，1*10’=10’）
1、R是A上的二元关系，证明：如果R是对称的，当且仅当R=R-1，且R-1也是对称的。
2、设R是A上的二元关系，试证：R是传递的当且仅当R2?R。
3、设R是A上一个二元关系，S={
4、设R1是非空集合A上的自反和传递的二元关系，R2也是A上的二元关系，且有
证明：R2是A上的等价关系。
5、设f :A→B, g:B→C，证明
(1) 若f, g都是满射，则g?f :A→C也是满射；
(2) 若f, g都是单射，则g?f :A→C也是单射；
6、若f: A→B是从A到B的函数，定义一个函数g:B→2A对任意b∈B有g(b) = {x|(x∈A)∧(f(x)=b)}，
2的单射。
证明：若f是A到B的满射，则g是从B到A
7、给定代数系统U=
W的同态。证明：g?f：X→Z是从U到W的同态。
8、设
个阿贝尔群。
9、设
10、证明：f是一个从V1到V2的同态映射。令V1 =
⊕6:?a,b∈Z6 ,a⊕6b=(a+b) mod 6，f:I→Z6,f(j)=j(mod 6),j∈I
离散数学试题（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 ＝{，，，，，，，，
《离散数学》模拟试题3 一、填空题（每小题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. 已知命题公式R Q P G→ ∧ ? =) (，则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分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
离散数学考试试题（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 。
试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 离散数学试题及答案 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)},则 离散数学期末试题及答 案 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的补元( ). 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 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 的关系图为 常熟理工学院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．设 一．判断题（共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?{ 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．． 命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．． 谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ） A ．一定是等价关系 B ．一定是相容关系 《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。 填空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) 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={离散数学试题及答案精选版
离散数学期末试题及答案完整版
离散数学试卷及答案(2)
离散数学题库
离散数学期末试卷及答案
自考离散数学试题及答案
离散数学期末试卷A卷及答案
离散数学题库及答案
离散数学试卷及答案
离散数学试卷及答案(1)
离散数学期末考试试题及答案
相关主题
文本预览