05级离散数学期末考试题

05级离散数学期末考试题一（共35分，每小题5分）1、已知A={0,1},B={a,b,c}，求AB。2、对给定的A=B=R并且f=x3，判断是否构成函数f:A→B，如果是，说明是否为单射、满射、双射的；如果不是说明理由。3、组数3,3,3,4能成为无向图的度数列吗?为什么？4、已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数。5、判断下图是否为欧拉图？是否有欧拉通路？为什么6、用真值表判定公式(┐P→Q)∧P的类型。7、将下列命题符号化“人都是要死的。”（令F(x):x是人,G(x):x是要死的。）二、（共15分）1、（10分）设“。”运算为Q上的二元运算，x,yQ,x。y=x+y+2xy,(1)判断“。”运算是否满足交换律和结合律，并说明理由。(2)求出“。”运算的单位元、零元和所有可逆元素的逆元。2、（5分）设V1=Q,+,V2=Q*,，其中Q*=Q{0}，令f:QQ*,f(x)=ex，证明f是V1到V2的同态映射。三、（共24分，每小题8分）1、已知偏序集A,R的哈斯图如下图所示,试求出集合A和关系R的表达式.；并求出A的极小元、最小元、极大元、最大元。2、给定集合A={1,2,3,4}，B={2,3,4}，C={1,2,3}，设R是A到B的关系；S是B到C的关系。其中R={x,y│x+y=6}，S={x,y│x-y=1}。求RS。3、设A={a,b,c,d},A上的关系,R={‹a,a›,‹a,b›,‹b,d›,‹c,a›,‹d,c›},求R的关系矩阵、关系图、domR、ranR、R–1。四、（共12分）求:(1)图G（如图所示）的邻接矩阵。(2)v1到v4,v4到v1长为3的通路各有多少条?(3)v1到自身长为1,2,3,4的回路各有多少条?(4)长为4的通路共有多少条?其中有多少条回路?(5)长度小于等于4的回路共有多少条?(6)写出D的可达矩阵?五、（共10分，每小题5分）1、构造下面推理的证明前提：如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。结论：羊不吃草。2、在自然推理系统F中，构造下面推理的证明前提：x(F(x)G(x))，x(F(x)∧H(x))结论：x(G(x)∧H(x))六、（4分）设S，*是有限可交换独异点，若对于所有的a,b,cS，有a*b=a*cb=c，试证明S，*是一个阿贝尔群。v1v2v3v4