《离散数学知识汇总.docx》由会员分享，可在线阅读，更多相关《离散数学知识汇总.docx（36页珍藏版）》请在金锄头文库上搜索。
1、离散数学知识汇总离散数学笔记第一章 命题逻辑合取析取定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果 那么”形式的语句定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句定义 1.2.1合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。(2)若某个字符串 A 是合式公式，则A、(A)也是合式公式。(3)若 A、B 是合式公式，则 AB、AB、AB、AB 是合式公式。(4)有限次使用(2)(3)形成的字符串均为合式公式。1.3等值式1.4析取范式与合取范式将一个普通公式转换为范式的基本步骤1.6推理定义
2、1.6.1 设 A 与 C 是两个命题公式，若 A C 为永真式、 重言式，则称 C 是 A 的有效结论，或称 A 可以逻辑推出 C，记为 A = C。（用等值演算或真值表）第二章 谓词逻辑2.1、基本概念：全称量词 ：存在量词一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如x(H(x)B(x)，即量词的后面为条件式，带“存在量词”的谓词公式形如x(H(x)WL(x)，即量词的后面为合取式例题R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快
3、表示为：xy(R(x)T(y)H(x,y)有的兔子比所有的乌龟跑得快表示为：xy(R(x)T(y)H(x,y)2.2、谓词公式及其解释定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示的 f(x,y)、 谓词常元(如表示人类的 H(x)。定义 2.2.2、逻辑符号：个体变元、量词()、联结词()、逗号、括号。定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。定义 2.2.4、原子公式：设 R()是 n 元谓词，是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓
4、词公式。定义 2.2.5合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(A)也是合式公式；(3)若 A,B 合式，则 AB, AB, AB , AB 合式(4)若 A 合式，则xA、xA 合式(5)有限次使用(2)(4)得到的式子是合式。定义 2.2.6量词辖域：xA 和xA 中的量词x/x 的作用范围，A 就是作用范围。定义 2.2.7约束变元：在x 和x 的辖域 A 中出现的个体变元 x，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。定义 2.2.8自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变
5、元不是约束变元，就是自由变元。注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。定义 2.2.9闭公式是指不含自由变元的谓词公式从本例(已省)可知， 不同的公式在同一个解释下， 其真值可能存在， 也可能不存在， 但是对于没有自由变元的公式(闭公式)，不论做何种解释，其真值肯定存在谓词公式的类型：重言式(永真式)、矛盾式(永假式)、可满足公式三种类型定义 2.2.10在任何解释下，公式的真值总存在并为真，则为重言式或永真式。定义 2.2.11在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。定义 2.2.12存在个体域并存在一个解释使得公式的真值存在
6、并为真，则为可满足式。定义 2.2.13代换实例 设是命题公式中的命题变元，是 n 个谓词公式，用代替公式中的后得到公式 A，则称 A 为的代换实例。如A(x)A(x)，xA(x) xA(x)可看成 p p 的代换实例，A(x) A(x)，xA(x) x A(x)可看成 p p 的代换实例。定理 2.2.1命题逻辑的永真公式之代换实例是谓词逻辑的永真公式， 命题逻辑的永假公式之代换实例是谓词逻辑的永假式。（代换前后是同类型的公式）2.3、谓词公式的等值演算定义 2.3.1设 A、B 是两个合法的谓词公式，如果在任何解释下，这两个公式的真值都相等，则称 A 与 B 等值，记为 A B。当 AB
7、时，根据定义可知，在任何解释下，公式 A 与公式 B 的真值都相同，故 AB 为永真式，故得到如下的定义。定义 2.3.2设 A、B 是两个合法谓词公式，如果在任何解释下， AB 为永真式， 则 A与 B 等值，记为 A B。一、利用代换实例可证明的等值式(pp 永真，代换实例xF(x)xF(x)永真)二、个体域有限时，带全称量词、存在量词公式的等值式如：若D=，则xA(x) A()A()A()三、量词的德摩律1、xA(x) xA(x) 2、xA(x) xA(x)四、量词分配律1、x(A(x)B(x) xA(x)xB(x) 2、x(A(x)B(x) xA(x)xB(x)记忆方法：与，一个尖角朝
8、下、一个尖角朝上，相反可才分配。2 式可看成 1 式的对偶式五、量词作用域的收缩与扩张律A(x)含自由出现的个体变元 x，B 不含有自由出现的 x，则有：1、/(A(x)B) /A(x)B 2、/(A(x)B) /A(x)B对于条件式 A(x)B， 利用 “基本等值一” 将其转换为析取式， 再使用德摩律进行演算六、置换规则若 B 是公式 A 的子公式，且B C，将 B 在 A 中的每次出现，都换成 C 得到的公式记为 D，则 A D七、约束变元改名规则将公式 A 中某量词的指导变元及辖域中约束变元每次约束出现，全部换成公式中未出现的字母，所得到的公式记为 B，则 A B例证明步骤：2.4、谓词
9、公式的范式从定理证明过程，可得到获取前束范式的步骤：(1)剔除不起作用的量词；(2)如果约束变元与自由变元同名，则约束变元改名；(3)如果后面的约束变元与前面的约束变元同名，则后的约束变元改名；(4)利用代换实例，将、转换表示；(5)利用德摩律，将否定深入到原子公式或命题的前面；(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边2.5、谓词推理定义 2.5.1 若在各种解释下只能为真即为永真，则称为前提可推出结论 B。定义 2.5.2 在所有使为真的解释下，B 为真，则称为前提可推出结论 B。谓词逻辑的推理方法分为以下几类：一、 谓词逻辑的等值演算原则、 规律： 代换实例、
10、 量词的德摩律、 量词的分配律、 量词辖域的扩张与收缩、约束变元改名。二、 命题逻辑的推理规则的代换实例， 如假言推理规则、 传递律、 合取与析取的性质律、CP 规则、反证法等。三、谓词逻辑的推理公理第三章 集合与关系3.1、基本概念在离散数学称 “不产生歧义的对象的汇集一块” 便构成集合。常用大写字母表示集合， 如 R 表示实数， N 表示自然数， Z 表示整数， Q 表示有理数，C 表示复数。描述一个集合一般有 “枚举法” 与 “描述法” ， “枚举法”。元素与集合之间有“属于”或“不属于”二种关系。定义 3.1.1设 A，B 是两个集合，如果 A 中的任何元素都是 B 中的元素，则称 A
11、 是 B的子集，也称 B 包含于 A，记为 BA，也称 A 包含 B，记为 AB。3.2集合运算性质定义 3.2.1设 A、B 为集合，A 与 B 的并集 AB、A 与 B 的的交集 AB、A-B 的定义：AB=x|xAxB，AB=x|xAxB，A-B=x|xAxB定 义 3.2.2设 A、 B 为 集 合 ， A 与 B 的 对 称 差 ， 记 为 AB=x|(xAxB)( xAxB)= AB - AB。定义 3.2.3设 A、B 是两个集合，若 AB、BA 则 A=B，即两个集合相等。幂等律AA=A、AA=A结合律ABC= A(BC)= (AB)CABC= A(BC)= (AB)C交换律A
12、B=BA、AB=BA分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一/零律A = A、A= 排中/矛盾律AA=E、AA= 吸收律(大吃小)A(BA)=A、 A(BA)=A德摩律(AB)=AB 、(AB)=AB双重否定A=A3.3、有穷集的计数定理 3.3.1 二个集合的包含排斥原理 | = | + | - |3.4、序偶定义 3.4.2令与是二个序偶，如果 x=u、y=v，那么=即二个序偶相等。定义 3.4.3如果是序偶，且,z也是一个序偶，则称为三元组。3.5、直积或笛卡尔积定义 3.5.1令 A、B 是两个集合， 称序偶的集合|xA, yB为A与B的直积或笛卡尔积，记为
13、AB。如：A=1,2,3，B=a,b,c则AB=1,2,3a,b,c=,直积的性质1、A(BC)= ABAC2、A(BC)= ABAC3、(BC)A = BACA4、(BC)A = BACA5、ABACBC CACB6、AB,CDACBD定义 3.5.2令是 n 个集合，称n元组的集合|，为的直积或笛卡尔积，记为。3.6、关系定义 3.6.1称直积中部分感兴趣的序偶所组成的集合为“关系” ，记为 R。如在直积1,2,3,4,5,6,7,81,2,3,4,5,6,7,8中， 只对第 1 个元素是第 2 个元素的因数的序偶感兴趣，即只对R=, , , , , ,，RAA（A=1,2,3,4,5,6,7,8）定义 3.6.2如果序偶或元组属于某个关系 R，则称序偶或元组具有关系 R。关系图，关系矩阵3.7、关系的复合定义
