离散数学3

下面先规定几个标准集合的基数： 1) 空集的基数为0。 2) 设n为一自然数，Nn为从1到n的连贯的自然数集合， Nn={1,2,3,…,n}，Nn的基数为n，|Nn|=n 。 3) 设N为自然数的全体，N={1,2,3,…},N的基数为ℵ0(读成 阿列夫零， ℵ是希伯莱文的第一个字母)。 4) 设R为实数的全体，R的基数为ℵ ,|R|= ℵ 。 • • 以上四项规定，对于空集及Nn的基数，实际上就是集 合中元素的个数，关于ℵ0及ℵ，下面将予探讨。 有了标准基数之后，我们可以对各种集合测量其基数。 测量的手段是以双射函数为主体的等价关系一等势。 比如说，一个集合与N等势，那么这个集合的基数为 ℵ0 。
定理6 设A及B为两个可数集，那么A×B为一可数集。 定理 推论1 推论 设A1,A2,A3,…,An为n个可数集，那么 × A是可数集。
i=1 i n
定理7 (0,1)开区间上的实数不是可数集。 定理 定理8 设A为一集Y的函数，若f 是双射函数，则f 的逆关系 f –1是从Y到X的双射函数。 定理2 定理 设f 是从X到Y的函数，g 是从Y到Z的函数，则复合关 系f οg是从 X到Z的函数，将f ο g记为g ο f 。 定理3 定理 设f 是从X到Y的函数，g 是从Y到Z的函数。 1）若f 和g是满射函数，则g ο f 是满射函数； 2）若f 和g是单射函数，则g ο f 是单射函数； 3）若f 和g是双射函数，则g ο f 是双射函数。 定理4 定理 设f 是从X到Y的双射函数， f –1是f 的逆函数，则 1) (f –1) –1 = f 2) f –1 ο f = IX 3) f ο f –1 = IY
定义3 定义 设 |X|=n，P是从X到X的双射函数，称P为X上的置 换，称n为置换的阶。 • 在n个元素的集合中，不同的n阶置换的个数为n!。 • 通常用下面的方法表示置换。 x1 x2 x3 … xn P = p(x ) p(x ) p(x ) … p(x ) 1 2 3 n • 若∀xi∈X 有 p(xi) = xi ，则称P是恒等置换。 • P的逆函数P-1可表示为 p(x1) p(x2) p(x3) … p(xn) P-1 = x1 x2 x3 … xn • 置换的复合与关系的复合相同。 1 2 3 1 2 3 1 2 3 3 2 1 2 1 3 3 1 2

以上运算律的证明思路：欲证P=Q，即证 x P x Q。
2013-7-10 离散数学
20
Байду номын сангаас
三、集合算律
证明分配律：A∪(B∩C) = (A∪B)∩(A∪C) 对x， x A∪(B ∩C) (x A ) (x B∩C )
(x A) (x B x C )
Z: 整数集合
Q: 有理数集合
R: 实数集合 C: 复数集合
: 空集(不含任何元素) E: 全集 （在某一问题中，含有所涉及的全部集合的集合。）
2013-7-10 离散数学 6
三、集合的表示方法
列出集合的所有元素，元素之间用逗号 1、列举法： 隔开。如A = { a, b, c } ， B = { 1,2,4,6,7,9 } 用谓词概括该集合中元素的属性。 2、描述法： 如：A = { x | xZ 3 < x 6 } A = { x | P (x) }，其中P (x)表示x满足的性质。 即A是由所有使P (x)为真的全体x构成。
2013-7-10 离散数学 3
§3.1 集合的基本概念
内容：集合，元素，子集，幂集等。 重点：(1) 掌握集合的概念及两种表示法， (2) 常见的集合N , Z, Q, R, C 和特殊集合 ,E， (3) 掌握子集及两集合相等的概念， (4) 掌握幂集的概念及求法。
2013-7-10 离散数学 4
2013-7-10
离散数学
8
四、集合之间的关系
3、真子集： B A。
B A B A B A
BABA B=A
4、幂 集：集合A的全体子集构成的集合，记作P (A)。 符号化为 P (A) = { x | x A} n 元集A的幂集P (A)含有2n个元素。

20
3.1.4 一阶逻辑公式与分类
解释和赋值的直观涵义
例 公式x(F(x)G(x)) 指定1 个体域:全总个体域, F(x): x是人, G(x): x是黄种人 真/假命题？ 假命题 指定2 个体域:实数集, F(x): x>10, G(x): x>0 真/假命题？ 真命题
21
3.1.4 一阶逻辑公式与分类
离散数学（第3版） 屈婉玲 耿素云 张立昂 编著 清华大学出版社出版
第3章 一阶逻辑
上海大学 谢江
1
第3章 一阶逻辑
• 3.1 一阶逻辑基本概念 • 3.2 一阶逻辑等值演算
2
3.1 一阶逻辑基本概念
• 3.1.1 命题逻辑的局限性 • 3.1.2 个体词、谓词与量词
– 个体常项、个体变项、个体域、全总个体域 – 谓词常项、谓词变项 – 全称量词、存在量词
n元谓词P(x1, x2,…, xn): 含n个个体变项的谓词, 是定义在 个体域上, 值域为{0,1}的n元函数 一元谓词: 表示事物的性质 多元谓词(n2): 表示事物之间的关系 0元谓词: 不含个体变项的谓词,即命题常项或命题变项 0元谓词是命题？ 命题均可表示成0元谓词？
8
3.1.2 个体词、谓词与量词
• 3.1.3 一阶逻辑命题符号化
3
3.1 一阶逻辑基本概念(续)
• 3.1.4 一阶逻辑公式与分类
– 一阶语言L （字母表、项、原子公式、合式 公式） – 辖域和指导变元、约束出现和自由出现 – 闭式 – 一阶语言L 的解释 – 永真式、矛盾式、可满足式 – 代换实例
4
3.1.1 命题逻辑的局限性
11
3.1.3 一阶逻辑命题符号化
一阶逻辑命题符号化

3
4
5
21
4、图的运算

1、删边、删点
2、删边集、删点集 3、收缩 4、交、并、环和
22



图的运算

1.删除运算 删边：从G中删去一边的子图，记为G-e 删点：从G中删去一点及其关联边所得的 子图，记为G-v
G
G-e
G-v
23
图的运算


删除边集：从G中删去边集E的子集E’所 得到的子图，记为G-E’ 删除点集：从G中删去点集V的子集V’及 它们的关联边所得的子图，记为G-V’
G
G-E’
G-V’
24
图的运算

2.收缩运算：
设图G中边e，它的端点为vi和vj，现删去边e，
并把vi和vj合并为新的一点vi-j，使原来与vi或vj
关联的边变为与新的点vi-j关联，称边e被收缩。
v1 v1 v5 v2 V4-5 v2
e
v4 v3
v3
25
图的运算

3.图的并、交、环和

设图G1=(V1,E1),G2=(V2,E2)
41
路与回路


在图G中，由弧组成的有限序列是弧序。 弧序的开始点记为v0，结束点记为vm。 弧序可以用有向边序列表示，也可以用顶点序列来表 示。 所有弧都不同的弧序即为有向迹，所有顶点都不同的 弧序即为有向路。

若v0= vm的有向迹，则称为有向闭迹，否则称有向开迹。 若v0= vm，而其余顶点都不相同的弧序，则称为有向闭路， 否则称有向开路。
15
图的同构
a c A B
b
d
a-A, b-B, c-C, d-D 观察点a:(a,b) ,(a,c),(a,d) 观察它对应的映射点A： (A,B),(A,C),(A,D) 其余的点都有这种点对点，边对边的映射关系。 这两个图都表现出“图中每一个顶点都与其他3

推理定律——重言蕴涵式
1. A (AB)
附加律
2. (AB) A
化简律
3. (AB)A B
假言推理
4. (AB)B A
拒取式
5. (AB)B A
析取三段论
6. (AB)(BC) (AC)
假言三段论
7. (AB)(BC) (AC)
等价三段论
8. (AB)(CD)(AC) (BD)
构造性二难
熟练掌握判断推理是否正确的不同方法（如真值表法、等 值演算法、主析取范式法等）
牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬
法 会解决实际中的简单推理问题
练习1：判断推理是否正确
1. 判断下面推理是否正确: (1) 前提：pq, q 结论：p
解 推理的形式结构: (pq)qp 方法一：等值演算法
练习2解答
(3) 证明： ① p(qr) ②p ③ qr ④ sq ⑤s ⑥ q ⑦r ⑧ rt
前提引入 前提引入 ①②假言推理 前提引入 前提引入 ④⑤假言推理 ③⑥析取三段论 ⑦附加
谢谢大家！
定理3.1 由命题公式A1, A2, …, Ak 推B的推理正确当且仅当 A1A2…AkB为重言式
注意: 推理正确不能保证结论一定正确
推理的形式结构
由{A1, A2, …, Ak}推B的推理有以下的形式结构： 1. {A1, A2, …, Ak} B
若推理正确, 记为{A1,A2,,An} B 2. A1A2…AkB
练习2：构造证明
2. 在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩.

命题演算证明法的书写规范 (以下的X和Y代表集合公式) (1) 证XY
任取x， xX … xY (2) 证X=Y
方法一 分别证明 XY 和 YX 方法二 任取x，xX … xY
注意：在使用方法二的格式时，必须保证每步推理都是充分 必要的
27
第三章 集合
命题演算法
例3-3.2 证明A(AB) = A （吸收律）
元素a属于A，记作aA； 或者a不属于A，记作aA，也可以记作┓(aA)。
（4）任意性：集合的元素也可以是集合。 例：A={1，{2}，2，{3，4}，{6}} A=5，2A，{2}A，6A,{6}A
6
第三章 集合 例如：A={{a,b}，d，{{b}}}。可以用一种树形图来表示这种
隶属关系，该图分层构成，每一层上的结点都表示一个集 合，它的儿子就是它的元素。 集合的树型层次结构
32
第三章 集合
§3-3-3 笛卡儿积
定义3-3.2 两个元素a，b组成二元组，若它们有次序 之别，称为二元有序组，或称为有序对或序偶，记为<a， b>，称a为第一分量，b为第二分量；若它们无次序区分， 称为二元无序组，或称为无序对，记为（a，b）。
有序对具有如下性质。 （1）有序性：当x≠y时<x，y>≠<y，x>。 （2）<x，y>与<u，v>相等的充分必要条件是
A
B
11
第三章 集合
§3-2 集合之间的关系
§3-2-1 集合之间的关系 （1）相等关系： • 两集合A和B相等，当且仅当它们有相同的元素。 • 若A与B相等，记为A=B；否则，记为A≠B。 • 可形式化为：A=B(x)(xAxB)。
12
第三章 集合

n i 1
Ai
(f) A (A∪B ), B (A∪B )
集合与关系 >集合的运算
交与 并的关系 定理3-2.1 设A、B、C为三个集合,则下列分配律 成立。 a) A∩(B∪C)=(A∩B)∪(A∩C) b) A∪(B∩C)=(A∪B)∩(A∪C) 定理3-2.2 设A、B为任意两个集合,则下列吸收律 成立 a) A∪(A∩B)=A b) A∩(A∪B)=A 定理3-2.3 A B 当且仅当 A∪B=B 或 A∩B=A。
集合与关系 > 集合的运算
本节重点掌握的概念: 集合, 集合相等,集合包含, 幂集。
本节重点掌握的方法: 集合的表示, 求幂集.
作业
3-1 （1）（a）,（c） ,（e）
（3） （4） （a）,（c） ,（e） (5) (6) （a）,（c） ,（e） (9)
集合与关系 >集合的概念和表示法
上节知识点: 1. 集合的概念 2. 集合的表示 3 集合之间的关系 4 空集和全集 5 幂集(power set)
A-B
E B
A
集合与关系 >集合的运算
• 绝对补 定义3-2.4 设E为全集,任一集合A关于E的补 E-A, 称为集合A的绝对补,记作~A。
即 ~ A={ x| xE ∧ xA}
集合与关系 >集合的运算
(3) 集合的补(complement) 定义3-2.3 设A、B为任意两个集合,所有属于A而 不属于B的一切元素组成的集合S称为B对于A的 补集,或相对补,记作A-B。 即 A-B={ x| xA ∧ xB} 或 xA-B xA但 xB
例如 A={2, 5, 6} B={1, 2, 4, 7, 9} A-B={5, 6} B-A={1,4,7,9} E - A?

集合的交，并运算 , :2X 2X 2X 是二元运算。
•关于运算，我们主要考虑其封闭性。 n元运算f的封闭性：对于任何n个元素x1 , x2 , , xn， x1 , x2 , , xnX f(x1 , x2 , , xn)X ，
或者 (x1 , x2 , , xn)Xn f(x1 , x2 , , xn)X 。
(8)偏函数(partial function)：部分有定义的函数。即 D(f)X （或者f -1(Y)X） 。
D(f) X D(f)X
2021/5/27
9
离散数学
例1.截痕函数(cross function)：f :X2XY ， f(x) = {x}Y 。
XY Y
{x}Y
Xx
例2.计算机是一个函数。即 计算机:输入空间输出空间；
2021/5/27
1
离散数学 第三章 函数
§1.函数的基本概念 §2.函数的复合
2021/5/27
2
离散数学
第三章 函数（function）
§1.函数基本概念
定义1.函数(映射(map)、变换(transformation))
函数是后者唯一的关系。即
f是由X到Y的函数，记为f :XY
f XY(xX)(yY)(zY)((x, y)f (x, z)f y=z)
f ={((x,y), z) : x, y , z 2X z= x y }
2021/5/27
13
离散数学
这里(x,y)是前者， z是后者；或者
f :2X 2X 2X ， f(x ,y) = z= x y ，
这里(x,y)是自变量， z是因变量； 因此 f = 。
例6.函数未必都有统一的表达式。不象连续函数那样大 多都有统一的表达式，离散函数大多都没有统一的表达 式。

（1） 任一对象a，对某一集合A来说，a属于A或a不属于A， 两者必居其一，且仅居其一。并且当a属于A时，称a是A的成
员，或A包含a，a在A之中，a属于A。即 a A a A
（2）集合中元素具有互异性和无序性。如{a,b,c,d}={a,b,b,c,d}
3-1 集合的概念和表示法
(3) 集合的元素个数可以是有限个也可以是无限个，具有有限个元素的集 合的为有限集，否则称为无限集。 (4) 集合中的元素也可以是集合，如
称为A和B的笛卡尔积，记作：A B
例：A {、、 、、
则：
3-4 序偶和笛卡尔积
5、多重直积：
A1 A2 A3是集合，A1 A2是笛卡尔集，也是集合仍可再作笛卡尔积
A A A A A A ( ) { , , | , , }
1
2
3
1
2
3
1
1
2
2
3
3
A A A { , , | , , }
E AB
S={x∣(x∈A)∧（xB）}
={x∣（x∈A）∧ （x∈B）}
3-2 集合的运算
b）集合A关于全集E的补。 E-A称为A的绝对补，记作~A。
E A
~A={x∣(x∈E）∧（x A）}
~ A有下列性质： ⑴ ~（ ~A）=A
⑵ ~E=
⑶~ =E
⑷A∪~A=E
⑸A∩~A=
3-2 集合的运算
* 以后判断两集合相等就主要用这一重要定理。
定理：对任一Set A， A
3-1 集合的概念和表示法
例：若A={a,b,c},写出其所有子集。 解：Ø 、{a}、{b}、{c}、{a，b}、{a，c}、{b，c}、{a，b，c}均是A的子 集

4
第三章：基于归结原理的推理证明
主要内容：谓词公式与子句集的概念,斯柯林(Sko
lem)标准范式及其求取过程,海伯伦（Herbrand） 理论的H域及其解释,置换与合一,命题和谓词归结 原理,归结过程的控制策略。
教学要求：深刻理解和掌握归结原理的基本概念
和基本归结过程。
重点：归结原理的基本概念和基本归结方法 难点：归结原理的实现方法 。 实践活动：归结原理的程序实现
离散数学讲义之
数理逻辑
主讲:邱晓红
数理逻辑简介
• 数理逻辑是用数学方法研究形式逻辑的科学。 数学方法即符号方法，故数理逻辑又称符号 逻辑。包含命题逻辑、谓词逻辑、证明论、 模型论、递归函数、公理化集合论、归纳逻 辑、模态逻辑、多值逻辑和时态逻辑等内容， 与计算机有密切关系。
2
各知识点关联图
命题逻辑 简单命题 命题 复合命题 对偶式 命题公式 真值表 主合取范式 主析取范式 合取范式 析取范式 蕴含式 前提引入 P 规则 置换等 T 规则 推理规则 推理系统 置换 归结原理 自动推理 合一 量词引入规则 量词消去规则
9
（5）把全称量词全部移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整 个部分。 （6）母式化为合取范式：任何母式都可以写成由一些谓词公式和谓词公式否定的析取的 有限集组成的合取。 需要指出的是，由于在化解过程中，消去存在量词时作了一些替换，一般情况下，公式 G 的 Skolem 标准型与 G 并不等值。
(x1 )(x2 )...(xn )M ( x1, x2 ,...,xn )
其中，M(x1,x2,…,xn)是一个合取范式，称为 Skolem 标准型的母式。
8
将谓词公式 G 化为 Skolem 标准型的步骤如下： （1）消去谓词公式 G 中的蕴涵（→）和双条件符号（） ，以A∨B 代替 A→B，以(A∧ B)∨(A∧B)替换 AB。 （2）减少否定符号（）的辖域，使否定符号“”最多只作用到一个谓词上。 （3）重新命名变元名，使所有的变元的名字均不同，并且自由变元及约束变元亦不同。 （4）消去存在量词。这里分两种情况，一种情况是存在量词不出现在全称量词的辖域内，此 时，只要用一个新的个体常量替换该存在量词约束的变元，就可以消去存在量词；另一种情况 是，存在量词位于一个或多个全称量词的辖域内，这时需要用一个 Skolem 函数替换存在量词 而将其消去。

0
0
0
1 1 0 0
1 0 1 0
0
13

一般来说, 只要不是非常明显的不可兼就使用.


例 p: 今天晚上我在寝室上自习, q :今天晚上我去电影 院看电影. 今天晚上我在寝室上自习或去电影院看电影。 p q.
14
5. 蕴涵(条件)联结词 : p q p: 我有时间, q : 我去看望我的父母. p q : 如果我有时间, 那么我去看望我的父母 . “”相当于“如果…那么…”, “若…则…”,等. p q 可读作“(若)p则q”. p称为前件, q称为后件.
p 1 1 0 0 q 1 0 1 0 pq 1 1 1 0
12
4. 异或联结词 : p q “不可兼或”, 它表示两者不能同时为真


例 p: 明天去深圳的飞机是上午八点起飞, q :明天去深圳 的飞机是上午八点半起飞. p q: 明天去深圳的飞机是上午八点或上午八点半起飞 . p 1 1 0 q 1 0 1 pq 0 1 1 p q pq 1 1 1


2

例







判断下列语句是否是命题. 2 + 3 = 5. √ 大熊猫产在我国东北. √ x > 3. 立正！ 这朵花真漂亮！ 你喜欢网络游戏吗? 1+1=10. √ 火星上有生物. √ 我说的都是假话. 小王和小李是同学. √ 你只有刻苦学习,才能取得好成绩. √
3
2. 命题的真值 命题的真值就是命题的逻辑取值. 经典逻辑值只有两个: 1和0 在数理逻辑中, 更多时候逻辑真是用 T(True) 或 t, 逻辑假用 F(False) 或 f 表示的.

例 构造下面推理的证明 2 是素数或合数. 若 2 是素数，则 2 是无理数. 若 2 是无理数，则 4 不是素数. 所以，如果 4 是素数，则 2 是合数. 用附加前提证明法构造证明 （1）设 p：2 是素数，q：2 是合数， r： 2 是无理数，s：4 是素数 （2）形式结构 前提：pq, pr, rs 结论：sq
结论（不正确）是对的 方法四 直接观察出 10 是成假赋值
解（2）答案：推理正确 方法一 方法二 方法三 方法四 真值表法（自己做） 等值演算法（自己做） 主析取范式法（自己做） P 系统中构造证明 ① pr ② rp ③ qr ④ qp （前提引入） （①置换） （前提引入） （③②假言三段论）
（8） 假言三段论规则： AB BC AC （9） 析取三段论规则： AB B A （10） 构造性二难推理规则： AB CD AC BD
(11) 破坏性二难推理规则： AB CD BD AC （12）合取引入规则： A B AB
三、P 中的证明 例 在自然推理系统 P 中构造下面推理的证明： (1)前提：p∨q,q→r,p→s,┐s 结论：r∧(p∨q) (2)前提：┐p∨q, r∨┐q ,r→s 结论：p→s 解 (1)证明： ① p→s 前提引入 ② ┐s 前提引入 ③ ┐p ①②拒取式 ④ p∨q 前提引入 ⑤ q ③④析取三段论 ⑥ q→r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ r∧(p∨q) ⑦④合取 此证明的序列长为 8，最后一步为推理的结论，所以推理正确，r∧(p∨q) 是有效结论。
例
判断下面推理是否正确：
(1)若 a 能被 4 整除，则 a 能被 2 整除；a 能被 4 整除。所以 a 能被 2 整除。 (2)若 a 能被 4 整除，则 a 能被 2 整除；a 能被 2 整除。所以 a 能被 4 整除。 (3)下午马芳或去看电影或去游泳；她没有看电影。所以，她去游泳 了。 (4)若下午气温超过 30℃，则王小燕必去游泳；若她去游泳，她就不 去看电影了。所以王小燕没有去看电影，下午气温必超过了 30℃。

第3章 集合的基本概念和运算
3.1 集合的基本概念
3.2 集合的基本运算
3.3 集合中元素的计数
3.1 集合的基本概念
1.子集:若 B⊆A⇔∀x(x∈B→x∈A),则称B为A的子集. 2.真子集:若 B⊆A ∧ B≠A,则称B为A的真子集. 3.集合相等: B⊆A ∧ A⊆B⇔A=B,称集合A与B相等. 4.空集:不含任何元素的集合称为空集.记作φ. 空集是一切集合的子集;空集是唯一的. 5.n元集:含有n个元素的集合称为n元集. 6.全集:如果所涉及的集合都是某个集合的子集,则称这个集 合为全集(E). 7.幂集:设A为集合,把A的全体子集构成的集合,称为A的幂集 记作P(A),P(A)={x|x⊆A}. 若A是n元集,则P(A)有2n个元集(n元集有2n个子集).
二.集合运算的算律 幂等律：A∪A=A, A∩A=A;
结合律: (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C); 交换律: A∪B=B∪A , A∩B=B∩A; 分配律: A∪(B∩C)=(A∪B)∩(A∪C), A∩(B∪C)=(A∩B)∪(A∩C); 同一律: A∪φ=A, 排中律: A∪～A=E; A∩E=A; 零律: A∪E=E, A∩φ=φ;
| Ai I A j I Ak | +... + ( −1) m | A1 I A2 I ...I Am | ∑
推论： 推论：在S中至少具有一条性质的元素数是
| A1 U A 2 U ... U A m |= +
1≤ i < j < k ≤ m
∑|A
i =1
m
i
|−
1≤ i < j ≤ m
∑|AI
i
二.包含排斥原理 包含排斥原理

16
在引入特性谓词后， 5. 在引入特性谓词后，使用全称量词与存 在量词符号化的形式是不同的。 在量词符号化的形式是不同的。
例将命题符号化:(1) 每个自然数都是实数. (2) 有的自然数是实数. 解(1) ∀x(N(x) →R(x)) 其中特性谓词N(x)：x是自然数 ; R(x)：x是实数 (2) ∃x(N(x) ∧R(x)) 其中特性谓词N(x)：x是自然数 ; R(x)：x是实数
8
例1(续) 续
2 (2) 2 是无理数仅当 3 是有理数 2 是无理数 3 在一阶逻辑中, 是无理数, 在一阶逻辑中 设F(x): x是无理数 G(x): x是有理 是有理 数 F ( 2 ) → G( 3 )
F ( 2 ) → G( 3 ) (3) 如果2>3，则3<4 如果 ，
符号化为
在一阶逻辑中, 在一阶逻辑中 设 F(x,y)：x>y，G(x,y)：x<y, ： ， ： 符号化为 F(2,3)→G(3,4) →
15
在不同的个体域中, 4. 在不同的个体域中,命题符号化的形式可能不一样 将命题符号化: 凡有理数均可表成分数, 例：将命题符号化: 凡有理数均可表成分数, 个体域是有理数集合. (1) 个体域是有理数集合. (2) 个体域是实数集合 解(1)∀xA(x) 其中A(x)：x可表成分数
(2)∀x( R(x)→A(x) ) 其中 R(x)：x是有理数， A(x)：x可表成分数
18
一阶逻辑中命题符号化( 一阶逻辑中命题符号化(续)
例3 在一阶逻辑中将下面命题符号化 (1) 兔子比乌龟跑得快 (2) 有的兔子比所有的乌龟跑得快 （3）并不是所有的兔子都比乌龟跑得快 ） （4）不存在跑得同样快的两只兔子 ）
19

• 充分性：设是双射，考虑的逆关系，易知，对于B 中的每个元素y，都对应着A中唯一的一个在下以y 为映象的元素x，因此， 的逆关系是B到A的映射。
2020/3/28
离散数学
12
双射的逆也是双射
• 显然，若是A到B的双射，则其逆映 射 – 1也是B到A的双射，并且对任意 的x∈A，均有： – 1((x)) = x .
2020/3/28
离散数学
24
抽屉原理（鸽巢原理）
我们知道，若A，B均为有限集，且A与B 之间存在双射，则A和B的元素个数相等，即 A～B。但是：
定理4.1.2 任何有限集均不能和其真子集等势。
• 此定理也称为抽屉原则：若将n+1个物体放入 n个抽屉中，则至少有一个抽屉中放了两个或 两个以上的物体。
第三章 映 射
映射又称为函数，是两个集合 之间一种特殊的二元关系。
本章主要介绍各种典型的映射及 其性质、运算以及它们之间的联 系。
2020/3/28
离散数学
1
§3.1 基本概念
定义3.1.1： 设A，B是两个集合，是A到B的二 元关系，若对A中每个元素a，有唯一的 b∈B， 使得<a,b>∈ ，则称为A到B的映射，记为：
本章将利用“映射”的概念建立集合 间的等势关系，并拓广集合中元素个数 的概念，引进集合的基数的概念，最后 讨论可数集与不可数集。
2020/3/28
离散数学
20
§4.1 等 势
如何比较两个集合中元素的多少呢？ 引入等势的概念。
定义4.1.1 设A和B是集合，若存在A到B 的双射，则称A与B等势，记为A ~B 。 (可形象理解为A与B的元素一样多。)
在，于是A～C，故～是传递的。 综上所

射函数。
第三章 函数
二、反函数
1、定义1：设f：AB是双射，则逆关系 f -1：BA
是从B到A的函数，称为 f 的反函数。
记 f -1 ：BA。 由定义可知：当函数 f：AB的反函数存在，若 f (x) = y，则f -1 (y) = x 且
f f 1 I A , f 1 f I B
f 0 ( x) x n 1 n f ( x ) f ( f ( x ))
第三章 函数
(2) 定理2： 设f: A→B,则 f。IB=IA。f=f
(3) 定理3：设有函数f：AB，g：BC
① 若f ，g是单射，则f g也是单射。
② 若f ，g是满射，则f g也是满射。
所以 f。g={(x, 4x 2+4x+2)}， g。f={(x, 2x 2+3)}
f。f={(x, 4x+3)}， g。g={(x, x 4+2x 2+2)}
第三章 函数
2、性质：
⑴ 定理1：设有函数f：AB，g：BC，h：
CD，则f ( g h) 和( f g ) h都是函数，且
③ 若f ，g是双射，则f g也是双射。
注：定理3的逆不成立。
第三章 函数
例3：设A={ 1, 2, 3 }, B={ a, b, c, d }, C={ x, y, z }
令 f = {(1, a), (2, b), (3, c)},
g = {(a , x), (b, y), (c, z), ( d, z)}
f ( g h) = ( f g ) h = f g h 证明： f。(g。h)(x) =(g。h) (f (x))=h (g (f (x)) =h((f。g) (x))=(f。g)。h (x)

P ( A) = {φ , A}
第二节 集合的运算 内容： 内容：集合的运算，文氏图，运算律。 重点： 重点：(1) 掌握集合的运算
A ∪ B, A ∩ B, A − B, ~ A, A ⊕ B
(2) 用文氏图表示集合间的相互 关系和运算， (3) 掌握基本运算律的内容及运用。
一、集合的运算。 集合的运算。 集合 A, B 的并集 A ∪ B， 交集 A ∩ B，相对补集
三 包含排斥定理 设A和 B是两个有限集合，则 A ∪ B = A + B − A ∩ B ，
B 其中 A, B 分别表示 A、的元数．
把包含排斥定理推广到n个集合的情况可用如下定 理表述： 设A1 , A2 ,⋯ A为有限集合，其元数分别为 A , A ,⋯, A ，则 n
1 2 n
A1 ∪ A2 ∪ ⋯ ∪ An
A= B ⇔ A⊆ B∧B⊆ A
5、特殊的集合。 空集 φ 全集 E (或 U )
φ ⊆ A ⊆ E ( A 为任一集合)
例1、选择适当的谓词表示下列集合。 、 (1) 小于5的非负整数集 (2) 奇整数集合
{x | x ∈ N ∧ x < 5} {x | x = 2n + 1 ∧ n ∈ Z }
{ } (8) {a, b} ∈ {a, b, {{a, b}}}
(7) {a, b} ⊆ a, b, {{a, b}}
例3、A, B, C 为集合，若 A ∈ B 且B ∈ C ， 、 有可能 A ∈ C 吗，有可能 A ∉ C 吗？ 解：两种情形都有可能。 设 A = {a}, B = {{a}} , C = {{a}, {{a}}} ， 则 A ∈ B, B ∈ C ，有 A ∈ C 。 又设 A = {a}, B = {{a}} , C = {{{a}}}， 则 A ∈ B, B ∈ C ，但 A ∉ C 。