离散数学复习题参考带答案
一、选择题：（每题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、在如下的有向图中，从V1到V4长度为3 的道路有（）条。
A．1 B．2 C．3 D．4
44、图中从v1到v3长度为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、如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所
以，当小赵去看电影时，小李也去看电影。
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={
试证：若R是A上一个等价关系，则S也是A上的一个等价关系。
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)}，证明：若f是A到B的满射，则g是从B到A
2的单射。
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
2016离散数学练习题 (答案修改)
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 ）个顶点。
离散数学期末试题
离散数学考试试题（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 。
离散数学考试试题(A卷及答案)
离散数学考试试题（A卷及答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。 三、（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 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。 正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。 解设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. 命题“对于任意给定的正实数，都存在比它大的实数”令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 =， }},{},{{3c b a S =，}},,{{4c b a S =，}}{},{},{{5c b a S =，}},{},{{6c a a S = 则A 的覆盖有 ，A 的划分有 。 11. 设}2,121{Z x x x x M ∈≤≤=整除，被，}3,121{Z x x x x N ∈≤≤=整除，被，则 =?N M ，=-N M 。 12. 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则B A ?= ，B A ο= 。 13. A={1，2，3，4，5，6}，A 上二元关系}|,{是素数y x y x T ÷><=，则用列举法 T= ； T 的关系图为 ，T 具有 性质。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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 ～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．设
离散数学期末考试试卷(A卷)
离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是
（１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分）
离散数学复习题
一、选择题： 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.
离散数学期末试卷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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。
离散数学试卷二十三试题与答案
试卷二十三试题与答案 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、?； C 、∈； D 、?。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=*； B 、),max(b a b a =*； C 、b a b a 5+=*； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（ ）可以构成无向简单图的结点度数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A 、5； B 、7； C 、9； D 、8。
离散数学 练习题七
9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={
离散数学期末试卷及答案
一．判断题（共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?{
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
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 ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(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 )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(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={
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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