离散数学期末考试题(附答案和含解析1)
一、填空
2．A ，B ，C
4．公式的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 在I 下真值为 1 。 6．设A={1，2，3，4}，A 上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。
//备注：
??????
?
??=0000100001010010
R
??????
?
?
?=00000000101001012
R
7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。
//备注：偏序满足自反性，反对称性，传递性
8．图
的补图为 。
//补图:给定一个图G,又G 中所有结点和所有能使G 成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a ，b ，c ，d} ，A 上二元运算如下：
那么代数系统的幺元是 a ，有逆元的元素为 a,b,c,d ，它们的逆元分别为 a,b,c,d 。 //备注：二元运算为x*y=max{x,y}，x,y ∈A 。 10．下图所示的偏序集中，是格的为 c 。
//（注：什么是格？即任意两个元素有最小上界 和最大
下界的偏序）
二、选择题
1、下列是真命题的有（ C 、D ）
A ． ；
B ．；
C ．
； D ．。
2、下列集合中相等的有（ B 、C ）
P R S R P ?∨∧∨∧)()()()(R S P R S P ∨?∨?∧∨∨?)()(x xP x xP ?→?}}{{}{a a ?}}{,{}}{{ΦΦ∈Φ}},{{ΦΦ∈Φ}}{{}{Φ∈Φ
A ．{4，3}；
B ．{，3，4}；
C ．{4，，3，3}；
D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ C ）个。 A ． 23 ； B ． 32 ； C ．
； D ． 。
//备注：A 的二元关系个数为：
2
n 2
个。
4、设R ，S 是集合A 上的关系，则下列说法正确的是（ A ） A ．若R ，S 是自反的， 则是自反的； B ．若R ，S 是反自反的， 则是反自反的； X C ．若R ，S 是对称的， 则是对称的； X D ．若R ，S 是传递的， 则是传递的。 X //备注：设R={<3,3>,<6,2>},S={<2,3>}, 则R S
={<6,3>} , S
R ={<2,3>}
5、设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下
，则P （A ）/ R=（ D ）
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 上包含关系“”的哈斯图为（ C ）
//例题：画出下列各关系的哈斯图 1）
P={1,2,3,4},
2）A={2,3,6,12,24,36},
7、下列函数是双射的为（ A ） //双射既是单射又是满射 A ．f : I E , f (x) = 2x ； B ．f : N N N, f (n) =
//备注：分别是v1->v1->v1->v3，v1->v4->v1->v3，v1->v3->v1->v3
A ．0；
B ．1；
C ．2；
D ．3。
Φ?ΦΦ332?2
23
?S R S R S R S R |}|
|(|)(,|,{t s A p t s t s R =∧∈><=ΦΦ?→→?→→
9、下图中既不是Eular （欧拉）图，也不是Hamilton （哈密顿）图的图是（ B ）
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ A ）个4度结点。 A ．1；
B ．2；
C ．3；
D ．4 。
//备注：树的顶点数=边数+1 7+3×3+4n=2（7+3+n-1） 解得n=1 三、证明题
1、R 是集合X 上的一个自反关系，求证：R 是对称和传递的，当且仅当< a, b>和在R 中有在R 中。 证： “”
若由R 对称性知，由R 传递性得 “” 若
，有 任意 ，因若 所以R 是对称的
若
， 则 即R 是传递的
2、f 和g 都是群
证明
证：
，有 ，又
★★
3）条边围成的连通平面图，则 ， 由此证明彼得
森图（Peterson ）图是非平面图。（11分） 证：
①设G 有r 个面，则
，即
。而
故
即得
。（
8分）
②彼得森图为
，这样不成立，
所以彼得森图非平面图为：
?X c b a ∈?,,R >c ,a <,>b ,a <∈R a ,c <,>a ,b <∈>R >c ,b <∈?R >b ,a <∈R >c ,a <∈R >c ,b <∈X b a ∈,R >a ,a <∈R
>b ,a <∈R >a ,b < ∈∴R >b ,a <∈R >c b,<∈R c b, R >a b,<>∈<∧∈R >c ,a < ∈∴)}()(|{1x g x f G x x =∈且C b a ∈?,)()(),()(b g b f a g a f ==)
()(,)()(111
1
b g b g b f
b f ----==)()()()(111
1----===∴b g b g b f
b f a f (∴a g b g a g b f a f b ()(*)()(*)()111===---)1-b -12)
2(--≤
k v k e rk
F d e r
i i ≥=∑=1
)(2k e
r 2≤
2=+-r e v k e
e v r e v 22+
-≤+-=2)2(--≤
k v k e 10,15
,5===v e k 2)
2(--≤
k v k e
四、逻辑推演
1、用CP 规则证明下题
①
P （附加前提）
②
US①
③ P ④
US③
⑤
T②④I ⑥
UG⑤ ⑦
CP
五、计算题
1、设集合A={a ，b ，c ，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R 的传递闭包t (R)。 解：
， ，
，
t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }
)()())()((x xQ x xP x Q x P x ?→??→?)(x xP ?)(c P ))()((x Q x P x →?)()(c Q c P →)(c Q )(x xQ ?)()(x xQ x xP ?→???
???
??
?
?=00001
00001010010R M ????
?
?? ??==00000000101
001012R R R M M M ???
????
??==000000000101101023R R R M M M ???
??
??
?
?==000000001010
0101
3
4R R R M M M ???
????
??=+++=00001000111
11111432)(R R R R R t M M M M M
华南农业大学 离散数学 期末考试2013试卷及答案
华南农业大学期末考试试卷（A 卷） 2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业 ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分） 1、下面语句是简单命题的为_____。 A 、3不是偶数 B 、李平既聪明又用功 C 、李平学过英语或日语 D 、李平和张三是同学 2、设 p:他主修计算机科学, q:他是新生，r:他可以在宿舍使用电脑，下列命题“除非他不是新生，否则只有他主修计算机科学才可以在宿舍使用电脑。”可以符号化为______。 A 、r q p →?∧? B 、r q p ?→∧? C 、r q p →?∧ D 、r q p ∧→ 3、下列谓词公式不是命题公式P →Q 的代换实例的是______。 A 、)()(y G x F → B 、),(),(y x yG y x xF ?→? C 、))()((x G x F x →? D 、)()(x G x xF →? 4、设个体域为整数集，下列公式中其值为 1的是_____。 A 、)0(=+??y x y x B 、)0(=+??y x x y C 、)0(=+??y x y x D 、)0(=+???y x y x
2 5、下列哪个表达式错误_____。 A 、 B x xA B x A x ∧??∧?)())(( B 、B x xA B x A x ∨??∨?)())(( C 、B x xA B x A x →??→?)())(( D 、)())((x xA B x A B x ?→?→? 6、下述结论错误的是____。 A 、存在这样的关系，它可以既满足对称性，又满足反对称性 B 、存在这样的关系，它可以既不满足对称性，又不满足反对称性 C 、存在这样的关系，它可以既满足自反性，又满足反自反性 D 、存在这样的关系，它可以既不满足自反性，又不满足反自反性 7、集合A 上的关系R 为一个等价关系，当且仅当R 具有_____。 A 、自反性、对称性和传递性 B 、自反性、反对称性和传递性 C 、反自反性、对称性和传递性 D 、反自反性、反对称性和传递性 8、下列说法不正确的是：______。 A 、R 是自反的，则2R 一定是自反的 B 、R 是反自反的，则2R 一定是反自反的 C 、R 是对称的，则2R 一定是对称的 D 、R 是传递的，则2R 一定是传递 9、设R 和S 定义在P 上，P 是所有人的集合，=R {x P y x y x ∧∈><,|,是y 的父亲}，=S {x P y x y x ∧∈><,|,是y 的母亲}，则关系{y P y x y x ∧∈><,|,是的x 外祖父}的表达式是：______。 A 、11--R R B 、11--S R C 、11--S S D 、11--R S 10、右图描述的偏序集中，子集},,{f e b 的上界为_____。 A 、c b , B 、b a , C 、b D 、c b a ,, 11、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A 、1，2，2，3，4，5
离散数学试卷及答案(2)
一、填空 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 的关系图为
《 离散数学》期中考试试卷(2006—2007学年第2学期)
《离散数学J》考试试卷（期中） 课程代码143140320命题单位学院：计算机学院信息教研室 学院:_______________班级:_____________姓名:_______________学号:____________ 1．将下列命题将其符号化。（4分） ①.李平不是不聪明，而是不用功。 假设p:李平聪明，q:李平用功 ②.如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 假设p：我懂得希腊文，q：我了解柏拉图 2．在一阶逻辑中将下列命题符号化。（9分） ①.整数都是有理数，并不是每个有理数一定是整数，有些有理数不是整数。 假设I(x)：x是整数，Q(x)：x是有理数。 ②.某些汽车比所有的火车慢。 假设F(x)：x是火车。G(x)：y是汽车。H(x,y)：x比y快 ③.谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。 假设：M(x)表示“x是人”，K(x)表示“x游戏人生”，L(x)表示“x 一事无成”，H(x,y)表示“x主宰y”，N(x)表示“x是奴隶”。 3．试证明： (┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R))=R(10分) 4．求公式G＝(P→Q)∧R的主析取范式和主合取范式。(12分) 5．先将些列论断符号化，再证明论断的正确性。（15分） 所有的大一学生都要学习英语；并非所有的大一学生都要学习离散数学；故有些学习英语的不学习离散数学。 假设谓词如下：P(x)：x是大一学生；Q(x)：x要学习英语； R(x)：x要学习离散数学。 6．某班学生50人，会排球的有40人，会篮球的35人，会足球的10人，以上三种运动都会的5人，都不会的没有，问只会两种运动的有几人？
中国石油大学大学《离散数学》期末复习题及答案
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
离散数学试卷及答案
一、单项选择题(本大题共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 系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 题 序 一 二 三 四 五 总分 成 绩 签 名 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}P(A) B ．{a}P(A) C ．{{a}}P(A) D ．{{a}}P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．01 B ．0011100000 C ．00 D ．00 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨q D ．r →p ∨q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ 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) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={ 1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={ 《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 离散数学考试试题（A卷及答案） 一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((P→Q)∧Q)?((Q∨R)∧Q) 2)?((Q→P)∨?P)∧(P∨R) 3)((?P∨Q)→R)→((P∧Q)∨R) 解：1)永真式；2）永假式；3)可满足式。 二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。 解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4）） ?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4）） ?（0∨0）∧（0∨1） ?1∧1?0 三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？ 解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。 四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。 解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>} 五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。 解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。 由容斥原理，得 |A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以 |A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。 六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R ∩S=[a]R∩[a]S。 解：?x∈A，因为R和S是自反关系，所以 2010-2011学年第一学期离散数学期中考试试卷答案 一、（本题满分12分）在命题逻辑中将下列命题符号化。 （1）小王边走路边听音乐。（2）除非a能被2整除，a才能被4整除。 （3）派小张、小李中的一人去开会。（4）小张和小李是同学。 （5）今天是星期一仅当明天是星期二。（6）若2+2≠4，则3+3≠6；反之亦然。 解：（1）令p：小王走路；q：小王听音乐。符号化为p∧q （2）令p：a能被2整除；q：a能被4。符号化为q→p （3）令p：派小张去开会；q：派小李去开会。符号化为（p∧┐q）∨（┐p∧q） （4）令p：小张和小李是同学。符号化为p （5）令p：今天是星期一；q：明天是星期二。符号化为p→q （6）令p：2+2=4；q：3+3=6。符号化为┐p?┐q 二、（本题满分12分）在一阶逻辑中将下列命题符号化。 （1）有的有理数能被2整除。（2）没有不犯错误的人。 （3）人都不一样高。（4）说火车比汽车跑的快是不对的。 （5）4>2与3≥1互为充要条件。（6）除非李键是东北人，否则他一定怕冷。解：（1）令F(x)：x为有理数；G(x)：x能被2整除。符号化为?x(F(x)∧G(x)) （2）令F(x)：x是人，G(x)：x犯错误，则命题符号化为：?x（F（x）→G(x)） （3）令F(x)：x是人；H(x,y)：x与y一样高。符号化为?x?y（F（x）∧F（y）→┐H（x，y））（4）令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快，┐?x?y（F（x）∧G（y）→H（x，y））（5）令F(x,y)：x>y，G(x,y):x≥y，a:4，b:2，c:3，d:1。符号化为F(a,b)?G(c,d) （6）令F(x)：x是东北人，G(x)：x怕冷，a：李键，符号化为┐G（a）→F（a） 三、（本题满分8分）给出公式(q →r) ∧ ( p→p)的真值表并求出成真赋值和成假赋值。解：真值表如下 成真赋值：000、001、011、100、101、111；成假赋值：010、110 四、（本题满分10分）设p:2能整除5，q:太阳从西方升起，r:一年分四季。求下列复合命题的真值： （1）((p ∨q) → r)∧(r→ (p ∧q)) （2）((┐q ?p) → (r ∨p)) ∨ ((┐p ∧┐q) ∧r) 解：由题意，p、q、r的真值分别为0、0、1。（1）的真值为0；（2）的真值为1。 五、（本题满分12分）使用等值演算法判断公式下列公式的类型。08计算机《离散数学》期中试卷答案
大学离散数学期末重点知识点总结(考试专用)
【浙江工商大学】《离散数学》期末考试题(B)
离散数学考试试题(A卷及答案)
河海大学文天学院09级离散数学期中考试试卷答案
相关文档
- 离散数学基础期中考试题
- 离散数学期中考试1
- 计算机《离散数学》期中试卷答案
- 离散数学期中考试题-0X-0X-2-A-试卷
- 《离散数学》期中试卷(2011年10月)及答案
- 离散数学期中考试题-参考试题(附答案)
- 2016-2017学年度第1 学期《离散数学》期中试卷
- 计算机离散数学期中试卷答案
- 离散数学期中考试
- 离散数学期中测试
- 离散数学期中考试题-参考试题(附答案)
- 离散数学期中试卷通关攻略
- 离散数学期中考试(3班4班)
- 河海大学文天学院09级离散数学期中考试试卷答案
- 第一学期《离散数学》期中考试
- 离散数学-期中复习考试
- 离散数学-期中试卷
- 北京大学 离散数学 2008下学期期中考试试题
- 离散数学期末考试试卷(A卷)
- 08计算机《离散数学》期中试卷答案