1. 全栈程序员必看首页

离散数学常见知识点

全栈程序员-站长 • • 未分类 • 阅读 2

离散数学常见知识点对于离散数学常见知识点的整理

离散数学常见知识点

本人复习自用，仅供参考，不保证全面

集合

集合的长度

集合加绝对值表示集合的长度

A = {1,2,{1,2}} 则|A|=3

B = {∅,2,{1,2}} 则|B|=3

幂集

集合A的全部子集构成的集合称之为A的幂集，记作P(A)

映射

两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素a，B中总有唯一的一个元素b与它对应，就这种对应为从A到B的映射，记作f：A→B

像：b称为元素a在映射f下的像，记作：b=f(a)

原像：a称为b关于映射f的原像。集合A中所有元素的像的集合称为映射f的值域，记作f(A)

要点：

  1. 定义域每个元素都能对应到值域中的唯一一个元素
  2. “映射”是比函数更广泛一些的数学概念，函数是特殊的映射
  3. 函数的值域不能有剩余元素，而映射可以
  4. 映射和函数都不可以一对多
  5. 映射可以多对一
  6. 原像集应当是像集的子集

若集合AB的元素个数为m,n, 则从集合A到集合B的映射的个数为 m n m^{^{n}} mn

可以把映射想象成镜子成像：

  1. 一个镜子照一个元素不能照出两个像。
  2. 集合A中每个元素都会被照到
  3. 单射：像的原像是唯一的
  4. 满射集合B的每个元素都有原像

单射

单射（injection）：每一个x都有唯一的y与之对应；

设f是由集合A到集合B的映射，如果所有x,y∈A,且x≠y，都有f(x)≠f(y),则称f为由A到B的单射。

满射

满射（surjection）：每一个y都必有至少一个x与之对应；

对于 y = x 2 y=x^{^{2}} y=x2，当你定义X属于实数且Y属于实数集时由于存在像Y<0没有原像X对应所以不满射，但是如果你改变像集定义为正实数那就满射了。

综上，映射先看集合的范围。

双射

双射（bijection）：同时满足单射满射，即每一个x都有y与之对应，每一个y都有x与之对应。

当且仅当映射F满足双射，其逆映射G存在。

命题逻辑与等值演算

析取与合取

name symbol
析取 ∨
合取 ∧
蕴含 →

所有简单合取式都是极小项的析取范式称为主析取范式

文字：命题变项及其否定。

简单析取式用∧连接若干有限个文字，如p∧q∧ ¬ \neg ¬r

简单合取式用∨连接若干有限个文字

范式 定义
析取范式 由有限个简单合取式的析取构成的命题公式
合取范式 由有限个简单析取式的合取构成的命题公式
名字 每个字母(或者它的否定)只出现一次时被称为
简单合取式 极小项
简单析取式 极大项
范式 定义
主合取范式 合取的是有限个极大项
主析取范式 析取的是有限个极小项
公式 成真赋值 名称
¬ p ∧ ¬ q ∧ ¬ r \neg p \wedge \neg q \wedge \neg r ¬p∧¬q∧¬r 0 0 0 m 0 {m\mathop{}\nolimits_{
{0}}} m0​
公式 成假赋值 名称
p ∨ q ∨ r {p \vee q \vee r} p∨q∨r 0 0 0 M 0 {M\mathop{}\nolimits_{
{0}}} M0​

不难看出，不管事极小项还是极大项的0号位都是赋值为000时的，事实上从角标0到7就是对应它们的二进制，也就是000到111

求析取范式和合取范式常用的套路：

  1. 消去 → \to →使用公式 A → B ⇔ ¬ A ∨ B A \to B \Leftrightarrow \neg A \vee B A→B⇔¬A∨B
  2. 归谬论： ( A → B ) ∧ ( A → ¬ B ) ⇔ ¬ A \left( A \to B \left) \wedge \left( A \to \neg B \left) \Leftrightarrow \neg A\right. \right. \right. \right. (A→B)∧(A→¬B)⇔¬A

等值演算

由已知的等值式退出另外一些等值式的过程叫做等值演算。等值演算用到的置换规则并不要求写明。

证明两个公式不等值一般不能用等值演算法，可以使用如下三种方法：

  1. 真值表法
  2. 观察法（找反例）
  3. 复杂的式子在等值演算后使用1、2

证明两个式子等值：将某公式A化简，若能化简为B，则认为A和B是等值的

量词

  • 全称量词 ∀ \forall ∀
  • 存在量词 ∃ \exists ∃

把这两个东西去掉，换成集合里具体的东西叫做量词消去

图

树

树的度：无向图顶点的边数叫度。有向图顶点的边数叫出度和入度。

分支点：不属于叶子节点的节点。

完全图

每对顶点之间都恰好有一条边的简单图

k阶完全图有k*(k-1)/2条边

关系

关系的性质

  1. 自反性：

设R是A上的一个二元关系，若对于A中的每一个元素a，(a,a)都属于R，则称R为自反关系。换言之，在自反关系中，A中每一个元素与其自身相关。

主对角线全是0就自反，全是1就反自反，可以既不自反又不反自反

  1. 对称性：

有xRy就有yRx，即有(a,b)就有(b,a)

对称性反对称性不可以同时存在

  1. 传递性

(a,b)和(b,c)就有(a,c)

等价关系

等价关系是集合上的一种特殊的二元关系,它同时具有自反性、对称性和传递性。

偏序关系与哈斯图

偏序关系

偏序关系要满足自反性、反对称性和传递性

偏序关系记作≤，如果有 < x , y > ∈ ≼ < x,y > \in \preccurlyeq <x,y>∈≼，那么记作 x ≼ y x \preccurlyeq y x≼y，读作x小于等于y

这里的小于等于不是数字大小上的，而是一个顺序性，x排在y的前面或者x就是y。并且有如下定义：

  1. ∀ x , y ∈ A , x ≺ y ⇔ x ≼ y ∧ x ≠ y { \forall x,y \in A,x \prec y \Leftrightarrow x \preccurlyeq y \wedge x \neq y} ∀x,y∈A,x≺y⇔x≼y∧x​=y
  2. ∀ x , y ∈ A , x 与 y 可比 ⇔ x ≼ y ∨ y ≼ x \forall x,y \in A,x\text{与}y\text{可}\text{比} \Leftrightarrow x \preccurlyeq y \vee y \preccurlyeq x ∀x,y∈A,x与y可比⇔x≼y∨y≼x

例如:A={1,2,3}, ≼ \preccurlyeq ≼是A上的整除关系，则有三种情况：

  1. 1 ≺ {\prec} ≺ 2,1 ≺ {\prec} ≺ 3
  2. 1 = 1, 2 = 2, 3 = 3
  3. 2和3不可比

设R是非空集合A上的偏序关系，若任意的A中x与y均可比则R成为A上的全序关系。

设 < A , ≼ > < A, \preccurlyeq > <A,≼>为偏序集， ∀ x , y ∈ A { \forall x,y \in A} ∀x,y∈A，如果 x ≺ y x \prec y x≺y且不存在 z ∈ A z \in A z∈A使得 x ≺ z ≺ y x \prec z \prec y x≺z≺y，则称y覆盖x。

{1,2,4,6}集合上的整除关系，2覆盖1，4和6都覆盖2，但4不覆盖1，6也不覆盖4。

哈斯图

哈斯图是自底向上的，在这个 ≼ \preccurlyeq ≼ 中最小的就在最底下。

  1. 最上面的就是最大元，最大元可能不存在，存在的话也只有一个。
  2. 最下面的就是最小元
  3. 极大元的意思就是在可比的那一条链中最大的
  4. 极小元的意思就是在可比的那一条链中最小的

最大元就找那B中，如果子图也是有分叉就没得最大元，没分叉尽头最高的就是了。

最小元就找那个B中 如果只有一个根（把哈斯图看成森林），那个根就是了，如果有好几个，就没得最小元。

极大元和极小元类似上述定义，但是如果有好几个，那就算好几个，也就是说这俩是必然存在而且可能不止一个的。

比如说树杈顶端有好几个 都互相不可比，那就都是极大元。

B的最小元一定是B的下界，B的最大元一定是B的上界。

由上面所述可知，未必存在最小元和最大元，那么上界和下界也是未必存在的。

上界定义：对于偏序集 < A , ≼ > < A, \preccurlyeq > <A,≼>, B ⊆ A , y ∈ A B \subseteq A,y \in A B⊆A,y∈A，有 ∀ x ( x ∈ B → x ≼ y ) \forall x \left( x \in B \to x \preccurlyeq y \right) ∀x(x∈B→x≼y)成立

下界定义：对于偏序集 < A , ≼ > < A, \preccurlyeq > <A,≼>, B ⊆ A , y ∈ A B \subseteq A,y \in A B⊆A,y∈A，有 ∀ x ( x ∈ B → y ≼ x ) \forall x \left( x \in B \to y \preccurlyeq x \right) ∀x(x∈B→y≼x)成立

显然上/下界是可能不在B里（但是一定在A里）

  • 上确界就是上界中“最小”的那个
  • 下确界就是下界中“最大”的那个

关系的运算

集合表达式

例如：R={

|x是y的倍数}

关系图

点＋箭头嘛

关系矩阵

就是一个矩阵，第i行j列的那个 r i j r\mathop{
{}}\nolimits_{
{ij}} rij​如果存在 x i R x j x\mathop{
{}}\nolimits_{
{i}}Rx\mathop{
{}}\nolimits_{
{j}} xi​Rxj​那就写1，否则写0。

闭包

对于A上的关系R，添加尽可能少的一些有序对使新的关系R’具有性质x，则称R’为R的x闭包

记作 名字 定义
r( R ) 自反闭包 r( R )= R ∪ R 0 {R \cup R\mathop{}\nolimits^{
{0}}} R∪R0
s( R ) 对称闭包 s( R )= R ∪ R − 1 {R \cup R\mathop{}\nolimits^{
{-1}}} R∪R−1
t( R ) 传递闭包 t( R )= R ∪ R 2 ∪ R 3 ∪ ⋯ {R \cup R\mathop{}\nolimits^{
{2}} \cup R\mathop{}\nolimits^{
{3}} \cup \cdots } R∪R2∪R3∪⋯
关系的幂运算

关系的幂运算是在关系的右复合运算基础上进行的

幂运算的计算方式如下：

R n + 1 = R n ∘ R R\mathop{}\nolimits^{ {n+1} }=R\mathop{}\nolimits^{
{n}} \circ R Rn+1=Rn∘R

对于任何A上任何关系，显然都有

R 0 = I A R\mathop{}\nolimits_{
{0}}=I\mathop{}\nolimits_{
{A}} R0​=IA​

换言之，A上任何关系的零次幂都相等。

右复合运算结果如果有相同的，只保留一个，不重复。

幂 定义
R 0 R\mathop{}\nolimits^{
{0}} R0		 { < x , x > ∣ x ∈ A } = I A \left\{ < x,x > \mid x \in A \left\} =I\mathop{
{}}\nolimits_{
{A}}\right. \right. {
<x,x>∣x∈A}=IA​
R − 1 R\mathop{}\nolimits^{
{-1}} R−1(关系的逆)
改为

代数系统

单位元

若ae=a，e称为右单位元，若ea=a，e称为左单位元，若ae=ea=a，则e称为单位元。

单位元用e表示，单位元也可以成为幺元。

除法中1是右单位元

逆元

左逆元：对于 x ∈ S x \in S x∈S 存在 y ∘ x = e y \circ x=e y∘x=e，那个y就是左逆元

右逆元：对于 x ∈ S x \in S x∈S 存在 x ∘ y = e x \circ y=e x∘y=e，那个y就是右逆元

逆元：若 y ∈ S y \in S y∈S既是x的左逆元又是x的右逆元，则称y是x的逆元



生成元

群中元素可以由最小数目个群元的乘积生成，这组群元称为该群的生成元，生成元的数目为有限群的秩。

幂等元

满足a · a = a的就是

子群

群G的某些非空子集H关于群的运算也能构成群，则称为G的子群。

交换群

若群G中的二元运算是可交换的，则称G为交换群或阿贝尔群。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226295.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月16日 下午11:53
下一篇 2026年3月16日 下午11:53


相关推荐

  • MySQL 5.7root用户密码修改[通俗易懂]

    MySQL 5.7root用户密码修改[通俗易懂]

    MySQL 5.7root用户密码修改[通俗易懂]在MySQL5.7password字段已从mysql.user表中删除，新的字段名是“authenticalion_string”.选择数据库：usemysql;更新root的密码：updateusersetauthentication_string=password(‘新密码’)whereuser=’root’andHost=’localhost’;刷新权限：fl…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年6月25日
    38
  • listView1.SelectedItems选中行要注意count>0[通俗易懂]

    listView1.SelectedItems选中行要注意count>0[通俗易懂]

    listView1.SelectedItems选中行要注意count>0[通俗易懂]在右边的ListView中选中一行，就把选中行的第二列里的值显示在textBox里 。但是当我第一次选择一行时没有什么问题，当我第二次选择一行时就出现下面的错误：未处理ArgumentOutOfRangeException InvalidArgument=“0”的值对于“index”无效。  参数名:index上网查找说是要加一句判断if(listView1.

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月12日
    15
  • Web程序员们，你准备好迎接HTML5了吗？

    Web程序员们，你准备好迎接HTML5了吗？

    Web程序员们，你准备好迎接HTML5了吗？

    全栈程序员-站长的头像 全栈程序员-站长
    2021年8月7日
    50
  • 批量添加的sql语句_批量执行sql语句

    批量添加的sql语句_批量执行sql语句

    批量添加的sql语句_批量执行sql语句假定我们的表结构如下：CREATETABLEexample(example_idINTNOTNULL,nameVARCHAR(50)NOTNULL,valueVARCHAR(50)NOTNULL,other_valueVARCHAR(50)NOTNULL)通常情况下单条插入的sql语句我们会这么写：INSERTINTOexample(example_i…

    全栈程序员-站长的头像 全栈程序员-站长
    2026年4月13日
    7
  • SPSS篇—方差分析

    SPSS篇—方差分析

    SPSS篇—方差分析上一篇文章跟大家分享了如何用 SPSS 进行回归分析 知道了回归分析下的用途以及使用的场景 今天跟大家分享的就是之前文章里面出现很多次的一个分析 方差分析 方差分析又被称作 F 检验 或者 变异数分析 主要是用于两个及两个以上样本均值差异的显著性检验 方差分析和回归分析一样 也有很多个分支 对于方差分析 一般我们是用来研究不同来源的变异对总变异的贡献大小 从而确定可控因素对因变量的影响大小 我

    全栈程序员-站长的头像 全栈程序员-站长
    2026年3月26日
    2
  • resultset类所有方法_resultset获取列名,和对应值

    resultset类所有方法_resultset获取列名,和对应值

    resultset类所有方法_resultset获取列名,和对应值 chenjieuniqueResult（）返回唯一结果（这种一般只会返一条实体类对象信息）Result（）返回结果（展示所有结果）   publicTQuaAcceptancegetTQuaAcceptance(StringqaId){       //sql语句      Stringhql="fromTQuaAcceptance…

    全栈程序员-站长的头像 全栈程序员-站长
    2025年10月20日
    5

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号