--- title: "02-离散数学" created: 2026-01-13 tags: - 博客 --- # 离散数学 ## 命题逻辑 ## 判断命题 命题的概念（给出语句，判断是否为命题） 下列语句是命题的有（） **明年中秋节的晚上是晴天**x+y>0 当x\*y>0当且仅当x和y都大于0 我正在说谎 下列不是命题的是 7能被3整除 当且仅当太阳从西边升起，5是素数 **x加7小于0** 南昌大学科技学院位于南昌市北京东路 下列各命题中真值为真的命题有( ) **2+2=4当且仅当3是奇数** 2+2=4当且仅当3不是奇数 2+2!=4当前仅当3是奇数 2+2=4当且仅当3不是奇数 下面哪一个命题是假命题（ ） **如果2是偶数，那么一个公式的析取范式唯一** 如果2是偶数 那么一个公式的析取范式不唯一 如果2是奇数 那么一个公式的析取范式唯一 如果2是奇数 那么一个公式的析取范式不唯一 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为( )。 **p->q**非p->q 非q->p q->p ## 主范式 命题逻辑：求主范式 前置知识点： 命题联结词的真值表 非：相反且：同时真才真 或：有一个真即真蕴含：10才0其他都1 （当且仅当：相同为1否则为0） ![[image-cfcfc61b.png]] 几个公式： 德摩根律蕴含等价式 等价等价式 ![[image-19f1ed6c.png]]![[image-d4dbddc5.png]]![[image-1ab56e3a.png]] **求析取范式合取范式** 公式化简一下 真值表写出来结果为1的取值 以小项(默认真赋值）的合取做析取 为主析取范式 反过来 结果为0的 以大项(默认假赋值)的析取做合取 为主合取范式 ![[image-5849fed5.png]]![[image-6ed3d995.png]] ## 演绎推理证明 命题逻辑：演绎法证明 提示：结论是蕴含式 ![[image-be495de7.png]]![[image-3f8bb9a8.png]] 考两个 一个是将题目符号化 然后再用演绎法证明 这个视频结合了两个考点 ![[image-9705a995.png]]![[image-76360640.png]]![[image-a7e66994.png]] ## 谓词逻辑 ### 谓词符号化 ![[image-27465dfd.png]]![[image-450b8da8.png]] 设S(x): x是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（ ） ![[image-5ac7980e.png]] ### 前束范式 谓词逻辑：求前束范式 ![[image-75cd920a.png]]![[image-a66527df.png]]![[image-6dea6bbc.png]] 求公式A：(xP(x)yQ(y))xR(x)的前束范式。 解：A(xP(x)yQ(y))xR(x)消去联结词 (xP(x)yQ(y))xR(x)向 内深入 (xP(x)yQ(y))zR(z)换名规则 (xP(x)yQ(y))zR(z)量词转换 x((P(x)yQ(y))zR(z)量词辖域扩张 xy((P(x)Q(y))zR(z)量词辖域扩张 xyz((P(x)Q(y))R(z))量词辖域扩张 ## 集合 ### 幂集 已知集合求幂集 ![[image-adfd1957.png]]![[image-a45d8bd8.png]] ### 包含排斥 包含排斥原理（记住两个公式） ![[image-fec2cc4b.png]]![[image-0d1f24a6.png]] ## 关系 ### 性质 关系性质的判断（自反性、对称性、传递性） ![[image-59044a9b.png]] 一些基本概念： ![[image-63151891.png]] 一个一个去检查自反 反自反 对称 反对称 传递 ![[image-33db76d1.png]] ### 闭包 ![[image-f5cbba00.png]] 求幂集、闭包（自反闭包r(R)、对称闭包s(R)、传递闭包t(R)） 设集合A = {a，b，c，d}，A上的关系R = {，，，，} R2={，，，，，，}。 R3={，，，，，，，}。 r(R)=R∪IA={，，，，，，，} s(R)= R∪R-1={，，，，，，} t(R)=R∪R2∪R3∪R4={，，，，} ∪{，，，，，，}∪{，，，，，，，} ∪{，，，，，，，}={，，，，，，，，} ### 等价关系 已知划分求等价关系，已知等价关系求商集（或划分） ![[image-db1a88b5.png]]![[image-ad6fd98b.png]] ## 函数 ### 概念 函数的概念（提示：两个条件） 一个x对于一个y,每一个x都要有y对应 ### 类型 函数类型的判断（单射，满射，双射） ![[image-5cdaad55.png]] ## 代数 Q为有理数集N，Q上定义运算*为a*b=a+b–ab，则的幺元为( ) a b 1**0** 在（）中 补元是唯一的？ 有界格有补格 分配格**有补分配格** 设S={0，1}，\*为普通乘法，则是( ) 半群，但不是独异点 **只是独异点，但不是群** 群 环，但不是群 六阶群的子群的阶数可以是( ) 1,2,5 2,4 3,6,7**2,3** 6阶有限群的任何子群一定不是( ) 2阶 3阶**4阶**6阶 ## 幺元零元逆元 代数结构中的特殊元素 定义实数集**R**上的二元运算为：r1 r2= r1+ r2– r1r2， 问：（1）它是否存在单位元？（2）**R**中的元素是否有逆元？ 解：（1）若rl是左单位元，则r **R**，应有rl r = rl+ r – rlr = r， 于是rl– rlr = 0，即rl(1 – r) = 0。由于r是任意的，故只有rl= 0。 由于运算可交换，因此0是运算的单位元。 （2）设s是r的左逆元，则应有sr = s + r – sr = 0， 于是sr – s = r，即s(r – 1) = r。 由于运算可交换，因此只要r1，**R**中任意元素r均有逆元，其逆元是r / (r – 1)。 ## 二元运算性质证明 ![[image-9e580aed.png]]![[image-d051140a.png]] 二元运算的性质（封闭、交换、结合、分配） 设∘运算为Q上的二元运算，𝑥,𝑦∈Q,𝑥∘𝑦=𝑥+𝑦2𝑥𝑦，证明∘运算满足交换和结合律。 任取𝑥，𝑦∈Q， 𝑥∘𝑦=𝑥+𝑦2𝑥𝑦=𝑦+𝑥2𝑦𝑥=𝑦∘𝑥， 所以∘运算满足交换律。 任取𝑥，𝑦，𝑧∈Q， (𝑥∘𝑦)∘𝑧=(𝑥+𝑦2𝑥𝑦)+𝑧2(𝑥+𝑦2𝑥𝑦)𝑧 =𝑥+𝑦+𝑧2𝑥𝑦2𝑥𝑧2𝑦𝑧4𝑥𝑦𝑧 𝑥∘(𝑦∘𝑧)=𝑥+(𝑦+𝑧2𝑦𝑧)+ 2𝑥(𝑦+𝑧2𝑦𝑧) =𝑥+𝑦+𝑧2𝑥𝑦2𝑥𝑧2𝑦𝑧4𝑥𝑦𝑧 所以∘运算满足结合律。 思考：如果给定两个运算如何验证分配律。 ## 格补元 特殊格的判断（分配格、有界格、有补格） 补元的求解 ## 树图 ### 出入度 如何从邻接矩阵获取点的出入度 横着数是出度数 竖着数是入度数 ### 握手定理 树的性质（点和边的关系m=n-1）与握手定理结合的使用。（提示：树是特殊的图，图中的握手定理在树中同样适用） ![[image-2fa76e24.png]]![[image-76689428.png]] 在任何图中必定有偶数个( ) 度数为偶数的结点 入度为奇数的结点**度数为奇数的结点**出度为奇数的结点 设G是一棵树，n,m分别表示顶点数和边数，则( ) n=m**n=m+1**m=n+1 不能确定 一棵树有10片树叶，3个3度结点，其余全是4度结点，则该树有( )个4度结点 **1**2 3 4 一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有( )片树叶 3 4**7**6 ## 匹配 4、特殊图：匹配的判定（t条件，相异性条件的使用） 提示：t条件为充分条件，相异性条件为充要条件 做题要点：画图、说明理由、写出其中的一种匹配方案 ![[image-26a3d3e9.png]]![[image-c4e44775.png]]![[image-d5de1be5.png]] 现有三个课外小组：语文组，数学组和英语组，有五个学生s1，s2，s3，s4，s5。在以下两种情况的每一种情况下，在s1，s2，s3，s4，s5 中选三位组长，不兼职，问能否办到？请说明理由。如果能办到，请列举其中一种满足条件的匹配。 （1）s1，s2为语文组成员，s2，s3，s4为数学组成员，s3，s5为英语组成员。 （2）s1为语文组成员，s1，s2，s3为数学组成员，s3，s4，s5为英语组成员。