离散数学模拟题2.docVIP

模 拟 试 题 2 一.填空 令P: 天气好. Q: 我有时间. R: 我在家. S: 我上街. L(x)： x是运动员； J(x)：x是教练。A(x,y)：y指导x 。 用上面给定符号将下面各个命题的符号表达式填在各个命题后面的括号内. ⑴ 天气不好,我就在家。 ( ) ⑵ 或者我上街,或者我在家。 ( ) ⑶不是所有运动员都是教练。 ( ) ⑷每个运动员都受到一些教练的指导。 ( ) 二. 令P表示小张去，Q表示小李去，用最简捷的语言说明公式 ( (Ｐ∧Ｑ)→((Ｐ∨((Ｐ∨Ｑ)) 所表达的含义。 三. 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 (x(A(x)(((B(x)((C(x))), (x(A(x)(((C(x)(D(x))), (x(A(x)((D(x)) ( (x(A(x)((B(x)) 四. 两个小题 1．括号内填入适当的符号，使得下面表达式成立。 设E是全集，A、B、C是任意集合，则 ⑴ A( ~E=( ) ⑵ A(A=( ) ⑶ ~A－A =（ ） ⑷ A－B( )A ⑸ A－B=A( )~B ⑹ A( )~A=E 2．证明吸收律： 对任何集合A、B，有 A∪(A∩B)=A 。 五．有五个小题。 1．是否有这样的关系，该关系同时具有自反性、对称性、反对称性、传递性？如果没有，说明理由。如果有，请画一个有3个结点的关系的有向图，使之同时具有上述性质。 2．分别说明等价关系和偏序关系的定义。 3．令A＝{1,2,3,4}，画A中两个关系的有向图，使之分别满足： (1) R是等价关系，对应商集A/R＝{{1,2},{3},{4}}。 (2) S是偏序关系，且其哈斯图是链。 4．已知A＝{1,2,3,4}，A中关系： R1={1,1, 1,2,2,2,2,4,3,3,4,2} R2={2,2,4,1,2,3,3,2,1,1} 分别求复合关系的逆(R1oR2)c和R2的传递闭包t(R2)。 六．有两个小题。 1． 令f和g都是实数集合R上的函数,如下: f={x,y|x,y∈R∧y=3x+1 } g={x,y|x,y∈R∧y= x2 + x} 分别求左复合函数： g( f 、 f(f。 2．已知f：:X(Y,和g:Y(Z都是满射的，证明g( f 也是满射的。 七．给定偏序集A,≤、B,≤、C,≤如下图所示，其中哪些不是格？为什么？ 八．有三个小题 1. 填空：令“*”是集合X上的二元运算，任意x,y,z∈X， 运算*有可交换性(（ ）。 运算*有可结合性(（ ）。 运算*有幂等性(（ ）。 运算*有有幺元e (（ ）。 运算*有有零元θ(（ ）。 2.说明什么群；然后列举一个你所熟悉的群，并具体说明它是群的理由。 3. 设G,(是个群 ,证明G中除幺元外,无其它幂等元。 九．有三个小题。 1．画出K4的所有不同构的生成子图。 2．一棵树有两个2度结点，三个3度结点，四个4度结点，问它有几个1度结点？要求有解题的过程。 3．根据给定一组权值:1,2,3,4,5,6,7,8,9,10 画出一棵最优完全三叉树。要求有画图的过程。 模拟试题2参考答案 一． ⑴ 天气不好,我就在家。 ( (Ｐ→R ) ⑵ 或者我上街,或者我在家。 ( SR 或者 （(S∧R) ∨ (S∧(R) ) ⑶不是所有运动员都是教练。 ( ((x(L(x)(J(x)), ) ⑷每个运动员都受到一些教练的指导。( (x(L(x)((y(J(x)(A(x,y))) ) 二．解：((P∧Q)→((P∨((P∨Q)) ((((P∧Q)∨(((P∨(P)∨Q) (E16, 结合) ((P∧Q)∨((P∨Q) (对合律，幂等律) ((P∧Q)∨(Q∨(P) (交换律) (((P∧Q)∨Q)∨(P (结合律) (Q∨(P (吸收律)