word离散数学笔记第一章 命题逻辑合取析取 否认：当某个命题为真时.其否认为假.当某个命题为假时.其否认为真 条件联结词.表示“如果那么形式的语句 双条件联结词.表示“当且仅当形式的语句 合式公式(1)单个命题变元、命题常元为合式公式.称为原子公式。(2)假如某个字符串 A 是合式公式.如此A、(A)也是合式公式。(3)假如 A、B 是合式公式.如此 A B、AB、A B、AB 是合式公式。(4)有限次使用(2)(3)形成的字符串均为合式公式。值式取式与合取式将一个普通公式转换为式的根本步骤定义 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 一样快.如此兔子比乌龟跑得快表示为： xy(R(x)T(y)H(x,y)有的兔子比所有的乌龟跑得快表示为：xy(R(x)T(y)H(x,y)、谓词公式与其解释、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示的 f(x,y)、 谓词常元(如表示人类的 H(x)。、逻辑符号：个体变元、量词()、联结词()、逗号、括号。、项的定义：个体常元、变元与其函数式的表达式称为项(item)。、原子公式：设 R()是 n 元谓词.是项.如此 R(t)是原子公式。原子公式中的个体变元.可以换成个体变元的表达式(项).但不能出现任何联结词与量词.只能为单个的谓词公式。合式公式：(1)原子公式是合式公式；(2)假如 A 是合式公式.如此(A)也是合式公式；(3)假如 A,B 合式.如此 AB, AB, AB , AB 合式(4)假如 A 合式.如此xA、xA 合式(5)有限次使用(2)(4)得到的式子是合式。量词辖域：xA 和xA 中的量词x/x 的作用围.A 就是作用围。约束变元：在x 和x 的辖域 A 中出现的个体变元 x.称为约束变元.这是与量词相关的变元.约束变元的所有出现都称为约束出现。自由变元：谓词公式中与任何量词都无关的量词.称为自由变元.它的每次出现称为自由出现。一个公式的个体变元不是约束变元.就是自由变元。注意：为了防止约束变元和自由变元同名出现.一般要对“约束变元改名.而不对自由变元改名。 闭公式是指不含自由变元的谓词公式从本例(已省)可知. 不同的公式在同一个解释下. 其真值可能存在. 也可能不存在. 但是对于没有自由变元的公式(闭公式).不论做何种解释.其真值肯定存在谓词公式的类型：重言式(永真式)、矛盾式(永假式)、可满足公式三种类型 在任何解释下.公式的真值总存在并为真.如此为重言式或永真式。定义1 在任何解释下.公式的真值总存在并为假.如此为矛盾式或永假式。 存在个体域并存在一个解释使得公式的真值存在并为真.如此为可满足式。定义 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.3、谓词公式的等值演算 设 A、B 是两个合法的谓词公式.如果在任何解释下.这两个公式的真值都相等.如此称 A 与 B 等值.记为 A B。当 AB 时.根据定义可知.在任何解释下.公式 A 与公式 B 的真值都一样.故 AB 为永真式.故得到如下的定义。 设 A、B 是两个合法谓词公式.如果在任何解释下. A B 为永真式. 如此 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)记忆方法：与.一个尖角朝下、一个尖角朝上.相反可才分配。2 式可看成 1 式的对偶式五、量词作用域的收缩与扩律A(x)含自由出现的个体变元 x.B 不含有自由出现的 x.如此有：1、/(A(x)B)/A(x)B2、/(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、谓词公式的式从定理证明过程.可得到获取前束式的步骤：(1)剔除不起作用的量词；(2)如果约束变元与自由变元同名.如此约束变元改名；(3)如果后面的约束变元与前面的约束变元同名.如此后的约束变元改名；(4)利用代换实例.将、转换表示；(5)利用德摩律.将否认深入到原子公式或命题的前面；(6)利用量词辖域的扩与收缩规律或利用量词的分配律.将量词移到最左边2.5、谓词推理定义 2.5.1 假如在各种解释下 只能为真即为永真.如此称为前提可推出结论 B。定义 2.5.2 在所有使 为真的解释下.B 为真.如此称为前提 可推出结论 B。谓词逻辑的推理方法分为以下几类：一、 谓词逻辑的等值演算原如此、 规律： 代换实例、 量词的德摩律、 量词的分配律、 量词辖域的扩与收缩、约束变元改名。二、 命题逻辑的推理规如此的代换实例. 如假言推理规如此、 传递律、 合取与析取的性质律、CP 规如此、反证法等。三、谓词逻辑的推理公理第三章 集合与关系3.1、根本概念在离散数学称 “不产生歧义的对象的聚集一块 便构成集合。常用大写字母表示集合. 如 R 表示实数. N 表示自然数. Z 表示整数. Q 表示有理数.C 表示复数。描述一个集合一般有 “枚举法 与 “描述法 .“枚举法。元素与集合之间有“属于或“不属于二种关系。 设 A.B 是两个集合.如果 A 中的任何元素都是 B 中的元素.如此称 A 是 B的子集.也称 B 包含于 A.记为 BA.也称 A 包含 B.记为 AB。集合运算性质 设 A、B 为集合.A 与 B 的并集 AB、A 与 B 的的交集 AB、A-B 的定义：AB=x|xAxB.AB=x|xAxB.A-B=x|xAxB 设 A、 B 为 集 合 . A 与 B 的 对 称 差 . 记 为 AB=x|(xAxB)( xAxB)= AB- AB。 设 A、B 是两个集合.假如 AB、BA 如此 A=B.即两个集合相等。幂等律 AA=A、AA=A结合律 ABC= A(BC)= (AB)CABC= A(BC)= (AB)C交换律 AB=BA、AB=BA分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)同一/零律A=A、A= 排中/矛盾律 AA=E、AA= 吸收律(大吃小) A(BA)=A、 A(BA)=A德摩律(AB)= A B 、(AB)= AB双重否认A=A3.3、有穷集的计数定理 3.3.1 二个集合的包含排斥原理 | |=|+|-|3.4、序偶 令与是二个序偶.如果 x=u、y=v.那么=即二个序偶相等。 如果是序偶.且,z也是一个序偶.如此称为三元组。3.5、直积或笛卡尔积 令 A、B 是两个集合. 称序偶的集合|xA, yB为A与B的直积或笛卡尔积.记为 AB。如：A=1,2,3.B=a,b,c如此AB=1,2,3a,b,c=,直积的性质1、A(BC)= A B A C2、A (BC)= A B A C3、(B C) A = B A C A4、(B C) A = B A C A5、ABA C B C C A C B6、AB,CDA C B D 令 是 n 个集合.称n元组的集合|.为的直积或笛卡尔积.记为。3.6、关系 称直积中局部感兴趣的序偶所组成的集合为“关系 .记为 R。如在直积1,2,3,4,5,6,7,81,2,3,4,5,6,7,8中. 只对第 1 个元素是第 2 个元素的因数的序偶感兴趣.即只对R=, , , , , ,.RAAA=1,2,3,4,5,6,7,8 如果序偶或元组属于某个关系 R.如此称序偶或元组具有关系 R。关系图.关系矩阵3.7、关系的复合 假如关系 FAA.关系 GAA.称集合|t 使得F.G为 F 与 G 的复合.记为 FG。 令 A=1,2,3.F=, G=,如此解： FG= , .GF=,. 因此关系的复合不满足交换律。采用复合的定义去计算.只适合于人工计算.为了编程实现.故采用矩阵表示关系。说明：的第 i 行与的第 j 列相乘时.乘法是合取.加法是析取.如 MF 的 1 行与 MG的第 3 列相乘是：(11)(10)(00).结果为 1。 假如关系 FAA.称集合|F 为 F 的逆.记为 令 A=1,2,3.F=,.如此= ,。3.8、关系的分类 假如都有R.如此R是自反关系。(自己到自己的关系全属于R) 假如都有R,如此 R 是反自反的。(自己