离散数学及其应用思维导图
U133583214
2023-05-05
离散数学
离散数学应用
高等数学
离散数学及其应用
树图思维导图提供《离散数学及其应用》在线思维导图免费制作，点击“编辑”按钮，可对《离散数学及其应用》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ea7f96f96692d0250a09af5cad0fc59f
思维导图大纲
相关思维导图模版
离散数学及其应用思维导图模板大纲
命题逻辑
1 命题基本概念
1 具有确切真值的陈述句称为命题,该命题可以取一个“值”，称为真值。
2 真值只有“真”和“假”两种，分别用“Ｔ”(或“１”)和“Ｆ”(或“0”)表示。
注意：一切没有判断内容的句子都不能作为命题
约定：在数理逻辑中像字母“x”、“y”、“z”等字母总是表示变量。
结论：命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。
2 命题联结词
五种联结词
1 否定联结词 ┐
定义
设P是任一命题，复合命题“非P”(或“P的否定”)称为P的否定式(Negation)，记作┐P，“┐ ”为否定联结词。┐P为真当且仅当P为假。
总结
否定取反
2 合取联结词 ∧
定义
设P、Q是任两个命题，复合命题“P并且Q”(或“P和Q”)称为P与Q的合取式(Conjunction)，记作P∧Q，“∧”为合取联结词。 P∧Q为真当且仅当P，Q同为真。
与自然语言的联系
合取联结词“∧”对应了自然语言的 “既…又…”、“不仅…而且…”,“虽然…但是…” 等
总结
同真则真，否则为假
3 析取联结词 ∨
定义
设P、Q是任两个命题，复合命题“P或者Q”称为P与Q的析取式(Disjunction)，记作P∨Q，“∨”为析取联结词。
与自然语言的联系
析取联结词“∨”对应的是相容（可兼）的或。
总结
有真为真，同假则假
4 蕴含联结词 →
定义
设P、Q是任两个命题，复合命题“如果P，则Q”称为P与Q的蕴涵式(Implication)，记作P→Q，“→”称为蕴涵联结词，P称为蕴涵式的前件，Q称为蕴涵式的后件。P→Q为假当且仅当P为真且Q为假。
与自然语言的联系
蕴涵联结词“→”,“P→Q”对应了自然语言中的“如P则Q”、“只要P就Q”、“P仅当Q”等；
总结
只有前真后假为假，否则为真
5 等价联结词 <->
定义
设P、Q是任两个命题，复合命题“P当且仅当Q”称为P与Q的等价式(Enuivalence)，记作P<->Q，“<->”称为等价联结词。P<->Q为真当且仅当P、Q同为真假
与自然语言的联系
等价联结词“↔”对应了自然语言中的“等价”、“当且仅当”、“充分必要”等；
总结
同真同假为真，否则为假
联结词优先级
1 否定→合取→析取→蕴涵→等价
2 同级的联结词（合取与析取，蕴涵与等价）按其出现的先后次序(从左到右)
3 若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。
3 命题公式、解释与真值表
定义
将命题变元以命题联结词或括号连接起来的公式叫做合式公式或命题公式
约定
1. 对于公式中最外层的括号，常可省略。如(┐G)可写成┐G，(G→H)可写成G→H。但必须指出这仅仅是一种约定，把程序输入计算机时，括号是不可随意省略的；
2. 否定联结词“┐”只作用于邻接后的原子命题变元，如可把(┐G)∨H写成是 ┐G∨H。
3. 相同联结词按其出现的先后次序,括号可以省略；
解释
设P1、P2、…、Pn是出现在公式G中的所有命题变元，指定P1、P2、…、Pn一组真值，则这组真值称为G的一个解释,常记为Ｉ。
真值表
将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。
命题公式类型
永真公式
公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。
永假公式
公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。
可满足公式
公式G称为可满足的，如果它不是永假的。
等价公式
结合律
Ｅ1：G∨(H∨S)＝(G∨H)∨S
Ｅ2: G∧(H∧S)＝(G∧H)∧S
交换律
Ｅ3：G∨H＝H∨G
Ｅ4：G∧H＝H∧G
幂等律
Ｅ5：G∨G＝G
Ｅ6：G∧G＝G
吸收律
Ｅ7：G∨(G∧H)＝ G
Ｅ8：G∧(G∨H)＝ G
分配律
Ｅ9：G∨(H∧S)＝(G∨H)∧(G∨S)
Ｅ10：G∧(H∨S)＝(G∧H)∨(G∧S)
同一律
Ｅ11：G∨0＝G
Ｅ12：G∧１＝G
零律
Ｅ13：G∨１＝１
Ｅ14：G∧0＝0
排中律
Ｅ15：G∨┐G ＝１
矛盾律
Ｅ16：G∧┐G ＝0
双重否定律
Ｅ17：┐(┐G)＝G
De MoRGan定律
Ｅ18：┐(G∨H)＝┐G∧┐H
Ｅ19：┐(G∧H)＝┐G∨┐H
等价式
Ｅ20: (G<->H)＝(G→H)∧(H→G)
蕴涵式
Ｅ21：(G→H)＝(┐G∨H)
假言易位
E22：G →Ｈ＝┐Ｈ→┐G
等价否定等式
E23：G <->Ｈ＝┐G<->┐Ｈ
归谬论
E24：(G →Ｈ) ∧(G→┐Ｈ)＝┐G
代入定理
设G(P1,P2,…,Pn)是一个命题公式，其中：P1、P2、…、Pn是命题变 元 ， G 1 ( P 1 , P 2 , … , P n ) 、 G 2 ( P 1 , P 2 , … , P n ) 、 . . . 、Gn(P1,P2,…,Pn)为任意的命题公式，分别用G1、G2…、Gn取代G中的P1、P2、…、Pn后得到新的命题公式：G(G1,G2,…,Gn)＝G’(P1,P2,…,Pn)
若G是永真公式（或永假公式），则G’也是一个永真公式（或永假公式）
替换定理
设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1＝H1，则G＝H。
4 命题范式
文字
命题变元或命题变元的否定称为文字
析取式（子句）
有限个文字的析取称为析取式(也称为子句）
合取式(短语）
有限个文字的合取称为合取式(也称为短语）
互补对
P与=┐ P称为互补对。
析取范式
有限个短语的析取式称为析取范式
合取范式
有限个子句的合取式称为合取范式
极大项和极小项
在含有n个命题变元P1、P2、P3、…、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、…、Pn的一个极小项或极大项
主析取范式
在给定的析取范式中，每一个短语都是极小项，则称该范式为主析取范式
主合取范式
在给定的合取范式中，每一个子句都是极大项，则称该范式为主合取范式
5 命题逻辑推理理论
定义
设G,H是公式，对任意解释I，如果I满足G，那么I满足H，则称H是G的逻辑结果(或称G蕴涵H),记为G=>Ｈ，此时称G为前提，H为结论。
判定定理
设G,H是公式， G=>Ｈ当且仅当
G→Ｈ为永真公式。
公 式 H 是 前 提 集 合
Г = { G 1 , G 2 , … , G n } 的 逻 辑 结 果 当 且 仅 当G1∧G2∧…∧Gn→Ｈ为永真公式。
推理定律
简化规则
添加规则
子主题 3
选言三段论
分离规则
否定后件式
假言三段论
二难推论
推理规则
规则P（称为前提引用规则）
在推导的过程中，可随时引入前提集合中的任意一个前提；
规则T（逻辑结果引用规则）
在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。
规则CP（附加前提规则）
如果能从给定的前提集合Г与公式P推导出S，则能从此前提集合Г推导出P→S。
命题逻辑推理的难点
弄清楚蕴涵式P→Q的逻辑关系及其真值，这里Q是P的必要条件。无论蕴涵关系如何表述，都要仔细地区分出蕴涵式的前件和后件。
2. 推理过程中推理规则、基本等值式和逻辑蕴涵式的引用要适当，逻辑思维要清晰。
3. 弄清楚几种推理方法的区别与联系，对于命题逻辑推理而言，任何一个问题的推理，都可以采取三种推理方法中的任何一种来证明，针对不同的问题选用不同的推理方法。一般而言，对于结论是蕴涵式或析取式的，大多可以采取带CP规则的直接证明方法。
谓词逻辑
1 谓词逻辑的基本概念
个体词
在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为个体词
谓词
用以刻画客体的性质或客体之间的关系即是谓词
个体常量
表示具体的或特定的个体词称为个体常量，一般用带或不带下标的小写英文字母a,b,c,…,a1,b1, c1,…等表示
个体变量
表示抽象的或泛指的个体词称为个体变量，
一般用带或不带下标的小写英文字母x,y,z,…,x1,y1,z1,…等表示
个体域（论域）
个体词的取值范围称为个体域(或论域)，常用D表示
全总个体
宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体
n元谓词（n元命题函数）
设D为非空的个体域，定义在Dn(表示n个个体都在个体域D上取值)上取值于{0,1}上的n元函数，称为n元命题函数或n元谓词，
记为P(x1, x2, …, xn)
总结
谓词中个体词的顺序是十分重要的，不能随意变更。如命题F(b, c)为“真”，但命题F(c, b)为“假”；
一元谓词用以描述某一个个体的某种特性，而n元谓词则用以描述n个个体之间的关系。
0元谓词(不含个体词的)实际上就是一般的命题；
具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中S(a)是有真值的，但S(x)却没有真值；
一个n元谓词不是一个命题，但将n元谓词中的个体变元都用个体域中具体的个体取代后，就成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。
2 谓词逻辑符号化及语言翻译
量词
定义
表达个体词量关系
全称量词
对于全称量词(x)，刻画其对应个体域的特性谓词作
为蕴涵式之前件加入。
存在量词
对于存在量词(x)，刻画其对应个体域的特性谓词
作为合取式之合取项加入
辖域
一般将其量词加在其谓词之前，记为(Vx)F(x)，(3x)F(x)
F(x) 为全称量词和存在量词的辖域
谓词翻译注意事项
如有多个量词，则读的顺序按从左到右的顺序；另外，量词对变元的约束，往往与量词的次序有关，不同的量词次序，可以产生不同的真值，此时对多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原有的含义。
有些命题在进行符号化时，由于语言叙述不同，可能翻译不同，但它们表示的意思是相同的，即句子符号化形式可不止一种。
复杂句子的谓词符号化
3 谓词的合式公式与解释
谓词公式涉及的四种符号
常量符号
用带或不带下标的小写英文字母a,b,c,…,a1,b1,c1,…来表示
个体域名称集合D给出时，它可以是D中的某个元素；
变量符号
用带或不带下标的小写英文字母x,y,z…,x1,y1,z1…来表示
当个体域名称集合D给出时，它可以是D中的任意元素；
函数符号
用带或不带下标的小写英文字母f,g,h,…,f1,g1,h1,…来表示
当个体域名称集合D给出时，n元函数符号f(x1, x2, …, xn)可以是Dn→D的任意一个函数；
谓词符号
用带或不带下标的大写英文字母P,Q,R,…,P1,Q1,R1…来表示。当个体域名称集合D给出时，n元谓词符号P(x1, x2, …, xn)可以是Dn→{0，1}的任意一个谓词。
项、原子公式和合式公式
项
任意的常量符号或任意的变量符号是项；
若 f ( x 1 , x 2 , … , x n ) 是 n 元 函 数 符 号 ， t 1 , t 2 ,…,tn是项，则f(t1, t2, …, tn)是项；
仅由有限次使用(1)，(2)产生的符号串才是项。
子主题 4
原子公式
若P(x1,x2,…,xn)是n 元谓词，t1，t2，…，tn是项，则称P(t1,t2,…,tn)为原子谓词公式，简称原子公式
合式公式
原子公式是合式公式；
若G，H是合式公式，则(┐G)、(┐H)、(G∨H)、(G∧H)、(G→H)、(G<->H)也是合式公式；
若G是合式公式，x是个体变量，则(Vx)G、(3x)G 也是合式公式；
仅仅由(1)-(3)产生的表达式才是合式公式
注意:
由原子公式、命题联结词、量词、圆括号、逗号组成的合法的符号串都是合式公式，
命题公式是特殊的合式公式。
自由变元和约束变元
约束变元
若变元x出现在使用变元的量词的辖域之内，则称变元x的出现为约束出现，此时的变元x称为约束变元。
自由变元
若x的出现不是约束出现，则称它为自由出现，此时的变元x 称为自由变元。
量词辖域
若量词后有括号，则括号内的子公式就是该量词的辖域；
若量词后无括号，则与量词邻接的子公式为该量词的辖域。
两个规则
改名规则
将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的个体变元替换；
新的变元一定要有别于改名辖域中的所有其它变量。
代入规则
将公式中出现该自由变元的每一处都用新的个体变元替换；
新变元不允许在原公式中以任何约束形式出现
改名规则和代入规则的关系
共同点
都是不能改变原有的约束关系
不同点
施行的对象不同
改名规则是对约束变元施行，代入规则是对自由变元施行
施行的范围不同
改名规则可以只对公式中的一个量词及其辖域内施行，即只对公式的一个子公式施行；而代入规则必须对整个公式同一个自由变元的所有自由出现同时施行，即必须对整个公式施行；
施行后的结果不同
施行后的结果不同：改名后，公式含义不变，因为约束变元只改名为另一个个体变元，约束关系不改变，约束变元不能改名为个体常量；代入后，不仅可用另一个个体变元进行代入，并且也可用个体常量去代入，从而使公式由具有普遍意义变为仅对该个体常量有意义，即公式的含义改变了。
闭式
设G是任意一个公式，若G中无自由出现的个体变元，则称G为封闭的合式公式，简称闭式。
谓词合式公式的解释
谓词逻辑中公式G 的每一个解释I由如下四部分组成
非空的个体域集合D ；
G 中的每个常量符号，指定D 中的某个特定的元素；
G 中的每个n 元函数符号，指定Dn到D中的某个特定的函数
G 中的每个n 元谓词符号，指定Dn到｛0, 1｝中的某个特定的谓词。
谓词合式公式的分类
有效公式
公式G称为有效公式，如果G在它所有的解释I下都取值为“真”。
矛盾公式
公式G称为矛盾公式，如果G在它所有的解释I下都取值为“假”。
可满足公式
公式G称为可满足公式，如果至少有一种解释I
使得G取值为“真”。
谓词合式公式的基本等价关系
改名规则
量词否定等值式
量词辖域的扩张与收缩律
量词分配律
改名规则
4 谓词范式
前束范式
称公式G是一个前束范式，如果G中的一
切量词都位于该公式的最前端(不含否定词)且这些
量词的辖域都延伸到公式的末端。其标准形式如下：
(Q1x1)(Q2x2)…(Qnxn)M(x1, x2, …, xn)
其中Q1为量词V或3(i=1，…，n)，M称作公式G
的母式(基式)，M中不再有量词。
谓词逻辑中的任一公式都可化为与之等价的前束范式，但其前束范式并不唯一。
转换为前束范式的步骤
消去公式中包含的联结词“->”、“<->”；
反复运用德·摩根定律，直接将“¬”内移到原子谓词公式的前端；
使用谓词的等价公式将所有量词提到公式的最前端。
Skolem标准型
设公式G是一个前束范式，如消去G中所有的存在量词和全称量词，所得到的公式称为Skolem标准型。
任意一个公式G都有相应的Skolem标准形存在，但此Skolem标准形不一定与原公式等值。
5 谓词逻辑的推理理论
定理
公式H是前提集合Г={G1 ,G2 ,…,Gn }的逻辑结果当且仅当G1∧G2∧…∧Gn→Ｈ为有效公式。
推理规则
量词关系图
推理规则
全称特指规则(US)
去掉全称量词
存在特指规则(ES)
去掉存在量词
全称推广规则(UG)
添加全称量词
存在推广规则(EG)
添加存在量词
谓词演算的综合推理方法
推导过程中可以引用命题演算中的规则P和规则T 。
如果结论是以蕴涵形式(或析取形式)给出，还可以使用规则CP。
若需消去量词，可以引用规则US和规则ES。
当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入。
证明时可采用如命题演算中的直接证明方法和间接证明方法。
在推导过程中，对消去量词的公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。
在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。
谓词逻辑推理的难点
在推导过程中，如既要使用规则US又要使用规则ES消去公式中的量词，而且选用的个体是同一个符号，则必须先先使用规则ES，再使用规则US。然后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所要的结论。
如一个变量是用规则ES消去量词，对该变量在添加量词时，则只能使用规则EG，而不能使用规则UG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。
如有两个含有存在量词的公式，当用规则ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。
在用规则US和规则ES消去量词、用规则UG和规则EG添加量词时，此量词必须位于整个公式的最前端，并且它的辖域为其后的整个公式。
在添加量词(Vx)、(3x)时，所选用的x不能在公式G(y)或G(c)中自由出现且G(y)或G(c)对x是自由的。
在使用规则EG引入存在量词(3x)时，此x不得仅为G(c)或G(y)中的函数变元。在使用规则UG引入全称量词(Vx)时，此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。
在使用规则UG引入全称量词(Vx)时，G(y)中不得出现在使用规则US引入y之后由规则ES引入的常量或函数。
查看更多
相似思维导图模版
首页
我的文件
我的团队
个人中心