2018-2019学年第一学期期末考试《离散数学》大作业

一、简要回答下列问题（每小题5分，共30分）

1、请给出集合的吸收率。

2、设A={1，2}，请给出A上的所有关系。

答：集合A上的全部关系有2^(2^2)=16种：空关系{}，全关系

{<1,1>,<1,2>,<2,1>,<2,2>}{<1,1>}{<2,2>}{<1,2>}{<2,1>}{<1,1>,<1,2>}{<1,1>,<2,1>}{<1,1>,<2,2>}{<1,2>,<2,1>}{<1,2>,<2,2>}{<2,1>,<2,2>}{<1,1>,<1,2>,<2,1>}{<1,1>,<1,2>,<2,2>}{<1,1>,<2,1>,<2,2>}{<1,2>,<2,1>,<2,2>}

3、什么是子句？请给出一例。

答：子句集S称为是可满足的，如果存在一个个体域和一种解释，使S中的每一个子句均为真，或者使得S的每一个子句中至少有一个文字为真。否则, 称子句集S是不可满足的

4、什么是前束范式？

答：前束范式亦称前束式，一种谓词演算公式。指其一切量词都未被否定地处于公式的最前端且其辖域都延伸至公式的末端的谓词演算公式。设Q∈{?，?}，一个公式α是前束范式，当且仅当存在一个不含量词的公式β，使得

α=(Q?x?)(Q?x?)…(Q?x?)β. 5、什么是谓词逻辑中的项？

答：谓词逻辑中的项指变项和常项，变项又分为自由变项和约束变项。 6、什么是命题公式的演绎？ 答：用A'表示非A,则 (A+B)'=A'B', (AB)'=A'+B'.

二、设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。（8分）

答：解：A 到B 上共有2mn 个二元关系。本题中A×B 的全部子集φ，{(a,1)}，{(a,2)}，{(b,1)}， {(b,2)}， {(a,1),(a,2)}，{(a,1),(b,1)}，{(a,1),(b,2)}，{(a,1),(b,2)}，{(a,2),(b,1)}，{(a,2),(b,2)}， {(a,1),(a,2),(b,1)}，{(a,1),(a,2),(b,2)}，{(a,1),(b,1),(b,2)}，{(a,2),(b,1),(b,2)}，{(a,1),(a,2),(b,1),(b,2)}为A 到B 的全部二元关系。

三、R，S是集合A上的两个关系。试证明下列等式：（10分）

（1）(R?S)= S?R

-1-1

（2）(R)= R

-1

-1

-1

证明：先证(R?S)--1?R-1，对任意(x，-1，则(y，

则存在，满足(y，且(a，，那么(x，-1且(a，，

-1，

2018-2019学年第一学期期末考试《离散数学》大作业

所以(x，对任意(x，所以(y，因此S-1?R--1?R-1，因此(R?S)--1?R-1；再证S-1?R--1?R-1，则存在，满足(x，-1且(a，且(a，，所以(y，，所以(x，

-1。

-1，-1，-1，

（2）(R-1)-1= R 证明：先证(R-1)-，对任意(x，-1)-1，则(y，-1，则(x，

，所以(R-1)-；再证-1)-1，对任意(x，，则(y，

-1，则(x，-1)-1，所以-1)-1。故(R-1)-1= R得证。

四、一公司在六个城市c1，c2，…，c6中的每一个都有分公司。从ci到cj的班机旅费由下列矩阵中的第i行第j列元素给出(?表示没有直接班机)：（12分）

0 50 ? 40 25 10 50 0 15 20 ? 25 ? 15 0 10 20 ? 40 20 10 0 10 25

25 ? 20 10 0 55 10 25 ? 25 55 0

公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。 解： C C1 0 C2 35 C1?C6 ?C2 C3 45 C1?C5 ?C3或 C1?C6 ?C4?C3或C1?C5 ?C4?C3 C2 35 C2?C6 ?C1 C3 45 C3?C4 ?C6 ?C1或 C3?C5 ?C1或C3?C4 ?C5?C1 C4 35 C4?C5 ?C1或 C4?C6 ?C1 15 C3?C2 0 15 C2? C3 0 20 C2?C4 10 C3?C4 30 C2?C4 ?C5 20 C3?C4 ?C5或C3?C5 25 C2?C6 35 C3?C4 ?C6 C4 35 C1?C5 ?C4或 C1?C6 ?C4 C5 25 C1?C5 C6 10 C1?C6 25 C4?C2 10 C4?C3 0 10 C4?C5 25 C4?C6 2018-2019学年第一学期期末考试《离散数学》大作业

C5 25 C5 ?C1 30 C5?C4 ?C2 20 C5?C4 ?C3或C5?C3 35 C6?C4 ?C3 10 C5 ?C4 0 35 C5?C4 ?C6或 C6 10 C6?C1 25 C6?C2 25 C6?C4 35 C6?C4 ?C5或 C6?C1 ?C5 C5?C1 ?C6 0

五、设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之等价的命题公式。（15分）

(1)?xR(x)??xS(x)

(2)?x(P(x)?Q(x)) (3)?x?P(x)??xP(x)

六、若R是等价关系，试证明R-1也是等价关系。（10分）

答：1.因为R是等价关系,所以 设x,y,z属于A,属于R；属于R并且属于R；若属于R且属于R,则属于R.

2.明显属于R的逆,满足自反性；属于R的逆 且属于R的逆,故满足对称性. 即属于R且属于R,即属于R的逆,故满足传递性. 即证R的逆也是等价关系. 七、设I是如下一个解释：（15分）

D={3，2}

a b f(3) f(2) P(3，3) P(3，2) P(2，3) P(2，2) 3 2 2 3 1 1 0 0 试求出下列公式在I下的真值：

（1） (a，f(a))?P(b，f(b))； （2） x?yP(y，x)；

（3） x?y(P(x，y)?P(f(x)，f(y)))； 解 （1） p( a,f(a))?p(b,f(b))

= p( 3，f(3))?p(2，f(2))= p(3,2)?p(2,3)= 1?0 (2) （2） ?x?P（y,x）

=?xP(3,x)?P(2,x)=(P(3,3) ?P(2,3) )?P(3,2) ?P(2,2))=(1?0) ?(1?0)=1?1=1.