离散数学-课件-PPT-超强合集

第一篇数理逻辑逻辑学（逻辑学（logic））是一门研究思维形式及思维规律的科学。是一门研究思维形式及思维规律的科学。数理逻辑数理逻辑（mathematicallogic)是用数学的方法来研究人类推理过程的一门数学学科。数理逻辑数理逻辑又称符号逻辑、现代逻辑。其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。第一章命题逻辑1-1命题及其表示法1-2联结词1-3命题公式与翻译1-4真值表与等价公式第一章命题逻辑1-5重言式与蕴涵式1-6其他联结词1-7对偶与范式1-8推理理论第一章命题演算及其形式系统1-1命题及其表示法把对确定的对象作出判断的陈述句称作命题命题（propositionsorstatements）当判断正确或符合客观实际时，称该命题真真（True），用“T”或“1”表示；否则称该命题假假（False），用“F”或“0”表示。要点：确定的对象作出判断陈述句（见P-2的句子）通常把不含有逻辑联结词的命题称为原子命题原子命题或原子原子（atoms）（自然语言中的单句,P-2的(1)、(2)、(4)）把由原子命题和逻辑联结词共同组成的命题称为复合命题复合命题（compositivepropositionsorcompoundstatements）（自然语言中的复句，P-2的(9)、(10)）。命题的符号化（标示符）：可以用以下两种形式将命题符号化：.用（带下标的）大写字母；例如：P：今天下雨。.用数字。例如：[12]：今天下雨。上例中的“P”和“[12]”称为命题标示符。命题常元命题常元（propositionconstants）我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元命题常元。命题变元命题变元（propositionvariable）是以“真、假”或“1，0”为取值范围的变元，它未指出符号所表示的具体命题，可以代表任意命题。指派当命题变元用一个特定命题取代时，该命题变元才能有确定的真值，从而成为一个命题。称对命题变元进行指派对任意给定的命题变元p1,…,pn的一种取值状况，称为指派指派或赋值赋值（assignments），用字母，等表示当A对取值状况为真时，称指派弄真弄真A或是A的成真赋值，记为(A)=1；反之称指派弄假弄假A或是A的成假赋值，记为(A)=0。1-2联结词否定词“并非”合取词“并且”析取词“或”条件词“如果……，那么……”双条件词“当且仅当”(1)(1)否定否定（negation）定义定义11--2.12.1设设PP为一命题，为一命题，PP的否定是一的否定是一个新命题，记作个新命题，记作““┐┐PP””。若。若PP为为TT，，┐┐PP为为FF；若；若PP为为FF，，┐┐PP为为TT。。联结词联结词“┐┐”表示自然语言中的“并非”（not）。p┐pF（0）T（1）T（1）F（0）表1-2.1否定词“┐┐”的意义“见假为真，见真为假”┐p读作“并非p”或“非p”。（（22））合取（conjunction）定义定义11--2.22.2两个命题两个命题PP和和QQ的合取是一个复合的合取是一个复合命题，记作命题，记作PP∧QQ。。当且仅当当且仅当PP、、QQ同时为同时为TT时，时，PP∧QQ为为TT，，其他情况下，其他情况下，PP∧QQ的真值都是的真值都是FF。。合取联结词“∧”表示自然语言中的“并且”（and）。1-2.2合取词“∧”的意义pqp∧qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）F（0）F（0）T（1）p∧q读作“p并且q”或“p且q”见假为假，全真为真。（（33）析取）析取词（disjunction）定义定义11--2.32.3两个命题两个命题PP和和QQ的析取是一个复合的析取是一个复合命题，记作命题，记作PP∨∨QQ。。当且仅当当且仅当PP、、QQ同时为同时为FF时，时，PP∨∨QQ为为FF，，其他情况下，其他情况下，PP∨∨QQ的真值都是的真值都是TT。。析析取联结词“∨∨”表示自然语言中的“或”（or）。表1-2.3析取词“∨∨”的意义pqp∨qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）T（1）T（1）T（1）见真为真，全假为假。p∨q读作“p或者q”、“p或q”。（（44）条件）条件词（implication)定义定义11--2.42.4给定两个命题给定两个命题PP和和QQ，，其条件命题是一个其条件命题是一个复合命题，记作复合命题，记作PP→→QQ。。当且仅当当且仅当PP的真值为的真值为TT，，QQ的真值的真值为为FF时，时，PP→→QQ的真值为的真值为FF，，其他情况下，其他情况下，PP→→QQ的真值的真值都是都是TT。。条件条件联结词“→→”表示自然语言中的“如果…，那么…”（if…then…）。表1-2.4条件条件词“→→”的意义pqp→qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）T（1）F（0）T（1）p→q中的p称为条件前件条件前件，q称为条件后件条件后件前真后假为假，其他为真。（（55）双条件）双条件(two-way-implication)定义定义11--2.52.5给定两个命题给定两个命题PP和和QQ，，其复合命题其复合命题PPQQ称作双条件命题称作双条件命题。当。当PP和和QQ的真值相同时，的真值相同时，PPQQ的真值的真值为为TT，，否则，否则，PPQQ的真值都是的真值都是FF。。双条件双条件联结词“”表示自然语言中的“当且仅当”（ifandonlyif）。1-2.5双向条件条件词“”的意义pqpqF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）F（0）F（0）T（1）pq读作“p与q互为条件”，“p当且仅当q”。相同为真，相异为假。定义1-3.1以下四条款规定了命题公式命题公式（propositionformula）的意义：（（11）单个）单个命题常元或命题变元是命题公式，也称为原子公式或原子。（（22））如果A是命题公式，那么┐A也是命题公式。（（33））如果A，B是命题公式，那么（A∧B），（A∨B），（A→B），（AB）也是命题公式。（（44））只有有限步引用条款（1）、（2）、（（33））所组成的符号串是命题公式。命题公式命题公式又称为又称为合式公式合式公式WffWff（（WellWellformedformulaformedformula））WffWff的的正例和反例见正例和反例见PP--1010页。页。1-3命题公式与翻译联结词的优先级联结词的优先级命题公式外层的括号可以省略；联结词的优先级：联结词的优先级：┐、∧、∨、→、。利用加括号的方法可以提高优先级利用加括号的方法可以提高优先级。范例：如下的WffWff：P∧Q→R等价于WffWff：（（P∧Q）→R）等价于WffWff：（P∧Q）→R不等价于WffWff：P∧（Q→R）自然语言的语句用WffWff形式化主要是以下几个方面：①要准确确定原子命题，并将其形式化。②要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。③必要时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致。④需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。⑤要注意语句的形式化未必是唯一的。自然语言的语句用WffWff形式化的的例子见例子见PP--1010页。页。1-4真值表与等价公式定义1-4.1（真值表）在命题公式WffWff中，中，对于公式中分量一切可能的指派组合,公式A的取值可能用下表来描述，这个表称为真指表真指表（truthtable）。真值表的例子见的例子见PP--1313页表页表1-4.1、表、表1-4.2、表、表1-4.3和PP--1414页表页表1-4.4、表表1-4.5、表、表1-4.6。。定义1-4.2（等价公式）给定两个命题公式A和B，设P1，P2，…，Pn为所有出现于A和B中的原子变元，若给P1，P2，…，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作AB等价证明方法1：可以用真值表验证两个WffWff是否等价，见P-13的例题5“真值表法”。常用的等价等值式E1┐┐AA双重否定律E2A∨AA幂等律E3A∧AA幂等律E4A∨BB∨A交换律E5A∧BB∧A交换律E6(A∨B)∨CA∨(B∨C)结合律E7(A∧B)∧CA∧(B∧C)结合律E8A∧(B∨C)(A∧B)∨(A∧C)分配律E9A∨(B∧C)(A∨B)∧(A∨C)分配律E10┐(A∨B)┐A∧┐B德摩根律E11┐(A∧B)┐A∨┐B德摩根律E12A∨(A∧B)A吸收律E13A∧(A∨B)A吸收律E14A→B┐A∨BE15AB(A→B)∧(B→A)E16A∨ttE17A∧tAE18A∨fAE19A∧ffE20A∨┐At排中律E21A∧┐Af矛盾律E22┐tf,┐ft否定律E23A∧B→CA→(B→C)E24A→B┐B→┐A逆否律E25(A→B)∧(A→┐B)┐AP-16例题6验证吸收率1律0律定义1-4.3如果X是WffWffA的一部分，且X本身也是一个WffWff，则称X为公式A的子公式。定理1-4.1（替换原理替换原理RuleofReplacement，简记为RR）如果X是WffWffA的子公式，若XY，如果将A中的X用Y来置换，所得到的新公式B与公式A等价，即AB。
等价证明方法2：证明思路：“讨论指派法”
等价证明方法3：见P-16的例题7“等价代换法”。定义1-5.1对命题公式A，如果对A中命题变元的一切指派均弄真A，则A称为重言式重言式（tautology），又称永真式永真式.如果至少有一个指派弄真A，则A称为可满足式可满足式（satisfactableformulaorcontingency）。定义1-5.2如果对A中命题变元的一切指派均弄假A，则称A为不可满足式不可满足式或矛盾式矛盾式（contradictionorabsurdity）或永假式永假式。1-5重言式与蕴涵式定理1-5.1任何两个重言式的合取或析取，仍然是一个重言式。
证明思路：“讨论指派法”A为T，B为T，A与B析取（或合取）仍为T，
定理1-5.2一个重言式，对同一分量都用任何Wff置换，其结果仍为一重言式。
证明思路：“讨论指派法”真值与分量的指派无关，置换后与仍为T。
见P-20的例题1定理1-5.3设A、B是两个Wff，一个重言式，AB当且仅当AB为一重言式。
关于“当且仅当”的证明思路：双向证明法，从“AB”出发推出“AB为一重言式”；再从“AB为一重言式”出发推出“AB”。
定义1-4.2‘（等价公式的另一种定义）当命题公式AB为重言式时，称A逻辑等价于B，记为AB，它又称为逻辑等价式逻辑等价式（logicallyequivalentorequivalent）。定义1-5.3当命题公式A→B为重言式时，称A逻辑蕴涵B，记为AB，它又称为逻辑蕴涵式逻辑蕴涵式(logicallyimplication)。常用的逻辑蕴涵式见逻辑蕴涵式见pp--2121页表页表11--5.25.2定理1-5.4设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP。
证明思路：本定理的结论是“PQ”本定理的条件是“PQ且QP”如果能从条件“PQ且QP”推出结论“PQ”，说明条件是充分的；如果能从结论“PQ”推出条件“PQ且QP”，说明条件是必要的。先证必要性：XXXXXX再证充分性：XXXXXX
关于等价式和蕴涵式的性质：（1）AB当且仅当AB（2）AB当且仅当A→B（3）若AB，则BA等价对称性（4）若AB，BC，则AC等价传递性（5）若AB，则┐B