离散数学

一、集合论

针对一个具体范围，所有对象的集合为全集，记作或者,在韦恩图中一般用方形表示全集。

幂集：设为任意集合，把的所有不同子集构成的集合叫做的幂集，记作

集合的运算：

• 对称差集：,即属于A且不属于B，或属于B但不属于A

德摩根律： 可数集合：凡是与自然数集合等势的集合，称为可数集合，该集合的基数记为(阿列夫零)。

不可数集合：凡是与开区间等势的集合，称为不可数集合，该集合的基数记为(阿列夫)。

二、命题逻辑

命题：具有确切真值的陈述句。

永真公式(重言式)：在所有的解释下其真值都为真。

永假公式(矛盾式)：在所有的解释下其真值都为假。

基本等价关系：

• 蕴含式：

• 假言易位：

• 等价式：

• 等价否定式：

• 归谬论：

三、谓词逻辑

在原子命题中，可以独立存在的客体，称为个体词。而用以刻画客体的性质或客体之间的关系就是谓词。

https://www.bilibili.com/video/BV1RA411C7ma?t=583.6&p=16

四、二元关系

4.1 关系的定义

序偶：由两个元素按照一定的次序组成的二元组称为序偶，记作,其中为第一元素，为第二元素。

笛卡尔积：

笛卡尔积不满足结合律和交换律。

当集合A，B都是有限集时，满足

什么是二元关系？

• 设A，B为两个非空集合，称的任意子集为从到的一个二元关系，简称关系。其中称为关系的前域，称为关系的后域。若，则称为上的一个二元关系。
• 若序偶,通常把这一事实记为，读作，对有关系。
• 恒等关系：
• 全关系：,记作

4.2 关系的性质

设R为集合A上的关系。

• 自反性：若对任意的,都有,那么称R在A上是自反的，或R具有自反性。
• 反自反性：若对任意的,都有,那么称R在A上是反自反的，或R具有反自反性。
• 对称性：若对任意的,如果,那么，那么称R是对称的。
• 反对称性：若对任意的,如果,且,那么,那么称R是反对称的。
• 传递性：对任意的，若且,那么,则称R是传递的。

五、特殊关系

5.1 等价关系

设R为非空集合A上的关系

• 等价关系：设R为非空集合A上的关系，若R是自反的、对称的、传递的，则称R为A上的等价关系。

• 生成元：设R为非空集合A上的关系，对任意的,称集合为x关于R的等价类，或叫做由x生成的一个R等价类，其中x称为的生成元。

• 商集：设R为非空集合A上的关系，由R确定的一切等价类的集合，称为集合A上关于R的商集，记为。

5.2 集合的划分

给定一个非空集合A，设有集合，如果满足： 则集合称作集合A的一个划分

5.3 偏序关系

设R为非空集合A上的关系，若R是自反的、反对称的、传递的，则称R为A上的偏序关系，记作,读作小于等于。

最大、最小、极大、极小元：

• b是B的最大元<->B中的所有元素都比b小。
• b是B的最小元<->B中的所有元素都比b大。
• b是B的极大元<->B中没有比b大的元素。
• b是B的极小元<->B中没有比b小的元素。

上确界：

设是偏序集，B是A的任何一个子集，若存在元素,使得：

• 对任意的,满足，则称a为B的上界。
• 若元素是B的上界，元素是B的任何一个上界，若均有,则称为B的最小上界或上确界。