当前位置:文档之家› 大学《离散数学》期末考试试卷及答案-(1)

大学《离散数学》期末考试试卷及答案-(1)

安徽大学2006-2007学年第1学期《离散数学》期末考试试卷(A卷)(时间120分钟)开课院(系、部)姓名学号.一、选择题(每小题2分,共20分)1.下列语句中,哪个是真命题()A、42=+x; B、我们要努力学习;C、如果ab为奇数,那么a是奇数,或b是偶数;D、如果时间流逝不止,你就可以长生不老。

2.下列命题公式中,永真式的是()A、PQP→→)(; B、PPQ∧→⌝)(; C、QPP↔⌝∧)(; D、)(QPP∨→。

3.在谓词逻辑中,令)(xF表示x是火车;)(yG表示y是汽车;),(yxL表示x比y快。

命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的()I.)),()()((y x L y G x F y x →∧∀⌝∀ II.)),()()((y x L y G x F y x ⌝∧∧∃∃ III. )),()()((y x L y G x F y x ⌝→∧∃∃A 、仅I ;B 、仅III ;C 、I 和II ;D 、都不对。

4.下列结论正确的是:( )A 、若C AB A =,则C B =; B 、若B A B A ⊆,则B A =;C 、若C A B A =,则C B =;D 、若B A ⊂且D C ⊂,则D B C A ⊂。

5.设φ=1A ,}{2φ=A ,})({3φρ=A ,)(4φρ=A ,以下命题为假的是( ) A 、42A A ∈; B 、31A A ⊆; C 、24A A ⊆; D 、34A A ∈。

6.设R 是集合},,,{d c b a A =上的二元关系,},,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。

下列哪些命题为真( )I.R R ⋅是对称的 II. R R ⋅是自反的 III. R R ⋅不是传递的A 、仅I ;B 、仅II ;C 、I 和II ;D 、全真。

7.R 是二元关系且4R R =,则一定是传递的是( ) A 、4R ; B 、3R ; C 、2R ; D 、R 。

8.设1R 和2R 是非空集合A 上的等价关系,确定下列各式,哪些是A 上的等价关系( )A 、1R A A -⨯;B 、21R R -;C 、21R R ;D 、21R R 。

9.函数:f X Y →可逆的充要条件是:( )A 、AB =; B 、||||A B =;C 、f 为双射;D 、f 为满射。

10.下列集合中,哪个集合的基数与其他集合的基数不同( ) A 、n N (N 为自然数集,N n ∈); B 、N N (N 为自然数集);C 、R R ⨯(R 为实数集);D 、x 坐标轴上所有闭区间集合;二、填空题(每小题2分,共32分)1.全集}5,4,3,2,1{=U ,}5,1{=A ,}4,3,2,1{=B ,}5,2{=C ,则可求出:=B A _________________________________;=)()(C A ρρ ___________________________;=C _____________________________________。

2.设3=A ,16)(=B ρ,64)(=B A ρ,则:B =______________________________,B A =__________________________,B A -=__________________________,B A ⊕=__________________________。

3.设}4,3,2,1{=A ,R 是A 上的二元关系,且}3,3,4,2,2,1{><><><=R ,则)(R r =________________________________________________;)(R s =________________________________________________;)(R t =________________________________________________;4.设A={1,2,3,4,5},则A 上共有多少个二元关系________________ 其中有多少个等价关系________________5.设函数A A f →:,A B ⊆为A 的子集。

则:))((1B ff -____________B ,))((1B f f-____________B ;当f 为__________函数时B B f f =-))((1; 当f 为__________函数时B B f f =-))((1。

三、综合题(第2小题16分,其它各小题8分,共48分)1.求命题公式P R Q P →⌝∨∧))((的主析取范式与主合取范式 (要求用等值演算的方法求解)。

(8分)2.用推理规则证明:(每小题8分,共16分) ①)(R Q P →→,P S ∨⌝,Q 永真蕴含R S →。

②前提:)))()(()((x R y Q x F x ∧→∀,)(x xF ∃;结论:))()((x R x F x ∧∃。

3.设集合},,{c b a A =,)(A ρ是集合A 的幂集,试给出⊆><),(A ρ的哈斯图,并指出子集}}{},{{b a 的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下届(如果存在的话)。

(8分)4.设R 是集合A 上的关系,令},,,,{R b c R c a A c b a S ∈><>∈<∈∃><=且使,证明:如果R 是等价关系,则S 也是等价关系。

(8分)5.已知N N N f →⨯:,22),(y x y x f +=><。

请问:(8分) ①f 是单射吗 ②f 是满射吗 ③计算})0({1-f 。

④计算})2,1,0,0({><><f 。

安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷答案(A 卷)(时间120分钟)一、选择题(每小题2分,共20分)1.C;;;;;;;;;二、填空题(每空2分,共32分)1.}5{;}}{φ;}4,3,1{5{,2.4,1,2,53.{<1,2>,<2,4>,<3,3>,<1,1>,<2,2>,<4,4>};{<1,2>,<2,4>,<3,3>,<2,1>,<4,2>};{<1,2>,<2,4>,<3,3>,<1,4>}4.252,525.⊆,满射,⊇,单射三、综合题(第2小题16分,其它各小题8分,共48分)1.∧⇔)∨(()P⌝QRPA→⌝∧)((⇔)∨⌝RPQP∨∨⌝⇔)⌝(()∧PRP∨Q⌝∧⇔)( 2分∨)(P∨RPQR∧⌝))()(()()(())()((R R Q Q P P P R Q Q Q R P ⌝∨∧⌝∨∧∨⌝∨∧∧⌝∨∨⌝∧∧⌝⇔ 4分 ∨∧⌝∧⌝∨∧⌝∧∨∧⌝∧⌝∨∧∧⌝⇔)()()()(R Q P R Q P R Q P R Q P )()()()(R Q P R Q P R Q P R Q P ⌝∧⌝∧∨∧⌝∧∨⌝∧∧∨∧∧ ∨∧∧∨∧⌝∧∨∧⌝∧⌝∨∧∧⌝⇔)()()()(R Q P R Q P R Q P R Q P )()(R Q P R Q P ⌝∧⌝∧∨⌝∧∧(主析取范式) 6分 )()(R Q P R Q P A ⌝∧∧⌝∨⌝∧⌝∧⌝⇔⌝∴ ))()(()(R Q P R Q P A A ⌝∧∧⌝∨⌝∧⌝∧⌝⌝⇔⌝⌝⇔)()(R Q P R Q P ∨⌝∨∧∨∨⇔(主合取范式) 8分2.①证明:(1) P S ∨⌝ P 1分 (2) S P (附加前提) 2分 (3) P T (1),(2) I 3分 (4) )(R Q P →→ P 4分 (5) R Q → T (3),(4) I 5分 (6) Q P 6分 (7) R T (5),(6) I 7分 (8) R S → CP (2),(7) 8分{c}{a,b②证明:(1) )(x xF ∃ P 1分 (2) )(c F ES (1) 2分 (3) )))()(()((x R y Q x F x ∧→∀ P 3分 (4) ))()(()(c R y Q c F ∧→ US (3) 4分 (5) )()(c R y Q ∧ T (2),(4) I 5分 (6) )(c R T (5) I 6分 (7) )()(c R c F ∧ T (2),(6) I 7分 (8) ))()((x R x F x ∧∃ EG (7) 8分3.解:⊆><),(A ρ的哈斯图如下图所示。

φ{a} {b}(2分);}}{},{{b a 的极大元是:}{},{b a ;极小元是:}{},{b a (4分);最大元不存在;最小元不存在(6分);上界有:},,{},,{c b a b a ;下界为:φ;最小上界为:},{b a ;最大下界为:φ(8分)。

4.证明:已知R 是等价关系,对S 是等价关系的证明分3步:(1)自反性R 是自反的,∴对A a ∈∀,有R a a >∈<,,根据S 的定义,有S a a >∈<,,∴S 是自反的;(2分)(2)对称性如果S b a >∈<,,则A c ∈∃,使R c a >∈<,且R b c >∈<,,R 是对称的,∴R c b >∈<,且R a c >∈<,,∴再根据S 的定义有S a b >∈<,,∴S 是对称的;(5分)(3)传递性如果S b a >∈<,,S c b >∈<,,则A d ∈∃使R d a >∈<,,且R b d >∈<,。

R 是传递的,∴R b a >∈<,。

则A e ∈∃使R e b >∈<,,且R c e >∈<,。

R 是传递的,∴R c b >∈<,。

∴根据S 的定义有S c a >∈<,。

∴S 是传递的。

(8分)由(1),(2),(3)得S 是等价关系。

5.解答:①N N ⨯>∈<><1,2,2,1,521)1,2()2,1(22=+=><=><f f ,但>>≠<<1,22,1,所以f 不是单射(2分)。

相关主题