四川大学离散数学2012年期中测试题答案

离散数学期中测试题(开卷) 姓名： 学号：

1、 用等价变换法求下列公式的主析取范式和主合取范式

2 把下列语句翻译成谓词合适公式： 每个正整数是奇数，就不是2的倍数；每个正整数要么是偶数，要么与2 互素；有的正整数不与2互素，因此，有的正整数不是奇数。 解:

I(x):x是正整数；O(x):x是奇数；E(x):x是偶数；P(x):x与2互素。

((x)[O(x)→～E(x)]  (x)[ I(x)→(E(x) P(x))]  (x) [I(x) ～P(x)]) → (x) [I(x) ～O(x)]

3. 下列判断，正确还是错误：

① PQ P→Q （ 正确 ） ② (～QQ)→(P→P) （ 正确 ）

③ (x) [P(x)→Q(x)] (x) P(x)→(x)Q(x) （ 错误 ）

④ 不存在同时具有反自反性、对称性、传递性的二元关系(不考虑空关系) ( 正确 ) ⑤ 2A-B=2A-2B （ 错误 ） ⑥ f是A上的函数，如果xA,f2(x)=x，则f=IA（ 错误 ）

((pq)(pq))(qp)

((pq)(pq))(qp)q(qp)

(q(qp))((qp)q)(pq)q(pq) 主析取式(pq)(q(pp)

(pq)(qp)(qp) 主合取式

⑦ 5个元素集合上可定义的单射有25个。 （ 错误 ） ⑧ 若存在从A到B的满射，则card(B)  card(A) （正确） ⑨ 不存在具最大基数的集合 （正确）

4、求2，其中A={，a，{b}}；

解：2A={，{}，{a}，{{b}}，{,a}，{,{b}}，{a,{b}}，A}

5、 在正整数集上定义关系R：nRm当且仅当n/m或m/n是2(k是整数）的形式。证明Ｒ是等价关系。 证明：

因为对于任意正整数n, n/n=1=20, 所以nRn, 即R自反； 若nRm,即n/m=2k,则m/n=2-k, 即mRn, 所以R对称；

若nRm且mRj, 即n/m=2,且m/j=2, 所以n/j=2, 即nRj, 所以R传递。 由于R自反、对称且传递，所以R是等价关系。

6、如图是偏序集 

X ,  的哈斯图，求X和≤的集合表达式， 并指出该偏序集的极大元、极小元、最大元、最小元。 解：X={a,b,c,d,e,f}

≤={〈a,b〉,〈a,c〉, 〈a,d〉, 〈a,e〉, 〈a,f〉, 〈b,e〉, 〈c,e〉, 〈c,f〉, 〈d,f〉}∪ IX

极大元e,f；极小元a；最大元不存在，最小元a；

k

l

k+l

k

A

eb

f

d

7、构造下面推理的证明

前提: (x)[F(x)→(y)[G(y)∧H(x)]]， (x)F(x) 结论: x[F(x)∧G(x)∧H(x)]

证明：

1) xF(x) P 2) F(c) ES(1) 3) x(F(x)→y(G(y)∧H(x))) P 4) xy (F(x)→ (G(y)∧H(x))) TE(3) 5) y (F(c)→ (G(y)∧H(c))) US(4) 6) F(c)→ (G(c)∧H(c)) US(5) 7) G(c)∧H(c) TI(2)(6) 8) F(c)∧G(c)∧H(c) TI(2)(7) 9) x[F(x)∧G(x)∧H(x)] EG(8)

8、用逻辑推理规则证明

Ｐ→(Ｑ∨Ｒ)，Ｒ→Ｐ，Ｓ→ＱＰ→Ｓ 证明：

步骤 公式 规则 1) P P (附加) 2) Ｐ→(Ｑ∨Ｒ) P

3) Ｑ∨Ｒ TI(1)(2) 4) Ｒ→Ｐ P 5) P→R TE(4) 6) R TI(1)(5) 7) Q TI(3)(6) 8) Ｓ→Ｑ P

9) Ｑ→Ｓ TE(8) 10) S TI(7)(9) 11) Ｐ→Ｓ CP(1)(10)

9、设f、g都是集合A上的函数，证明当gf是双射时，f必是单射，g必是满射。  证明：

设f(x)=f(y), 则gf(x)= gf(y)，而gf是双射，所以x=y, 则f是单射。

因为gf是双射，所以gf是满射，所以yA, xA使gf(x)=y=g(f(x))，即y在g下像源是f(x),即g是满射。

10、 在一个道路网络上连接有8个城市，分别标记为a,b,c,d,e,f,g,h；城市之间的直接连接的道路有a→b,a→c,b→g,g→b,c→f,f→e,b→d,d→f。对每个城市求出从它出发能够到达的所有其它城市。

解：

令 S={a,b,c,d,e,f,g,h}, 定义S上的关系R 如下:〈x,y〉R  从a到b有一条直接的道路 R={〈a,b〉,〈a,c〉, 〈b,g〉, 〈g,b〉, 〈c,f〉, 〈f,e〉, 〈b,d〉, 〈d,f〉}, 求出R的传递闭包t(R) 即可获得问题的解。

00  0MR 0

0 0 0

1000001

1

0

01001

00010



00010



00000



0 010 0



00000

000

Mt(R)

0000000

1100001

1

1

01111

00110



00110



00000



0 010 0



01111

111

[a]={b，c，d，e，f，g} [b]={d，e， f，g} [c]={ e，f } [d]={ e，f } [e]=

[f]={e}

[g]={b，d，e，f，g}