离散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

