(完整word版)离散数学知识汇总,推荐文档

式记为 B，则 A ? B 例

证明步骤：

2.4、谓词公式的范式

从定理证明过程，可得到获取前束范式的步骤： (1)剔除不起作用的量词；

(2)如果约束变元与自由变元同名，则约束变元改名；

(3)如果后面的约束变元与前面的约束变元同名，则后的约束变元改名； (4)利用代换实例，将→、?转换﹁∨∧表示；

(5)利用德摩律，将否定﹁深入到原子公式或命题的前面；

(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边

2.5、谓词推理

An?B只能为真即为永真，An可推出定义 2.5.1 若在各种解释下 A1?A2?...则称为前提A1?A2?...结论 B。

An 为真的解释下，An可推出结论 B。定义 2.5.2 在所有使 A1?A2?...B 为真，则称为前提 A1?A2?...

谓词逻辑的推理方法分为以下几类：

vi

一、 谓词逻辑的等值演算原则、 规律： 代换实例、 量词的德摩律、 量词的分配律、 量词 辖域的扩张与收缩、约束变元改名。

二、 命题逻辑的推理规则的代换实例， 如假言推理规则、 传递律、 合取与析取的性质律、 CP 规则、反证法等。

三、谓词逻辑的推理公理

第三章 集合与关系

3.1、基本概念

在离散数学称 “不产生歧义的对象的汇集一块” 便构成集合。常用大写字母表示集合， 如 R 表示实数， N 表示自然数， Z 表示整数， Q 表示有理数，C 表示复数。描述一个集合一般有 “枚举法” 与 “描述法” ， “枚举法”。元素与集合之间有“属于?”或“不属于?”二种关系。

定义 3.1.1 设 A，B 是两个集合，如果 A 中的任何元素都是 B 中的元素，则称 A 是 B 的子集，也称 B 包含于 A，记为 B?A，也称 A 包含 B，记为 A?B。

vii

3.2集合运算性质

定义 3.2.1 设 A、B 为集合，A 与 B 的并集 A?B、A 与 B 的的交集 A?B、A-B 的定 义：A?B={x|x?A?x?B}，A?B={x|x?A?x?B}，A-B={x|x?A?x?B}

定 义 3.2.2 设 A、 B 为 集 合 ， A 与 B 的 对 称 差 ， 记 为 A?B={x|(x?A?x?B)?( x ?A?x?B)}= A?B - A?B。

定义 3.2.3 设 A、B 是两个集合，若 A?B、B?A 则 A=B，即两个集合相等。 幂等律 结合律 交换律 分配律

A?A=A、A?A=A

A?B?C= A?(B?C)= (A?B)?C A?B?C= A?(B?C)= (A?B)?C A?B=B?A、A?B=B?A A?(B?C)=(A?B)?(A?C) A?(B?C)=(A?B)?(A?C) A?? = A、A??= ? A??A=E、A??A= ?

A?(B?A)=A、 A?(B?A)=A

? (A?B)= ?A ??B 、? (A?B)= ?A??B ??A=A

同一/零律 排中/矛盾律 吸收律(大吃小) 德摩律 双重否定

3.3、有穷集的计数

定理 3.3.1 二个集合的包含排斥原理 |A1?A2 | = |A1| + |A2| - |A1?A2|

3.4、序偶

定义 3.4.2 令与是二个序偶，如果 x=u、y=v，那么=即二个序偶相等。 定义 3.4.3 如果是序偶，且<,z>也是一个序偶，则称为三元组。

3.5、直积或笛卡尔积

定义 3.5.1 令 A、B 是两个集合， 称序偶的集合{|x?A, y?B}为A与B的直积或笛卡尔积，记为 A?B。

viii

如：A={1,2,3}，B={a,b,c}则A?B={1,2,3}?{a,b,c}={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>} 直积的性质

1、A?(B?C)= A ? B ? A ? C 2、A ? (B?C)= A ? B ? A ? C 3、(B? C) ? A = B ? A? C ? A 4、(B ? C) ? A = B ? A ? C ? A

5、A?B?A ?C ? B ? C ? C ? A ? C ? B 6、A?B,C?D?A ? C ? B ? D

An是 n 个集合，称n元组的集合{| 定义 3.5.2 令 A1,A2,...x1?A1,x2?A2,...,xn?An}，为A1,A2,...An的直积或笛卡尔积，记为A1?A2?...?An。

3.6、关系

定义 3.6.1 称直积中部分感兴趣的序偶所组成的集合为“关系” ，记为 R。

如在直积{1,2,3,4,5,6,7,8}?{1,2,3,4,5,6,7,8}中， 只对第 1 个元素是第 2 个元素的因数的序偶感兴趣，即只对R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>, <1,7>,<1,8>, <2,2>,<2,4>, <2,6>, <2,8>, <3,3>,<3,6>,<4,4>,<4,8>,<5,5>, <6,6>,<7,7>,<8,8>}，R?A?A（A={1,2,3,4,5,6,7,8}）

定义 3.6.2 如果序偶或元组属于某个关系 R，则称序偶或元组具有关系 R。 关系图，关系矩阵

3.7、关系的复合

定义 3.7.1 若关系 F?A?A，关系 G?A?A，称集合{|?t 使得?F，?G} 为 F 与 G 的复合，记为 F?G。

例题 3.7.1 令 A={1,2,3}，F={<1,1>,<1,2>} G={<2,2>,<1,3>,<1,1>}则

解： F?G={ <1,3>,<1,1>,<1,2>} ，G?F={<1,2>,<1,1>}， 因此关系的复合不满足交换律。 采用复合的定义去计算，只适合于人工计算，为了编程实现，故采用矩阵表示关系。

ix

说明：MF的第 i 行与MG的第 j 列相乘时，乘法是合取?，加法是析取?，如 MF 的 1 行与 MG 的第 3 列相乘是：(1?1)?(1?0)?(0?0)，结果为 1。

定义 3.7.2 若关系 F?A?A，称集合{|?F }为 F 的逆，记为F例题 3.7.2 令 A={1,2,3}，F={<1,2>,<1,3>,<2,1>}，则F?1?1

={ <2,1>,<3,1>,<1,2>}。

3.8、关系的分类

定义 3.8.1 若?x?定义 3.8.2 若?x?A都有?R，则R是自反关系。(自己到自己的关系全属于R) A都有?R,则 R 是反自反的。(自己到自己的关系全不属于R)

定义 3.8.4 如果所有形如的序偶都在关系 R 中， R 也只有这种形式的序偶， 则称 R为恒等关系，记为IA。

对于恒等关系而言，其关系矩阵是单位矩阵，即其主对角线全是 1，其他位置全是 0，对关系图是每个点都有自旋，仅只有自旋，没有其他边。

定义 3.8.5 令关系R?A?A，如果当?R 时?R，则称 R 为对称关系。

定义 3.8.6 令关系R?A?A，如果当?R 且x?y时?R， 则称 R 为反对称关系。

定义 3.8.8 令关系R?A?A，若当?R,?R时有?R，则称R为可传递关系。

从R?R 的关系矩阵可知，其非0元素在R的关系矩阵都出现，即MR?R?MR，凡满足这个不等式的关系，肯定为可传递关系。

所以不可传递。

从R?R的关系矩阵可知，其非0元素出现在(1,1)，(1,3)，(2,2)，(2,4)，在 R 的关系矩 阵都没出现，不满足MR?R?MR，不可传递关系。

x