《离散数学》 教案
《离散数学》教案
第一章集合与关系
集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。
G. Cantor(康脱)是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯·诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。
一、学习目的与要求
本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运算方法，为学习后续章节打下良好基础。
二、知识点
1．集合的基本概念与表示方法；
2．集合的运算；
3．序偶与笛卡尔积；
4．关系及其表示、关系矩阵、关系图；
5．关系的性质，符合关系、逆关系；
6．关系的闭包运算；
7．集合的划分与覆盖、等价关系与等价类；相容关系；
8．序关系、偏序集、哈斯图。
三、要求
1．识记
集合的层次关系、集合与其元素间的关系，自反关系、对称关系、传递关系的识别，复合关系、逆关系的识别。
2．领会
领会下列概念：两个集合相等的概念几证明方法，关系的闭包运算，关系等价性证明。
1.1 集合论的基本概念与运算
1.1.1 集合的概念
集合不能精确定义。集合可以描述为：一个集合把世间万物分成两类,一些对象属于该集合，是组成这个集合的成员，另一些对象不属于该集合。可以说，由于一个集合的存在，世上的对象可分成两类，任一对象或属于该集合或不属于该集合，二者必居其一也只居其一。
直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。
例如：方程x2－1＝0的实数解集合；26个英文字母的集合；坐标平面上所有点的集合；……
集合通常用大写的英文字母A,B,C,…,来标记，元素通常用小写字母a,b,c,…,来表示。例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。
集合的表示方法：表示一个集合的方法通常有三种：列举法、描述法和归纳定义法。
(1) 列举法列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。在能清楚地表示集合成员的情况下可使用省略号。
例如 A={a，b，c，…，z}，Z={0，±1，±2，…}都是合法的表示。
(2) 描述法用谓词来概括集合中元素的属性来表示这个集合。
例如 B＝{x|x∈R∧x2－1＝0}表示方程x2－1＝0的实数解集。
许多集合可以用两种方法来表示，如B也可以写成{-1，1}。但是有些集合不可以用列元素法表示，如实数集合。
(3) 归纳定义法：1.3节再讨论。
属于、不属于：元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作?。例如A＝{a，{b，c}，d，{{d}}}，这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但b?A，{d}?A。b和{d}是A的元素的元素。
外延公理：两个集合A和B相等，当且仅当它们有相同的成员。
集合的元素是彼此不同的：如果同一个元素在集合中多次出现应该认为是一个元素。
如 {1，1，2，2，3}＝{1，2，3}。
集合的元素是无序的：如{1，2，3}＝{3，1，2}。
1.1.2 集合间的关系
定义1.1.1 设A ，B 为集合，如果B 中的每个元素都是A 中的元素，则称B 是A 的子集合，简称子集。这时也称B 被A 包含，或A 包含B ，记作B ?A 。称B 是A 的扩集。
包含的符号化表示为：B ?A ??x(x∈B→x∈A)。如果B 不被A 包含，则记作B ?A 。
例如 N ?Z ?Q ?R ?C ，但Z ?N 。显然对任何集合A 都有A ?A 。
注意：属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如A ＝{a ，{a}}和{a}，既有{a}∈A，又有{a}?A 。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。
定义1.1.2 设A ，B 为集合，如果B ?A 且B≠A，则称B 是A 的真子集，记作B ?A 。如果B 不是A 的真子集，则记作B ?A 。真子集的符号化表示为：B ?A ?B ?A∧B≠A。
例如 N ?Z ?Q ?R ?C ，但N ?N 。
为方便起见，所讨论的全部集合和元素是限于某一论述域中，即使这个论述域有时没有明确地指出，但表示集合元素的变元只能在该域中取值。此论述域常用U 表示，并称为全集。
定义1.1.3 不含任何元素的集合叫空集，记作Φ。空集可以符号化表示为Φ＝{x|x≠x}。
例如{x|x∈R∧x 2+1=0}是方程x 2
+1=0的实数解集，因为该方程无实数解，所以是空集。
定理1.1-1 空集是一切集合的子集。
证：对任何集合A ，由子集定义有()A x x x A Φ???∈Φ→∈，右边的蕴涵式因前件为假而为真命题，所以A Φ?也为真。
推论 空集是唯一的。
证：假设存在空集1Φ和2Φ，由定理6.1有12Φ?Φ，21Φ?Φ。根据集合相等的定义，有12Φ=Φ。
含有n 个元素的集合简称n 元集，它的含有m(m≤n)个元素的子集叫做它的m 元子集。任给一个n 元集，怎样求出它的全部子集呢？举例说明如下。
例1.1.1 A ＝{1,2,3}，将A 的子集分类：
0元子集，也就是空集，只有一个：Φ；1元子集，即单元集：{1}，{2}，{3}； 2元子集：{1,2}，{1,3}，{2,3}； 3元子集：{1,2,3}。
一般地说，对于n 元集A ，它的0元子集有0n C 个，1元子集有1n C 个，…，m 元子
集有m n C 个，…，n 元子集有n n C 个。子集总数为012n n n n n C C C +++= 个。
全集与空集在本章中起重要作用，注意掌握它们的基本概念。
注意：∈与?的联系与区别。
(1) ∈表示集合的元素（可以为集合）与集合本身的从属关系，
(2) ?表示两个集合之间的包含关系。
例如：对于集合A={a,b,c},{a}是A 的子集：{a}?A ，a 是A 的元素：a∈A。 注意：不要写成{a}∈A 和a ?A 。
{}a a ≠，但{}a a ∈；{}Φ是一元集，而不是空集。|{}|1Φ=，||0Φ=。
1.1.3 集合的运算
集合的交、并和差运算
1. 集合交、并、差运算的定义（注意集合运算与逻辑运算的对应关系）
定义 设A 和B 是集合，
(1) A 和B 的交记为A B ，定义为：{|}A B x x A x B =∈∧∈ ；
(2) A 和B 的并记为A B ，定义为：{|}A B x x A x B =∈∨∈ ；
(3) A 和B 的差记为A B -，定义为：{|}A B x x A x B -=∈∧?。
例：设{,,,}A a b c d =，{,,}B b c e =，则
{,}A B b c = ，{,,,,}A B a b c d e = ，{,}A B a d -=，{}B A e -=
定义：如果,A B 是两个集合，A B =Φ ，那么称A 和B 是不相交的。如果C 是一个集合的族，且C 中的任意两个不同元素都不相交，那么称C 是（两两）不相交集合的族。
2. 集合的并和交运算的推广（广义交、广义并）
n 个集合 12121{|}n
i n n i A A A A x x A x A x A ===∈∧∈∧∧∈ ，
12
121
{|}n i n n i A A A A x x A x A x A ===∈∨∈∨∨∈ ， 无穷可数个集合： 1
21i i A A A ∞== ，121
i i A A A ∞
== 一般情形：
{|()}S C S x S S C x S ∈=?∈→∈ （C ≠Φ），
{|()
S C S x S S C x S ∈=?∈∧∈ 3. 集合交、并、差运算的性质：
(1) 交换律 A B B A = ， A B B A = ，
(2) 结合律 ()()A B C A B C = ， ()()A B C A B C = .
(3) 分配律 ()()A B C A B A = ， ()()()A B C A B A C =
(4) 幂等律 A A A = , A A A = ,
(5) 同一律 A A Φ= , A U A = ，
(6) 零 律 A U U = A Φ=Φ ,
(7) 吸收律 ()A A B A = ， ()A A B A = ，
(8) 德摩根律 ()()()A B C A B A C -=-- ()()()A B C A B A C -=--
(9) (a) A A -Φ=, (b) A B A -?, (c)A A B ? , (d)A B A ? ,
(e) 若A B ?，C D ?,则()()A C B D ? ，()()A C B D ? ,
(f) 若A B ?，则A B A = , (g) 若A B ?，则A B B = ，
(h) A B A A B B A B =?=?-=Φ 。
证：利用运算的定义（与逻辑运算的关系）或已证明的性质。
集合的补运算
1. 集合的补运算的定义
定义：设U 是论述域而A 是U 的子集，则A 的（绝对）补为：
{|}{|}A U A x x U x A x x A =-=∈∧?=?
B A =当且仅当A B U = 和A B =Φ 。
2. 集合补运算的性质：
(1) 矛盾律 A A =Φ ； (2) 排中律 A A U = ；
(3) 德摩根律 U Φ=， U =Φ， ________A B A B = ， ________
A B A B = ；
(4) 双重否定律（A 的补的补是A ）：A A =；(5) 若A B ?，则B A ?。 例：证明A －(B ∪C)＝(A －B)∩( A －C)。
证 对任意的x ，
x ∈A －(B ∪C) ? x ∈A ∧x ?B ∪C ? x ∈A ∧┐(x ∈B ∨x ∈C) ? x ∈A ∧(┐x ∈B ∧┐x ∈C) ? x ∈A ∧x ?B ∧x ?C
? (x ∈A ∧x ?B)∧(x ∈A ∧x ?C) ? x ∈A －B)∧x ∈A －C
? x ∈(A －B)∩(A －C)
所以 A －(B ∪C)＝(A －B)∩( A －C)。
例：证明A ∩E ＝A 。
证 对任意的x ，x ∈A ∩E ?x ∈A ∧x ∈E ?x ∈A(因为x ∈E 是恒真命题)，所以A ∩E ＝A 。
注意：以上证明的基本思想是：设P ，Q 为集合公式，欲证P ＝Q ，即证P ?Q ∧Q ?P 为真。
也就是要证对于任意的x 有 x ∈P ?x ∈Q 和x ∈Q ?x ∈P 成立。对于某些恒等式可以将这两个方向的推理合到一起，就是 x ∈P ?x ∈Q 。
不难看出，集合运算的规律和命题演算的某些规律是一致的，所以命题演算的方法是证明集合恒等式的基本方法。
证明集合恒等式的另一种方法是利用已知的恒等式来代入。
例：证明A ∪(A ∩B)＝A 。
证 A∪(A∩B)＝(A∩E)∪(A∩B)＝A∩(E∪B)＝A∩(B∪E)＝A∩E＝A 。
例：证明等式A －B ＝A ∩～B 。
证 对于任意的x ，x ∈A －B ?x ∈A ∧x ?B ?x ∈A ∧x ∈～B ?x ∈A ∩～B ， 所以A －B ＝A ∩～B 。
注意：上式把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。
例：证明(A －B)∪B ＝A ∪B
证 (A －B)∪B ＝(A ∩～B)∪B ＝(A ∪B)∩(～B ∪B)＝(A ∪B)∩E ＝A ∪B 。
例：证明命题A ∪B ＝B ?A ∩B ＝A ?A －B ＝Φ。
证
(1) 证A ∪B ＝B ?A ?B ，对于任意的x ，
x ∈A ?x ∈A ∨x ∈B ?x ∈A ∪B ?x ∈B(因为A ∪B ＝B)，所以A ?B 。
(2) 证A ?B ?A ∩B ＝A 。显然有A ∩B ?A ，下面证A ?A ∩B ，对于任意的x ， x ∈A ?x ∈A ∧x ∈A ?x ∈A ∧x ∈B(因为A ?B) ?x ∈A ∩B ，由集合相等的定义有A ∩B ＝A 。
(3) 证A ∩B ＝A ?A －B ＝Φ。
A －
B ＝A ∩～B ＝(A ∩B)∩～B(因为A ∩B ＝A)＝A ∩(B ∩～B)＝A ∩Φ＝Φ。
(4) 证A －B ＝Φ?A ∪B ＝B 。A ∪B ＝B ∪(A －B)＝B ∪Φ＝B 。
注意：上式给出了A ?B 的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。
例：化简((A ∪B ∪C)∩(A ∪B))－((A ∪(B －C))∩A)。
解 因为A ∪B ?A ∪B ∪C ，A ?A ∪(B －C)，故有
((A ∪B ∪C)∩(A ∪B))－((A ∪(B －C))∩A)＝(A ∪B)－A ＝B －A 。
定义：两集合,A B 的环和（对称差）定义为：
环和： ()(){|}A B A B B A x x A x B x A x B ⊕=--=∈∧?∨?∧∈
2. 环和与环积的性质： (1) ()()()()A B A B A B A B A B ⊕==- ， (2) A B A B ⊕=⊕， B A A B ⊕=⊕，
(3) ()()A B C A B C ⊕⊕=⊕⊕， ()()()C A B C A C B ⊕=⊕ ；
(4) A A ⊕=Φ， A A ⊕Φ=，
(5) A B A C B C ⊕=⊕?=
例：已知A ⊕B ＝A ⊕C ，证明B ＝C 。
证 已知A ⊕B ＝A ⊕C ，所以有
A ⊕(A ⊕B)＝A ⊕(A ⊕C) ?(A ⊕A)⊕
B ＝(A ⊕A)⊕C
?Φ⊕B ＝Φ⊕C ?B ⊕Φ＝C ⊕Φ?B ＝C 。
3. 集合运算的文氏图表示
注意：如果没有特殊说明，任何两个集合都画成相交的。
幂集合
定义：设A 是一个集合，A 的幂集是A 的所有子集的集合，即(){|}A B B A ρ=?。 若A 是n 元集，则()A ρ有2n
个元素。
例：若A =Φ，则(){}A ρ=Φ；若{1,2}A =，则(){,{1},{2},{1,2}}A ρ=Φ。 对任意集合A ：()A ρΦ∈，()A A ρ∈。
集合运算的顺序：为了使得集合表达式更为简洁，我们对集合运算的优先顺序做如下规定：称广义交，广义并，幂集，绝对补运算为一类运算，交，并，补，环和，环积运算为二类运算。一类运算优先于二类运算；一类运算之间由右向左顺序进行；二类运算之间由括号决定先后顺序。
1.2 关系及其表示
1.2.1集合的笛卡儿积与二元关系
定义 1 由两个元素x 和y （允许x=y ）组成的序列记作
有序对
1．当x ≠y 时，
例1 已知
解 由有序对相等的充要条件有x+2=5，2x+y=4，解得x=3，y=-2。
定义2 设12,,,n a a a 是(2)n n >个元素，定义
121121,,,,,,,,n n n n a a a a a a a a --<<>>=<>
为n 重组。
注意：n 重组是一个二重组，其中第一个分量是1n -重组。如2,3,5<>代表2,3,5<<>>而不代表2,3,5<<>>，按定义后者不是三重组，并且2,3,52,3,5<<>>≠<<>>。
n 重组121,,,,n n a a a
a -<> 与121,,,,n n
b b b b -<> 相等当且仅当i i a b =，1i n ≤≤。
定义3 设A ，B 为集合，用A 中元素为第一元素，B 中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A 和B 的笛卡儿积（叉积），记作A ×B 。
笛卡儿积的符号化表示为A ×B={
集合12,,,n A A A （2n >）的叉积记为12n A A A ??? 或1n
i i A =?，定义为 1211()n
i n n i A A A A A -=?=???? 例2 设A={a,b}, B={0,1,2}，则
A×B={
B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}。
由排列组合的知识不难证明，如果|A|=m，|B|=n，则|A×B|=mn。
笛卡儿积的运算性质
(1).对任意集合A，根据定义有 A×Φ=Φ, Φ×A=Φ；
(2).一般地说，笛卡儿积运算不满足交换律，即A×B≠B×A(当A≠Φ∧B≠Φ∧A ≠B时)；
(3)．笛卡儿积运算不满足结合律，即(A×B)×C≠A×(B×C)(当A≠Φ∧B≠Φ∧C≠Φ时)；
(4).笛卡儿积运算对并和交运算满足分配律，即
A×(B∪C)=(A×B)∪(A×C)； (B∪C)×A=(B×A)∪(C×A)；
A×(B∩C)=(A×B)∩(A×C)； (B∩C)×A=(B×A)∩(C×A)。
我们证明其中第一个等式。
证任取
?(x∈A∧y∈B)∨(x∈A∧y∈C)?
所以有 A×(B∪C) = (A×B)∪(A×C)。
(5)．A?C∧B?D?A×B?C×D
性质5的证明和性质4类似，也采用命题演算的方法。
注意：性质5的逆命题不成立，可分以下情况讨论。
(a) 当A=B=Φ时，显然有A?C和B?D成立。
(b) 当A≠Φ且B≠Φ时，也有A?C和B?D成立。证明如下：任取x∈A，由于B≠Φ,必存在y∈B，因此有x∈A∧y∈B?
从而证明了A?C。同理可证B?D。
(c) 当A=Φ而B≠Φ时，有A?C成立，但不一定有B?D成立。
反例：令A=Φ，B={1}，C={3}，D={4}。
(d) 当A≠Φ而B=Φ时，有B?D成立，但不一定有A?C成立。反例类似于(c)。
例3 设A={1,2},求P(A)×A。
解 P(A)×A={Φ,{1},{2},{1,2}}×{1,2}
={<Φ,1>,<Φ,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2},2>}
例4 设A ，B ，C ，D 为任意集合，判断以下命题是否为真，并说明理由。
(1) A ×B=A ×C ?B=C ； (2) A-(B ×C)=(A-B)×(A-C)；
(3) A=B ∧C=D ?A ×C=B ×D ； (4) 存在集合A ，使得A ?A ×A 。 解 (1) 不一定为真。当A=Φ，B={1},C={2}时，有A ×B=Φ=A ×C ，但B ≠C 。 (2) 不一定为真。当A=B={1},C={2}时有A-(B ×C)={1}–{<1,2>}={1}， (A-B)×(A-C)= Φ×{1}=Φ
(3) 为真。由等量代入的原理可证。
(4) 为真。当A=Φ时有A ?A ×A 成立。
定理1：若(1,2i A i n
= 都是有限集合，则1212||||||||
n n A A A A A A ???= 。 定义4 如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对；
（2）集合是空集；则称该集合为一个二元关系，记作R 。二元关系也可简称为关系。
对于二元关系R ，若,x y R <>∈，则称,x y 有关系R ，可记作xRy ；若
,x y R <>?，则记作xRy /。一般地,,x y y x <>≠<>，因此xRy yRx ≠。
例1 1{1,2,,}R a b =<><>，2{1,2,,}R a b =<>，则1R 是二元关系，2R 不是二元关系，只是一个集合，除非将a 和b 定义为有序对。根据以上记法可以写成112R ，1aR b 等。
定义5 设,A B 为集合，A B ?的任何子集所定义的二元关系叫做从A 到B 的二元关系，特别地，当A B =时，则叫做A 上的二元关系。12n A A A ??? 的子集称为
12n A A A ??? 上的一个n 元关系，当12n A A A === 时称为
A 上的一个n 元关系。 例2 {0,1}A =,{1,2,3}
B =，那么1{0,2}R =<>，2R A B =?，3R =Φ，4{0,1}R =<>等都是从A 到B 的二元关系，而其中3R 和4R 同时也是A 上的二元关
系。
注：可把A 到B 的二元关系看成是A B 上的二元关系或2()A B 上的二元关系。 二元关系的数目：集合A 上的二元关系的数目依赖于A 中的元素数。如果||A n =，那么2||A A n ?=，A A ?的子集就有2
2n 个。每一个子集代表一个A 上的二元关系，所
以A 上有22n 个不同的二元关系。例如||3A =，则A 上有232512=个不同的二元关系。如果||i i A m =，则1212||n n A A A m m m ???=??? ，因此12n A A A ??? 上有122n m m m ??? 个不同的n 元关系。
一些重要关系：
(1) 空关系：若R =Φ，则R 称为空关系；
(2) 全域关系：{,|}A E x y x A y B A B =<>∈∧∈=?
(3) 恒等关系：A 上的二元关系{,|}A I x x x A =<>∈称为恒等关系。
(4) 小于或等于关系：{,|,}A L x y x y A x y =<>∈∧≤，这里A R ?；
(5) B 上的整除关系：{,|,}B D x y x y B x y =<>∈∧整除，这里A Z *
?（非零整数集）；
(6) A 上的包含关系：{,|,}R x y x y A x y ?=<>∈∧?，这里A 是集合族。 例3 设{1,2,3}A =，{,}B a b =，(){,{},{},{,}}C B a b a b ρ==Φ，则 {1,1,1,2,1,3,2,2,2,3,3,3}A L =<><><><><><>，
{1,1,1,2,1,3,2,2,2,3}A D =<><><><><>
C 上的包含关系：
{,,,{},,{},,{,},{},{},R a b a b a a ?=<ΦΦ><Φ><Φ><Φ><>
{},{,},{},{},{},{,},{,},{,}}a a b b b b a b a b a b <><><><>。
类似的还可以定义大于等于关系，小于关系，大于关系，真包含关系等等。 关系是有序对的集合，因此对它可进行集合运算，运算结果定义一个新的关系。例如：设R 和S 是给定集合上的关系，则R S ，R S ，R S -，R 分别称为关系R 与S 的并关系，交关系，差关系和R 的补关系。这样一来，可以从已知关系派生出各种新关系。
二元关系
A 到
B 的二元关系可以用一个图来形象地表示。
定义6 设R 是A 到B 的一个二元关系，则A 叫着关系R 的前域，B 叫着关系R 的陪域；(){|(,)}D R x y x y R =?<>∈称为关系R 的定义域；
(){|(,)}R R y x x y R =?<>∈称为关系R 的值域。
关于关系的定义域、值域的一些性质：
()()()D R S D R D S = ；()()()D R S D R D S ? ；
()()()R R S R R R S = ；()()()D R S R R R S ? 。
证明 （证明第一个式子，其余类似）
()(())()()()()()()()
x D R S y x R S y y xRy xSy y xRy y xSy x D R x D S x D R D S ?∈????∨??∨??∈∨∈?∈ 1.2.2关系矩阵与关系图
(1) 集合表示法：非空关系都是元素为有序对的集合。
(2) 关系图：设12{,,,}n A x x x = ，R 是A 上的关系，令图,G V E =<>，其中顶点集合V A =，边集为E ，对于,i j x x V ?∈，满足,i j i j x x E x Rx <>∈?，则称图G 为R 的关系图，记作R G 。
(3)关系矩阵：设12{,,,}n A x x x = ，R 是A 上的关系，令10i j ij i j x Rx r x Rx ?=?/?
，(,1,2,,)i j n =
则111212122212()n n ij n n nn r r r r r r r r r r ?? ? ?= ? ???
称为关系R 的关系矩阵，记作R M 。 例 空关系的关系矩阵为全0矩阵：0A M =； 全域关系的关系矩阵为全1矩阵，记为J ；相等关系的关系矩阵为单位矩阵：A I M I =。
基于关系R 与关系矩阵R M 互相唯一决定的特性，可用关系矩阵有效地刻画关系的许多性质。如对于有限集A 上的任意关系R 与S ：R S R S M M =?=；R S R S M M ??≤。
1.3关系的运算
1.3.1关系的逆
定义1 设R 是从A 到B 的二元关系，关系R 的逆（R 的逆关系）记为R
，定义如下：
{,|,}R x y x y R =<><>∈
当A 上的关系R 具有对称性时，R
R = 。 相等关系的逆是相等关系；空关系的逆是空关系；全域关系的逆是全域关系。
列举法：把R 中每个有序对的第一和第二成分都加以交换，就可得到逆关系R
的所有元素。
对x A ∈和y B ∈来说，这意味着xRy yRx
? 。 关系矩阵：将R M 的行和列交换即可得到R M ，即T
R R M M = （T R M 表示R M 的转置）。
关系图：颠倒R 的关系图中的每条弧（有向边）的箭头，就得到R
的关系图。 逆关系的性质：
(1) 设12,,R R R 都是从A 到B 的二元关系，则
(a) ()R R = ；(b) 1212R R R R = ；(c) 1212
R R R R = ；(d) 1212
R R R R -=- ； (e) R R = ，（R A B R =?-）； (f) 1212
R R R R ??? ； (2) 设1R 是从A 到B 的关系，2R 是从B 到C 的关系，则1221
()R R R R ?=? 。
1.3.2关系的合成
定义2 设1R 是从A 到B 的关系，2R 是从B 到C 的关系，则1R 与2R 的合成（右复合）为从A 到C 的关系，记为12R R 或12R R （其中 表示合成运算），定义为
1212{,|(,,)}R R a c a A c C b b B a b R b c R =<>∈∧∈∧?∈∧<>∈∧<>∈。 例1 设{1,2,3,4}A =，{2,3,4}B =，{1,2,3}C =，1R 是从A 到B 的关系，2R 是从B 到C 的关系：
1{,|6}{2,4,3,3,4,2}R x y x y =<>+==<><><>，
2{,|1}{2,1,3,2,4,3}R y z y z =<>-==<><><>。
分别用列举法、图示法、关系矩阵表示关系的合成12R R ，21R R 。
例2 设{1,2,3,4,5}A =，1R 和2R 都是A 上的二元关系，如果
1{1,2,3,4,2,2}R =<><><>，
2{4,2,2,5,3,1,1,3}R =<><><><>，
分别用列举法、图示法、关系矩阵表示关系的合成12R R ?，21R R ?，121()R R R ??，121()R R R ??，11R R ?，22R R ?等。
合成关系的性质：
(1) 设R 是从A 到B 的关系，,A B I I 分别是,A B 上的相等关系，则
A B I R R I R ?=?=；
(2) 如果关系1R 的值域与2R 的定义域的交集为空集，则合成关系12R R ?是空关系；
(3) 关系的合成关于交和并的分配律：
设1R 是从A 到B 的关系，23,R R 是从B 到C 的关系，4R 是从C 到D 的关系，则 (a) 1231213()()()R R R R R R R = ，(b) 1231213()()()R R R R R R R ? ；
(c) 2342434()()()R R R R R R R = ，(d) 2342434()()()R R R R R R R ? ；
(4) 关系的合成满足结合律：
设123,,R R R 分别是从A 到B ，B 到C ，C 到D 的关系，则123123()
()RR R R RR =。 1.3.3 关系的幂
定义3设R 是集合A 上的二元关系，n N ∈为任一自然数，则R 的n 次幂记为n R ，
定义为：(1) 0R 为A 上的相等关系，0{,|}R x x x A =<>∈ (2) 1n n R
R R +=?。
关系的幂运算的性质：
(1) 对A 上的任意关系12,R R 有：0012A R R I ==，1011111A R R R I R R =?=?=； (2) 设R 是集合A 上的二元关系，,m n N ∈，则m n m n R R R +?=，()m n mn R R =；
(3) 设||A n =，R 是集合A 上的一个二元关系，则存在i 和j ，202n i j ≤<≤使
i j R R =；
(4) 循环性质：设R 是集合A 上的二元关系，若存在i 和j ，i j <，使i j
R R =，则
(a) 对所有0k ≥，i k j k R R ++=； (b) 对所有,0k m ≥，i mdk i k R R ++=（其中d j i =-）；(c) 令0121{,,,,}j S R R R R -= ，则R 的每一次幂是S 的元素，即对
n N ∈，n R S ∈。
关系的幂的计算：
给定A 上的关系R 和自然数n ，怎样计算n
R 呢？若n 是0或1，结果是很简单的。 下面考虑2n ≥的情况。
如果R 是用集合表达式给出的，可以通过1n -次合成计算得到n R 。
如果R 是用关系矩阵M 给出的，则n R 的关系矩阵是n M ，即n 个矩阵M 之积。
与普通矩阵乘法不同的是，其中的相加是逻辑加，即111,10011,000+=+=+=+=。
如果R 是用关系图G 给出的，可以直接由图G 得到n R 的关系图G '。G '的顶点集与G 相同。考察G 的每个顶点i x ，如果在G 中从i x 出发经过n 步长的路径到达顶点j x ，则在G '中加一条从i x 到j x 的边。当把所有这样的边都找到以后，就得到图G '。
例3 设{,,,}A a b c d =，{,,,,,,,}R a b b a b c c d =<><><><>，求R 的各次幂，分别用矩阵和关系图表示。
解 R 的关系矩阵为0100101000010
000M ?? ? ?= ? ???，则234,,R R R 的关系矩阵分别是 21010010100000
000M MM ?? ? ?== ? ???，320101101000000000M M M ?? ? ?== ? ???，431010010100000
000M M M ?? ? ?== ? ??? 因此42M M =，53R R =， 。所以可以得到246R R R === ，
357R R R === ，而0R ，即A I 的关系矩阵为01000010000100
001M ?? ? ?= ? ???
。至此，R 各次幂的关系矩阵都得到了。 用关系图的方法得到0123
,,,,R R R R 的关系图如下图所示。
合成关系的矩阵表达
二元集{,}{1,0}T F ≈上的布尔运算：
① T F F T T T T ∨?∨?∨?，F F F ∨?； 1001111∨=∨=∨=，000∨=；
② T F F T F F F ∧?∧?∧?，T T T ∧?； 1001000∧=∧=∧=，111∧=；
③ T F =?，F T =?； 10=?，01=?；
④ 配合,∨∧的其他性质(结合律、分配律等)可计算更复杂的式子。
注 {0,1}关于上述两个运算构成二元数域。
(0,1)-矩阵的布尔运算：
对于m n ?的(0,1)矩阵()R ij mn M r =，()S ij mn M s =，定义下列运算：
()R ij mn M r =??，()R S ij ij mn M M r s ∨=∨，()R S ij ij mn M M r s ∧=∧；
对m n ?和n p ?的(0,1)矩阵()R ij mn M r =和()S ij np M r =：
1(())n
R S ik kj mp k M M r s =?=∨∧。 例4 对全0矩阵0，全1矩阵J 有
零律：000M M ∧=∧=，J M M J J ∨=∨=；
同一律：0M M ∨=，J M M ∧=。
用关系矩阵的布尔运算研究关系的运算：
《离散数学》-教案.doc
《离散数学》教案 第一章集合与关系 集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普 遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的 一个分支。 G. Cantor( 康脱 ) 是作为数学分支的集合论的奠基人。1870 年前后，他关于无穷序列的研究导致集合论的系统发展。 1874 年他发表了关于实数集合不能与自然数集合建立 一一对应的有名的证明。 1878 年，他引进了两个集合具有相等的“势”的概念。然 而，朴素集合论中包含着悖论。第一个悖论是布拉利 - 福尔蒂的最大序数悖论。 1901 年罗素发现了有名的罗素悖论。 1932 年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908 年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称 为策梅罗 - 弗兰克尔集合论（ ZF），其中包括 1904 年策梅罗引入的选择公理。另外一种系 统是冯·诺伊曼 - 伯奈斯 - 哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗 - 弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗 - 弗兰克尔集合论的独立性。现在把策梅罗 - 弗兰克尔集合论与选择公理一起称为 ZFC系统。 一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。 通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运 算方法，为学习后续章节打下良好基础。 二、知识点 1．集合的基本概念与表示方法； 2．集合的运算； 3．序偶与笛卡尔积； 4．关系及其表示、关系矩阵、关系图； 5．关系的性质，符合关系、逆关系； 6．关系的闭包运算； 7．集合的划分与覆盖、等价关系与等价类；相容关系； 8．序关系、偏序集、哈斯图。
离散数学作业
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学作业答案
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
离散数学(大作业)与答案
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)
离散数学教案
学习目标: 1.深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、(最大)相容类、偏序关系、极大元、极小元、上(下)界、上(下)确界、最大(小)元、全序关系、良序关系等概念; 2.掌握集合的交、并、差、补、对称差的运算及其运算规律; 3.掌握关系的交、并、逆、复合运算、闭包运算及其性质; 4.掌握关系的矩阵表示与关系图; 5.深刻理解关系的自反性、反自反性、对称性、反对称性与传递性,掌握其判别方法; 6.掌握集合的覆盖与划分的联系与区别; 7.掌握偏序关系的判别及其哈斯图的画法;会求偏序集中给定集合的极大元、极小元、上(下)界、上(下)确界、最大(小)元。 主要内容: 1.集合的基本概念及其运算 2.序偶与笛卡尔积 3.关系及其表示 4.关系的性质及其判定方法 5.复合关系与逆关系 6.关系的闭包运算 7.等价关系与相容关系 8.偏序关系 重点: 1.关系的性质及其判别; 2.关系的复合运算及其性质; 3.等价关系与等价类、等价关系与集合的划分的联系; 4.偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点: 1.关系的传递性及其判别; 2.等价关系的特性; 3.偏序关系的哈斯图的画法;偏序集中特异位置元素的求法。 教学手段: 通过多个实例的精讲帮助同学理解重点与难点的内容,并通过大量的练习使同学们巩固与掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题: 习题3、1:4,6;习题3、2:3(8),4(12),6(m);习题3、4:1 (2)、(4),3;习题3、5:1,4;习题3、6:2,5,6;习题3、7:2,5,6;习题3、8:1(1)-(6);习题3、9:3(2)、(4),4(3);习题3、10:1 ,4,5。
离散数学作业(2)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
离散数学教案
学习目标： 1．深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、（最大）相容类、偏序关系、极大元、极小元、上（下）界、上（下）确界、最大（小）元、全序关系、良序关系等概念； 2．掌握集合的交、并、差、补、对称差的运算及其运算规律； 3．掌握关系的交、并、逆、复合运算、闭包运算及其性质； 4．掌握关系的矩阵表示和关系图； 5．深刻理解关系的自反性、反自反性、对称性、反对称性和传递性，掌握其判别方法； 6．掌握集合的覆盖与划分的联系与区别； 7．掌握偏序关系的判别及其哈斯图的画法；会求偏序集中给定集合的极大元、极小元、上（下）界、上（下）确界、最大（小）元。 主要内容： 1．集合的基本概念及其运算 2．序偶与笛卡尔积 3．关系及其表示 4．关系的性质及其判定方法 5．复合关系和逆关系 6．关系的闭包运算 7．等价关系与相容关系 8．偏序关系 重点： 1．关系的性质及其判别； 2．关系的复合运算及其性质； 3．等价关系与等价类、等价关系与集合的划分的联系； 4．偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点： 1．关系的传递性及其判别； 2．等价关系的特性； 3．偏序关系的哈斯图的画法；偏序集中特异位置元素的求法。 教学手段： 通过多个实例的精讲帮助同学理解重点和难点的内容，并通过大量的练习使同学们巩固和掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题：
习题 3.1：4，6；习题 3.2：3（8），4（12），6（m ）；习题 3.4：1 （2）、 (4)，3；习题 3.5：1，4；习题 3.6：2，5，6；习题 3.7：2，5，6；习题 3.8：1（1）-（6）；习题3.9：3（2）、（4），4（3）；习题3.10：1 ，4，5。 3.1 集合的基本概念 集合(set)（或称为集）是数学中的一个最基本的概念。所谓集合，就是指具有共同性质的或适合一定条件的事物的全体，组成集合的这些“事物”称为集合的元素。 集合常用大写字母表示，集合的元素常用小写字母表示。若A 是集合，a 是A 的元素，则称a 属于A ，记作a A ∈；若a 不是A 的元素，则称a 不属于A ，记作。若组成集合的元素个数是有限的，则称该集合为有限集(Finite Set)，否则称为无限集(Infinite Set)。 常见集合专用字符的约定： N —自然数集合(非负整数 集) I (或Z )—整数集合(I +，I -) Q —有理数集合(Q +，Q -) R —实数集合(R +，R -) F —分数集合(F +，F -) 脚标+和-是对正、负的区分 C —复数集合 P —素数集合 O —奇数集合 E —偶数集合 幂集 定义 3.1.1 对于每一个集合A ，由A 的所有子集组成的集合，称为集合A 的幂集(Power Set)，记为 ()P A 或2A ．即(){}P A B B A =?。 例如：{,,}A a b c =, (){,{},{},{},{,},{,},{,},{,,}}P A a b c a b b c a c a b c φ=。 定理3.1.1 如果有限集A 有n 个元素，则其幂集()P A 有2n 个元素。 证明 A 的所有由k 个元素组成的子集数为从n 个元素中取k 个的组合数。 (1)(2)(1)! k n n n n n k C k ---+= L 另外，因A φ?，故()P A 的元素个数N 可表示为 1 201n k n k n n n n n k N C C C C C ==++++++=∑L L 又因 0()n n k k n k n k x y C x y -=+= ∑ 令 1x y == 得 02n n k n k C ==∑ 故()P A 的元素个数是2n 。 人们常常给有限集A 的子集编码，用以表示A 的幂集的各个元素。具体方法是： 设12{,,,}n A a a a =L ，则A 子集B 按照含i a 记1、不含i a 记0(1,2,,)i n =L 的规定
离散数学作业
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
天大20秋《离散数学(2)-2》在线作业二
《离散数学(2)-2》在线作业二 1：设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（） A、2 B、3 C、4 D、5 答案：C 2：题面见图片： A、A B、B C、C D、D 答案：D 3：在n个结点的连通图中，其边数 ( )。 A、最多有n-1条 B、至少有n-1条 C、最多有n条 D、至少有n条 答案：B
4：题面见图片： A、A B、B C、C D、D 答案：D 5：设G是n个顶点的无向简单图，则下列说法不正确的是 ( ) A、若G是树，则其边数等于n-1 B、若G是欧拉图，则G中必有割边 C、若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D、若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路答案：D 6：题面见图片： A、A B、B C、C D、D 答案：D
7：设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（） A、3 B、4 C、5 D、6 答案：B 8：设集合A={a，b，c}，A上的关系R={（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c）}，则R具有关系的（）性质。 A、自反 B、对称 C、传递 D、反对称 答案：B 9：具有6个结点的非同构的无向树的数目为（） A、4 B、5 C、7 D、8 答案：C 10：任何无向图中结点间的连通关系是 ( )。 A、偏序关系 B、等价关系 C、相容关系
D、拟序关系 答案：B 11：设|V|>1,D=
离散数学作业
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
离散数学作业答案完整版
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
北京大学2017秋课件作业【离散数学】及答案
2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}?A。 1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．?。 1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题） （1）N?Q，Q∈S，则N?S，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］ 1-4设集合B={4，3}∩?，C={4，3}∩{?}，D={3，4，?}，E={x│x∈R并且x2-7x+12=0}，F={4，?，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答：按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章二元关系 2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA， 试求：（综合题） (1)domR=?;(2)ranR=?;(3)R的性质。 （4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。R）=？ 答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。 （4）商集A/R={{1，2，3}，{2，3}，{3}}。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系R必须是等价关系。至于作业中，此两题应说：因为R不是等价关系，此题无解。 2-2设R是正整数集合上的关系，由方程x+3y=12决定，即 R={〈x，y〉│x，y∈Z+且x+3y=12}， 试给出dom（R。R）。（选择题）[B] A.3； B.{3}； C.〈3，3〉； D.{〈3，3〉}。
离散数学作业答案
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
2019年秋季离散数学综合考试
离散数学形成性考核作业4 姓名：严先贵 学号1944201250206 得分： 教师签名： 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设：P:小王去上课。 Q：小李去旅游。 则P Q 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设：P:他去旅游 Q：他有时间 则P Q 3．请将语句“有人不去工作”翻译成谓词公式． 设A（x）：x是人 B（x）：去工作 x(A(x)﹁B(x)) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）：x是人 B（x）：努力学习 x(A(x)B(x))
二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A B)；（2）(A∩B)；（3）A×B． 解 （1）（A B）= {{1},{2}} （2）（A∩B）= {1,2} （3） A×B = {< 1 }，1＞，{{ 1 }，2＞ 2．设A={1，2，3，4，5}，R={
离散数学教案范本
《离散数学》教案 课目：第一章命题逻辑 教师：熊建英 学时： 12课时
Ⅰ教学提要 一、教学对象（人数） 学生：信息安全专业本科二年级学生50人 二、教学目标（任务） 各小结中知识点掌握程度(* 理解；** 基本掌握；***熟练掌握) 三、教学要求 （一）学生：着重知识点的学习，积极思考，参与提问。 （二）教官：严格纪律，严密组织、保持良好教学秩序，确保教学效果。 四、教官分工 主讲教师1名：负责教案编写，课堂的组织教学，教学总结编写。
五、本章重点 1、利用联接词构造复合命题公式 2、真值表的构建 3、等值演算 4、复合命题公式转化为主析取范式、主合取范式的方法 5、推理证明 六、本章难点 1、利用命题公式演算、真值表进行等值判断和公式类型判断 2、利用命题公式演算、真值表转化主析取范式、主合取范式 3、将现实背景下的条件约束构造为命题公式 七、教学方法 采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 八、课时分配 1.1 命题及联接词2课时； 1.2 命题公式及其赋值2课时； 1.3 等值式2课时； 1.4 析取范式与合取范式2课时； 1.5 推理理论与消解法2课时； 1.6 命题逻辑应用案例2课时； 九、场地器材 多媒体教室 十、参考书目 1、杨圣洪、张英杰、陈义明：《离散数学》，科学出版社，2011年。 2、屈婉玲、耿素云、张立昂：《离散数学》，高等教育出版社，2008年。 3、屈婉玲、耿素云、张立昂：《离散数学学习指导与习题解析》，高等教育出版社，2008年。
Ⅱ教学进程 1.1 命题及联接词（2课时） 一、教学内容 1、命题的概念表示与分类 2、五种基本的联接词的逻辑关系 3、复合命题的符号化 4、复合命题的真值判断 二、课程时间安排 1、首先介绍本课程的性质，任务和教学安排，对学生明确提出教学上的要求（10分钟） 2、介绍离散数学学科的发展历史（20分钟） 3、命题与真值、命题的分类、简单命题符号化（15分钟） 4、联结词与复合命题（35分钟） 5、本次课小结（10分钟） 三、教学实施 （一）创设意境、导入课程（10分钟） 目的 体会离散数学理论在现实生活中的应用、是计算机专业多门核心课程的基础，让学生明白“离散数学”课程作用和意义。 1、从生活应用中理解逻辑推理作用，及离散数学学习意义； 如：犯罪推理、电路设计、人事安排的最优方案、网络中最优路径等； (1)逻辑推理问题范例（PPT展示一个犯罪推理案例） (2)离散数学是一门可以对逻辑推理规律建立相应的符号运算系统，解决此类问题的科学。 2、离散数学与其他专业课程的联系； (1) 涉及多门计算机专业中很多专业课程，如：编程语言、数据结构、操作系统、数据数据加密。
华南理工离散数学作业题2017版
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
离散数学 作业及答案
2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）：
2018秋季学期离散数学语音答疑提纲下(全书考试内容)
2018秋季学期《离散数学》语音答疑提纲(下) 本次语音答疑分两步完成。第一，回答全书各部分问题。第二，指出全书考试 范围，并给出例题，加以分析。 一．2018秋季学期期末考题在参考书中内容的分配: 集合论部分（共40分） 集合的基本概念及运算(第三章，2 选择题;共 4 分). 关系及函数(第四章，4选择题-2关系，2函数;1综合.共20分). 群论(第九章，2题单选;1综合.共16分). 图论部分（共30分） 图,图-树关系(第五，七章，8选择题-图2，图-树关系6;1综合.共30分). 逻辑学部分（共30分） 逻辑学(第一，二章，8选择题（7题命题逻辑）;1综合.共 30分).
二.参考书第五版各章节考试范围内的知识点及例题 第三章集合的基本概念和运算 1.集合的基本概念要求掌握： 集合与元素的关系—属于或不属于；（***） 集合与集合间的关系—子集与集合叫包含，相互包含叫相等； 子集为集合的元素时也叫属于关系。 例题1: 设集合 A ={1，{2}，a，4，3}，则有 2 ∈A [ 非 ]; 单项选择题： 例题2: A,B，C 为任意集合，则他们的共同子集是 [ D ] A．A；B．B；C．C；D．?。 例题3：设集合 A ={1，{2}，a，4，3}，下面命题为真是 [ B ] A．2 ∈A； B．1 ∈ A； C．5 ∈A； D．{2} A。 例题4: 设集合 A ={1，{2}，a，4，3}，则有 2 （）A。 ***** 请比较例题1，3，4，那个最容易；那个最难？！***** 2.集合的基本运算重点掌握： 五大基本运算定义的表达式。例如,并运算的”或”,交运算的”且”字的意义. 例题：N, Z+分别是自然数集合,正整数集合,则[ C ] A．N=Z+ +{0} B．N=Z+ + 0 C．N=Z+∪{0} D．N=Z+.∪0 .
离散数学作业标准答案
离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A )