离散数学笔记第一章 命题逻辑合取析取定义 1. 1.3 否定：当某个命题为真时.其否定为假.当某个命题为假时.其否定为真定义 1. 1.4 条件联结词.表示“如果… …那么……”形式的语句定义 1. 1.5 双条件联结词.表示“当且仅当”形式的语句定义 1.2.1 合式公式(1)单个命题变元、命题常元为合式公式.称为原子公式2)若某个字符串 A 是合式公式.则A、(A)也是合式公式3)若 A、B 是合式公式.则 A B、AB、A B、AB 是合式公式4)有限次使用(2)~(3)形成的字符串均为合式公式1.3等值式1.4析取范式与合取范式将一个普通公式转换为范式的基本步骤1.6推理定义 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 一样快.则兔子比乌龟跑得快表示为： ∀x∀y(R(x)∧T(y)→H(x,y))有的兔子比所有的乌龟跑得快表示为：∃x∀y(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)是原子公式原子公式中的个体变元.可以换成个体变元的表达式(项).但不能出现任何联结词与量词.只能为单个的谓词公式定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式.则(﹁A)也是合式公式；(3)若 A,B 合式.则 A∨B, A∧B, A→B , A↔B 合式(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 自由变元：谓词公式中与任何量词都无关的量词.称为自由变元.它的每次出现称为自由出现一个公式的个体变元不是约束变元.就是自由变元注意：为了避免约束变元和自由变元同名出现.一般要对“约束变元”改名.而不对自由变元改名。
定义 2.2.9 闭公式是指不含自由变元的谓词公式从本例(已省)可知. 不同的公式在同一个解释下. 其真值可能存在. 也可能不存在. 但是对于没有自由变元的公式(闭公式).不论做何种解释.其真值肯定存在谓词公式的类型：重言式(永真式)、矛盾式(永假式)、可满足公式三种类型定义 2.2.10 在任何解释下.公式的真值总存在并为真.则为重言式或永真式定义 2.2.11 在任何解释下.公式的真值总存在并为假.则为矛盾式或永假式定义 2.2.12 存在个体域并存在一个解释使得公式的真值存在并为真.则为可满足式定义 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。
当 AóB 时.根据定义可知.在任何解释下.公式 A 与公式 B 的真值都相同.故 A↔B 为永真式.故得到如下的定义定义 2.3.2 设 A、B 是两个合法谓词公式.如果在任何解释下. A↔ B 为永真式. 则 A与 B 等值.记为 A ó B一、利用代换实例可证明的等值式(p↔﹁﹁p 永真.代换实例∀ xF(x) ↔﹁﹁∀ xF(x)永真)二、个体域有限时.带全称量词、存在量词公式的等值式如：若D={ }.则∀ xA(x) ó A()∧A()∧…∧A()三、量词的德摩律1、﹁∀xA(x) ó ∃x﹁A(x) 2、﹁∃xA(x) ó ∀x﹁A(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)∨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、谓词公式的范式从定理证明过程.可得到获取前束范式的步骤：(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 表示复数描述一个集合一般有 “枚举法” 与 “描述法” . “枚举法”元素与集合之间有“属于”或“不属于”二种关系定义 3.1.1 设 A.B 是两个集合.如果 A 中的任何元素都是 B 中的元素.则称 A 是 B的子集.也称 B 包含于 A.记为 BA.也称 A 包含 B.记为 AB3.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交换律 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、序偶定义 3.4.2 令与是二个序偶.如果 x=u、y=v.那么=即二个序偶相等定义 3.4.3 如果是序偶.且<,z>也是一个序偶.则称为三元组3.5、直积或笛卡尔积定义 3.5.1 令 A、B 是两个集合. 称序偶的集合{|xA, yB}为A与B的直积或笛卡尔积.记为 AB如：A={1,2,3}.B={a,b,c}则AB={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(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、ABóA C B C ó C A C B6、AB,CDóA C B D定义 3.5.2 令 是 n 个集合.称n元组的集合{<>|}.为的直积或笛卡尔积.记为。
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>}.RAA（A={1,2,3,4,5,6,7,8}）定义 3.6.2 如果序偶或元组属于某个关系 R.则称序偶或元组具有关系 R关系图.关系矩阵 3.7、关系的复合定义 3.7.1 若关系 FAA.关系 GAA.称集合{|t 使得F.G}为 F 与 G 的复合.记为 FG例题 3.7.1 令 A={1,2,3}.F={<1,1>,<1,2>} G={<2,2>,<1,3>,<1,1>}则解： FG={ <1,3>,<1,1>,<1,2>} .GF={<1,2>,<1,1>}. 因此关系的复合不满足交换律。
采用复合的定义去计算.只适合于人工计算.为了编程实现.故采用矩阵表示关系说明：的第 i 行与的第 j 列相乘时.乘法是合取.加法是析取.如 MF 的 1 行与 MG的第 3 列相乘是：(11)(10)(00).结果为 1定义 3.7.2 若关系 FAA.称集合{|F }为 F 的逆.记为例题 3.7.2 令 A={1,2,3}.F={<1,2>,<1,3>,<2,1>}.则={ <2,1>,<3,1>,<1,2>}3.8、关系的分类定义 3.8.1 若都有R.则R是自反关系自己到自己的关系全属于R)定义 3.8.2 若都有R,则 R 是反自反的自己到自己的关系全不属于R)定义 3.8.4 如果所有形如的序偶都在关系 R 中. R 也只有这种形式的序偶. 则称 R为恒等关系.记为对于恒等关系而言.其关系矩阵是单位矩阵.即其主对角线全是 1.其他位置全是 0.对关系图是每个点都有自旋.仅只有自旋.没有其他边定义 3.8.5 令关系RAA.如果当R 时R.则称 R 为对称关系定义 3.8.6 令关系RAA.如果当R 且xy时R. 则称 R 为反对称关系。
定义 3.8.8 令关系RAA.若当R,R时有R.则称R为可传递关系从RR 的关系矩阵可知.其非0元素在R的关系矩阵都出现.即.凡满足这个不等式的关系.肯定为可传递关系所以不可传递从RR的关系矩阵可知.其非0元素出现在(1,1).(1,3).(2,2).(2,4).在 R 的关系矩阵都没出现.不满足.不可传递关系3.9、关系的闭包将关系矩阵的主角线上全部变成 1. 即得到其自反闭包的关系矩阵. 从而可得到其自反闭包3.10、等价关系与集合的划分定义 3.10.1 设R AA.如果 R 是自反、对称、可传递的关系则称为等价关系定义 3.10.2 设R AA.如果 R 是等价关系. BA. B 中任意二个元素之间都有关系R.则 B 是一个等价类定义 3.10.3 设R AA.R是等价关系.是基于 R 得到的等价类.则称集合{}为 A 关于 R 的商集.记为 A/R定义 3.10.3 若是 A 的子集.若时.并且.则称是A的一个划分定理 3.10.1 设R AA.R 是等价关系.是利用 R 得到的 k 个不同的等价类.则 为集合 A 的划分定理 3.10.2 设是A 的划分. R=. 则 R 是等价关系。
3.11、偏序关系定义 3.1 1.1 设R AA.如果 R 是自反、反对称、可传递的关系则称为偏序关系如：R 是实数中小于等于关系.则R是偏序关系定义 3.1 1.2 设R AA.R 偏序关系.x 与 y 是 A 中的元素.若序偶与至少有一个在 R 中.则称 x 与 y 可比定义 3.1 1.3 设R AA.R 偏序关系.若 A 中任意二个元素都可比.则称 A 为全序关系或线序关系定义 3.1 1.4 设R AA.R 偏序关系.将关系图绘制成所有箭头都朝上.然后去掉所有箭头、去掉自旋边、去掉复合边.得到关系图的简化形式.称为哈斯图定义 3.1 1.5 在哈斯图中.如果某个元素 y 在元素 x 的直接上方.则称 y 盖住了 x记COVA={}定义 3.1 1.6 设R AA.R 偏序关系.将偏序关系与集合 A 一块称为偏序集.记为.表示是 A 上的偏序关系以后说偏序关系时.可简单地说偏序集定义 3.1 1.7 在偏序集中.BA.yB.若都有R.则称 y 是最大元即最大元与 B 中每个元素都可比.并且都比其大定义 3.1 1.8 在偏序集中.BA.yB.若都有R.则称 y 是最小元。
即最小元与 B 中每个元素都可比.并且都比其小一个子集中没有最大元或最小元时.可能存在极大元或极小元定义 3.1 1.9 在偏序集中.BA.yB.若不存在 xB 使得R.则称 y是极大元. 即B中不存在比y“大”的元素 即极大元与 B 中有些元素是否可比不做要求定义 3.1 1.10 在偏序集中.BA.yB.若不存在xB 都有R.则称 y是极小元.不存在比 y 小的元素即极小元与 B中元素是否可比不做要求定义 3.1 1.1 1 在偏序集中.BA.yB.若任意xB都有R.则称y是B 的上界与 B 中每个元素都可比.并且都 B 中的元素大3.12、其它关系定义3.6.1 给定集合A上的关系ρ.若ρ是自反的、对称的.则称ρ是A上的相容关系定义3.6.3 给定非空集合A.设有集合S={}.其中且.i=1,2,…,m,且.则称集合S称作A的覆盖定理3.6.1 给定集合A的覆盖..由它确定的关系：是相容关系定义3.7.1 设R为定义在集合A上的一个关系.若R是自反的.对称的.传递的.则R称为等价关系显然等价关系一定是相容关系)定义3.7.2 设给定非空集合A.若有集合S={}.其中且(i=1,2,…,m).且有.同时有.则称S为A的一个划分。
所有子集的并为A.且子集的交为空.则这些子集组成的集合为A的一个划分.覆盖中.子集的交集可不为空)等价类商集偏序关系(自反性.反对称性.传递性).哈斯图.可比的.元素y盖住元素x.全序关系.极大元.极小元.最大元.最小元拟序关系(反自反的.传递的)第四章 代数系统定义 4.3.1 设°是集合 S 上的二元运算.若都有 x°y=y°x.则称°在 S 上是可交换的.或者说运算°在 S 上满足交换律定义 4.3.2 设°是集合 S 上的二元运算.若都有(x°y)°z=x°(y°z).则称°在 S上是可结合的,或者说运算°在 S 上满足结合律定义 4.3.3 设°是集合 S 上的二元运算.若都有 x°x=x. 则称°在 S 上是幂等的,或说运算°在 S 上满足幂等律定义 4.3.4 设°与*是集合 S 上的二种运算.若都有 x*(y°z)=(x*y)°(x*z)与(y°z)*x=(y*x)°(z*x).则称*对°是可分配的定义 4.3.5 设°与*是集合 S 上的二种可交换的二元运算.若都有 x*(x°y)=x 与x°(x*y)=x 则称*与°是满足吸收律.内外二种运算不一样.运算符内外各出现一次.以多吃少。
广群：半群：群：子群：欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力赠语； 1、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就做得更好，来给人笑吧！ 2、现在你不玩命的学，以后命玩你3、我不知道年少轻狂，我只知道胜者为王4、不要做金钱、权利的奴隶；应学会做“金钱、权利”的主人5、什么时候离光明最近？那就是你觉得黑暗太黑的时候6、最值得欣赏的风景，是自己奋斗的足迹 7、压力不是有人比你努力，而是那些比你牛×几倍的人依然比你努力 .。