离散数学

命题逻辑

判断命题

命题的概念（给出语句，判断是否为命题）

下列语句是命题的有（）

明年中秋节的晚上是晴天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）

几个公式：

德摩根律蕴含等价式 等价等价式

求析取范式合取范式

公式化简一下 真值表写出来结果为1的取值 以小项(默认真赋值）的合取做析取 为主析取范式 反过来 结果为0的 以大项(默认假赋值)的析取做合取 为主合取范式

演绎推理证明

命题逻辑：演绎法证明 提示：结论是蕴含式

考两个 一个是将题目符号化 然后再用演绎法证明 这个视频结合了两个考点

谓词逻辑

谓词符号化

设S(x): x是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（ ）

前束范式

谓词逻辑：求前束范式

求公式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))量词辖域扩张

集合

幂集

已知集合求幂集

包含排斥

包含排斥原理（记住两个公式）

关系

性质

关系性质的判断（自反性、对称性、传递性）

一些基本概念：

一个一个去检查自反 反自反 对称 反对称 传递

闭包

求幂集、闭包（自反闭包r(R)、对称闭包s(R)、传递闭包t(R)）

设集合A = {a，b，c，d}，A上的关系R = {<a，b>，<b，a>，<b，c>，<c，c>，<c，d>}

R2={<a，a>，<a ，c>，<b，b>，<b，c>，<b，d>，<c，c>，<c，d>}。

R3={<a，b>，<a，c>，<a，d>，<b，a>，<b，c>，<b，d>，<c，c>，<c，d>}。

r(R)=R∪IA={<a，a>，<b，b>，<c，c>，<d，d>，<a，b>，<b，a>，<b，c>，<c，d>}

s(R)= R∪R-1={<a，b>，<b，a>，<b，c>，<c，b>，<c，c>，<c，d>，<d，c>}

t(R)=R∪R2∪R3∪R4={<a，b>，<b，a>，<b，c>，<c，c>，<c，d>}

∪{<a，a>，<a，c>，<b，b>，<b，c>，<b，d>，<c，c>，<c，d>}∪{<a，b>，<a，c>，<a，d>，<b，a>，<b，c>，<b，d>，<c，c>，<c，d>}

∪{<a，a>，<a，c>，<a，d>，<b，b>，<b，c>，<b，d>，<c，c>，<c，d>}={<a，a>，<a，b>，<a，c>，<a，d>，<b，b>，<b，c>，<b，d>，<c，c>，<c，d>}

等价关系

已知划分求等价关系，已知等价关系求商集（或划分）

函数

概念

函数的概念（提示：两个条件）

一个x对于一个y,每一个x都要有y对应

类型

函数类型的判断（单射，满射，双射）

代数

Q为有理数集N，Q上定义运算为ab=a+b–ab，则<Q，*>的幺元为( )

a b 10

在（）中 补元是唯一的？

有界格有补格 分配格有补分配格

设S={0，1}，*为普通乘法，则<S，*>是( )

半群，但不是独异点

只是独异点，但不是群

群

环，但不是群

六阶群的子群的阶数可以是( )

1,2,5 2,4 3,6,72,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)。

二元运算性质证明

二元运算的性质（封闭、交换、结合、分配）

设∘运算为Q上的二元运算，𝑥,𝑦∈Q,𝑥∘𝑦=𝑥+𝑦2𝑥𝑦，证明∘运算满足交换和结合律。

任取𝑥，𝑦∈Q， 𝑥∘𝑦=𝑥+𝑦2𝑥𝑦=𝑦+𝑥2𝑦𝑥=𝑦∘𝑥，

所以∘运算满足交换律。

任取𝑥，𝑦，𝑧∈Q，

(𝑥∘𝑦)∘𝑧=(𝑥+𝑦2𝑥𝑦)+𝑧2(𝑥+𝑦2𝑥𝑦)𝑧

=𝑥+𝑦+𝑧2𝑥𝑦2𝑥𝑧2𝑦𝑧4𝑥𝑦𝑧

𝑥∘(𝑦∘𝑧)=𝑥+(𝑦+𝑧2𝑦𝑧)+ 2𝑥(𝑦+𝑧2𝑦𝑧)

=𝑥+𝑦+𝑧2𝑥𝑦2𝑥𝑧2𝑦𝑧4𝑥𝑦𝑧

所以∘运算满足结合律。

思考：如果给定两个运算如何验证分配律。

格补元

特殊格的判断（分配格、有界格、有补格）

补元的求解

树图

出入度

如何从邻接矩阵获取点的出入度

横着数是出度数 竖着数是入度数

握手定理

树的性质（点和边的关系m=n-1）与握手定理结合的使用。（提示：树是特殊的图，图中的握手定理在树中同样适用）

在任何图中必定有偶数个( )

度数为偶数的结点 入度为奇数的结点度数为奇数的结点出度为奇数的结点

设G是一棵树，n,m分别表示顶点数和边数，则( )

n=mn=m+1m=n+1 不能确定

一棵树有10片树叶，3个3度结点，其余全是4度结点，则该树有( )个4度结点

12 3 4

一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有( )片树叶

3 476

匹配

4、特殊图：匹配的判定（t条件，相异性条件的使用）

提示：t条件为充分条件，相异性条件为充要条件

做题要点：画图、说明理由、写出其中的一种匹配方案

现有三个课外小组：语文组，数学组和英语组，有五个学生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为英语组成员。