离散数学试题
第一部分选择题
一、单项选择题
1.下列就是两个命题变元p,q的小项就是( C )
A.p∧┐p∧q
B.┐p∨q
C.┐p∧q
D.┐p∨p∨q
2.令p:今天下雪了,q:路滑,则命题“虽然今天下雪了,但就是路不滑”可符号化为( D )
A.p→┐q
B.p∨┐q
C.p∧q
D.p∧┐q
3.下列语句中就是命题的只有( A )
A.1+1=10
B.x+y=10
C.sinx+siny<0
D.x mod 3=2
4.下列等值式不正确的就是( C )
A.┐(?x)A?(?x)┐A
B.(?x)(B→A(x))?B→(?x)A(x)
C.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)
D.(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)
5.谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域就是( C )
A.(?x)Q(x,z)→(?x)(?y)R(x,y,z))
B.Q(x,z)→(?y)R(x,y,z)
C.Q(x,z)→(?x)(?y)R(x,y,z)
D.Q(x,z)
6.设A={a,b,c,d},A上的等价关系R={
是( D )
A.{{a},{b,c},{d}}
B.{{a,b},{c},{d}}
C.{{a},{b},{c},{d}}
D.{{a,b},{c,d}}
7.设A={?},B=P(P(A)),以下正确的式子就是( A )
A.{?,{?}}∈B
B.{{?,?}}∈B
C.{{?},{{?}}}∈B
D.{?,{{?}}}∈B
8.设X,Y,Z就是集合,一就是集合相对补运算,下列等式不正确的就是( A )
A.(X-Y)-Z=X-(Y∩Z)
B.(X-Y)-Z=(X-Z)-Y
C.(X-Y)-Z=(X-Z)-(Y-Z)
D.(X-Y)-Z=X-(Y∪Z)
9.在自然数集N上,下列定义的运算中不可结合的只有( D )
A.a*b=min(a,b)
B.a*b=a+b
C.a*b=GCD(a,b)(a,b的最大公约数)
D.a*b=a(mod b)
02324# 离散数学试题第1 页共4页
02324# 离散数学试题 第 2 页 共4页
10、设R 与S 就是集合A 上的关系,R ∩S 必为反对称关系的就是( A )
A.当R 就是偏序关系,S 就是等价关系;
B.当R 与S 都就是自反关系;
C.当R 与S 都就是等价关系;
D.当R 与S 都就是传递关系
11、设R 就是A 上的二元关系,且R ·R ?R,可以肯定R 应就是( D )
A.对称关系;
B.全序关系;
C.自反关系;
D.传递关系
第二部分 非选择题
二、填空题
1.设论域就是{a,b,c},则(?x)S(x)等价于命题公式 S(a)∧S(b)∧S(c)
;(x ?)S(x)等价于命
题公式 S(a)∨S(b) ∨S(c)
。
2.设R 为A 上的关系,则R 的自反闭包r(R)= _R ∪A I _ ,对称闭包s(R)= _R ∪R ~
。
3.某集合A 上的二元关系R 具有对称性,反对称性,自反性与传递性,此关系R 就是 A I _ ,
其关系矩阵就是 只有主对角线上元素为1 。
三、计算题
1.(4分)如果论域就是集合{a,b,c},试消去给定公式中的量词:)0y x )(x )(y (=+??。
2.用等值演算求下面公式的主析取范式。)()(P Q Q P ∨?→→?
3.用等值演算法求公式)()(Q P Q P ?→?→?的主合取范式。
4.(6分)在偏序集
D={2,3,4,6}的极大元,极小元,最大元,最小元,最小上界与最大下界。
5.设集合A={1,2,3,4,5},A上的划分为π＝{{1,2,3},{4,5}},试求:
1)写出划分π诱导的等价关系R;
M;
2)写出关系矩阵R
3)画出关系图。
02324# 离散数学试题第3 页共4页
离散数学考试（试题及答案） 一、（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>}。
离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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
《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 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。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) (
7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f
《离散数学》模拟试题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) ? 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 ＝{，，，，，，，，
离散数学（上）模拟题 1、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数x，总存在y使得xy=1。 c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得 f(a)=b. 2、简答题（共6道题，共32分） 1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范 式，并写出所有成真赋值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) xy(x+y=4) b) yx (x+y=4) 3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （AB）－C=(A-B) (A-C) b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. 设A是有穷集，|A|=5，问（每小题2分，共4分） a) A上有多少种不同的等价关系？ b) 从A到A的不同双射函数有多少个？ 6. 设有偏序集
下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即 可）(6分) 3、证明题（共3小题，共计40分） 1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10 分） a) A→(B∧C),(E→F)→C, B→(A∧S)B→E b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x) 2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R 满足：<
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 ,则有向图 >= 常熟理工学院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．设 大学2013—2014学年度第二学期期末考试《离散数学》试卷 A 第一部分 选择题（共20 分） 一、单项选择题（本大题共10小题，每题只有一个正确答案，答对一题得2分共20分） 1、对任意集合A 、B 、和C ，下列论断中正确的是： 【 】 A. 若A ∈B ，B ?C ，则A ∈C B. 若A ∈B ，B ?C ，则A ?C C. 若A ?B ，B ∈C ，则A ∈C D. 若A ?B ，B ∈C ，则A ?C 2、设A={a,{a}},下列式子中正确的有： 【 】 A. {a}∈ρ(A) B. a ∈ρ(A) C. {a}?ρ(A) D. 以上都不是 3、P ：我将去镇上。Q ：我有时间。命题“我将去镇上，当且仅当我有时间”符号化为： 【 】A. P →Q B. Q →P C. P ?Q D. Q ∨?P 4、命题公式：（P ∧（P →Q ））→Q 是 【 】 A ．矛盾式 B. 可满足式 C. 重言式 D. 不能确定 5、谓词公式)())()((x Q y yR x P x →?∨?中，量词x ?的辖域是： 【 】 A. ))()((y yR x P x ?∨? B. )(x P C. )(),(x Q x P D. )()(y yR x P ?∨ 6、在如下各图中，哪一个是欧拉图？ 【 】 7、设|V|>1，G= < V , E >是强连通图，当且仅当： 【 】 A ．G 中至少有一条通路 B ．G 中至少有一条回路 C ．G 中有通过每个结点至少一次的通路 D ．G 中有通过每个结点至少一次的回路 8、设}}2,1{},1{,{Φ=S ，则 ρ(S) 有多少个元素？ 【 】 A ．3； B ．6； C ．7； D ．8 ； 9、集合A={1，2，3，4，5，6，7，8，9，10}上的关系R={ 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个 试卷二试题与参考答案 一、填空 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．设无向图G 的邻接矩阵为 ??????? ? ??? ?? ???010 1010010000 011100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ A．{(a, e)}是割边B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集 图三 7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )． 图四 A．（a）是强连通的B．（b）是强连通的 C．（c）是强连通的D．（d）是强连通的 应该填写：D 8．设完全图K n 有n个结点(n≥2)，m条边，当（）时，K n 中存在欧拉 回路． A．m为奇数B．n为偶数C．n为奇数D．m为偶数9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点 11．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树． A．1 m n-+B．m n-C．1 m n++D．1 n m -+ 12．无向简单图G是棵树，当且仅当( )． A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 《离散数学》模拟试题 一、 填空题（每小题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 →∧?=)( 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个 安徽大学20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 一、单项选择题（每小题2分，共20分） 1. 设:P 天没下雪，:Q 我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ D ） A.Q P ?→?； B. P Q ?→?； C.Q P ?∧； D. Q P ?∧?。 2.下列命题是重言式的是（ C ） A.)()(P Q Q P →∧→； B. )()(Q P P Q P ???∧； C. )(Q P Q P →→∧； D. Q P R Q P ∧?∧?∨→))((。 3. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):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 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 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 t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学题库
离散数学试卷
离散数学模拟试卷和答案
离散数学试题与答案
上海大学-离散数学2-图部分试题
离散数学模拟试题及答案
离散数学模拟试卷和答案
《离散数学》(上)试卷(A卷)及参考答案
离散数学全部试卷
相关主题
文本预览