离散数学集合论部分测试题
离散数学集合论部分综合练习
本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。
一、单项选择题
1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．
A．A?B，且A∈B B．A∈B，但A?B
C．A?B，但A?B D．A?B，且A?B
2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．
A．{a，{ a }}∈A B．{ a }?A
C．{2}∈A D．?∈A
3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )．
A．{a，{a}}∈A B．{2}?A
C．{a}?A D．?∈A
4．若集合A={a，b，{1，2 }}，B={1，2}，则（）．
A．B? A，且B∈A B．B∈ A，但B?A
C．B ? A，但B?A D．B? A，且B?A
5．设集合A = {1, a }，则P(A) = ( )．
A．{{1}, {a}} B．{?,{1}, {a}}
C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}
6．若集合A的元素个数为10，则其幂集的元素个数为（）．
A．1024 B．10 C．100 D．1
7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
A．自反的B．对称的
C．传递且对称的D．反自反且传递的
8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b∈A , 且a +b = 8}，则R具有的性质为（）．
A．自反的B．对称的
C．对称和传递的D．反自反和传递的
9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．
A．0 B．2 C．1 D．3
10．设集合A={1 , 2 , 3 , 4}上的二元关系
R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，
9．设A ={a ，b ，c }，B ={1，2}，作f ：A →B ，则不同的函数个数为 ．
三、判断说明题（判断下列各题，并说明理由．）
1．设A 、B 、C 为任意的三个集合，如果A ∪B =A ∪C ，判断结论B =C 是
否成立？并说明理由．
2．如果R 1和R 2是A 上的自反关系，判断
结论：“R -11、R 1∪R 2、R 1?R 2是自反的” 是否
成立？并说明理由．
3． 若偏序集的哈斯图如图一所示，
则集合A 的最大元为a ，最小元不存在． 4．若偏序集的哈斯图如图二所示，
则集合A 的最大元为a ，最小元不存在．
5．设N 、R 分别为自然数集与实数集，f ：N
→R ，f (x )=x +6，则f 是单射．
四、计算题 1．设集合A ＝{a , b , c }，B ={b , d , e }，求
（1）B ?A ； （2）A ?B ； （3）A －B ； （4）B ⊕A ．
2．设A ={{a , b }, 1, 2}，B ={ a , b , {1}, 1}，试计算
（1）（A -B ） （2）（A ∪B ） （3）（A ∪B ）-（A ∩B ）．
3．设集合A ={{1},{2},1,2}，B ={1,2,{1,2}}，试计算
（1）（A -B ）； （2）（A ∩B ）； （3）A ×B ．
4．设A ={0，1，2，3，4}，R ={
5．设A ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R 是A 上的整除关系，B ={2, 4, 6}．
（1）写出关系R 的表示式； （2）画出关系R 的哈斯图；
（3）求出集合B 的最大元、最小元．
6．设集合A ＝{a , b , c , d }上的二元关系R 的关系图 如图三所示．
（1）写出R 的表达式；
（2）写出R 的关系矩阵；
（3）求出R 2． 7．设集合A ={1，2，3，4}，R ={
（1）写出R 的有序对表示； （2）画出R 的关系图；
（3）说明R 满足自反性，不满足传递性．
五、证明题
1．试证明集合等式：A ? (B ?C )=(A ?B ) ? (A ?C )．
2．试证明集合等式A ? (B ?C )=(A ?B ) ? (A ?C )．
图一 图二
a d
b
c 图三
3．设R 是集合A 上的对称关系和传递关系，试证明：若对任意a ∈A ，存在b ∈A ，使得∈R ，则R 是等价关系．
4．若非空集合A 上的二元关系R 和S 是偏序关系，试证明：S R ?也是A 上的偏序关系．
参考解答
一、单项选择题
1．A 2．B 3．C 4．B 5．C 6．A 7．B 8．B 9．B 10．C 11．C 12．B 13．B
二、填空题
1．2n
2．{?,{a ,b },{a },{b }}
3．{<2, 2>，<2, 3>，<3, 2>}，<3, 3>
4．????
??????011000011 5．{, }
6．反自反的
7．{<1, 1>, <2, 2>}
8．{<1, a >, <2, b >}，{<1, b >, <2, a >}
9．8
三、判断说明题（判断下列各题，并说明理由．）
1．解：错．
设A ={1, 2}，B ={1}，C ={2}，则A ∪B =A ∪C ，但B ≠C ．
2．解：成立．
因为R 1和R 2是A 上的自反关系，即I A ?R 1，I A ?R 2。
由逆关系定义和I A ?R 1，得I A ? R 1-1；
由I A ?R 1，I A ?R 2，得I A ? R 1∪R 2，I A ? R 1?R 2。
所以，R 1-1、R 1∪R 2、R 1?R 2是自反的。
3．解：正确．
对于集合A 的任意元素x ，均有
（或xRa ），所以a 是集合A 中的最大元．
按照最小元的定义，在集合A 中不存在最
小元．
4．解：错误．
集合A 的最大元不存在，a 是极大元．
5．解：正确．
设x 1，x 2为自然数且x 1≠x 2，则有f (x 1)= x 1+6≠ x 2+6= f (x 2)，故f 为单射．
四、计算题
1．解：（1）B ?A ={a , b , c }?{b , d , e }={ b }
（2）A ?B ={a , b , c }?{b , d , e }={a , b , c , d , e }
（3）A －B ={a , b , c }－{b , d , e }={a , c }
（4）B ⊕A = A ?B －B ?A ={a , b , c , d , e }－{ b }={a , c , d , e }
2．解：（1）（A -B ）={{a , b }, 2}
（2）（A ∪B ）={{a , b }, 1, 2, a , b , {1}}
（3）（A ∪B ）-（A ∩B ）={{a , b }, 2, a , b , {1}}
3．解：（1）A -B ={{1},{2}}
（2）A ∩B ={1,2}
（3）A ×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，
<{2},{1,2}>，<1,1>，<1,2>，<1, {1,2}>，<2,1>，<2,2>,
<2, {1,2}>}
4．解：R =?,
S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>}
R ?S =?，
R -1=?，
S -1= S ，
r (R )=I A ．
5．解：（1）R =I ?{<1,2>, <1,3>, …, <1,12> ,
<2,4>, <2,6>, <2,8>, <2,10>, <2,12>, <3,6>, <3,9> ,
<3,12>, <4,8>, <4,12>, <5,10>, <6,12>}
（2）关系R 的哈斯图如图四
（3）集合B 没有最大元，最小元是：2 6．解：R ＝{, , ,
?????
???????=1000000001000101R M R 2 = {, , ,
7．解：（1）R ={<1,1>,<2,2>,<3,3>,<4,4>,
<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}
（2）关系图如图五
（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R ，
即A 的每个元素构成的有序对均在R 中，故R 在
A 上是自反的。
因有<2,3>与<3,4>属于R ，但<2,4>不属于R ，
所以R 在A 上不是传递的。 1 2 3 4 6 9 5 7 8 111图四：关系R 的哈
斯图 ? ? ? ? 1 2 3 4 图五
五、证明题
1．证明：设，若x ∈A ? (B ?C )，则x ∈A 或x ∈B ?C ，
即 x ∈A 或x ∈B 且 x ∈A 或x ∈C ．
即x ∈A ?B 且 x ∈A ?C ，
即 x ∈T =(A ?B ) ? (A ?C )，
所以A ? (B ?C )? (A ?B ) ? (A ?C )．
反之，若x ∈(A ?B ) ? (A ?C )，则x ∈A ?B 且 x ∈A ?C ，
即x ∈A 或x ∈B 且 x ∈A 或x ∈C ，
即x ∈A 或x ∈B ?C ，
即x ∈A ? (B ?C )，
所以(A ?B ) ? (A ?C )? A ? (B ?C )．
因此．A ? (B ?C )=(A ?B ) ? (A ?C )．
2．证明：设S =A ∩(B ∪C )，T =(A ∩B )∪(A ∩C )， 若x ∈S ，则x ∈A 且x ∈B ∪C ，即 x ∈A 且x ∈B 或 x ∈A 且x ∈C ，
也即x ∈A ∩B 或 x ∈A ∩C ，即 x ∈T ，所以S ?T ．
反之，若x ∈T ，则x ∈A ∩B 或 x ∈A ∩C ，
即x ∈A 且x ∈B 或 x ∈A 且x ∈C
也即x ∈A 且x ∈B ∪C ，即x ∈S ，所以T ?S ．
因此T =S ．
3．设R 是集合A 上的对称关系和传递关系，试证明：若对任意a ∈A ，存在b ∈A ，使得∈R ，则R 是等价关系．
证明：已知R 是对称关系和传递关系，只需证明R 是自反关系．
?a ∈A ，?b ∈A ，使得∈R ，因为R 是对称的，故∈R ； 又R 是传递的，即当∈R ，∈R ?∈R ；
由元素a 的任意性，知R 是自反的．
所以，R 是等价关系．
4．若非空集合A 上的二元关系R 和S 是偏序关系，试证明：S R ?也是A 上的偏序关系．
证明：.① S R x x S x x R x x A x ?>∈?<>∈<>∈<∈?,,,,,，所以S R ?有自反性； ②,,A y x ∈?因为R ，S 是反对称的，
y
x x y y x S x y S y x R x y R y x S x y R x y S y x R y x S R x y S R y x =?=∧=?>∈<∧>∈<∧>∈<∧>∈∈<∧>∈<∧>∈<∧>∈<∧?><),,(),,(),,(),,(,, 所以，R ?S 有反对称性． ③ A z y x ∈?,,，因为R ，S 是传递的，
S R z y S R y x ?>∈<∧?>∈<,,
S z y R z y S y x R y x >∈<∧>∈<∧>∈<∧>∈?<,,,,
S z y S y x R z y R y x >∈<∧>∈<∧>∈<∧>∈?<,,,, S R z x S z x R z x ?>∈?<>∈<∧>∈?<,,,
所以，S R ?有传递性．
总之，R 是偏序关系．
华南农业大学期末考试试卷（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
一、填空 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 的关系图为
离散数学常考题型梳理 第2章关系与函数 一、题型分析 本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括： 2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。 2-3等价关系 2-4偏序关系和哈斯图 2-5 函数的概念和性质 因此，在本章学习过程中希望大家要清楚地知道： 1．有序对和笛卡尔积 （1）有序对：所谓有序对就是指一个有顺序的数组，如< x , y >，x , y的位置是确定的，且< a , b >< b , a >。 （2）笛卡尔积：把集合A，B合成集合A×B，规定： {,|} ?=<>∈∈ 且 A B x y x A y B 由于有序对< x , y >中x，y 的位置是确定的，因此A×B 的记法也是确定的，不能写成B×A 。 笛卡儿积的运算一般不满足交换律。 2．二元关系的概念和表示、几种特殊的关系和关系的运算 （1）二元关系的概念：二元关系是一个有序对集合，设集合A，B ，从集合A 到B的二元关系 R∈ x ∈ < y =且 > } , x {B | y A 记作xRy。 二元关系的定义域：A Ram? R ) (。 ) R Dom? (；二元关系的值域：B 二元关系R 是一个有序对组成的集合．因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集合是由有序对元素组成的，才能当做二元关系。 常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。
《离散数学》期末复习题 一、填空题（每空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、设
《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
一、单项选择题(本大题共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 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={ 安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设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 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈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 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学考试试题（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是自反关系，所以 离散数学集合论部分测试题 离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={ 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF大学离散数学期末重点知识点总结(考试专用)
安徽大学期末试卷离散数学上卷及参考答案.doc
离散数学考试试题(A卷及答案)
离散数学集合论部分测试题
离散数学考试试题(A、B卷及答案)
相关主题
文本预览