离散数学知识汇总

i离散数学笔记第一章命题逻辑合取析取定义1.1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义1.1.4条件联结词，表示“如果……那么……”形式的语句定义1.1.5双条件联结词，表示“当且仅当”形式的语句定义1.2.1合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。(2)若某个字符串A是合式公式，则A、(A)也是合式公式。(3)若A、B是合式公式，则AB、AB、AB、AB是合式公式。(4)有限次使用(2)~(3)形成的字符串均为合式公式。1.3等值式1.4析取范式与合取范式ii将一个普通公式转换为范式的基本步骤iiiiv1.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)、函数常元(如表示22yx的f(x,y))、谓词常元(如表示人类的H(x))。定义2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。定义2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。定义2.2.4、原子公式：设R(nxx...1)是n元谓词，ntt...1是项，则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闭公式是指不含自由变元的谓词公式v从本例(已省)可知，不同的公式在同一个解释下，其真值可能存在，也可能不存在，但是对于没有自由变元的公式(闭公式)，不论做何种解释，其真值肯定存在谓词公式的类型：重言式(永真式)、矛盾式(永假式)、可满足公式三种类型定义2.2.10在任何解释下，公式的真值总存在并为真，则为重言式或永真式。定义2.2.11在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。定义2.2.12存在个体域并存在一个解释使得公式的真值存在并为真，则为可满足式。定义2.2.13代换实例设nppp,...,,21是命题公式0A中的命题变元，nAAA,...,,10是n个谓词公式，用iA代替公式0A中的ip后得到公式A，则称A为0A的代换实例。如A(x)∨﹁A(x)，∀xA(x)∨﹁∀xA(x)可看成p∨﹁p的代换实例，A(x)∧﹁A(x)，∀xA(x)∧﹁∀xA(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={naaa,...,,21}，则∀xA(x)A(1a)∧A(2a)∧…∧A(na)三、量词的德摩律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)∨B2、∀/∃(A(x)∧B)∀/∃A(x)∧B对于条件式A(x)↔B，利用“基本等值一”将其转换为析取式，再使用德摩律进行演算六、置换规则若B是公式A的子公式，且BC，将B在A中的每次出现，都换成C得到的公式记为D，则AD七、约束变元改名规则将公式A中某量词的指导变元及辖域中约束变元每次约束出现，全部换成公式中未出现的字母，所得到的公vi式记为B，则AB例证明步骤：2.4、谓词公式的范式从定理证明过程，可得到获取前束范式的步骤：(1)剔除不起作用的量词；(2)如果约束变元与自由变元同名，则约束变元改名；(3)如果后面的约束变元与前面的约束变元同名，则后的约束变元改名；(4)利用代换实例，将→、↔转换﹁∨∧表示；(5)利用德摩律，将否定﹁深入到原子公式或命题的前面；(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边2.5、谓词推理定义2.5.1若在各种解释下BAAAn...21只能为真即为永真，则称为前提nAAA...21可推出结论B。定义2.5.2在所有使nAAA...21为真的解释下，B为真，则称为前提nAAA...21可推出结论B。谓词逻辑的推理方法分为以下几类：vii一、谓词逻辑的等值演算原则、规律：代换实例、量词的德摩律、量词的分配律、量词辖域的扩张与收缩、约束变元改名。二、命题逻辑的推理规则的代换实例，如假言推理规则、传递律、合取与析取的性质律、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。viii3.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)CA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=A3.3、有穷集的计数定理3.3.1二个集合的包含排斥原理|21AA|=|1A|+|2A|-|21AA|3.4、序偶定义3.4.2令x,y与u,v是二个序偶，如果x=u、y=v，那么x,y=u,v即二个序偶相等。定义3.4.3如果x,y是序偶，且x,y,z也是一个序偶，则称x,y,z为三元组。3.5、直积或笛卡尔积定义3.5.1令A、B是两个集合，称序偶的集合{x,y|xA,yB}为A与B的直积或笛卡尔积，记为AB。ix如：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C2、A(BC)=ABAC3、(BC)A=BACA4、(BC)A=BACA5、ABACBCCACB6、AB,CDACBD定义3.5.2令nAAA,...,21是n个集合，称n元组的集合{nxxx,...,,21|nnAxAxAx,...,,2211}，为nAAA,...,21的直积或笛卡尔积，记为nAAA...21。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，称集合{x,y|t使得x,tF，t,y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}，因此关系的复合不满足交换律。采用复合的定义去计算，只适合于人工计算，为了编程实现，故采用矩阵表示关系。x说明：FM的第i行与GM的第j列相乘时，乘法是合取，加法是析取，如MF的1行与MG的第3列相乘是：(11)(10)(00)，结果为1。定义3.7.2若关系FAA，称集合{y,x|x,yF}为F的逆，记为1F例题3.7.2令A={1,2,3}，F={1,2,1,3,2,1}，则1F={2,1,3,1,1,2}。3.8、关系的分类定义3.8.1若Ax都有x,xR，则R是自反关系。(自己到自己的关系全属于R)定义3.8.2若Ax都有x,xR,则R是反自反的。(自己到自己的关系全不属于R)定义3.8.4如果所有形如x,x的序偶都在关系R中，R也只有这种形式的序偶，则称R为恒等关系，记为AI。对于恒等关系而言，其关系矩阵是单位矩阵，即其主对角线全是1，其他位置全是0，对关系图是每个点都有自旋，仅只有自旋，没有其他边。定义3.8.5令关系RAA，如果当x,yR时y,xR，则称R为对