离散数学期末考试试卷(A卷)
一、判断题:(每题2分,共10分)
(1)
(1)
(2)对任意的命题公式, 若, 则
(0)
(3)设是集合上的等价关系, 是由诱导的上的等价关系,则。(1)
(4)任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。
(0)
(5)设是上的关系,分别表示的对称和传递闭包,则
(0)
二、填空题:(每题2分,共10分)
(1) 空集的幂集的幂集为()。
(2) 写出的对偶式()。
(3)设是我校本科生全体构成的集合,两位同学等价当且仅当他们在
同一个班,则等价类的个数为(),同学小王所在
的等价类为()。
(4)设是上的关系,则满足下列性质的哪几条:自反的,对称的,传递的,反自反的,反对称的。
()
(5)写出命题公式的两种等价公式( )。
三、用命题公式符号化下列命题(1)(2)(3),用谓词公式符号化下列命题(4)(5)(6)。(12分)
(1)(1)仅当今晚有时间,我去看电影。
(2)(2)假如上午不下雨,我去看电影,否则就在家里读书。
(3)你能通你能通过考试,除非你不复习。
(4)(4)并非发光的都是金子。
(5)(5)有些男同志,既是教练员,又是国家选手。
(6)(6)有一个数比任何数都大。
四、设,给定上的两个关系和分别是
(1)(1)写出
和 的关系矩阵。(2)求 及 (12分) 五、求
的主析取范式和主合取范式。(10分)
六、设
是 到 的关系, 是 到 的关系,证明: (8分)
七、设 是一个等价关系,设 对某一个 ,有
,证明:
也是一个等价关系。(10分) 八、(10分)用命题推理理论来论证 下述推证是否有效?
甲、乙、丙、丁四人参加比赛,如果甲获胜,则乙失败;如果丙获胜,则乙也获
胜,如果甲不获胜,则丁不失败。所以,如果丙获胜,则丁不失败。
九、(10分) 用谓词推理理论来论证下述推证。
任何人如果他喜欢步行,他就不喜欢乘汽车,每一个人或喜欢乘汽车,或喜欢骑
自行车(可能这两种都喜欢)。有的人不爱骑自行车,因而有的人不爱步行 (论
域是人)。
十、(8分) 利用命题公式求解下列问题。
甲、乙、丙、丁四人参加考试后,有人问他们,谁的成绩最好,
甲说:“不是我,”乙说:“是丁,”丙说:“是乙,”
丁说:“不是我。” 四人的回答只有一人符合实际,问若只有一人成绩最
好,是谁?
离散数学期末考试试卷答案(A 卷)
一、判断题:(每题2分,共10分)
(1)}}{{}{x x x -∈ ( ∨)
(2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? )
(3)设R 是集合A 上的等价关系, L 是由
R A 诱导的A 上的等价关系,则L R =。 ( ∨ )
(4) 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等
价。 ( ? )
(5)设R 是A 上的关系,)(),(R t R s 分别表示R 的对称和传递闭包,则
)()(R st R ts ? ( ? )
二、填空题:(每题2分,共10分)
(1) 空集的幂集的幂集为 ( }},{{φφ)。
(2) 写出)()(R P Q P →∧∨的对偶式( )()(R P Q P ∧?∨∧ )。
(3)设A 是我校本科生全体构成的集合,两位同学等价当且仅当他们在
同一个班,则等价类的个数为(我校本科生的班级数 ),同学小王所在
的等价类为(小王所在的班的集合)。
(4)设},,,{},,,{><><==3121321R A 是A 上的关系,则R 满足下列性质的哪
几条:自反的,对称的,传递的,反自反的,反对称的。 ( 传递的,反自反的,反对称的 )
(5)写出命题公式Q
P ?的两种等价公式( )()()()(P Q Q P P Q Q P ∨?∧∨?→∧→)。
三、用命题公式符号化下列命题(1)(2)(3),用谓词公式符号化下列命题
(4)(5)(6)。(12分)
(3)(1)仅当今晚有时间,我去看电影。
解:P: 今晚我有时间. Q: 我去看电影
P Q →
(4)(2)假如上午不下雨,我去看电影,否则就在家里读书。
解 P: 上午下雨, Q: 我去看电影 R: 我在家里读书。
)()(R P Q P →∧→? (3)你能通你能通过考试,除非你不复习。
解 P 你能通过考试, Q: 你复习.
P Q →
(7)(4)并非发光的都是金子。
解 x x A :)(是发光的, x x B :)(是金子
))()()((x B x A x →??
(8)(5)有些男同志,既是教练员,又是国家选手。
解 x x A :)(是男同志,x x B :)(是教练员,x x C :)(是国家选手
)()()()((x C x B x A x ∧∧?)
(9)(6)有一个数比任何数都大。
解 x x A :)(是数,x y x B :),(比y 大,
))),()()(()()((y x B y A y x A x →?∧?
四、设},,,{d c b a A =,给定A 上的两个关系R 和L 分别是
)}.,(),,(),,(),,(),,(),,{()},,(),,(),,{(c d a d c c a c b b d a L a c c b b a R ==
(2)(1)写出R 和L 的关系矩阵。(2)求L R 及)(L R t (12分)
解
????????????=0000100000100100R M ????????????=1010101001000001L M
????????????=0000000110100100L
R M ????????????=00000000010110102)(L R M
????????????=00000000101001013)(L R M
????????????=00000000010110104)(L R M ????????????=0000000111111111)
(L R t M 五、求))(())((R Q P R Q P ?∧?→?∧∧→的主析取范式和主合取范式。(10分)
解∑?∏??∨∨∧∨?∨∧∨?∨∧∨?∨?∧?∨∨?∧∨∨???∨?∨∧∨?∨∧?∨?∨∧∨?∨∧
∨?∨?∧∨∨?∧?∨∨?∧∨∨???∨∧?∨∧∨?∧∨???∧?∨∧∧∨???∧?→?∧∧→706
54321,,,,,,)
()()()
()()()
()()()()()()()()
()()()())
(())(())
(())((R Q P R Q P R Q P R Q P R Q P R Q P Q R P Q R P R Q P R Q P R Q P R Q P R Q P R Q P R P Q P R P Q P R Q P R Q P R Q P R Q P 六、设T
是X 到Y 的关系,S 是Y 到Z 的关系,证明:c c c T S S T =)((8分)
证明:
c
c c c c T S x z S y z T x y Y y y S z y T y x Y y y S
T z x S T x z >∈?<>∈<∧>∈<∧∈??>∈<∧>∈<∧∈??>∈?<>∈<,)
,,)(()
,,)((,)(,
七、设R 是一个等价关系,设:,{><=b a S 对某一个c ,有},,,R b c R c a >∈<>∈<且,证明:S 也是一个等价关系。(10分)
证明:(1) 对任一A x ∈, 因为R 在A 上是自反的,
所以R x x >∈<,. 由S 的定义,
(3)(2)对任意A y x ∈,,若,,S y x >∈<则对于某个c
使得,,,R y c R c x >∈<∧>∈<因为R 对称的,故有:,,,R x c R c y >∈<∧>∈<由S 的定义可知:,,S x y >∈<
所以S 是对称的。
(3)对任意A z y x ∈,,,若S y x >∈<,及,,S z y >∈<
则必存在某个1c ,使得,,,R y c R c x >∈<∧>∈<11由R 传递性,可知R y x >∈<,,同理存在2c 使得,,,R z c R c y >∈<∧>∈<22由R 传递性,可知R z y >∈<,。 再由S 的定义,得,,S z x >∈<故 S 是传递的。
综上可知,S 是A 上的等价关系。
八、(10分)用命题推理理论来论证下述推证是否有效?
甲、乙、丙、丁四人参加比赛,如果甲获胜,则乙失败;如果丙获胜,则乙也获胜,如果甲不获胜,则丁不失败。所以,如果丙获胜,则丁不失败。
解:
设A :甲获胜。B :乙获胜。
C :丙获胜。 D:丁获胜。
前提为:D A B C B A →??→?→,,
结论为:D C →
(1)B A ?→ P
(2) A B ?→ (1)T,E
(3) D A →? P
(4) D B → (2)(3)T,I
(5) B C → P
(6) D C → (5)(4)T,I
九、(10分) 用谓词推理理论来论证下述推证。
任何人如果他喜欢步行,他就不喜欢乘汽车,每一个人或喜欢乘汽车,或喜欢骑自行车(可能这两种都喜欢)。有的人不爱骑自行车,因而有的人不爱步行 (论域是人)。
解:设P(x):x 喜欢不行。Q(x)喜欢乘汽车。
R(x):x 喜欢骑自行车。
本题符号化为:)),()()(()),()()((x R x Q X x Q X P X ∨??→?
)()()()(x P x x R x ?????
(1) )()(x R x ?? P
(2) )(c R ? (1)ES
(3) ))()()((x R x Q X ∨? P
(4) )()(c R c Q ∨ (3) US
(5) )(c Q (2)(4)T,I
(6) ))()()((x Q X P X ?→? P
(7) ))()(c Q c P ?→ (6)US
(8) )(c P ? (5)(7)T,I
(9) )()(x P x ?? (8)EG
十、(8分) 利用命题公式求解下列问题。
甲、乙、丙、丁四人参加考试后,有人问他们,谁的成绩最好,
甲说:“不是我,”乙说:“是丁,”丙说:“是乙,”
丁说:“不是我。” 四人的回答只有一人符合实际,问若只有一人成绩最
好,是谁?
解:设A:甲的成绩最好,B:乙的成绩最好,
C:丙的成绩最好,D:丁的成绩最好。
因为四人的回答只有一人符合实际,故
T D B D A D B D A D B D A D B D A ??∧?∧?∧∨∧?∧?∧∨∧?∧∧∨∧?∧?∧?)()
(()()(
即 T D B A D B A ??∧?∧∨∧?∧)()(
但 )()()
()()
()(C D B A C D B A C D B A C D B A D B A D B A ?∧?∧?∧∨∧?∧?∧∨?∧∧?∧∨∧∧?∧??∧?∧∨∧?∧
故有(一)甲、丙、丁三人并列成绩最好。
(二)甲、丁并列成绩最好。
(三)甲、丙并列成绩最好。
(四) 甲的成绩最好。
只有一人成绩最好的是甲。
华南农业大学期末考试试卷(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
《离散数学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的补元( ).
《离散数学》试卷(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人同时选修三门课程。问 (1)三门课程都不选的学生有多少? (2)只选修计算机课程的学生有多少?
系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院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.整环不一定是域. ( )
安徽大学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 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分)使用等值演算法判断公式下列公式的类型。 离散数学试题(B卷答案1) 一、证明题(10分) 1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((P∨Q)∧R)∨((Q∨P)∧R) ((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2) x (A(x)B(x))xA(x)xB(x) 证明:x(A(x)B(x))x(A(x)∨B(x)) x A(x)∨xB(x) xA(x)∨xB(x) xA(x)xB(x) 二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R)) (P∧(Q∨R))∨(P∧Q∧R) (P∧Q)∨(P∧R))∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R) m0∨m1∨m2∨m7 M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D,(C∨D)E, E(A∧B),(A∧B)(R∨S)R∨S证明:(1) (C∨D) E ?P (2) E(A∧B) ??P (3) (C∨D)(A∧B) T(1)(2),I (4) (A∧B)(R∨S)??P (5) (C∨D)(R∨S) ? T(3)(4),I (6) C∨D P (7) R∨S T(5),I 2) x(P(x)Q(y)∧R(x)),xP(x)Q(y)∧x(P(x)∧R(x)) 证明(1)xP(x) P (2)P(a) T(1),ES (3)x(P(x)Q(y)∧R(x)) P (4)P(a)Q(y)∧R(a) T(3),US (5)Q(y)∧R(a) T(2)(4),I (6)Q(y) T(5),I (7)R(a) T(5),I (8)P(a)∧R(a) T(2)(7),I (9)x(P(x)∧R(x)) T(8),EG (10)Q(y)∧x(P(x)∧R(x)) T(6)(9),I 四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解:A,B,C分别表示会打排球、网球和篮球的学生集合。则|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。 先求|A∩B|。 ∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3。 于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C)(10分)。 证明:∵x A-(B∪C) x A∧x(B∪C) xA∧(xB∧x C) (x A∧x B)∧(x A∧xC) x(A-B)∧x(A-C) x(A-B)∩(A-C) ∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={河海大学文天学院09级离散数学期中考试试卷答案
离散数学期末考试试题及答案