离散1知识点总结
本word文档是个人根据大连理工大学离散数学的PPT和课本进行的知识点总结，仅限参考，如有造成知识点空缺，本人概不负责。
该word文档的所有解释权归本人所有。
该word文档拒绝以盈利性质分享。
该word文档不会更新，所以有错误请自行更正并及时告知诸位。
命题逻辑
命题和联结词
1.1.1命题的概念
所谓命题，是指具有非真必假性质的陈述句
命题的判断结果称作命题的真值，真值只有两个取值------真（1）或假（0）
命题常用大写字母表示
一个命题不能再分解为更简单的命题，这个命 题称为原子命题。
由多个原子命题和联结词组成的命题成为复合命题
1.1.2联结词
设P是一个命题，则P的否定是一个新的命题， 记作" ¬P"，读作"非P"
设P 和Q是命题，则用 PΛQ 表示 " P并且 Q"
设P和Q是命题，则用 P∨Q表示命题"P或者Q"
设P和Q是命题，则用P∇Q表示命题"P异或Q"
设P和Q是命题，则用P→Q表示命题"如果P那么Q"
在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为实质条件命题。
设P和Q是命题，则用P↔Q表示命题"P等值于Q"
1.2合式公式与真值表
1.2.1合式公式
1.2.2真值表
1.3永真式和等价式
1.3.1永真式
永真式/重言式：不依赖命题变元真值指派而总是取值为真（1）的命题公式
永假式/矛盾式：不依赖命题变元真值指派而总是取值为假（0）的命题公式
可满足式：至少存在一组命题变元的真值指派使命题公式为真
永真式的否定是矛盾式，矛盾式的否定是重言式。
永真式的析取、合取、单条件和双条件都是重言式。
重言式可以产生许多有用的恒等式。
1.3.2等价式
设A、B是两个命题公式，如果A、B在任意解释下（任意命题变元真值指派组合下），其真值都是相同的（A↔B为重言式），则称A和B等价。
常用等价逻辑式：
个人认为常用的有但不限于：1、2、3（交换律） 4、5、6（结合律） 7、8、9（分配律） 11、12、13（摩根律） 14（逆反律） 27（如何把蕴含拆掉） 29、30（吸收律）
1.3.3代入规则和替换规则
1.4对偶式与蕴含式
1.4.1对偶式
对偶原理↓
1.4.2蕴含式
常用永真蕴含公式：
个人认为常用的有：9（析取三段论） 12（假言三段论） 10（假言推论） 1、2、3、4（化简附加式）
1.5范式和判定问题
1.5.1析取范式与合取范式
P∧¬P永假 P∨¬P永真
1.5.2主析取范式与主合取范式
对于任意的命题公式A，其真值表中，真值取值为真（1）的真值指派组合都是主析取范式中的一个极小项
对于任意的命题公式A，其真值表中，真值取值为假（0）的真值指派组合都是主合取范式中的一个极大项
1.6命题演算的推理理论
你可以不用看懂下边这个定义（出于礼貌，我写进来了），你只要会写题就行↓
这就是前边写到的公式，可以略过↓
极速版------当你要用引入一个新的条件时（P规则）
当你要用前边的等价公式推出新的条件时（T规则）
当你要证的结论是蕴含式/你需要引入结论作为前提时（CP规则，记得写附加前提）
当你要用反证法，取结论的反为前提时（F规则，记得写假设前提）
以下用三道例题分别演示，普通方法、CP法、反证法
普通方法：
CP法：
反证法：
（反证法是引入相反的结论作为前提，推出和现有前提的矛盾，例如该题的第7步）
自己写题时可以省略部分文字，但必须要包含的是每条结论前边的序号、结论、使用的规则、规则涉及到的结论的序号
谓词逻辑
2.1基本概念和表示
2.1.1个体、谓词和谓词形式
2.1.2量词
存在唯一量词∃！，表示"恰有一个"、"唯一存在"。辖域等概念同上
存在唯一量词应该是不列入考纲的（我上了一学期翻书头一次看见它）
谓词逻辑翻译时非常重要的注意事项↓
一般来讲，量词的先后顺序不可随意交换
当量词辖域中的个体变元互不干涉时才可随意交换。
2.1.3合适谓词公式
2.1.4自由变元和约束变元
2.2谓词逻辑的翻译与解释
2.2.1谓词逻辑的翻译
把一个文字叙述的命题，用谓词公式表示出来，成为谓词逻辑的翻译或符号化
该部分十分重要，以下用两道例题做演示
2.2.2谓词公式的解释
对于一个谓词公式A，其个体域为D，若在D中怎么解释A，A的真值总为真（1），则称A在D中永真。（永假和可满足 类似定义）
2.3谓词逻辑的等价式与蕴含式
非常重要的三个公式↓
以下是一些等价式和永真蕴含式：
个人认为常用的有：E39、E40、I17、I18、I19、I20（抛开上边提到的三个公式）
以下是量词转换
2.4谓词逻辑中的推理理论
2.4.1推理规则
P、T、CP、F规则在谓词逻辑推理中仍然使用（对，就是使用，离不开的）
下边这个US、ES、UG、EG是最重要的，做题时经常会用到的（注意相应规则的使用条件）
2.4.2推理实例
谓词逻辑的推理相较于命题逻辑复杂的多，所以给出四道例题做演示，希望能总结一些经验。（不是我不想总结，是我真的不知道做题的思路怎么写）
2.5谓词逻辑中公式范式
2.5.1前束范式
2.5.2斯柯林范式
个人感觉：谓词逻辑的范式考察的可能性不大，稍微记一下看看例题就行
集合论
集合论概念较多，所以该部分总结时以概念为主，习题方面大量减少
3.1集合的概念及其表示
集合中的元素也可以是集合！！！！！！！！（套娃）
（外延和内涵不考，但是可以看看，不过也没什么b用）
（基数在离散1基本上用不到，但是是很重要的概念）
（请务必玩懂空集，在这里会非常绕弯）
（真包含只是在包含的基础上去掉了相等的情况）
（用定义证明相等可行）
（用A包含B同时B包含A也可以证明相等）
（也可以用第五章的特征函数进行相等的证明）
幂集的元素都是集合
3.2集合的运算与恒等式
交集并集在此不赘述，大家应该高中都讲过
以下是常用的集合定律：
个人认为常用的有：9、10（分配律） 19、20（吸收律） 21-26（摩根律） 31 32 33
3.3有穷集的计数和包含排斥原理
包含排斥原理↓
以下用两道例题做演示：
二元关系
4.1多重序元与笛卡尔乘积
（我们只学二重序偶，所以多重序偶带过）
|A|=m，|B|=n则|A*B|=m*n
A*∅=∅ 般来说，笛卡尔乘积不满足交换律
切记，笛卡尔乘积对应的是集合运算
笛卡尔乘积满足分配律
A⊆C∧B⊆D=＞A*B⊆C*D
4.2关系的基本概念
我们只研究二元关系
很重要的恒等关系↓
4.3关系的运算
限制用的很少↓
以下定理很少用到↓
4.4关系的性质
极速版
自反：对于x∈A，则<x,x>∈R
反自反：对于x∈A,则<x,x>∉R
极速版
对称：对于x、y∈A, <x,y>∈R,则<y,x>∈R
反对称：对于x、y∈A, <x,y>∈R,则<y,x>∉R，或当且仅当，x=y <y,x>∈R
注意的是， x和y可以相等
极速版
可传递：对于x、y、z∈A, <x,y>、<y,z>∈R,则<x,z>∈R
不可传递：对于x、y、z∈A, <x,y>、<y,z>∈R,则<x,z>∉R
注意的是，x和y和z可以任意两个相等，甚至三个相等
对于有限集合A,|A|=n
4.5关系的表示
自反关系：每个节点都有指向自己的有向边
对称关系：每两个有连线的节点必然是相互指向的
4.6关系的闭包运算
人话版
R自反------r(R)=R
R对称------s(R)=R
R可传递------t(R)=R
闭包的计算↓
比较重要的性质↓
4.7特殊关系
4.7.1集合的划分和覆盖
4.7.2等价关系
非常重要的模m同余关系↓
模m同余是等价关系
人话版
对于a∈A，与a有关系的所有元素构成的一个集合，称为等价类
我也不知道这个3是什么，所以不能给出回答。
全域关系将一个集合作为一个划分，即秩为1
恒等关系将集合中每一个元素作为一个等价类，即秩为|X|
"划分"的概念和"等价关系"的概念本质 上是相同的。
4.7.3相容关系
相容关系相较于等价，缺少了可传递的性质
4.7.4次序关系
偏序关系的性质------自反 反对称 可传递
人话版
<P, ≤>是一个偏序集合，其中≤所表示的关系不定，根据题意可以随意翻译
注意：取反不影响关系（即取反前是偏序，取反后仍是偏序）
"整除"和"整倍数"互为逆关系， 它们都是I+ 中的偏序关系。
拟序条件的性质------反自反 反对称 可传递
实数集合中的大于小于、集合中的真包含都是拟序关系
全序集合的性质------自反 反对称 可传递
全序集合是在偏序集合的基础上得来的，相较于偏序集合，全序集合中任意两个元素总有关系成立
人话版:
对于一个字符串，字母序就是从第一位开始比较大小（判断关系成立与否），若当前比较位置相同，则比较下一个位置，直到某一个字符串先遍历完，先遍历完的小于为遍历完的。
4.7.5偏序集合与哈斯图
最小（大）成员是唯一的
函数
5.1函数的基本概念与性质
很重要的一个定义（小心看不懂题）
5.2函数的合成和合成函数的性质
第二条性质非常重要
5.3特殊函数
5.4反函数
一个函数的左逆和右逆不一定是唯一的
5.5特征函数
都挺重要的，尽力记一下↓
如果记不全，可以挑几个重要的，比如7、8、9、10
特征函数可以用来证明函数的相等亦或包含关系，也可以进行函数双射等性质的推导
事例如下：
5.6基数
等势满足交换律和传递性
↑如何证明一个集合可数
查看是否有函数能实现A到N的双射（可以考虑用特征函数证明），否则可以考虑将A中的元素一一对应N中的元素
每取一次幂集，阿列夫数字+1，例如自然数集合N取幂集则从阿列夫0变成阿列夫1
