《离散数学》复习题
7月无纸化考试复习专用（答案在试卷后） 一、单选题
1.下列式子正确的是 ( )。
A.p ?q = q ?p B.p ?q = ?q ? p
C.p ?q，q ?s ? p ?s D.p ?q = (p ? q) ? (q? p) 2.下列语句中，( )是命题。
A.请把门关上 B.地球外的星球上也有人 C.x + 5 > 6 D.下午有会吗？ 3.设G、H是一阶逻辑公式，P是一个谓词，G＝?xP(x), H＝?xP(x),则一阶逻辑公式G?H是( )。 A.恒真的 B.恒假的
C.可满足的 D.前束范式.
4.命题?xG(x)取真值1的充分必要条件是( )。
A.对任意x，G(x)都取真值1. B.有一个x0，使G(x0)取真值1. C.有某些x，使G(x0)取真值1. D.以上答案都不对.
5.设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是( )。
A.{2}?A B.{a}?A C.??{{a}}?B?E D.{{a},1,3,4}?B. 6.下列关于集合的表示中正确的为( )。
A.{a}?{a,b,c} B.{a}?{a,b,c} C.??{a,b,c} D.{a,b}?{a,b,c} 7.设简单图G所有结点的度之和为12，则G一定有 ( ) 条边。
A.3 B.4 C.5 D.6 8.设G是一棵树，则G 的生成树有 ( ) 棵
A.0 B.1 C.2 D.不能确定
二、填空题
1.已知命题公式G＝?(P?Q)∧R，则G的主析取范式是（ ）。 2.(?P?Q)?(?P??Q) = （ ）。
3.设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是（ ）。 4.设集合A,B，其中A＝{1,2,3}， B= {1,2}，则A - B＝（ ）
第1页，共1页
5.设有限集合A, |A| = n, 则 |?(A×A)| = （ ）。
6.设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x?R}, B = {x | 0≤x < 2, x?R},则A-B = （ ）， B-A = （ ），A∩B = （ ）。
三、简答题
1.证明((Q∧S) → R)∧(S→ (P∨R)) = (S∧(P→Q))→R
2. 试将?x((??yP(x，y))?(?zQ(z)?R(x)))化成等价的前束范式。
离散数学答案
一．单选题
1.C 2.B 3.C 4.A 5.C 6.B 7.D 8.B 二．填空题
1.(P∧ Q∧R) 2.?P 3.(R(a)∧R(b))→(S(a)∨S(b)) ≤x < 0, x R}; {x | 1 < x < 2, x R}; {x | 0≤x≤1, x R} 三．简答题
1.左边：((Q∧S)→R)∧(S→ (P∨R))
= (? (Q∧S)∨R)∧(?S∨(P∨R)) = (?Q∨?S∨R)∧(?S∨P∨R)
= (?Q∨?S∨R)∧(?S∨P∨R)
右边：(S∧(P→Q))→R
= ? (S∧(?P∨Q))∨R
第2页，共1页
4.{3}; 5.2n2 6.{x | -1 = (?S∨(P∧?Q))∨R = (?Q∨?S∨R)∧(?S∨P∨R)
所以 ((Q∧S) → R)∧(S→ (P∨R)) = (S∧(P→Q))→R. 2.?x?y?z (P(x，y) ? ?Q(z) ? R(x) )
《离散数学》Ｂ卷
一、单选题
1.设R为实数集，映射σ：R →R ，σ(x) = | 2x | -10，则σ是 ( )。 A.入射而非满射
B.满射而非入射 C.双射 D.既不是入射也不是满射
2.令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化为 ( )。 A.p → ┐q B.p∨┐q C.p∧q D.p∧┐q 3.下列式子正确的是 ( )。
A. p ?q = q ?p B. p ?q = ?q ? p
C. p ?q，q ?s ? p ?s D. p ?q = (p ? q) ? (q? p) 4.设I是如下一个解释：D＝{a,b}, ( )。
A.?x?yP(x,y) B.?x?yP(x,y) C.?xP(x,x) D.?x?yP(x,y). 5.命题?xG(x)取真值1的充分必要条件是( )。
A.对任意x，G(x)都取真值1. B.有一个x0，使G(x0)取真值1. C.有某些x，使G(x0)取真值1. D.以上答案都不对 6.设A, B为集合，当( )时A－B＝B。 A.A＝B
B.A?B
C.B?A
D.A＝B＝?.
P(a,a) P(a,b) P(b,a) P(b,b)则在解释I下取真值为1的公式是
1 0 1 07.设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( )。 A.自反性
B.传递性
C.对称性
D.反对称性
8.设G是连通平面图，有5个顶点，6个面，则G的边数是( )。 A.9条 B.5条
C.6条 D.11条
第3页，共1页
山东交通学院成人高等教育期末考试离散数学复习题
