离散数学模拟题3

《离散数学模拟题3》由会员分享，可在线阅读，更多相关《离散数学模拟题3（7页珍藏版）》请在装配图网上搜索。

1、离散数学模拟题3 - 教育文库 模 拟 试 题 3 一. 有两个小题 1分别说明联结词?、以及?的名称，以及在自然语言中表示什么含义。 2分别列出P?Q、P?Q、P?Q、P?Q的真值表(填下表)。 P 二有三个问题 1.先说明什么叫永真式(也叫重言式)。 2.指出下面的命题公式中哪些是永真式(只写题号即可)。 (1). (PQ)P (2). P(PQ) (3). (P(PQ)Q (4). (PQ)Q 3.然后对上面的永真式任选其中一个给予证明(方法不限)。 三判断下面命题的真值。对你的回答，给予证明或者举反例。 (1)如果AB，B?C，则 A?C 。 (2)空集是唯一的。 四R是实数集合，给定

2、R上的五个关系如下: R1=|x=y2 R2=|y=x+6 R3=|y=(x+1)-1 R4=|y=2x R5=|x2+y2=4 上述五个关系中，哪些不是从R到R的函数，为什么？如果是函数，则哪些是从R到R的入射函数？哪些是从R到R的双射函数？ 五用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。 ?xP(x), ?x(Q(x)? R(x), ?x(?P(x)? R(x)? ?x? Q(x) 六给定集合A=1,2,3,定义A上的关系如下： R=, S=, T=, M=(空关系) N=AA(完全关系（全域关系）) 1. 分别画出上述各个关系的有向图。 2. 用“”表示“是

3、”，用“”表示“否”，填下表： R 自反的 反自反 对称的 反对称 传递的 Q P?Q P?Q P?Q P?Q S T M N 3. 上述五个关系中，哪些是等价关系？哪些是偏序关系？是等价关系，写出相应的商集。是偏序关系，画出相应的哈斯图，以及A的极小元、极大元、最小元、最大元、上界与下界。 4. 分别求复合关系 R?S 和闭包t(R) 七. 1R是实数集合，给出R上的运算：+、max、min、|x-y，分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y的绝对值运算。用“”表示“是”，用“”表示“否”，判断这些运算的性质，填下表： 有交换性 有结合性 有幂等性 有幺元 有零元

4、 + max min |x-y| 2设是群，而aG，f：G?G是映射定义为： 对?xG, f(x)=a?x?a-1 首先证明求f：G?G是双射；再证明f是G到G的自同构映射。 八下面具有五个元素的格中，哪些是分配格？ a 九有二个小题。 b c d e 1. 给定图的集合G=A,B,C,D,E,F,H,K,M,N,R,S,T,V,W,X,Y,其中各个图如下所示，请指出这些图中哪些是彼此同构的。 2. 有两个小题 1) 分别说明什么叫欧拉图、汉密尔顿图、完全图Kn以及树。 2) 请画出五个具有五个结点的无向图，使之分别满足： (1) 此图既是欧拉图也是汉密尔顿图。 (2) 此图是欧拉图但不是汉密

5、尔顿图。 (3) 此图是汉密尔顿图但不是欧拉图 。 (4) 此图是完全图K5。 (5) 此图是棵树。 模拟试题3参考答案 一1 (1) “?”叫做否定 。 (2) “” 叫做合取。 (3) “”叫做析取。 (4) “?”叫做蕴涵、条件。 (5) “?” 叫做等价、双条件。 “?”表示：“不成立”，“不”。 “”表示：“并且”、“不但而且.”、“既又 .”、“尽管还 ” “”表示“或者”， 是可兼取的或。 “?”表示 如果 ，则 ；只要 ，就 ； 只有 , 才； 仅当 。 “?”表示“当且仅当”、“充分且必要” 2 P F F T T Q F T F T PQ F F F T PQ F T T

6、T P?Q T T F T P?Q T F F T 二1A(P1,P2,Pn) 是含有命题变元P1,P2, Pn的命题公式，如不论对P1,P2, Pn作任何指派，都使得A(P1,P2,Pn) 为真，则称之为重言式，也称之为永真式。 2命题公式2、3、4是永真式。 3证明公式4：设前件(PQ)为真，则得Q为真。所以. (PQ)Q是永真式。 三1F，例A=1 B=1 C=1,2，满足AB, B?C ，但是不满足A?C。 (因为1A 但1?C )。 2证明 假设有两个空集1 、2 ，则 因为1是空集，由于空集是任何集合的子集，所以 1 ?2。 因为2是空集，类似得 2 ?1 。所以1=2 。所以空集

7、是唯一的。 四R1、R3和R5不是从R到R的函数。 R1：当x0时，没有相应的y对应，又当x0时，对应的y值不唯一。所以它不是从R到R的函数。 R3：当x1时，没有相应的y对应，所以它不是从R到R的函数。 R5：当|x|2时，没有相应的y对应，又当|x|, t(R)= , 七1 有交换性 有结合性 有幂等性 有幺元 有零元 2证明： a) 证明f是满射：任取yG，因aG a-1G a-1?y?aG , 令x= a-1?y?a , 则 f(x)=a?x?a-1=a?(a-1?y?a)?a-1=(a?a-1)?y?(a?a-1) =y 所以 f是满射的。 b) 证明f 是入射的：任取x1,x2G，

8、设 f(x1)=f(x2) 即 a?x1?a-1=a?x2?a-1由群可消去性得 x1=x2 f是入射的。 所以f是双射的 + max min |x-y| 3 2 1 c) 再证f满足同构等式：任取x1,x2G， f(x1?x2) = a?(x1?x2)?a-1 = a?(x1?e?x2)?a-1=a?(x1?(a-1?a)?x2)?a-1 = (a?x1?a-1)?(a?x2?a-1 )= f(x1)?f(x2) 所以f是G到G的自同构。 八 a,d,e是分配格。 九1解:同构的有:AR ,BD , CMSW , EFTY , H , KX , VN。 21）欧拉图、汉密尔顿图、完全图Kn以及树的定义 同学们看书。 2）a)：既是欧拉图也是汉密尔顿图。 b) 是欧拉图但不是汉密尔顿图。 c)：是汉密尔顿图但不是欧拉图 。d)：是完全图K5。 e)：是棵树。 a) b) c) d) e) 第 7 页 共 7 页