当前位置：文档之家 › 离散试卷

离散试卷

  • 格式：doc
  • 大小：58.17 KB
  • 文档页数：3

离散试卷
一：选择题 （30）

1、下列是真命题的有（ C D ）
A． }}{{}{aa； B．}}{,{}}{{；
C． }},{{； D． }}{{}{。
2、设A={1，2，3}，则A上的二元关系有（ C ）个。

A． 23 ； B． 32 ； C． 332； D． 223。
3、下列语句不是命题的有（ D ）。
A、 x=13；
B、 离散数学是计算机系的一门必修课；
C、明天会下雨；
D、你打算考硕士研究生吗？
4、下列公式是重言式的有（ B ）。

A、)(QP；B、QQP)(；C、PPQ)(；D、PQP)(
5、一棵树有7片树叶，3个3度结点，其余全是4度结点，
则该树有（ A ）个4度结点。

A、1； B、2； C、3； D、4 。

6设集合A={1，2，3，4，5}上偏序关系的Hass图为 A

则子集B={2，3，4}的最大元（ ）；最小元（ ）；极大元（ ）；
极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下
确界（ ）。
A、 无，4，2、3，4，1，1，4，4； B、无，4、5，2、3，4、5，1，1，4，4；
C、无，4，2、3，4、5，1，1，4，4； D、无，4，2、3，4，1，1，4，无。
7、下列等价式成立的有（ ）。
A、PQQP；B、RRPP)(；
C、 QQPP)(； D、RQPRQP)()(。

8．设R是实数集合，“”为普通乘法，则代数系统 不是（ ）。
A．群； B．独异点； C．半群 ； D．广群。
9．对于集合A={x∣-10A．+； B．—； C．∣x-y∣； D．∣x∣。

10．下列各图中，能够被一笔画出的是 ( ).

二：填空题 （40）
1．设}4,}3{,,2{aA，}1,4,3,}{{aB，请在下列每对集合中填入适当的符号
（,）： （1）}{a B , (2) }}3{,4,{a A。
2．设P，Q 的真值为0，R，S的真值为1，则)()))(((SRPRQP的真
值为 1 。
3.Ｐ→Ｑ=

4. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；
“虽然你努力了，但还是失败了”的翻译为 。

5. 设R为集合A上的关系，则t（R）= 。
6.若R 是集合A上的偏序关系，则R满足 。
7.如果有一台计算机，它有一条加法指令，可计算四数的和。现有28个数需要计算和，它
至少要执行 次这个加法指令。
8、设G是n阶完全图，则G的边数m= 。

三：计算题（18）
1．一棵树有三个结点度数为2，两个结点度数为3，两个节点度数为4，问它有几片树叶。
2．假设在10名青年中有5名是工人，7名是学生，其中兼具工人与学生双重身份的青年有

3名，问既不是工人也不是学生的青年有几名？
3．求出公式RQP)(的主合取范式，并指出使公式成T的真值指派。
四：证明题 （12）

1；证明 RQPRPQP,)()( 等价。

110101100
110101100
)()()()()()())()(())()(()()()()()()())()(())()(()()()()(MMMRQPRQPRQPRQPRQPRQPQQRPRRQPRPQPRQPRQPMMMRQPRQPRQPQQRPRRQPRPQPRPQP










2：如果R、S都是集合X上的等价关系，证明SR也是等价关系
任何X属于A (X,X)属于R (X,X)属于S 所以属于R∩S (自反性)
若 (X,Y)属于R∩S 则 (X,Y)属于R (X,Y)属于S 所以 (Y,X)属于R
(Y,X)属于S 所以(Y,X)属于R∩S (对称性)
若 (X,Y)属于R∩S (Y,Z)属于R∩S 所以(X,Y)属于R (Y,Z)属于R 所以
(X,Z)属于R 同理 (X,Z)属于S 所以 (X,Z)属于R∩S (传递性)
所以R∩S是A上的等价关系

合集下载

离散数学考试试卷

离散数学考试试卷

离散数学考试试卷一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．下列语句中不是命题的只有（）A．或重于泰山，或轻于鸿毛。

B．鸡毛也能飞上天？C．不经一事，不长一智。

D．牙好，胃口就好。

2．从真值角度看，命题公式的全部类型是（）A．永真式 B．永假式C．永真式，永假式 D．永真式，永假式，可满足式3．设M（x）：x是人；F（x）：x要吃饭。

用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）A．B．C．D．4．下列公式是前束范式的是（）A．B．C．D．5．下列命题公式为重言式的是（）A．P→(P∨Q) B．(P ∨┐P) →QC．Q∧┐Q D．P→┐Q6.设P：我很累，Q：我去学习，命题：除非我很累，否则我就去学习的符号化正确的是：（）A．┐P∧Q B．┐P→QC．┐P→┐Q D．P→┐Q7.下列等价式正确的是：A．┐（x）A(x)〈＝〉（x）┐A(x)B．(x) (y) A(x) 〈＝〉（x）(y) A(x)C．┐(x) A(x) 〈＝〉（x）┐A(x)D．(x)( A(x) ∧B(x)) 〈＝〉(x) A(x) ∨(x) B(x)8.在公式（x）(y)P(x,y) ∧Q(z)) →（y）P(y,z)中变元y是（）姓名：＿＿＿＿＿＿得分：＿＿＿＿＿＿A.自由变元B.约束变元C.既是自由变元，又是约束变元D. 既不是自由变元，又不是约束变元9．下列各图是无向完全图的是（）10．下列各有向图是强连通图的是（）二、填空题（本大题共10小题，每小题2分，共20分）（1）能判断真假而不是可真可假的陈述句被称为________，真值只取两个值：________或________。

（2）所谓________是指不能再分解的命题，而复合命题是由一些________经过联结词复合而成的命题。

离散数学复习题

离散数学复习题

离散数学复习题一、单项选择题1.下列命题公式为重言式的是【 A 】。

A．p→(p∨q) B．(p∨┐p)→qC．q∧┐q D．p→┐q2．下列语句中不是．．命题的是【 A 】。

A．这个语句是假的。

B．1+1=1.0C．飞碟来自地球外的星球。

D．凡石头都可练成金。

3．设A={Φ，{1}，{1，3}，{1，2，3}}，则A上包含关系“⊆”的哈斯图为【 C 】4．在公式)QyzPyxP∧∀→x∃y∃中变元y是【 B 】。

(z()))y,(()())((,A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元5．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是【 D 】。

A．自反关系B．反自反关系C．对称关系D．传递关系6．图中从v1到v3长度为3 的通路有【 D 】条。

离散数学试卷（B）第1页（共6页）离散数学试卷（B ）第2页（共6页）A ．0；B ．1；C ．2；D ．3。

7．在下列代数系统中，不是环的只有【 C 】。

A ．<Z ，+，*)，其中Z 为整数集，+，*分别为整数加法和乘法。

B ．(Q ，+，*)，其中Q 为有理数集，+，*分别为有理数加法和乘法。

C ．<R ，+，*>，其中R 为实数集，+为实数加法，a*b=a+2b 。

D ．<M n (R)，+，*>，其中M n (R)为实数集n×n 阶矩阵结合，+，*是矩阵加法和乘法。

8．下列整数集对于整除关系都构成偏序集，而能构成格的是【 B 】。

A ．{l ，2，3，4，5} B ．{1，2，3，6，12} C ．{2，3，7}D ．{l ，2，3，7}9．结点数为奇数且所有结点的度数也为奇数的连通图必定是【 D 】。

A ．欧拉图 B ．汉密尔顿图 C ．非平面图D ．不存在的10．无向图G 是欧拉图当且仅当G 是连通的且【 C 】。

离散数学样卷参考答案

离散数学样卷参考答案

参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D 10.B二、填空1.主合取范式)()(q p q p ⌝∨∧∨⌝.前束范式))()((x G x F x →∀或))()((y G x F y x →∀∀ 2. n-k,93.=)(A ρ{Φ,{1}，{2}，{1，2}}，B A ⨯={〈1,a 〉,<1,b>,<2,a>,<2,b>}4. [b]R ={1,2,3}, X/R={{1,2,3},{4},{5}}.5． ,,G y x ∈∀ )()()(y f x f y x f *= 。

6.=-)(1R r { <2,1>,< 4,2>,<1,1>,<3,3>,<2,2>}，=S R {<1,4>,<2,2>}。

7.15，12.8. =τσ⎪⎪⎭⎫ ⎝⎛42134321 =(132) =-1στ⎪⎪⎭⎫ ⎝⎛41324321=(123) 9．0, 45 10．2,0三 1.× 2.√ 3. √ 4.× 5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。

试求其共有多少个结点？多少片叶？解: 设该树其有x 片叶,则顶点数为x+7, 根据树的性质知,该树有x+6边,由握手定理有:3*2+2*3+2*4+x*1=2(x+6), 得x=8故该树共有15个结点,8 片叶 .2.已知X={a,b,c},给出X 上的所有等价关系。

解:X 的划分其有五种:S 1={{a,b,c}}, S 2={{a,b},{c}}, S 3={{a,c},{b}}, S 4={{a},{b,c}},S 5={{a},{b},{c}},因为X 上划分与等价关系一一对应,故x 上共有五个等价关系，它们是：R 1＝{<a,b>,<b,a>,<a,c><c,a>,<b,c>,<c,b>}X I ⋃R 2＝{<a,b>,<b,a>}X I ⋃, R 3＝{<a,c><c,a>}X I ⋃R 4＝{<b,c>,<c,b>}X I ⋃, R 5＝X I3.．画一棵权为2，3，3，4，5，6，7，8 的最优二叉树，并计算出它的树权。

离散数学期末试卷(4套附答案)

离散数学期末试卷(4套附答案)

一、单项选择题（每小题3分，共30分）1．下列为两个命题变元ｐ，ｑ的最小项的是（ ） A ．ｐ∧ｑ∧⎤ ｐB ．⎤ ｐ∨ｑC ．⎤ ｐ∧ｑD ．⎤ ｐ∨ｐ∨ｑ 2．下列句子不是命题的是（ ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的D ．太好了！3．对于公式(∀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 )4．7．集合A={1，2，…，10}上的关系R={（x ，y ）|x +y =10，x ∈A ，y ∈A}，则R 的性质是（ ）A ．自反的B ．对称的C ．传递的、对称的D ．反自反的、传递的 5．设论域为{l ，2}，与公式)(x xA ∃等价的是( ) A.A (1)∨A (2)B. A (1)→A (2)C.A (1)D. A (2)→A (1)6. 下列关系矩阵所对应的关系具有反自反性的是（ ） A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101100001 C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0010101017. 下列运算不满足．．．交换律的是（ ） A ．a *b =a+2bB ．a *b =min(a ,b )C ．a *b =|a -b |D ．a *b =2ab8．.设A 是奇数集合，下列构成独异点的是( ) A.<A ，+> B.<A ，-> C.<A ，×> D.<A ，÷> 9. 右图的最大入度是( ) A ．0 B ．1 C ．2D ．3第9题图拟题学院（系）： 高密校区 适用专业： 学年 2学期 离散数学 （Ｂ卷） 试题标准答案10. 设有向图D 的节点数大于1，D=（V ,E ）是强连通图，当且仅当（ ） A. D 中至少有一条通路 B. D 中至少有一条回路C. D 中有通过每个结点至少一次的通路D. D 中有通过每个结点至少一次的回路 二、填空题(每空3分，共30分)1．设A ={1，2，3，4}，B ={2，4，6}，则A -B =________，A ⊕B =________。