离散数学期末作业本科

1 / 6

一、 命题逻辑部分

1．计算真值表、并由此写出主析取与主合取范式(一个命题公式的主范式具有唯一的表示形式，这样可以精减一个推理系统，去掉多余的等价的前提。其唯一性借助于小项或大项的设计，一个公式中所用到的小项或大项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。注意：真值表与公式有什么区别？

2．设 A 、B 是两个命题公式，证明：

a) A B 当且仅当A B 是永真式。b) A B 的充要条件是A B 且B A 。

等价与蕴涵是对两个公式进行比较的概念，性质b)说明两者之间的关系，相对而言蕴涵比等价更重要。与上面两个性质相关联的一个等价公式是：A B A →B ∧B →A.3．证明 P →(Q →R )?Q →(P →R )? ┐R →(Q → ┐P ) 4．证明从前提P →Q ，┐(Q ∨R)可演绎出┐P .

5．证明R →S 可从前提P →(Q →S)，┐R ∨P 和Q 推出。 ├ 6、使用推理规则或归结推理，论证推理形式 1) P →Q, R →?Q ,R ∨S, S →?Q ├?P

2)?P ?Q, S →?Q, ?R, R ∨S ├ P

二、 谓词逻辑

1、 写出谓词的含义、一个谓词公式的解释应包含什么内容？

1 1 1 1 1 1 1 1

1 1 1 1 0 0 1 1

1 1 1 1 0 0 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

((p →q ) →(?q →?p )) ∨r

?q →?p p →q p q r

谓词是命题中用于判断的部分，从语法上看就是陈述句的谓语部分，因而并不十分关注特定的个体，而是将个体作为一个变化的量来对待(类似于函数的自变量_函数形式)，当这个变化的量指定为一个固定的个体时，谓词转变为一个命题(类似于函数值)。所以，谓词的逻辑表达能力比命题更精细。

谓词概念的产生源于命题概念，因而，对其进行研究的基本内容和思路与命题相同，如谓词公式的基本构成方式，公式的等价与蕴涵，公式的判定等。

谓词公式的形式要复杂得多，因而研究方法及理论变得更加复杂，如个体变元可以是函数的形式_项，如量词“?”、“?”的引用，出现了等同赋值概念；对公式的判定问题成为不可解；推理理论更加复杂等。

2、并非一切劳动都能用机器代替。

解设L(x): x是一种劳动, M(x): x是一种机器,

R(x, y): x被y代替。命题表示为:

?(?x) (L(x) → (?y) (M(y)∧R(x,y)))

3、数学分析中函数f (x)在点a连续的定义为:对任意的ε>0, 存在一个δ>0, 使得对所有x,

若|x – a|<δ, 则|f (x) – f (a)|<ε, 符号化此定义。

解令R(x): x是实数, G(x, y): x大于y。

(?ε) ((R(ε)∧G(ε, 0)) → (?δ) (R(δ)∧G(δ, 0)∧(?x) ((R(x)∧G(δ, |x – a|))

→G(ε, |f (x) – f (a)| ) )))。

4、证明等价式：┐(?x)A?(?x)┐A

5、证明等价式：(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)

6、证明蕴含式：(?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x)

7、证明蕴含式：(?x)(?y)A(x，y)?(?y)(?x)A(x，y)

三、集合与关系

1、A?B?┐(B?A)

2、∪(A∪B)=(∪A)∪(∪B)

3、定理3.5.1对于任意集合S，有S?S。

证明：设有集合S使S ∈S，由此构造一个单元集{S}，显然S ∈{S}，即{S}不空。由正则公理可知{S}有极小元，而{S}只有元素S，故S∩{S}= ?。但由假设S ∈S，所以S∩{S} ≠ ?，矛盾。

4、定理3.5.2对任何集合S1和S2，都有┐(S1∈S2∧S2∈S1)。

证明：设S={S1，S2}，假设有(S1∈S2)∧(S2∈S1)，则S1 ∈(S2 ∩S)且S2 ∈(S1 ∩S)。于是S2 ∩S ≠ ?，S2 ∩S ≠ ?，而S1与S2都是S的极小元，故与正则公理矛盾。因此对对任何集合S1和S2，都有┐(S1∈S2∧S2∈S1)

5、一个集合A是传递集当且仅当A?P(A)。

6、从集合的观点来定义有序对={{x},{x,y}}，解释其合理性。

6、设R={，，}，试求r(R)，s(R)和t(R)

7、设R、S、T、W为关系，证明

1) (R?S)-1=R-1?S-1

2) R?S∧T?W ?R*T?S*W

3) R*(S?T)=(R*S)? (R*T)

4) (R*S)-1=S-1*R-1

2 / 6

8、设R是实数集合，定义R?R上关系Q：Q 当且仅当u+y=x+v，证明Q是R?R上等价关系。

9、习题35。

10、已知集合{a,b,c,d,e}上的一个关系R={,,,}，若将其中的有序对解释成为：从结点x到结点y的有向边连接，则关系R可表示为一个有向图模型，如下

1)计算关系R的传递闭包t(R)，并在上图中画出其余的连接边。

2)若用矩阵来表示关系R，写出M t(R)的形成过程。

四、代数部分

1、定理12.2.5给定且| S |＞1。如果θ，e∈S，其中θ和e分别为关于⊙的零元和幺元，则θ ≠ e。

2、定理12.2.6给定及幺元e∈S。如果⊙是可结合的并且一个元素x的左逆元x l-1和右逆元x r-1存在，则x l-1=x r-1。

3、定理12.2.7给定及幺元e∈S。如果⊙是可结合的并且x的逆元x-1存在，则x-1是惟一的。

4、给定 ~ 且f为其满同态映射，则

(a)如果⊙满足结合律，则⊕也满足结合律。

(b)如果⊙满足交换律，则⊕也满足交换律。

5、定理12.4.1设与是同类型的且f为其同态映射。对应于f，定义关系E f 如下：

xE f y：=f(x)= f(y)，其中x，y∈S

则E f是中的同余关系，并且称E f为由同态映射f所诱导的同余关系。

6、习题

7、

8、

9、12。

7、积代数：例题12.6.1.

8、两个代数系统来源于同一个代数系统，说明两个代数结构<{0,1},⊙>,<{0,1},⊕>之间的关系(_同构，同构映射_┐)，解释对应的两种运算，⊙_∨，⊕_∧并用一个命题公式表示(┐

(P∨Q)?┐P∧┐Q)。代数结构一样，表明运算规则相同，但当元素的角色不同时，具体的运算含义不一样。

* αβ

3 / 6

设Z为整数集合，代数系统，+，?为通常的加法与乘法运算。定义Z上的关系E={|x-y=3k，k∈Z,x,y∈Z}，E为Z上的等价关系，由此得到三个等价类分别为

[0]E={…,-6,-3,0,3,6,…}，

[1]E={…,-5,-2,1,4,7,…}，

[2]E={..,-4,-1,2,5,8,…}。证明E为上的同余关系：设,∈E，即

x1-y1=3m,x2-y2=3n,有

1)(x1+x2)-(y1+y2)=3(m+n)，所以∈E。

2)(x1?x2)-(y1?y2)=3(y1n+y2m+2mn)，∈E.

说明：同余关系是一个高级的等价关系，即针对集合Z上的运算“+,?”方式，仍然封闭。

可以定义商集Z/E={[0]E,[1]E,[2]E}中的运算”⊕，?”

[x]E⊕[y]E=[x+y]E

[x]E? [y]E=[x?y]E

这两种新定义的运算直接依赖于源系统中的运算

形成一个商代数。它与源代数结构具有类似的运算规则_同态：因为存在一个自然同态映射为：

g E(x)=[x]E (自然同态)

g E(x+y)=[x+y]E=[x]E⊕[y]E =g E(x)⊕g E(y)

g E(x?y)=[x?y]E =[x]E? [y]E =g E(x)?g E(y)

以上说明：由同余关系可以构造出与源代数系统同态的代数系统。

另一种方法：直接定义一个同态映射f:Z→Z3={[0],[1],[2]}

f(i)=[(i)(mod 3)]

与同态，

[a]+3 [b]=[(a+b)(mod 3)]

[a]?3 [b]=[(a?b)(mod 3)]

与同构是比较明显的，但产生方式不同，一个来源于同余关系，不需要直接定义同态映射或者说与同态映射无关；一个源于直接定义或寻找同态映射。

同态映射并不强调对原集合进行划分，但可以诱导出一个同余关系，如集合

{…,-6,-3,0,3,6,…}中所有元素在映射f(i)=[(i)(mod 3)]下的像都一样。

4 / 6

5 /

6 五、 图论部分

1、两个图的关系

(b)

(a)

(b)(a)

1

1 d

1

1g 1 e

d

2写出Dijkstra 算法，并计算图中从v1到其他结点的最短链长度。

3、 给定PERT 图，计算关键路径。

6 / 6

4v v 6

本文来源：https://www.bwwdw.com/article/8pwq.html