离散数学
一、集合论
针对一个具体范围,所有对象的集合为全集,记作
幂集:设
集合的运算:
- 对称差集:
,即属于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,设有集合
5.3 偏序关系
设R为非空集合A上的关系,若R是自反的、反对称的、传递的,则称R为A上的偏序关系,记作
最大、最小、极大、极小元:
- b是B的最大元<->B中的所有元素都比b小。
- b是B的最小元<->B中的所有元素都比b大。
- b是B的极大元<->B中没有比b大的元素。
- b是B的极小元<->B中没有比b小的元素。
上确界:
设
- 对任意的
,满足 ,则称a为B的上界。 - 若元素
是B的上界,元素 是B的任何一个上界,若均有 ,则称 为B的最小上界或上确界。
离散数学
https://d4wnnn.github.io/2024/06/25/Courses/离散数学/