离散数学模拟题3

模 拟 试 题 3 一. 有两个小题

1．分别说明联结词?、∧、∨、→以及?的名称，以及在自然语言中表示什么含义。 2．分别列出P?Q、P?Q、P?Q、P?Q的真值表(填下表)。 P

二．有三个问题

1.先说明什么叫永真式(也叫重言式)。

2.指出下面的命题公式中哪些是永真式(只写题号即可)。 (1). (P∨Q)→P (2). P→(P∨Q) (3). (P∧(P→Q))→Q (4). (P∧Q)→Q

3.然后对上面的永真式任选其中一个给予证明(方法不限)。

三．判断下面命题的真值。对你的回答，给予证明或者举反例。

(1)．如果A∈B，B?C，则 A?C 。 (2)．空集是唯一的。

四．R是实数集合，给定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={<1,1>,<1,2>,<1,3>,<3,3>} S={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>} T={<1,1>,<2,1>,<2,2>,<2,3>,<3,3>} M=Ф(空关系)

N=A×A(完全关系（全域关系）) 1. 分别画出上述各个关系的有向图。

2. 用“√”表示“是”，用“×”表示“否”，填下表： R 自反的 反自反 对称的 反对称 传递的 Q P?Q P?Q P?Q P?Q S T M N

3. 上述五个关系中，哪些是等价关系？哪些是偏序关系？是等价关系，写出相应的商集。是偏序关系，画出相应的哈斯图，以及A的极小元、极大元、最小元、最大元、上界与下界。 4. 分别求复合关系 R?S 和闭包t(R) 七.

1．R是实数集合，给出R上的运算：+、－、×、max、min、|x-y，分别表示加法、减法、乘法、两个数中取最大的、两个数中取最小的、x-y的绝对值运算。用“√”表示“是”，用“×”表示“否”，判断这些运算的性质，填下表：

有交换性 有结合性 有幂等性 有幺元 有零元 + － × max min |x-y| 2．设是群，而a∈G，f：G?G是映射定义为： 对?x∈G, 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) 此图是欧拉图但不是汉密尔顿图。 (3) 此图是汉密尔顿图但不是欧拉图 。 (4) 此图是完全图K5。 (5) 此图是棵树。

模拟试题3参考答案 一．1．

(1) “?”叫做否定 。 (2) “∧” 叫做合取。

(3) “∨”叫做析取。 (4) “?”叫做蕴涵、条件。 (5) “?” 叫做等价、双条件。 “?”表示：“…不成立”，“不…”。

“∧”表示：“并且”、“不但…而且...”、“既…又 ...”、“尽管…还… ” “∨”表示“或者”， 是可兼取的或。

“?”表示 如果… ，则 …；只要… ，就 …； 只有… , 才…； 仅当 … 。 “?”表示“当且仅当”、“充分且必要” 2．

P F F T T Q F T F T P∧Q F F F T P∨Q F T T T P?Q T T F T P?Q T F F T 二．1．A(P1,P2,…,Pn) 是含有命题变元P1,P2,…, Pn的命题公式，如不论对P1,P2,…, Pn作任何指派，都使得A(P1,P2,…,Pn) 为真，则称之为重言式，也称之为永真式。

2．命题公式2、3、4是永真式。

3．证明公式4：设前件(P∧Q)为真，则得Q为真。所以. (P∧Q)→Q是永真式。

三．1．F，例A={1} B={{1}} C={{1},2}，满足A∈B, B?C ，但是不满足A?C。 (因为1∈A 但1?C )。

2．证明 假设有两个空集Φ1 、Φ2 ，则

因为Φ1是空集，由于空集是任何集合的子集，所以 Φ1 ?Φ2。

因为Φ2是空集，类似得 Φ2 ?Φ1 。所以Φ1=Φ2 。所以空集是唯一的。

四．R1、R3和R5不是从R到R的函数。

R1：当x≤0时，没有相应的y对应，又当x>0时，对应的y值不唯一。所以它不是从R到R的函数。 R3：当x＝－1时，没有相应的y对应，所以它不是从R到R的函数。

R5：当|x|>2时，没有相应的y对应，又当|x|<2时，对应的y值不唯一。所以它不是从R到R的函数。 从R到R的入射函数的分别是R2 、R4 ；是从R到R的双射函数的分别是R2 。 五． ⑴ ?x P(x) P

⑵ P(a) ES ⑴ ⑶ ?x(?P(x)? R(x))? P ⑷ ?P(a)? R(a) US ⑶ ⑸ R(a) T⑵⑷ I ⑹ ?x(Q(x)??? R(x)) P ⑺ (Q(a)??? R(a)) US ⑹ ⑻ ?Q(a) T ⑸ ⑺ I ⑼ ?x ?Q((x) EG ⑻