离散数学第2章 集合-简化

离散数学第二章一阶逻辑知识点总结数理逻辑部分第2章一阶逻辑2.1 一阶逻辑基本概念个体词（个体）: 所研究对象中能够独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示个体变项：抽象的事物，用x, y, z表示个体域: 个体变项的取值范围有限个体域，如{a, b, c}, {1, 2}无限个体域，如N, Z, R, …全总个体域: 宇宙间一切事物组成谓词: 表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词: 表示事物的性质多元谓词(n元谓词, n2): 表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：x y，…0元谓词: 别含个体变项的谓词, 即命题常项或命题变项量词: 表示数量的词全称量词: 表示任意的, 所有的, 一切的等如x 表示对个体域中所有的x存在量词: 表示存在, 有的, 至少有一具等如x表示在个体域中存在x一阶逻辑中命题符号化例1 用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲在命题逻辑中, 设p:墨西哥位于南美洲符号化为p, 这是真命题在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲符号化为F(a)例2 在一阶逻辑中将下面命题符号化(1) 人都爱美; (2) 有人用左手写字分不取(a) D为人类集合, (b) D为全总个体域.解：(a) (1) 设G(x)：x爱美, 符号化为x G(x)(2) 设G(x)：x用左手写字, 符号化为x G(x)(b) 设F(x)：x为人，G(x)：同(a)中(1) x (F(x)G(x))(2) x (F(x)G(x))这是两个基本公式, 注意这两个基本公式的使用.例3 在一阶逻辑中将下面命题符号化(1) 正数都大于负数(2) 有的无理数大于有的有理数解注意: 题目中没给个体域, 一律用全总个体域(1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值(2) 令F(x): x是无理数, G(y): y是有理数,L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或x y(F(x)G(y)L(x,y)) 两者等值几点注意：1元谓词与多元谓词的区分无特殊要求，用全总个体域量词顺序普通别能随便颠倒否定式的使用考虑：①没有别呼吸的人②别是所有的人都喜爱吃糖③别是所有的火车都比所有的汽车快以上命题应怎么符号化？2.2 一阶逻辑合式公式及解释字母表定义字母表包含下述符号：(1) 个体常项：a, b, c, …, a i, b i, c i, …, i1(2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1(3) 函数符号：f, g, h, …, f i, g i, h i, …, i1(4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1(5) 量词符号：,(6) 联结词符号：, , , ,(7) 括号与逗号：(, ), ，定义项的定义如下：(1) 个体常项和个体变项是项.(2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n是任意的n个项，则(t1, t2, …, t n) 是项.(3) 所有的项基本上有限次使用(1), (2) 得到的.个体常项、变项是项，由它们构成的n元函数和复合函数依然项定义设R(x1, x2, …, x n)是任意的n元谓词，t1,t2,…, t n 是任意的n个项，则称R(t1, t2, …, t n)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y), F(f(x1,x2),g(x3,x4))等均为原子公式定义合式公式（简称公式）定义如下：(1) 原子公式是合式公式.(2) 若A是合式公式，则(A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B),(A B)也是合式公式(4) 若A是合式公式，则xA, xA也是合式公式(5) 惟独有限次地应用(1)~(4)形成的符号串是合式公式.请举出几个合式公式的例子.定义在公式xA和xA中，称x为指导变元，A为相应量词的辖域. 在x和x的辖域中，x的所有浮现都称为约束浮现，A中别是约束浮现的其他变项均称为是自由浮现的.例如, 在公式x(F(x,y)G(x,z)) 中,A=(F(x,y)G(x,z))为x的辖域，x为指导变元, A中x的两次浮现均为约束浮现，y与z均为自由浮现.闭式: 别含自由浮现的个体变项的公式.给定公式A=x(F(x)G(x))成真解释: 个体域N, F(x): x>2, G(x): x>1代入得A=x(x>2x>1) 真命题成假解释: 个体域N, F(x): x>1, G(x): x>2 代入得A=x(x>1x>2) 假命题咨询: xF(x)x F(x) 有成真解释吗？xF(x)x F(x) 有成假解释吗？被解释的公式别一定全部包含解释中的4部分.闭式在任何解释下基本上命题，注意别是闭式的公式在某些解释下也也许是命题.永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满脚式：至少有一具成真赋值几点讲明：永真式为可满脚式，但反之别真谓词公式的可满脚性（永真性,永假性)是别可判定的利用代换实例可判某些公式的类型定义设A0是含命题变项p1, p2, …,p n的命题公式，A1,A2,…,A n是n个谓词公式，用A i处处代替A0中的p i (1i n)，所得公式A称为A0的代换实例.例如:F(x)G(x), xF(x)yG(y) 等基本上p q的换实例，x(F(x)G(x)) 等别是p q 的代换实例.定理重言式的代换实例基本上永真式，矛盾式的代换实例基本上矛盾式.2.3 一阶逻辑等值式等值式定义若A B为逻辑有效式，则称A与B是等值的，记作A B，并称A B 为等值式.基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y) xF(x)yG(y)(xF(x)yG(y)) xF(x)yG(y) 等消去量词等值式设D={a1,a2,…,a n} xA(x)A(a1)A(a2)…A(a n)xA(x)A(a1)A(a2)…A(a n)量词否定等值式设A(x)是含x自由浮现的公式xA(x)x A(x)xA(x)x A(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律例将下面命题用两种形式符号化(1) 没有别犯错误的人(2) 别是所有的人都爱看电影解(1) 令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x))x(F(x)G(x))请给出演算过程，并讲明理由.(2) 令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x))x(F(x)G(x))给出演算过程，并讲明理由.前束范式定义设A为一具一阶逻辑公式, 若A具有如下形式Q1x1Q2x2…Q k x k B, 则称A为前束范式, 其中Q i(1i k)为或，B为别含量词的公式.例如，x y(F(x)(G(y)H(x,y)))x(F(x)G(x))是前束范式, 而x(F(x)y(G(y)H(x,y)))x(F(x)G(x))别是前束范式.定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式注意:公式的前束范式别惟一求公式的前束范式的办法: 利用重要等值式、置换规则、换名规则、代替规则举行等值演算.换名规则: 将量词辖域中浮现的某个约束浮现的个体变项及对应的指导变项，改成其他辖域中未曾浮现过的个体变项符号，公式中其余部分别变，则所得公式与原来的公式等值.代替规则: 对某自由浮现的个体变项用与原公式中所有个体变项符号别同的符号去代替，则所得公式与原来的公式等值.例求下列公式的前束范式(1) x(M(x)F(x))解x(M(x)F(x))x(M(x)F(x)) （量词否定等值式）x(M(x)F(x))两步结果基本上前束范式，讲明前束范式别惟一.(2) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x) （量词否定等值式）x(F(x)G(x)) （量词分配等值式）另有一种形式xF(x)xG(x)xF(x)x G(x)xF(x)y G(y) ( 换名规则) x y(F(x)G(y)) ( 量词辖域扩张) 两种形式是等值的(3) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)) （为啥？）或x y(F(x)G(y)) （为啥？）(4) xF(x)y(G(x,y)H(y))解xF(x)y(G(x,y)H(y))zF(z)y(G(x,y)H(y)) （换名规则）z y(F(z)(G(x,y)H(y))) （为啥？）或xF(x)y(G(z,y)H(y)) （代替规则）x y(F(x)(G(z,y)H(y)))(5) x(F(x,y)y(G(x,y)H(x,z)))解用换名规则, 也可用代替规则, 这个地方用代替规则 x(F(x,y)y(G(x,y)H(x,z)))x(F(x,u)y(G(x,y)H(x,z)))x y(F(x,u)G(x,y)H(x,z)))注意：x与y别能颠倒。

《离散数学(本)》主要概念、定理与方法第1章集合及其运算一、概念集合（元素）——集合是一些具有确定的、可以区分的若干事件的全体，而集合中的事件称为元素．因此，集合是由若干元素组成的．若a是集合A中的元素，则称a属于A，记作a∈A；若a不是集合A中的元素，则称a不属于A，记作a∉A．定义1.1.1（子集）对任意两个集合A和B，若B中的每个元素都是A中的元素，则称B 为A的子集，记作B⊆A或A⊇B．若B是A的子集，也称A包含B，或B被A包含．若B不是A的子集，即B⊆A不成立时，记作B⊆A．定义1.1.2（集合相等）对任意两个集合A和B，若有A⊆B且B ⊆A，则称A与B相等，记作A= B．定义1.1.3（真子集）对任意两个集合A和B，若B⊆A且B≠A，则称B为A的真子集，记作B⊂A或A⊃B．定义1.1.4（空集）不含任何元素的集合称为空集，记作∅．空集的定义也可以写成≠} （1.1.1）∅={x x xn元集（m元子集）——含有n个元素的集合简称n元集，它的含有m（m≤n）个元素的子集叫做它的m元子集．定义1.1.5（全集）在一个具体问题中，如果所涉及的集合都是某个集合的子集，则将这个集合称为全集，记作E．定义1.1.6（幂集）设A是一个集合，由A的所有子集组成的集合，称为A的幂集，记作P(A)或2A．定义1.2.1（并集、交集、差集、补集、对称差）设E为全集，A和B是E中任意两个子集．（1）所有属于A或属于B的元素组成的集合，称为集合A与B的并集，记作A⋃B．即∈}（1.2.1）{或x BA B x x A⋃=∈⋂．即（2）既属于A又属于B的所有元素组成的集合，称为集合A与B的交集，记作A B∈}（1.2.2）{且x B⋂=∈A B x x A如果两个集合A和B没有公共元素，即A B⋂=∅，称为集合A与B不相交．-．即（3）属于A而不属于B的所有元素组成的集合，称为A与B的差集，记作A B-=∈∉A B且（1.2.3）x x A x B{}（4）由E中所有不属于A的元素组成的集合，称为A的补集，记作~A．即~A={}且（1.2.4）x x E x A∈∉补集~A可以看作全集E与集合A的差集，即~A = E -A．（5）集合(A - B )⋃(B - A )称为集合A和B的对称差，记作A⊕B．即A⊕B = (A - B )⋃(B - A )．（1.2.5）对称差运算的另一种定义是A⊕B = (A⋃B ) - (B ⋂A )．（1.2.5’）二、定理与性质集合包含关系的自反性：对于任意集合A，有A⊆A．集合包含关系的反对称性：对任意两个集合A和B，若有A⊆B且B⊆A，则A=B．集合包含关系的传递性：对任意三个集合A，B和C，若有A⊆B，B⊆C，则A⊆C．定理1.1.1空集是一切集合的子集．定理1.1.1的推论空集是唯一的．集合运算的交换律：A B B A⋃=⋃⋂=⋂A B B A集合运算的结合律：()()A B C A B C ⋃⋃=⋃⋃()()A B C A B C ⋂⋂=⋂⋂集合运算的分配律：A B C A B A C ⋃⋂=⋃⋂⋃()()()A B C A B A C ⋂⋃=⋂⋃⋂()()()集合运算的幂等律：A ⋃A = AA ⋂A = A集合运算的同一律：A A ⋃∅=A E A ⋂=集合运算的零律：A ⋃E = EA ⋂∅=∅集合运算的补余律：A ⋃~A = EA ⋂~A =∅集合运算的吸收律：A A B A ⋃⋂=()A AB A ⋂⋃=()集合运算的摩根律：A - (B ⋃C ) = (A - B )⋂(A - C )A - (B ⋂C ) = (A - B )⋃(A - C )~ (B ⋃C ) = ~ B ⋂~ C~ (B ⋂C ) = ~ B ⋃~ C~∅= E~E =∅集合运算的双补律：~(~A ) = A对称差的交换律：A B B A ⊕=⊕对称差的结合律：()()A B C A B C ⊕⊕=⊕⊕对称差的分配律：A B C A B A C ⋂⊕=⋂⊕⋂()()()对称差的同一律：A A ⊕∅=对称差的零律：A ⊕A = ∅对称差的性质：A ⊕(A ⊕B ) = B定理1.2.1 对任意两个有限集合A 和B ，用S 表示有限集合S 中的元素数，则(1) A B ⋃≤A +B ； (2) A B ⋂≤min (A +B ) ；(3) A B -≥A -B ； (4) A B ⊕=A +B - 2A B ⋂ ．定理1.2.2（容斥定理） 对任意两个有限集合A 和B ，有A B ⋃= A +B - A B ⋂ （1.2.6） 其中A ，B 分别表示A ，B 的元素个数．定理1.2.2的推广结论：对于任意三个有限集合A , B , C ，有A B C ⋃⋃ = A +B +C -A B ⋂-A C ⋂-B C ⋂+A B C ⋂⋂（1.2.7）三、方法1．集合的三种表示方法列举法是列出集合的所有元素，并用花括号括起来．例如A = {a b c d ,,,}，N = {0, 1, 2, 3, …}．描述法是将集合中元素的共同属性描述出来．例如B = {x x x R 210-=∈且}，D = {x x 是正整数}．文氏图法是用一个简单的平面区域表示一个集合，用区域内的点表示集合内的元素．2．有限集合的计数方法首先根据已知条件把对应的文氏图画出来，然后将已知集合的元素填入表示该集合的区域内．通常从几个集合的交集填起，根据计算结果将数字逐步填入所有的空白区域内．如果交集的数字是未知的，可以将其设为x ，再根据已知条件列出方程或方程组，解出未知数x ．第2章 关系与函数一、概念有序对——有序对是指两个元素x 和y (允许x = y ) 按给定顺序排列组成的二元组合，记作<x , y > ．其中x 是它的第一元素，y 是它的第二元素．定义2.1.1（笛卡尔积、直乘积） 设A 和B 是任意两个集合，用A 中元素为第一元素，B 中元素为第二元素构成有序对，所有这样的有序对组成的集合称为集合A 和B 的笛卡尔积，或称为集合A 和B 的直乘积，记作A ⨯B ．即A ⨯B = {< x , y >x A ∈且y B ∈}定义2.1.2（二元关系） 任何一个有序对集合，称为一个二元关系，简称关系，记作R ．对于二元关系R ，若<a ，b >∈R ， 可记作aRb ；若<a ，b >∉R ， 则记作a R b ．定义2.1.3（从A 到B 的二元关系） 设A 和B 是两个集合，A ⨯B 的任一子集所定义的二元关系R 称为从A 到B 的二元关系．当A =B 时，称R 为A 上的二元关系．定义2.1.4（定义域、值域） 关系R 中有序对的第一元素所允许选取对象集合称为关系R 的定义域，记作Dom （R ），第二元素所允许选取对象集合称为关系R 的值域，记作Ran （R ）． 定义2.1.5（空关系、全关系、恒等关系） 对任何集合A ，(1) 因为空集∅是A ⨯A 的子集，所以定义了A 上的关系，称为A 上的空关系；(2) 定义 E A ={<a ，b >⎢a ∈A 且b ∈A }= A ⨯A ，称为A 上的全关系；(3) 定义I A ={<a ，a >⎢a ∈A }，称为A 上的恒等关系．定义2.1.6（关系矩阵） 设集合A ={a 1，a 2，…，a m }，B ={b 1，b 2，…，b n }，(1) 若R 是从A 到B 的一个关系，则R 的关系矩阵是m ⨯n 矩阵M R =()nm j i r ⨯， 其中 ⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1，(i =1, 2, …, m ；j =1, 2, …, n )． (2) 若R 是A 上一个关系，则R 的关系矩阵是m 阶矩阵M R =()mm j i r ⨯， 其中 ⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1，(i , j =1, 2, …, m )． 定义2.1.7（结点、关系图、自回路） 设集合A ={a 1，a 2，…，a m }，B ={b 1，b 2，…，b n }，若R 是从A 到B 的一个关系，则用m 空心点表示a 1，a 2，…，a m ，用n 空心点表示b 1，b 2，…，b n ，这些空心点统称为结点．如果a i Rb j ，那么由结点a i 到结点b j 作一条有向弧，箭头指向b j ；如果<a i ，b j >∉R ，那么结点a i 与b j 之间没有弧连结，这样的图形称为R 的关系图． 若R 是A 上一个关系，如果a i Ra j (i ≠j )，有向弧的画法与上面相同；如果a i Ra i ，则画一条从结点a i 到结点 a i 的带箭头的封闭弧，称为自回路．定义2.2.1（复合关系） 设A ，B ，C 是三个集合，R 是从A 到B 的一个二元关系，S 是从B 到C 的一个二元关系，则R 与S 的复合关系为R ·S ={<a , c >⎢a ∈A ，c ∈C ，且存在b ∈B ，使<a , b >∈R ，<b , c >∈S }这个复合关系是从A 到C 的一个二元关系．布尔运算——布尔运算只涉及数字0和1，规定：加法：0+0 = 0， 0+1 = 1+0 = 1+1 = 1；乘法：1⨯1 = 1， 1⨯0 = 0⨯1 = 0⨯0 = 0 ．定义2.2.2（复合关系矩阵） 设集合A ={a 1，a 2，…，a m }，B = {b 1，b 2，…，b n }，C = {c 1，c 2，…，c p }，从A 到B 的二元关系R 的关系矩阵M R 是一个m 行n 列的矩阵，从B 到C 的二元关系S 的关系矩阵M S 是一个n 行p 列矩阵，则从A 到C 的复合关系R ·S 的关系矩阵S R M •是一个m 行p 列矩阵，并且S R M •= M R ⨯ M S （2.2.1）其中⨯表示按布尔运算进行矩阵乘法运算．定义2.2.3（二元关系的幂） 设R 是集合A 上的一个二元关系，n ∈N ，则关系R 的n 次幂R n 定义为：(1) R 0= I A ，即R 0是集合A 上的恒等关系；(2) R n +1 = R n ·R ．定义2.2.4（逆关系） 设R 是从集合A 到B 的二元关系，则从集合B 到A 的二元关系R –1：R –1 = {<b , a > <a , b >∈R } (2.2.3) 称为R 的逆关系．定义2.3.1（自反关系、反自反关系） 设R 是集合A 上的二元关系，若对任意a ∈A ，都有aRa ，即<a , a >∈R ，则称R 为A 上自反的关系；若对任意a ∈A ，都有a R a ，即<a , a >∉R ，则称R 为A 上反自反的关系．定义2.3.2（对称关系、反对称关系） 设R 是集合A 上的二元关系，对任意a ，b ∈A ，若有<a , b >∈R ，就必有<b , a >∈R ，则称R 为A 上对称的关系；若有<a , b >∈R ，且<b , a >∈R ，就必有b = a ，则称R 为A 上反对称的关系．定义2.3.3（传递关系） 设R 是集合A 上的二元关系，对任意a ，b ，c ∈A ，若有<a , b >∈R ，且<b , c >∈R ，就必有<a , c >∈R ，则称R 为A 上传递的关系．定义2.3.4（自反闭包、对称闭包，传递闭包） 设非空集合A 上的二元关系R ，若有A 上的另一个二元关系R '满足：(1) R '是自反的（对称的，传递的）；(2) R ⊆R '；(3) 对A 上任何包含R 的自反（对称，传递）关系R ''都有R '⊆R ''；则称关系R '为R 的自反（对称，传递）闭包，记作r (R )（s (R )，t (R )）．定义2.4.1（等价关系） 设R 是非空集合A 上的二元关系，如果R 是自反的、对称的和传递的，则称R 是A 上的等价关系．设R 是一个等价关系，如果<a , b >∈R ，称a 等价于b ，记作a ~ b ．定义2.4.2（等价类） 设R 是非空集合A 上的等价关系，对任意a ∈A ，令[a ]R = {b ⎪b ∈A 且aRb } (2.4.1)则称集合[a ]R 为a 关于R 的等价类，简称a 的等价类，简记作[a ]或a ．定义2.4.3（商集） 设R 是非空集合A 上的等价关系，以R 的所有等价类作为元素的集合，成为A 关于R 的商集，记作A/R ．即A/R = {[a ]R ⎪a ∈A } (2.4.2) 定义2.4.4（划分块） 设A 是非空集合，若A 的子集族π满足：(1) π∉∅；(2) π中任何两个子集都不相交；(3) π中所有子集的并集就是A ．则称π为A 的一个划分，称π中的元素为A 的划分块．定义2.5.1（相容关系） 设R 是非空集合A 上的二元关系，如果R 是自反的、对称的，则称R 是A 上的相容关系．定义2.5.2（相容类） 设R 是非空集合A 上的相容关系，B 是A 的子集，如果在B 中的任意两个元素都是相关的，则称为由相容关系R 产生的相容类．最大相容类——R 是A 上的相容关系，B 是相容类，若在差集A -B 中没有一个元素能和B 中所有元素都是相关的，则称B 为最大相容类．定义2.5.3（覆盖） 设A 是非空集合，若A 的子集族π满足：(1) π∉∅；(2) π中所有子集的并集就是A ．则称π为A 的一个覆盖，称π中的元素为A 的覆盖块．定义2.5.4（完全覆盖） 设集合A 的子集族π={A 1 , A 2 , … , A n }是A 的覆盖，且对π中任意元素A i ，不存在其它元素A j ，使得A i 是A j 的子集，则称π为A 的一个完全覆盖．定义2.5.5（偏序关系） 设R 是非空集合A 上的二元关系，如果R 是自反的、反对称的和传递的，则称R 是A 上的偏序关系，或称序关系，记作≤．设≤是偏序关系，如果<a , b >∈≤，则记作a ≤b ，读作a “小于等于”b ．定义2.5.6（拟序关系） 设R 是非空集合A 上的二元关系，如果R 是反自反的和传递的，则称R 是A 上的拟序关系，记作<．设<是拟序关系，如果<a , b >∈<，则记作a <b ，读作a “小于”b ．定义2.5.7（全序关系、线序关系） 设R 是非空集合A 上的偏序关系，如果对任意a ，b ∈A ，必有a ≤b 或b ≤a ，则称R 是A 上的全序关系，或称线序关系．定义2.5.8（偏序集） 集合A 和A 上的偏序关系≤一起称为偏序集，记作<A ，≤>． 哈斯图——对于给定的偏序集<A ，≤>，用一个简化的偏序关系图来表示，我们将这种简化的关系图称为哈斯（Hasse ）图．它的作图规则为：(1) 去掉每个结点的自回路，只用一个空心点表示集合A 的元素；(2) 适当排列结点的顺序，即对任意a ，b ∈A ，若a ≤b ，则将a 画在b 的下方；(3) 对任意a ，b ∈A ，若a <b ，且不存在c ∈A ，使得a <c <b ，则就在a ，b 之间画一条无向弧．定义2.5.9（盖住） 设R 是非空集合A 上的偏序关系，a 和b 是A 中两个不同的元素，如果<a , b > ∈R ，且在A 中没有其它元素c ，使得<a , c >∈R 和<c , b >∈R ，则称元素b 盖住元素a ． 定义2.5.10（最大元、最小元、极大元、极小元） 设<A ，≤>为序集，集合B ⊆A ，存在元素b ∈B ，(1) 若对任意a ∈B ，都有a ≤b ，则称b 为B 的最大元；(2) 若对任意a ∈B ，都有b ≤a ，则称b 为B 的最小元；(3) 若对任意a ∈B ，且b ≤a ，都有a = b ，则称b 为B 的极大元；(4) 若对任意a ∈B ，且a ≤b ，都有a = b ，则称b 为B 的极小元．定义2.5.10（上界、下界、最小上界、上确界、最大下界、下确界） 设<A ，≤>为偏序集，集合B ⊆A ，存在元素b ∈A ，(1) 若对任意a ∈B ，都有a ≤b ，则称b 为B 的上界；(2) 若对任意a ∈B ，都有b ≤a ，则称b 为B 的下界；(3) 若集合C = {b ⎪b 为B 的上界}，则C 的最小元称为B 的最小上界或上确界；(4) 若集合D = {b ⎪b 为B 的下界}，则D 的最大元称为B 的最大下界或下确界． 定义2.6.1（函数、映射） 对集合A 到集合B 的二元关系f ，若满足下列条件：(1) 对任意a ∈Dom(f )，都存在唯一的b ∈Ran(f )，使<a , b >∈f ，（即afb ）成立；(2) Dom(f ) = A ；则称f 为从A 到B 的函数，或称为映射，记作f ：A →B ．若有afb ，则可记作b = f (a )．定义2.6.2（函数相等） 设f 和g 是从集合A 到B 的两个函数，若对任意a ∈A ，都有f (a ) = g (a )，则称函数f 和g 相等，记作f = g ．定义2.6.3（函数的象） 设f 是从集合A 到B 的函数，且A 1⊆A ，则将f (A 1) = {f (a ) a ∈A 1}称为A 1在f 下的象．特别地，称f (A )为函数的象．定义2.6.4（满射、单射、双射） 设f 是从集合A 到B 的函数，(1) 若Ran(f ) = B ，则称f 为从A 到B 的满射；(2) 若对任意b ∈Ran(f )，都存在唯一的a ∈Dom(f )，使得f (a ) = b ，则称f 为从A 到B 的单射，或称一对一的；(3) 若f 从A 到B 既是满射又是单射的，则称f 为从A 到B 的双射，或称一一对应的．定义2.6.5（常数函数、恒等函数、单调递增、严格单调递增、单调递减、严格单调递减、特征函数、自然映射）(1) 设f 是从集合A 到B 的函数，若存在一个b ∈B ，使得对所有的a ∈A 都有f (a ) = b ，则称f 是从A 到B 的常数函数．(2) 集合A 上的恒等关系I A 称为A 上的恒等函数．即对所有的a ∈A 都有I A (a ) = a ．(3) 设f 是实数集R 上的函数，对任意的a 1，a 2∈A ，如果由a 1< a 2，可得f (a 1)≤ f (a 2)，则称f 为单调递增的；如果由a 1< a 2，可得f (a 1)< f (a 2)，则称f 为严格单调递增的．类似地，可以定义单调递减的和严格单调递减的函数．(4) 设A 为集合，对任意子集A '⊆ A ，A '的特征函数A 'χ：E →{0 , 1}定义为A 'χ(a )=⎩⎨⎧'-∈'∈A A a A a ,0,1 (2.6.1) (5) 设R 是集合A 上的等价关系，令g 为从A 到A/R 的函数，即g (a ) =[a ]，则称g 为从A 到商集A/R 的自然映射．定义2.6.6（复合函数）设函数f：A→B，g：B→C，则将复合关系g•f = {<a , c> a∈A，c∈C，且存在b∈B，使f(a) = b，g(b) = c}称为函数f和g的复合函数．定义2.6.7（反函数）设函数f：A→B是双射的，则将f的逆关系称为反函数，记作f–1：B →A．可逆函数——如果函数f 存在反函数f–1，称f是可逆的．二、定理与性质有序对性质1 当x≠y时，有序对< x , y >≠< y , x > ．有序对性质2有序对< x , y > = < a , b > 的充分必要条件是x = a，y = b．笛卡尔积性质1对任意集合A，有A⨯∅= ∅，∅⨯A= ∅．笛卡尔积性质2 笛卡尔积运算不满足交换律，即当集合A≠∅，B≠∅且A≠B时，A⨯B≠B⨯A．笛卡尔积性质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 )；笛卡尔积性质5对交集的分配律：A⨯(B⋂C ) = (A⨯B)⋂(A⨯C )；(B⋂C )⨯A= (B⨯A)⋂(C⨯A )．定理2.1.1对任意三个集合A, B和C，若有C≠∅，则(1)A⊆B的充分必要条件是A⨯C⊆B⨯C；(2)A⊆B的充分必要条件是C⨯A⊆C⨯B．定理2.1.2对任意四个非空集合A, B, C和D，则A⨯B⊆C⨯D的充分必要条件是A⊆C，B⊆D．定理2.2.1设R和S从A到B的两个二元关系，那么R和S的R⋃S，R⋂S，R-S，~R，R⊕S仍然是从A到B的二元关系．定理2.2.2设R是从集合A到B的二元关系，S和T分别是从集合B到C的二元关系，U 是从集合C到D的二元关系，则(1) R·(S⋃T) = R·S⋃R·T；(2) R·(S⋂T)⊆R·S⋂R·T；(3)(S⋃T)·U = S·U⋃T·U；(4)(S⋂T)·U⊆S·U⋂T·U．定理2.2.3设R，S，T，分别表示从集合A到B，从集合B到C，从集合C到D的二元关系，则(R·S)·T= R·(S·T) （2.2.2）定理2.2.4设R是集合A上的二元关系，m，n∈N，则(1) R m·R n = R m + n；(2) (R m)n = R m n．定理2.2.5设R和S分别是从集合A到B的二元关系，则(1) (R –1)-1 = R(2) (R⋃S)-1 = R -1⋃S -1(3) (R⋂S)-1 = R -1⋂S -1(4) (R -S)-1 = R –1 -S -1(5) (~R)–1 = ~R -1(6) (A⨯B)-1 = B⨯A(7) ∅-1 =∅(8) R=S⇔R –1=S –1 (9) R⊆S⇔R -1⊆S -1定理2.2.6设R是从集合A到B的二元关系，S是从集合B到C二元关系，则(R·S)-1 = S -1·R –1定理2.3.1设R是非空集合A上的二元关系，则(1) R是自反的当且仅当r (R) = R；(2) R是对称的当且仅当s (R) = R；(3) R是传递的当且仅当t (R) = R；定理2.3.2设R是非空集合A上的二元关系，I A是A上的恒等关系，则r (R) = R⋃I A．（2.3.1）定理2.3.3设R是非空集合A上的二元关系，则s (R) = R⋃R –1（2.3.3）定理2.3.4 设R是非空集合A上的二元关系，则t (R) =∞=⋃1iR i=R⋃R 2⋃R 3⋃… （2.3.5）定理2.3.4的推论设R是非空有限集合A上的二元关系，且A有n个元素，则t (R ) = ni 1=⋃R i =R ⋃R 2⋃…⋃R n （2.3.6） 定理2.4.1 设R 是非空集合A 上的等价关系，对任意a , b ∈A ，(1) [a ]∅≠，且[a ]⊆A ； (2) 若aRb ，则[a ]= [b ]；(3) 若a R b ，则[a ]⋂[b ]= ∅； (4) ⋃{[a ]⎪a ∈A }= A ．定理2.5.1 设R 是集合A 上的拟序关系，则R 是反对称的．定理2.6.1 设函数f ：A →B ，g ：B →C ，那么复合函数g •f 是一个从A 到C 的函数，而且，对任意一个a ∈A ，都有(g •f )(a ) = g (f (a ))．定理2.6.2 设函数f ：A →B ，g ：B →C ，h ：C →D ，那么h •(g •f ) = (h •g )•f (2.6.2)定理2.6.3 设函数f ：A →B ，g ：B →C ，且g •f ：A →C ，那么(1) 若f 和g 都是满射的，则g •f 也是满射的；(2) 若f 和g 都是单射的，则g •f 也是单射的；(3) 若f 和g 都是双射的，则g •f 也是双射的．定理2.6.4 设函数f ：A →B ，g ：B →C ，且g •f ：A →C ，那么(1) 若g •f 是满射的，则g 也是满射的；(2) 若g •f 是单射的，则f 也是单射的；(3) 若g •f 是双射的，则g 是满射的，f 是单射的．定理2.6.5 设函数f ：A →B 是双射的，则f -1：B →A 也是双射的．定理2.6.6 如果函数f ：A →B 是双射的，则有(1) f –1•f = I A ， f •f –1= I B ；(2) (f –1)-1 = f ． (2.6.4) 定理2.6.7 设函数f ：A →B ，g ：B →C ，且f 和g 都是双射的，则有(g •f )-1 = f –1•g –1 (2.6.5)定理2.6.8 设函数f ：A →B ，g ：B →C ，且f 和g 都是双射的，则有(g •f )-1 = f –1•g –1三、方法1．关系的矩阵表示法设集合A ={a 1 , a 2 , … , a m }，B ={b 1 , b 2 , … , b n }，(1) 若R 是从A 到B 的一个关系，则R 的关系矩阵是m ⨯n 矩阵M R =()n m j i r ⨯，其中⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1 ，(i =1, 2, …, m ；j =1, 2, …, n ） (2) 若R 是A 上一个关系，则R 的关系矩阵是m 阶矩阵M R =()m m j i r ⨯，其中 ⎪⎩⎪⎨⎧=ji j i j i b R a Rb a r 当当,0,1 ，(i , j =1, 2, …, m ） 2．关系的图象表示法设集合A ={a 1 , a 2 , … , a m }，B ={b 1 , b 2 , … , b n }，若R 是从A 到B 的一个关系，则用m 空心点表示a 1 , a 2 , … , a m ，用n 空心点表示b 1 , b 2 , … , b n ，这些空心点统称为结点．如果a i Rb j ，那么由结点a i 到结点b j 作一条有向弧，箭头指向b j ；如果<a i , b j >∉R ，那么结点a i 与b j 之间没有弧连结，这样的图形称为R 的关系图．若R 是A 上一个关系，如果a i Ra j (i ≠j )，有向弧的画法与上面相同；如果a i Ra i ，则画一条从结点a i 到结点 a i 的带箭头的封闭弧，称为自回路．3．复合关系的矩阵运算法设集合A ={a 1，a 2，… ，a n }，B = {b 1，b 2，… ，b n }，C = {c 1，c 2，… ，c n }，从A 到B 的二元关系R 的关系矩阵M R 是一个m 行n 列的矩阵，从B 到C 的二元关系S 的关系矩阵M S 是一个n 行p 列矩阵，则从A 到C 的复合关系R ·S 的关系矩阵S R M •是一个m 行p 列矩阵，并且S R M •= M R ⨯ M S ，其中⨯表示按布尔运算进行矩阵乘法运算．4．二元关系性质的判别法(1) 若R 是集合A 上自反的关系，则有I A ⊆R ⊆E A ；(2) 若R 是集合A 上非自反的关系，则有R ⋂I A =∅；(3) R 为集合A 上对称关系的充分必要条件是R = R -1 ；(4) R 为集合A 上反对称关系的充分必要条件是R ⋂R -1⊆ I A ；(5) R 为集合A 上传递关系的充分必要条件是R ·R ⊆R ．5．求闭包的方法(1) 设R 是非空集合A 上的二元关系，I A 是A 上的恒等关系，则r (R ) = R ⋃I A ．(2) 设R 是非空集合A 上的二元关系，则s (R ) = R ⋃R –1．(3) 设R 是非空集合A 上的二元关系，则t (R ) = ∞=⋃1i R i =R ⋃R 2⋃R 3⋃… 设R 是非空有限集合A 上的二元关系，且A 有n 个元素，则t (R ) = ni 1=⋃R i =R ⋃R 2⋃…⋃R n ． 6．等价关系的判别方法利用等价关系的关系图进行判别，即当关系R 的关系图满足：每个结点都有自回路；两个结点a ，b 之间若有从a 指向b 的弧，就有从b 指向a 的弧；若有从结点a 指向b 的弧，且有从b 指向c 的弧，就有从a 指向c 的弧时，则R 是等价关系．7．哈斯图的作图规则(1) 去掉每个结点的自回路，只用一个空心点表示集合A 的元素；(2) 适当排列结点的顺序，即对任意a ，b ∈A ，若a ≤b ，则将a 画在b 的下方；(3) 对任意a ，b ∈A ，若a <b ，且不存在c ∈A ，使得a <c <b ，则就在a ，b 之间画一条无向弧．第3章 图的基本概念与性质一、概念图——图可以用集合的形式表示，即图可以表示为一个三元组，包含结点集、边集，以及边与结点对集间的映射．如果用结点对来表示边，则图可以表示成一个由结点集与边集组成的二元组．定义3.1.1 图G 是一个三元组<V （G ），E （G ），ϕG >，其中V （G ）是一个非空的结点集（或称顶点集），E （G ）是边集，ϕG 是从边集E （G ）到结点偶对（无序偶或有序偶）集上的函数．图定义中的结点偶对可以是有序的，也可以是无序的．有向边、端点——若图中的边e 所对应的结点偶对是有序的，记为<a ，b >，则称e 是有向边（简称弧）．a ，b 分别称为弧的始点与终点，并均称为e 的端点．称e 是关联于结点a 和b 的，结点a 和结点b 是相、邻的，或称结点a 和结点b 是邻接的．无向边、端点——若图中的边e 所对应的结点偶对是无序的，记为（a ，b ），则称e 是无向边（简称棱）．a ，b 称为e 的端点．称e 是关联于结点a 和b 的，结点a 和结点b 是相、邻的，或称结点a 和结点b 是邻接的．有向图——每一条边均为有向边的图称为有向图．无向图——每一条边均为无向边的图称为无向图．底图——如果把有向图中每条有向边都看作无向边，就得一个无向图，此无向图称为原有向图的底图．底图只表示出结点间的连接关系而没有表示出连接边的方向．弧立结点——图中不与任何相邻的结点称为弧立结点．零图——全由孤立结点构成的图称为零图．自回路（环）——关联于同一结点的一条边称为自回路或环．重边（平行边）——在有向图中，两结点间（包括结点自身间）若多于一条边，则称这几条边为重边或平行边．多重图——含有重边的图称为多重图．线图——非多重图称为线图．定义3.1.2（简单图）无自回路的线图称为简单图．定义3.1.3（结点的度数、最大度、最小度）图G=<V，E>中，与V中结点v（v∈V）相关联的边数，称为该结点的度数，记作为deg(v)．记∆（G）= max{deg(v)| v∈V（G）}，δ（G）= min{deg(v)| v∈V（G）}，分别称为G=<V，E>的最大度和最小度．定义3.1.4（出度、入度、度数）在有向图中，对于任何结点v，以v为始点的边的条数称为结点v的引出次数（或出度）；以v为终点的边的条数称为结点v的引入次数（或入度）；结点v的引出次数和引入次数之和称为v的次数（或度数）．定义3.1.5（二部图）设G=〈V，E>是n阶无向图，若能将V分成两个互不相交的子集V1与V2使得G中任一边的两端点都不在同一个V i（i=1,2）中，则称G为二部图．记G=<V1,V2，E>．定义3.1.6（完全图）简单图G=<V，E>中，若每一对结点间都有边相连，则称该图为完全图．有n个结点的无向完全图记为K n．定义3.1.7（k-正则图）若无向简单图中，每个结点的度均为某个固定整数k，则称该图为k-正则图．定义3.1.8（赋权图）赋权图G是一个三重组<V，E，g>或四重组<V，E，f，g>，其中V 是结点集合，E是边的集合，f是定义在V上的函数，g是定义在E上的函数．定义3.1.9（补图）设图G=<V，E>有n个顶点，图H=<V，E’>也有同样的顶点，而E’是由n个结点的完全图的边删去E所得，则图H称为图G的补图，记为H=G，显然，G=H．定义3.1.10（子图、真子图、生成子图）设G=<V,E>和G’=<V’,E’>是两个图．(1)若V’⊆V且E’⊆E，则称G’是G的子图；(2)若V’⊂V或E’⊂E,则称G’是G的真子图；(3)若V’=V和E’ ⊆E,则称G’是G的生成子图；(4)若子图G’中没有孤立结点，G’由E’唯一确定，则称G’为由边集E’导出的子图；(5)若子图G’中，对V’中的任意两个结点u，v，当u，v∈V’时有[u，v]∈E’，则G’由V’唯一确定，则称G’为由结点集V’导出的子图．定义3.1.11(补图) 设G’=<V’，E’>是G=<V，E>的子图，若给定另外一个图G’’=<V’’，E’’>，使得E’’=E-E’，且V’’中仅包含E’’的边所关联的结点，则称G’’是子图G’的相对于G的补图．定义3.1.12(同构) 设G=〈V，E>和G’=<V’,E’>是两个图，若存在从V到V’的双射函数f，使对任意[a，b]∈E，当且仅当[f(a)，f(b)]∈E’，并且[a，b]和[f(a)，f(b)]有相同的重数，则称G 和G’是同构的．定义3.1.13(路径) 在图G=<V，E>中，设v0，v1，…，v n∈V，e1，e2,…., e n∈E，其中e i是关联于结点v i-1，v i的边，交替序列v0 e1 v1 e2…e n v n称为联结v0到v n的路径（或称路）．v0与v n 分别称为路的起点与终点，边的数目n称为路的长度．孤立点——长度为0的路定义为孤立点．简单路径——若序列中所有的边e1，e2,…., e n均互不相同，则称此路径为简单路径．基本路径——若序列中所有的点v0，v1，…，v n均互不相同，则称此路径是基本路径．回路——若v0=v n，即路径中的终点与始点相重合，则称此路径为回路．简单回路——没有相同边的回路称为简单回路．基本回路（圈）——各结点均互不相同的回路称为基本回路（或圈）．奇圈（偶圈）——长度为奇（偶）数的圈称为奇（偶）圈．定义3.2.1（可达、连通）在图G=<V,E>中，设有结点v j与v k，若从v j到v k存在任何一条路径，则称结点v k从结点v j可达，也称结点v j与v k是连通的．定义3.2.2（连通图、非连通图、分离图）若G是平凡图或G中任意两个结点都是连通的，则称G是连通图，否则称G为非连通图或分离图．定义3.2.3（连通分支） 设G =<V ,E >是图，连通关系的商集为{V 1, V 2,…, V m }，则其导出的子图G (V i)（i=1,2,…m ）称为图G 的连通分支（图），将图G 的连通分支数记作W （G ）．定义3.2.4（短程线） 设u 与v 是图G 的两个结点，若u 与v 连通，则称u 与v 之间的长度最短的路为u 与v 之间的短程线，短程线的长度可作为结点u 与v 间的距离，记作d (u ,v )，其满足下列性质：d (u ,v ) ≥ 0，u =v 时，d (u ,v ) =0 （非负性）d (u ,v ) = d (v ,u ) （对称性）d (u ,v ) + d (v ,w ) ≥ d (u ,w ) （三角不等式）若u 与v 不连通，则通常记d (u ,v ) = ∞ ．定义3.2.5（单向连通、强连通、弱连通） 在简单有向图中，如果在任何结点偶对中，至少从一个结点到另一个结点可达的，则称图G 是单向（侧）连通的；如果在任何结点偶对中，两结点对互相可达，则称图G 是强连通的；如果图的底图（在图G 中略去边的方向，得到无向图）是连通的，则称图G 是弱连通的． 定义3.2.6（极大强连通子图、极大单向连通子图、极大弱连通子图、强分图、单向分图、弱分图） 在简单有向图G =<V ，E >中，G’是G 的子图，如G’是强连通的（单向连通的，弱连通的），且没有包含G’的更大的子图G’’是强连通的（单向连通的，弱连通的），则称G’是极大强连通子图（极大单向连通子图，极大弱连通子图）又叫强分图（单向分图，弱分图）．定义3.2.7（点割集、割点） 设无向图G =<V ,E >为连通图，若有点集V 1⊂V ，使图G 删除了V 1的所有结点后，所得的子图是不连通图，而删除了V 1的任何真子集后，所得的子图是连通图，则称V 1是G 的一个点割集．若某个结点构成一个点割集，则称该结点为割点．定义3.2.8（点连通度） 若G 为无向连通图且不含Kn 为生成子图，则称k (G )=min{|V 1| ∣V 1是G 的一个点割集}为G 的点连通度（简称连通度）．规定：完全图Kn 的点连通度为n ，n ≥1．非连通图的点连通度为0．若k (G ) ≥k ，则称G 为k -连通图．定义3.2.9（边割集、割边、桥） 设无向图G =<V ,E >为连通图，若有边集E 1⊂E ，使图G 删除了E 1的所有边后，所得的子图是不连通图，而删除了E 1的任何真子集后，所得的子图是连通图，则称E 1是G 的一个边割集．若某个边构成一个边割集，则称该结点为割边（或桥）．定义3.2.10（连通度） 若G 为无向连通图，则称λ(G )=min{|E 1| ∣E 1是G 的一个边割集}为G 的边连通度．规定：非连通图的边连通度为0．若λ(G ) ≥k ，则称G 为k 边-连通图．定义3.3.1（邻接矩阵） 设G =<V ，E >是一个简单图，其中V ={v 1，v 2，…， v n }，则n 阶方阵A （G ）=（a ij ）称为G 的邻接矩阵．其中各元素⎪⎩⎪⎨⎧==ji v v v v a j i j i ij 不相邻或与相邻与01 定义3.3.2（可达性矩阵） 设G =<V ，E >是一个简单图，|V |=n ,假定G 的结点已编序，即V ={v 1，v 2，…， v n }，定义一个n ⨯n 方阵P =（p ij ）．其中⎪⎩⎪⎨⎧=不存在一条路与从至少存在一条路到从j i j i ij v v v v p 01 则称矩阵P 为图G 的可达性矩阵．最短路径的数学模型——给定一个网络N （有向或无向赋权图），u 0与v 0是N 中指点的两个顶点，在N 中找一条从u 0到v 0且权最小的路．规定N 中的一条路P 的权w (P )称为p 的长度．若N 中存在从u 到v 的路，则将N 中从u 到v 且权最小的路称为u 到v 的最短路，其长度称为u 到v 的距离，记为d N （u ,v ）．二、定理定理3.1.1（握手定理） 设G 是一个图，其结点集合为V ，边集合为E ，则∑∈=V v E v ||2)deg(定理3.1.2 图中次数为奇数的结点有偶数个．。

离散数学（第五版）清华大学出版社第2章习题解答2.1 本题没有给出个体域,因而使用全总个体域.(1) 令F(x):x是鸟G(x):x会飞翔.命题符号化为?x(F(x)→G(x)).(2)令F(x):x为人.G(x):x爱吃糖命题符号化为??x(F(x)→G(x))或者?x(F(x)∧?G(x))(3)令F(x):x为人.G(x):x爱看小说.命题符号化为?x(F(x)∧G(x)).(4) F(x):x为人.G(x):x爱看电视.命题符号化为??x(F(x)∧?G(x)).分析1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。

（1）-（4）中的F(x)都是特性谓词。

2°初学者经常犯的错误是，将类似于（1）中的命题符号化为27?x(F(x)∧G(x))即用合取联结词取代蕴含联结词，这是万万不可的。

将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。

”因而符号化应该使用联结词→而不能使用∧。

若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。

”这显然改变了原命题的意义。

3°（2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。

2.2 (1)d (a),(b),(c)中均符号化为?xF(x)其中F(x):(x+1)2=x2+2x+1,此命题在(a),(b),(c)中均为真命题。

（2）在(a),(b),(c)中均符号化为?xG(x)其中G(x):x+2=0，此命题在（a）中为假命题，在(b)(c)中均为真命题。

（3）在(a),(b),(c)中均符号化为?xH(x)其中H(x):5x=1.此命题在(a),(b)中均为假命题，在(c)中为真命题。

分析1°命题的真值与个体域有关。

2°有的命题在不同个体域中，符号化的形式不同，考虑命题“人都呼吸”。

离散数学（微课版）第2章习题答案2.1 集合与运算习题1给定两个集合A={1，3，5，7，9}和B={2，4，6，8，10}，求A∪B和A∩B。

解答：集合A和B的并集（A∪B）是包含了A和B中所有元素的集合。

根据题目给出的集合A和B，可以得到并集A∪B={1，2，3，4，5，6，7，8，9，10}。

集合A和B的交集（A∩B）是包含了A和B中共有的元素的集合。

根据题目给出的集合A和B，可以得到交集A∩B={}，因为集合A和B中没有共有的元素。

习题2给定两个集合A={奇数}和B={偶数}，求A和B的交集和并集。

如果集合B改为B={2，4，6，8}，结果是否有变化？解答：集合A表示奇数，集合B表示偶数。

当集合A和B中元素的范围比较广泛时，它们的交集为{}，因为奇数和偶数没有共有的元素。

当集合B改为B={2，4，6，8}时，集合A和B中共有的元素为{}，并集为A∪B=奇数∪{2，4，6，8}={奇数，2，4，6，8}。

2.2 命题与逻辑运算习题3给定两个命题p：“小明喜欢篮球”和q：“小明是篮球队的队长”。

请判断以下复合命题是真还是假：（1）p∧q；（2）p∨q；（3）p→q。

解答：命题p：“小明喜欢篮球” 是真命题。

命题q：“小明是篮球队的队长” 是假命题。

（1）p∧q：当p和q都为真时，命题p∧q才为真。

根据题目中给出的p和q的真值，可以确定p∧q是假命题。

（2）p∨q：当p和q中至少一个为真时，命题p∨q就为真。

根据题目中给出的p和q的真值，可以确定p∨q是真命题。

（3）p→q：当p为真时，命题p→q为真，否则为假。

根据题目中给出的p和q的真值，可以确定p→q是真命题。

习题4给定一个命题p：“2是偶数”。

请判断以下复合命题是真还是假：（1）¬p；（2）p∧¬p；（3）¬p∨p。

解答：命题p：“2是偶数” 是真命题。

（1）¬p：取命题p的否定，即“2不是偶数”，根据命题p的真值，可以确定¬p是假命题。

离散数学教程集合的基本概念标题：离散数学教程——集合的基本概念离散数学是数学的一个重要分支，它研究的是数学中离散对象的性质和结构。

在这些离散对象中，集合是最基本的概念之一。

集合是由一些互不相同的、可以区分的对象组成的整体，这些对象可以是数字、字母、图形等。

在离散数学中，集合的概念被广泛地应用于各种不同的领域，包括计算机科学、信息论、统计学等。

一、集合的基本定义1、集合是由一些特定对象组成的整体，这些对象可以是任何类型，如数字、字母、图形等。

2、集合中的对象必须是互不相同的，即集合中的每个对象都是独一无二的，不能有两个或更多的对象重复。

3、集合的元素具有可区分性，即可以根据一定的规则或性质将集合中的对象区分开来。

二、集合的表示在数学中，通常用大写字母来表示集合，如A、B、C等。

如果集合中有多个元素，则可以用列举法或描述法来表示集合。

1、列举法：将集合中的所有元素一一列举出来，用大括号括起来。

例如，A={1, 2, 3}表示集合A包含1、2和3这三个元素。

2、描述法：用特定的符号或语言来描述集合的性质或特征。

例如，B={x|x是正方形}表示集合B包含所有的正方形。

三、集合的运算在离散数学中，集合的运算是最基本的概念之一。

常见的集合运算包括交集、并集、补集等。

1、交集：如果集合A和B的元素都有共同的属性或特征，则称A和B有交集。

记作A∩B或A.B，表示A和B的交集。

2、并集：如果集合A和B的所有元素都属于另一个集合C，则称A 和B的并集为C。

记作A∪B或A.B，表示A和B的并集。

3、补集：如果集合A中存在一些不属于B的元素，则称B为A的补集。

记作∁AB，表示A的补集。

四、集合的性质1、空集：没有任何元素的集合称为空集。

记作∅。

空集是所有集合的子集。

2、全集：包含所有可能元素的集合称为全集。

记作U。

全集是所有集合的超集。

3、幂集：给定一个集合A，A的幂集是指包含A的所有子集的集合。

记作P(A)。

4、子集：如果一个集合B的所有元素都属于另一个集合A，则称B为A的子集。

离散数学集合及运算离散数学是计算机科学的基本学科之一，也是计算机学习和研究的重要基础。

集合和运算是离散数学中最基本的概念之一，也是计算机学习过程中最基础的概念之一。

本文主要介绍集合及运算的相关概念。

一、集合的定义在数学中，集合是一组确定的对象的集合。

它们可以是数、字母、变量、符号、函数或其他数学实体。

集合是以大写字母表示的，属于这个集合的元素以小写字母表示。

例如，集合A可以包括元素a、b和c，表示为A={a，b，c}。

集合中没有重复的元素，但元素的顺序是不重要的。

例如，集合{a，b，c}和{c，a，b}是相等的，因为它们包含相同的元素。

二、集合的运算1. 并集对于两个集合A和B，它们的并集就是包含A和B的所有元素的集合。

简单而言，对于集合A和B，A ∪ B就是由A和B中的元素组成的集合。

例如，如果A={a，b，c}，B={c，d，e}，那么A ∪ B={a，b，c，d，e}。

并集也可以扩展到多组集合的情况。

例如，如果有三个集合A、B和C，它们的并集可以表示为A∪B∪C。

2. 交集对于两个集合A和B，它们的交集是指它们共有的元素所组成的集合。

简单来说，如果一个元素同时属于集合A和集合B，那么这个元素就属于A和B的交集。

例如，如果A={a，b，c}，B={c，d，e}，那么A ∩ B={c}。

同样地，交集也可以扩展到多组集合的情况。

例如，如果有三个集合A、B和C，它们的交集可以表示为A∩B∩C。

3. 补集对于一个集合A和它包含的全集U，它的补集是指所有不属于集合A的元素构成的集合。

简单来说，补集就是相对于全集的补集。

例如，如果集合A={a，b，c}，全集U={a，b，c，d，e}，那么A的补集就是U-A={d，e}。

4. 差集对于两个集合A和B，它们的差集是指所有属于集合A但不属于集合B的元素所构成的集合。

简单来说，差集就是集合A中除了集合B以外的所有元素构成的集合。

例如，如果A={a，b，c}，B={c，d，e}，那么A-B={a，b}。

习题 2.11．将下列命题符号化。

(1) 4不是奇数。

解：设A(x)：x是奇数。

a：4。

“4不是奇数。

”符号化为：¬A(a)(2) 2是偶数且是质数。

解：设A(x)：x是偶数。

B(x)：x是质数。

a：2。

“2是偶数且是质数。

”符号化为：A(a)∧B(a)(3) 老王是山东人或河北人。

解：设A(x)：x是山东人。

B(x)：x是河北人。

a：老王。

“老王是山东人或河北人。

”符号化为：A(a)∨B(a)(4) 2与3都是偶数。

解：设A(x)：x是偶数。

a：2，b：3。

“2与3都是偶数。

”符号化为：A(a)∧A(b)(5) 5大于3。

解：设G(x,y)：x大于y。

a：5。

b：3。

“5大于3。

”符号化为：G(a,b)(6) 若m是奇数，则2m不是奇数。

解：设A(x)：x是奇数。

a：m。

b：2m。

“若m是奇数，则2m不是奇数。

”符号化为：A(a)→A(b)(7) 直线A平行于直线B当且仅当直线A不相交于直线B。

解：设C(x,y)：直线x平行于直线y。

设D(x,y)：直线x相交于直线y。

a：直线A。

b：直线B。

“直线A平行于直线B当且仅当直线A不相交于直线B。

”符号化为：C(a,b)↔¬D(x,y)(8) 小王既聪明又用功，但身体不好。

解：设A(x)：x聪明。

B(x)：x用功。

C(x)：x身体好。

a：小王。

“小王既聪明又用功，但身体不好。

”符号化为：A(a)∧B(a)∧¬C(a)(9) 秦岭隔开了渭水和汉水。

解：设A(x,y,z)：x隔开了y和z。

a：秦岭。

b：渭水。

c：汉水。

“秦岭隔开了渭水和汉水。

”符号化为：A(a,b,c)(10) 除非小李是东北人，否则她一定怕冷。

解：设A(x)：x是东北人。

B(x)：x怕冷。

a：小李。

“除非小李是东北人，否则她一定怕冷。

”符号化为：B(a)→¬A(a)2．将下列命题符号化。

并讨论它们的真值。

(1) 有些实数是有理数。

解：设R(x)：x是实数。

离散数学: 两个集合的差集离散数学是数学的一个分支，主要研究离散和不连续的数学结构，其中一个重要的概念是集合。

在离散数学中，集合是由一些确定的元素组成的。

集合的运算有交集、并集和差集等。

本文将重点讨论两个集合的差集运算。

什么是集合的差集给定两个集合A和B，集合A减去集合B的结果称为集合A和B的差集。

通常用符号A−B表示。

差集包含了所有属于集合A但不属于集合B的元素。

换句话说，如果将一个集合的所有元素放在一个大集合中，其中有些元素只属于集合A，有些元素只属于集合B，那么集合A减去集合B的结果就是包含了所有属于集合A但不属于集合B的元素的集合。

如何求两个集合的差集求两个集合的差集可以通过以下步骤进行：1.遍历集合A中的每个元素，判断该元素是否也属于集合B。

2.如果元素不属于集合B，则将其添加到差集的结果中。

3.重复上述步骤，直到遍历完集合A中的所有元素。

4.最后，得到的结果就是集合A减去集合B的差集。

举例说明为了更好地理解集合的差集运算，我们来看一个例子。

假设有两个集合A和B，其中：A = {1, 2, 3, 4, 5}B = {3, 4, 5, 6, 7}我们需要求集合A减去集合B的差集。

首先，我们从集合A中选取第一个元素1。

由于1不在集合B中，所以我们将其添加到差集的结果中。

接下来，我们选取元素2，同样地，2不在集合B中，所以将其添加到差集的结果。

然后，我们选取元素3。

由于3在集合B中，所以不将其添加到差集中。

继续遍历集合A中的元素，同理处理元素4和5。

最后，我们得到集合A减去集合B的差集：A -B = {1, 2}性质和注意事项下面是集合差集运算的一些性质和注意事项：•差集运算是一种不交换的运算，即A−B≠B−A。

•差集运算的结果是一个新的集合，该集合的元素个数可能比原集合少。

•如果集合A和B相等，即A=B，那么它们的差集为空集，即$A - B = \empty$。

•如果集合A是集合B的子集，即A⊆B，那么它们的差集是空集，即$A - B = \empty$。