离散数学知识点总结.docx

注意/技巧：析取符号为V,大写字母V
x+y=3不是命题
前件为假时，命题恒为真
运用吸收律
命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。也就是说，在不改变原意的基础上，按明法推出矛盾，比如R合取非R，即可得证。否定的步骤写作P（假设前提）
CP规则法：结论必须是条件式，若不是，需要作出转换，将前件加入前提的步骤写作P（附加前提）
以上用到的命题等价公式、蕴含公式只需写E、I即可
第二章谓词逻辑
谓词和量词
谓词将简单命题进一步分析，找出所描述的对象及对象间的关系，抽象出同类命题描述的一般模式，谓词刻画了单个个体的的特性或者多个个体间关系的模式
个体常元、个体变元
论域（个体域）：个体变元的取值范围
量词分为全称量词和存在量词。
量化分为全称量化和存在量化。
量化后所得命题的真值与变元的论域有关。引入一个统一的个体论域——全总个体域，它包括所有个体变元所能代表的所有可能的个体以后除非特别说明，否则论域都默认是全总个体域。此时，对个体变元的变化范围，可以用特性谓词（如H（x）:x是人）来加以限制
将特性谓词加入命题公式时，有以下两条重要的规则：
对于全称量词，特性谓词作为条件式的前件加入
对于存在量词，特性谓词作为合取式的合取项加入
谓词公式
谓词公式的定义与命题公式的定义基本上相同
在辖域内x的一切出现称为约束出现，约束出现的个体变元x称为约束变元。
个体变元的非约束出现称为自由出现，自由出现的个体变元称为自由变元约束变元的换名（防止引起混淆）规则:对某个约束变元换名时，需对量词的作用变元以及该量词辖域内所有受该量词约束的约束变元一起换名。
自由变元的换名规则:自由变元代入时，谓词公式中该变元自由出现的每一处都要同时代入
谓词演算的永真公式
谓词公式有永真、永假和可满足三种情况，而这都是针对特定论域而言的
等价：给定任意两个谓词公式A和B，若对于任何赋值，A和B的真值均相同，则称谓词公式A和B等价，记为AB
蕴含：给定任意两个谓词公式A和B，若A-B是永真式，则称A蕴含B，记为AB
命题逻辑中的代入规则、替换规则在谓词逻辑中同样适用
量词的否定律
不是对于任意的x都有P（x）成立等价于存在一个x使得P（x）不成立
不存在一个x使得P（x）成立等价于对于任意的xP（x）都不成立
以上两个公式说明了全称量词和存在量词可以相互表达
量词的辖域可以扩张与收缩
量词的分配律
全称量词对合取可分配
存在量词对析取可分配
课本第51页有关于分配律的若干重要公式
全称量词和存在量词在谓词公式中出现的次序不能随意改变
课本第53页有若干等价公式和蕴含公式
谓词逻辑的推理理论
命题逻辑的推理规则，如P规则、T规则和CP规则，以及证明方法在谓词逻辑中同样适用。
消去量词和引入量词的四种常用推理规则
（1）存在指定规则
存在xP（x）,有P（a）,其中a是论域中使得P（a）的真值为真的个体
（2）全称指定规则
VxP（x）,有p（y）（y在P（y）中是自由变元）和P（a）
注意：当对谓词公式存在xP（x）和VxQ（x）均应用指定规则指定为同一个体时，应先进行存在指定，再进行全称指定(3)存在推广规则
P(a),有存在xP(x)
(4)全称推广规则
TnP(x),有TnVxP(x)。如果能够从已知的公理和前提证明对于论域中的任一个体都使(x)为真，则可以得到VxP(x)为真
第三章集合与关系
集合的概念与表示
符号：子集匸，真子集u或
空集是任意集合的子集且是任何非空集合的真子集。因为空集不是空集的真子集
重要的概念还有幂集
集合的基本运算
基础：交、并、补、差(也叫做相对补)
对称差(环和)，环积的定义及运算需要背过
课本69页有若干集合运算律
课本70页有三条重要的公式
容斥原理
两个集合的容斥原理非常重要必须掌握
若干个集合的容斥原理也要了解
归纳证明
需要掌握的有数学归纳法第一原理和数学归纳法第二原理
数学归纳法第一原理在证明n+1规模成立时为了尽量避免分解中的错误通常采用“从n+1
个元素集合中取出1个元素让问题变成n规模，应用归纳假设后再放回去”的策略
集合的笛卡尔积
笛卡尔积也叫做叉集，其中的元素为序偶或n元组（序偶为n=2的特例）集合A的n次方An的概念便出于此。
注意做笛卡尔积的顺序不能随意改变
笛卡尔积运算对交、并运算可分配。同时注意先后顺序
二元关系
定义：两个集合A和B的笛卡尔积AxB的任意子集R,称为集合A到B上的二元关系。二元二元，说明了R是由序偶组成的集合
若x与y有R关系，则序偶＜x,y＞应属于集合R，并与＜y,x＞属