离散数学测试题一.选择题(10*2)1.设L (x ):x 是演员,J (y ):y 是老师,A (x ,y ):x 佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )(A) ),()(y x A x xL →∀ (B) ))),()(()((y x A y J y x L x ∧∃→∀ (C) )),()()((y x A y J x L y x ∧∧∃∀ (D) )),()()((y x A y J x L y x →∧∃∀2.令F(x):x 是有理数,G(x):x 是实数。
将命题“所有的有理数都是实数,但有的有实数不是有理数”符号化为 ( )A.∀x(F(x)∧G(x))∧∃x(G(x)→⌝F(x))B.∀x(F(x)→G(x))∧∃x(G(x)∧⌝F(x))C.∀x(F(x)∧G(x))∧∃x(G(x)∧⌝F(x))D.∀x(F(x)→G(x))∧∃x(G(x)→⌝F(x))3.设R 是集合A={a,b,c,d}上的二元关系,R={<a,a>,<a,b>,<a,c>,<a,d>,<c,b>,<d,b>,<d,c>},则R 具有关系的哪些性质( )A.自反性、反对称性B.反自反性、传递性C.自反性、对称性D.反对称性、传递性4.设A ={1,2},B ={a,b,c},C ={c,d},则A ×(B ∩C )为( )A .{},1,2,c c <><>B .{}1,,2,c c <><>C .{},1,,2c c <><>D .{}1,,,2c c <><>5.设A={a,b,c,d},A 上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A ,则对应于R 的A 的划分是( )A .{{a},{b,c},{d}}B .{{a,b},{c},{d}}C .{{a},{b},{c},{d}}D .{{a,b},{c,d}}6.设A ={a,b},则A 的幂集P (A )为( )A .{a,b}B .{Φ,{a},{b}}C .{Φ,{a,}}D .{Φ,{a},{b},{a,b}}7、设A , B , C 都是集合,如果A ⋂C =B ⋂C ,则有( )(A) A =B (B) A ≠B (C) 当A -C =B -C 时,有A =B (D) 当C =U 时, 有A ≠B8.集合A ={1,2,3,4,5,6,7,8,9,10},A 上的整除关系是一个偏序关系,则元素10是集合A 的( ).A .最大元;B .最小元;C .极大元;D .极小元9.设R 为实数集,映射f :R →R ,f (x )=-x 2+2x-1,则f 是( )A .单射而非满射B .满射而非单射C .双射D .既不是单射,也不是满射10.集合A={},,,a b c d ,A 上的一个划分{}{}{}{}1,,,a b c d π=,则对应的等价关系1R π=( )。
A .{,,,}A a b b a I <><>⋃B .{,,,,,,,}a b b a c c d d <><><><>C .{,,,,,,,}a a b b c c d d <><><><>D .{,,,}a b b a <><>二.填空题(10*1 每个空一分)1..设置F(x):x 为整数,G(x):x 是自然数,则命题“并不是每一个整数都是自然数”符号化为____________________。
2.集合的表示方法有两种: 法和 法。
3.设f ={<1,2>,<2,2>,<3,4>},g ={<2,5>,<3,1>,<4,2>},则f g =____________________。
4.Z 是整数集合,R 是Z 上的整除关系,则R 具有的性质是________________5.设集合A ={a,b,c,d},A 上的二元关系R ={<a,a>,<a,c>,<b,d>},则二元关系2R =_________________6.全集E ={1,2,3,4,5},A ={1,5},B ={1,2,3,4},C ={2,5},则A⋂ ~ B =____,P (A )⋂ P (C )=____________。
7.设R 是集合A 上的二元关系,如果关系R 同时具有________、对称性和________,则称R 是等价关系。
三.简答题1.试将一阶逻辑公式()()()()()x R y yQ y x yP x ∨⌝∃∨∃∃,化成前束范式。
2. 设R 和S 是集合}4,3,2,1{=A 上的关系,其中}4,4,4,2,3,2,2,1{}4,3,3,2,3,1,1,1{><><><><=><><><><=S R ,试求:(1)写出R 和S 的关系矩阵;(2)计算111,,,---⋃R S R S R S R 。
3、设集合A={1, 2, 3, 4, 6, 8, 12},R是A上的整除关系,1. 画出偏序集(A, R)的哈斯图;2. 写出A的子集{2, 4, 6, 8}的上界,下界,最小上界,最大下界;3. 写出集合A的最大元,最小元,极大元,极小元。
4. R={<x,y>|x≡y(mod3),x,y∈Z}是整数集合Z上模3的同余关系(Congruence Relation) ,可以证明R是等价关系,求各元素等价类及商集。
5.化简集合表达式:((A⋃B⋃C)⋂(A⋃C))-((C⋃(C-B)-A)6.设V1= <R+ ,×>:是正实数R+上的乘法×;V2=<R, +> :是实数R上的加法+。
令f: R+ R f(x)=lgx ,证明f是V1 到V2 的同构映射。
7.设S=R-{-1},S上定义运算*:a*b=a+b+ab,试证明<S,*>是群。
答案:一:BBDBD DCCDA二:1.∃x(F(x) ∧﹁G(x))2.列举;描述;3.{<3,2>,<4,2>}4.___自反性、反对称性和传递性__。
5_{<a,a>,<a,c>}_6 {5} {∅,{5}}7.自反性,传递性 三.1.解:()()()()()()()()()()()()()()()()()()x R z Q y x P z y x x R z Q z y x yP x x R y Q y y x yP x x R y yQ y x yP x G ∨⌝∨∀∃∃=∨⌝∀∨∃∃=∨⌝∀∨∃∃=∨⌝∃∨∃∃=,,,,2.解:(1)⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1000000011000010,0000100001000101S R M M (2)S R ⋅={<1,3>,<2 ,4>}S R ⋃={<1,1>,<1,2>,<1,3>,<2,3>,<2,4>,<3,4>,<4,4>} 1-R ={<1,1>,<3,1>,<3,2>,<4,3>}11--⋅R S ={<3,1>,<4,2>}3 . 集合A ={1, 2, 3, 4, 6, 8, 12}(1) 半序集(A, R)的哈斯图(2) 子集{2, 4, 6, 8}无上界,下界是1,2,无最小上界,最大下界是2.(3) A 无最大元,最小元是1,极大元是8, 12,极小元是1。
4.解:各元素等价类如下(其中k ∈Z):[0]={…,-6,-3,0,3,6,…}={x|x=3k}[1]={…,-5,-2,1,4,7,…}= {x|x=3k+1}[2]={…,-4,-1,2,5,8,…}= {x|x=3k+2}商集:Z /R ={[0],[1],[2]}={ {x|x=3k} , {x|x=3k+1} , {x|x=3k+2} } 5.((A ⋃B ⋃C )⋂(A ⋃C ))-((C ⋃(C -B )⋂~A )=(A ⋃C )-(C ⋂~A )(两次用吸收律)=((A ⋃C )⋂(~C ⋃A )=(A ⋂~C )⋃(C ⋂~C)⋃A ⋃(A ⋂C )=(A ⋂~C )⋃∅⋃A =A6.证明:(1)同态关系式x ,y ∈ R+ , f(x ×y)=lg(x ×y)=lgx+lgy=f(x)+f(y)(2)f 的性质单射性: x ,y ∈ R+ ,若x ≠ y ,则lgx ≠ lgy ;满射性: y ∈ R , x=10y ∈ R+ ,使得 f(x)=lg(10y)=y ; 综上知,f 是R+ R 上的双射函数,即V1 ≌ V27.证明:1)运算*在S 上封闭:任意a ,b ∈S ,有a*b=a+b+ab ∈R ,且a ≠ -1,b ≠ -1。
若a*b= -1即a+b+ab= -1,则a= -1或b= -1,与题设矛盾,故a*b ≠ -1. 所以a*b ∈S ,即运算*在S 上封闭。
2) 运算*满足结合律:任意a ,b ,c ∈S ,有(a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c=a+b+c+ab+ac+bc+abc,且a*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc)=a+b+c+ab+ac+bc+abc, 1 248 3 6 12所以,(a*b)*c=a*(b*c),即*满足结合律。
3) 存在幺元:若幺元e存在,则对任意a∈S,满足a*e=a a+e+ae=ae*a=a 即e+a+ea=a得 e = 0 ,即幺元存在且为0。
4) 每个元素存在逆元:对于任意a∈S,设a-1存在且a-1 ∈S ,则a*a^-1=0 a+a^-1+a*a^-1=0 a^-1*a=0 即a^-1+a+a^-1*a=0得a-1 =(-a)/(1+a) ∈S。
综上知<S,*>是群。