离散数学第三章练习题

第二部分集合、矩阵、关系和函数集合论是处理集合，函数和关系的数学理论。

集合包括最基本的数学概念，例如集合，元素和成员关系。

在大多数现代数学公式中，集合论提供了一种描述数学对象的语言。

集合可用来表示数及其运算，还可表示和处理非数值计算，如数据间关系的描述等。

集合论，逻辑和一阶逻辑构成了数学公理化的基础。

同时，函数和关系是基于集合的映射，它们是满足某些属性的特殊集合。

接下来，我们将在两个单独的章节中介绍它们。

集和矩阵将在第3章中介绍，而关系和函数将在第4章中介绍。

第三章集合和矩阵3.1 集合3.1.1 集合概念集合没有确定的概念。

一般地，我们把研究的对象统称为元素；把一些元素组成的总体叫做集合，也简称集。

通常用大写英文字母表示集合。

例如，N代表是自然数集合，Z代表是整数集合，R代表是实数集合。

用小写英文字母表示集合内元素。

若元素a是集合A的一个元素，则表示为a A∈，读作元素a属于集合A；若元素a不是集合A的一个元素，则表示为a A∉，读作a不属于集合A。

集合分为有限集合和无限集合两种，下面给出定义。

表示集合方法有列举法和描述法两种方式，下面分别介绍。

1. 列举法当集合是有限集合时，可以列出集合的所有元素，用逗号隔开各元素，并用花括号把所有元素括起来。

这种表述方式为列举法。

例如：S1={a, b, c, d, e, f}，S2={a, b, b, c, d, e, f}，S3={ d, e, a, b, c, f}上述三个集合S1、S2和S3是相同集合，尽管有重复元素。

且集合元素之间没有次序关系。

一个集合可以作为另个集合的元素。

例如，S1={a, b,{ c, d, e, f }}集合S1包含元素a, b和{ c, d, e, f }。

因为{ c, d, e, f }是集合S1中的元素，故可记为：{}∈。

,,,c d e f A以上给出的集合实例都是有限集合。

当集合是无限集合时，无法列出集合的所有元素，可先列出一部分元素，若剩余元素与已给出元素存在一定规律，那剩余元素的一般形式很明显可用省略号表示。

若 ( x1) ( x2),则由(*)知不是映射 故 ( x1) ( x2),即是单射
6.
设A={1,2},B={x,y,z},C={u,v}
令 (1) x, (2) y, ( x) u, ( y) ( z) v,
则有 是满射和单射 , 但不是满射, 而不是单射 .
4.
(1)设和是满射, 则对任意的z C, 有y B, 使得 ( y) z. 又有x A, 使得 ( x) y 于是, ( x) ( ( x)) ( y) z 故 是满射.
(2)设和是单射, 则对任意的 x1, x2 A, x1 x2, 有 ( x1) ( x2). 设 ( x1) y1 B. ( x2) y 2 B.于是y1 y 2 从而 ( y1) ( y 2).设 ( y1) z1 C, ( y 2) z 2 C, 于是 ( x1) ( ( x1)) ( y1) z1 ( x 2) ( ( x2)) ( y 2) z 2 因此 ( x1) ( ( x2)).故 是单射
(a) b1 , (a) b2 , 从而b1 b2.矛盾.
故A1 A2 ,即是单射.
若是单射, 则不一定是满射 .例如, 令 A {1,2}, B {x, y}, (1) (2) x,
( x) {1,2}, ( y)
于是,是单射, 但不是满射 .
(3)设和是双射, 则由(1)和(2)知, 是双射.
5.
(1)设 是满射.任取z C, 则存在x A 使得z ( x) ( ( x)) ( y) 即存在y B.使得 ( y) z.故是满射

a t a t i m e an dA l lt h i ng si nt h ei r be i ng ar eg oo df o r so me t hi n 3-5.1 列出所有从X={a,b,c}到Y={s}的关系。

解：Z 1={<a,s>}Z 2={<b,s>} Z 3={<c,s>}Z 4={<a,s>,<b,s>} Z 5={<a,s>,<c,s>} Z 6={<b,s>,<c,s>}Z 7={<a,s>,<b,s>,<c,s>}3-5.2 在一个有n 个元素的集合上，可以有多少种不同的关系。

解 因为在X 中的任何二元关系都是X ×X 的子集，而X ×X=X 2中共有n 2个元素，取0个到n 2个元素，共可组成22n 个子集，即22|)(|n X X =⨯℘。

3-5.3 设A ＝{6：00，6：30,7：30，…, 9：30,10：30}表示在晚上每隔半小时的九个时刻的集合，设B={3,12,15,17}表示本地四个电视频道的集合,设R 1和R 2是从A 到B 的两个二元关系，对于二无关系R 1，R 2，R 1∪R 2，R 1∩R 2，R 1⊕R 2和R 1-R 2可分别得出怎样的解释。

解：A ×B 表示在晚上九个时刻和四个电视频道所组成的电视节目表。

R 1和R 2分别是A ×B 的两个子集，例如R 1表示音乐节目播出的时间表，R 2是戏曲节日的播出时间表，则R 1∪R 2表示音乐或戏曲节目的播出时间表，R 1∩R 2表示音乐和戏曲一起播出的时间表，R 1⊕R 2表示音乐节目表以及戏曲节目表，但不是音乐和戏曲一起的节日表，R 1-R 2表示不是戏曲时间的音乐节目时间麦。

3-5.4 设L 表示关系“小于或等于”，D 表示‘整除”关系,L 和D 刀均定义于解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>}D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L ∩D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>}3-5.5对下列每一式，给出A 上的二元关系，试给出关系图：a){<x,y>|0≤x ∧y ≤3}，这里A={1,2,3,4}；b){<x,y>|2≤x,y ≤7且x 除尽y ,这里A ＝{n|n ∈N ∧n ≤10}c) {<x,y>|0≤x-y<3}，这里A={0,1,2,3,4}；d){<x,y>|x,y 是互质的}，这里A={2,3,4,5,6}解：a) R={<0,0>,<0,1>,<0,2>,<0,3>, <1,0>,<1,1>,<1,2>,<1,3>, <2,0>,<2,1>,<2,2>,<2,3>, <3,0>,<3,1>,<3,2>,<3,3>,} 其关系图b) R={<2,0>,<2,2>,<2,4>,<2,6>,<3,0>,<3,3>,<3,6>, <4,0>,<4,4>, <5,0>,<5,5>,i m e an dA l lt h in gs in th ei r be i ng ar eg oo df o rsa）若R1和R2是自反的，则R1○R2也是自反的；b）若R1和R2是反自反的，则R1○R2也是反自反的；c）若R1和R2是对称的，则R1○R2也是对称的；d）若R1和R2是传递的，则R1○R2也是传递的。

习题3.11.(1) {0,1,2,3,4,5,6,7,8,9}(2) {aa , ab , ba , bb }(3) {-1,1}(4) {11,13,17,19,23,29}(5) {1,2,3, (79)(6) {2}2. 用描述法表示下列集合:(1) 不超过200的自然数的集合;{|N 200}x x x ∈∧≤(2) 被5除余1的正整数的集合;+{|I (N 51)}x x y y x y ∈∧∃∈∧=+(3) 函数y =sin x 的值域;{|R 11}y y y ∈∧-≤≤(4) 72的质因子的集合;{|N |72(N 2|)}x x x y y y x y x ∈∧∧∀∈∧≤<→/(5) 不等式031>-x 的解集; {|R 3}x x x ∈∧>(6) 函数2312+-=x x y 的定义域集. {|R 12}x x x x ∈∧≠∧≠3. 用归纳定义法描述下列集合:(1) 允许有前0的十进制无符号整数的集合;① {0,1,2,3,4,5,6,7,8,9}A ⊆② 如果x A ∈，则{0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9}x x x x x x x x x x x x x x x x x x x x A ⊆(2) 不允许有前0的十进制无符号整数的集合;① {1,2,3,4,5,6,7,8,9}A ⊆② 如果x A ∈，则{0,1,2,3,4,5,6,7,8,9}x x x x x x x x x x A ⊆(3) 不允许有前0的二进制无符号偶数的集合;① 1A ∈② 如果x A ∈，则{0,1}x x A ⊆(4) 5的正整数倍的集合.① 5A ∈② 如果x A ∈，则5x A +∈4. 判断下列命题中,哪些是真的,哪些是假的(A 是任意集合):(1) ;A ∈∅(2) ;A ⊆∅ (3) };{A A ∈ (4) ;A A ⊆ (5) ;A A ∈ (6) };{A A = (7) }.{∅=∅答：(2),(3),(4)为真，(1),(5),(6),(7)为假。

11
河南工业大学离散数学课程组
四.证明R的反对称性 方法1 用定义1证： 任取 x,y∈A,设<x,y>∈R, <y,x>∈R.证出 x=y。 方法2 用定义2证： 任取 x,y∈A,x≠y, 设<x,y>∈R,证出<y,x>R. 方法3 用定理证：证出 R∩Rc IA . (见教材P118) 五.证明R的传递性： 方法1 用传递定义证： 任取 x,y,z∈A,设<x,y>∈R,<y,z>∈R, 证出 <x,z>∈R. 方法2 用传递闭包证：证出 t(R)=R, 即 R∪R2∪R3∪... =R. 方法3 用定理证：证出R R R ( P119 (2) a) ) 下面证明第113页 (4)
河南工业大学离散数学课程组
离散数学
河南工业大学 第三章
信息科学与工程学院
集合与关系
1
河南工业大学离散数学课程组 3-2（9）在什么条件下，下面命题为真？
a) (A-B)∪(A-C)=A (A-B)∪(A-C)= (A∩~B)∪(A∩~C)=A∩(~B∪~C) = A∩~(B∩C)=A-(B∩C)=A 所以满足此式的充要条件是： A∩(B∩C)= Φ或A ~ (B∩C) b) (A-B)∪(A-C)=Φ (A-B)∪(A-C)= A∩~(B∩C)= A-(B∩C)=Φ 所以满足此式的充要条件是：A B∩C c) (A-B)∩(A-C)=Φ (A-B)∩(A-C)= (A∩~B)∩(A∩~C)=A∩(~B∩~C) = A∩~(B∪C)=A-(B∪C)=Φ 所以满足此式的充要条件是: A B∪C d) (A-B)(A-C)=Φ 因为 当且仅当A=B ，才有AB=Φ 所以满足此式的充要条件是: A-B=A-C

但对于等式（4），左边经变形后得
( A B C) ( A B) ((A B) ( A B)) (C ( A B))
= (C ( A B)) C ( A B). 易 见 ， C (A B) C, 但 不 一 定 有 C (A B) C.如 令 A B C {1}.时，等式（4）不为真。类假地，等式（5）的左 边经化简后得 (A C) B ，而 (A C) B 不一定恒等于 A-C。 3．17 （1）不为真。（2），（3）和（4）都为真。对于题 （1）举反例如下：令 A {1}, A {1}, B {1,4},C {2}, D {2,3}, 则 A B 且 C B ，但 A C B D ，
这是 S T 的充公必要条件,从而结论为真. 对 于 假 命 题 都 可 以 找 到 反 例 , 如 题 (2) 中 令 S {1,2},T z{1}, M {2}即可;而对于题(5),只要 S 即可. 3.9 (2),(3)和(4)为真,其余为假. 3.10 (1) A {0,1,2}. (2) A {1,2,3,4,5} (3) A {1} (4) A { 0,0 , 0,1 1,0 , 0,2 , 1,1 , 2,0 , 0,3 ,
A B .
（4）易见，当 A=B 成立时，必有 A-B=B-A。反之，由 A-B=B-A 得
( A B) B (B A) B
化简后得 B A ，即 B A，同理，可证出 A B ，从而 得到 A=B。
3．18 由| P(B) | 64 可知|B|=6。又由| P(A B) | 256 知| A B | 8 ， 代入包含排斥原理得
{,{1},{2},{1,2}}}.
(4) P( A) {,{{1}},{{1,2}},{{1}},{{1,2}} (5) P( A) {,{1},{1},{2},{1,1},{1,2}{1,2}{1,1,2}. 分析 在做集合运算前先要化简集合,然后再根据题目 要求进行计算.这里的化简指的是元素,谓词表示和集合公 式三种化简. 元素的化简——相同的元素只保留一个，去掉所有冗余 的元素。 谓词表示的化简——去掉冗余的谓词，这在前边的题解 中已经用到。 集合公工的化简——利用简单的集合公式代替相等的 复杂公式。这种化简常涉及到集合间包含或相等关系的判别。 例如，题（4）中的 A {{1,1},{2,1},{1,2,1}}化简后得 A {{1},{1,2}}， 而题（5）中的 A {x | x R x3 2x2 x 2 0} 化 简为 A {1,1,2}。 3．15

第三章习题一解答一、求下列集合的幂集1、{杨,李,石}解：P({杨,李,石}) ={Φ, {石},{李,石},{杨},{杨,石},{杨,李},{杨,李,石}}2、{{1,2},{2,1,1},{2,1,1,2}}解：原集合={{1,2},{2,1},{2,1}}={{1,2}}，只含一个元素，故其幂集只有2 个元素： P={Φ,{1,2}}二、利用包含排斥原理，求解以下各题。

1、对60 人调查，25 读《每周新闻》，26 读《时代》，26 人读《财富》，9 人读《每周新闻》和《财富》，11 读《每周新闻》和《时代》，8 人读《时代》与《财富》，还有 8 人什么都不读，请计算：(1) 阅读全部三种杂志的人数。

(2) 分别求只阅读每周新闻、时代、财富杂志的人数。

解：记A={《每周新闻》的读者}，B={《时代》的读者}，C={《财富》的读者}。

由于8 人什么都不读，故只有 52 人读杂志，即 |A ∪B ∪C|=52。

已知|A|=25，|B|=26，|C|=26|A ∩C|=9，|A ∩B|=11，|B ∩C|=8（1）由包含排斥原理可知|A ∪B ∪C|=|A|+|B|+|C|-|A ∩C|-|A ∩B|-|B ∩C|+| A ∩B ∩C|，故 52=25+26+26-9-11-8+| A ∩B ∩C|，即有| A ∩B ∩C|=3，所以同时读三种杂志的人为3 人。

（2）注意到 |S ∩T| = |S|-|S ∩T|，故只读《每周新闻》的人数为：|)()(||||)(||||)(|||C A B A A C B A A C B A C B A ⋂⋃⋂-=⋃⋂-=⋃⋂=⋂⋂ =|A|-|A ∩B|-|A ∩C|+| A ∩B ∩C|=25-9-11+3=8；只读《时代》人数为：=⋂⋂||C A B |B|-|B ∩A|-|B ∩C|+| A ∩B ∩C|=26-11-8+3=10 ； 只读《财富》的人为：=⋂⋂||B A C |C|-|C ∩A|-|C ∩B|+| A ∩B ∩C|=26-9-8+3=12。

《离散数学》第三部分----代数结构一、选择或填空1、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点<A,*>中，单位元是( )，零元是( )。

答：2，62、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点<A,*>中，单位元是( )，零元是( )；答：9，33、设〈G,*〉是一个群，则(1) 若a,b,x∈G，a*x=b，则x=( )；(2) 若a,b,x∈G，a*x=a*b，则x=( )。

答：（1）a*-1 b （2）b4、设a是12阶群的生成元，则a2是( )阶元素，a3是( )阶元素。

答：6,45、代数系统<G,*>是一个群，则G的等幂元是( )。

答：单位元6、设a是10阶群的生成元，则a4是( )阶元素，a3是( )阶元素。

答：5，107、群<G,*>的等幂元是( )，有( )个。

答：单位元，18、素数阶群一定是( )群, 它的生成元是( )。

答：循环群，任一非单位元9、设〈G,*〉是一个群，a,b,c∈G，则(1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。

答：（1）b1-*a(2) b10、<H,,*>是<G,,*>的子群的充分必要条件是( )。

答：<H,,*>是群或∀ a，b ∈G，a*b∈H，a-1∈H 或∀ a,b ∈G，a*b-1∈H 11、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。

答：1，单位元，012、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。

答：k13、在自然数集N上，下列哪种运算是可结合的？（）(1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 答：(2)14、任意一个具有2个或以上元的半群，它（）。

第三章习题一解答一、求下列集合的幂集1、{杨,李,石}解：P({杨,李,石}) ={Φ, {石},{李,石},{杨},{杨,石},{杨,李},{杨,李,石}}2、{{1,2},{2,1,1},{2,1,1,2}}解：原集合={{1,2},{2,1},{2,1}}={{1,2}}，只含一个元素，故其幂集只有2 个元素： P={Φ,{1,2}}二、利用包含排斥原理，求解以下各题。

1、对60 人调查，25 读《每周新闻》，26 读《时代》，26 人读《财富》，9 人读《每周新闻》和《财富》，11 读《每周新闻》和《时代》，8 人读《时代》与《财富》，还有 8 人什么都不读，请计算：(1) 阅读全部三种杂志的人数。

(2) 分别求只阅读每周新闻、时代、财富杂志的人数。

解：记A={《每周新闻》的读者}，B={《时代》的读者}，C={《财富》的读者}。

由于8 人什么都不读，故只有 52 人读杂志，即 |A ∪B ∪C|=52。

已知|A|=25，|B|=26，|C|=26|A ∩C|=9，|A ∩B|=11，|B ∩C|=8（1）由包含排斥原理可知|A ∪B ∪C|=|A|+|B|+|C|-|A ∩C|-|A ∩B|-|B ∩C|+| A ∩B ∩C|，故 52=25+26+26-9-11-8+| A ∩B ∩C|，即有| A ∩B ∩C|=3，所以同时读三种杂志的人为3 人。

（2）注意到 |S ∩T| = |S|-|S ∩T|，故只读《每周新闻》的人数为：|)()(||||)(||||)(|||C A B A A C B A A C B A C B A ⋂⋃⋂-=⋃⋂-=⋃⋂=⋂⋂ =|A|-|A ∩B|-|A ∩C|+| A ∩B ∩C|=25-9-11+3=8；只读《时代》人数为：=⋂⋂||C A B |B|-|B ∩A|-|B ∩C|+| A ∩B ∩C|=26-11-8+3=10 ； 只读《财富》的人为：=⋂⋂||B A C |C|-|C ∩A|-|C ∩B|+| A ∩B ∩C|=26-9-8+3=12。

离散数学第三章习题详细答案3.9解：符号化：p：a是奇数.q：a是偶数.r：a能被2整除前提：(p→¬r),(q→r)结论：(q→¬p)证明：方法2（等值演算法）(p→¬r)∧(q→r)→(q→¬p)⇔(¬p∨¬r)∧(¬q∨r)→(¬q∨¬p)⇔(p∧r)∨(q∧¬r)∨¬q∨¬p⇔((p∧r)∨¬p)∨((q∧¬r)∨¬q)⇔(r∨¬p)∨(¬r∨¬q)⇔¬p∨(r∨¬r)∨¬q⇔1即为成佛该式为重言式，则原结论恰当。

方法3（主析取范式法）(p→¬r)∧(q→r)→(q→¬p)⇔(¬p∨¬r)∧(¬q∨r)→(¬q∨¬p)⇔(p∧r)∨(q∧¬r)∨¬q∨¬p⇔m0+m1+m2+m3+m4+m5+m6+m7所述该式为重言式，则结论推理小说恰当。

3.10.解：符号化：p：a就是负数.q：b就是负数.r：a、b之四维负前提：r→(p∧¬q)∨(¬p∧q)结论：¬r→(¬p∧¬q)方法1（真值法）证明：方法2（主析取范式法）证明：(r→(p∧¬q)∨(¬p∧q))→(¬r→(¬p∧¬q))⇔¬(¬r∨(p∧¬q)∨(¬p∧q))∨(r∨(¬p∧¬q))⇔r∨(¬p∧¬q)⇔m0+m2+m4+m6+m7只不含5个极小项，课件完整不是重言式，因此推理小说不恰当3.11.填充下面推理证明中没有写出的推理规则。

解：③：①②谓词三段论⑤：③④谓词三段论⑦：⑤⑥假言推理小说3.12.填充下面推理证明中没有写出的推理规则。

天津理工大学中环信息学院《离散数学》第三、四章检测题请将填空题答案填入下面相应位置1. ；2. ；3. ；4. ；5. , ；6. , ；7. , , , , , ；8. ；9. , , , , 。

一、填空题（每空2分，共40分）1．若集合A 的基数为n ，则()A P A ⨯= 。

2n n ⨯２．设A =｛｛Φ，｛Φ｝｝｝，则A ×(())P P Φ= 。

其中()P A 表示集合A 的幂集．{,{}},{,{}{,}},{}ΦΦΦΦΦΦ3．设{{,{,}}}A a b c =，则()P A = 。

其中()P A 表示集合A 的幂集．,{{,{}{},}}a b c Φ4．设A ={1，2，3}，A 上的二元关系R ={1,1,1,2,1,3,3,3}〈〉〈〉〈〉〈〉，则关系R 具有 性。

反对称，传递。

5．设R 是集合A 上的二元关系，则()S R = ，()t R = 。

1R R- ；1i i R ∞=6．设R 是集合A 上的具有自反性、对称性、反对称性和传递性的二元关系，则R = ，R 的关系矩阵是 。

（A I ，100010001⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭或单位矩阵） 7． 在偏序集,A ≤中，其中A ={1,2,3,4,6,8,12,14}，≤是A 中的整除关系，则集合B ={2,3,4,6}的极大元是 4,6 ，极小元是 2,3 ，最大元是 无 ，最小元是 无 ，上确界是 12 ，下确界是 1 。

8．设{,{}},{0,1A B φφ==, 所有从A 到B 的双射函数是1f ={,0,{},1}φφ, 2f ={,1,{},0}φφ。

9．设f 是A 到B 的函数，如果对2121,,x x A x x ≠∈∀，都有)()(21x f x f ≠，则称f 为 ，如果B f ran =)(，则称f 为 ；若f ，则称f 为双射。

当f 为双射时，1-f是B 到A 的函数，且1-ff = ，f f1-= 。

A B
A
C
习题三
14.
下面证明有效吗？ (x)[x A B] (x)[x A x B] (x)[x A x B] (x)[x A B] (x)[x A B] 答: 原证明无效. 因为(x)[x A x B] (x)[x A B]. 实际上 (x)[x A x B] (x)[~(x A x B)] (x)[x A B] (x)[x A B]
X 2 AB
等号成立的条件: A B或B A (因为若A和B没有子集关系, 必有a A– B和 b B– A， 使{a, b} 2 A B ，但{a, b} 2A B = 2 A B. 证明：X 2A 2B X 2A X 2B XAXB XAB X2A
习题三 4. 仔细区别集合中的关系符和，并 判断下列各蕴含关系的真假：
(1)Y, (2)~(5)N, (6)Y
习题三
9.证明下列各式：
(3) (A-B)-C = A –(B C) = (A –C)-B 证明: (A-B)-C = (A B) C = A B C = A –(B C) =(A C )B)= (A –C)-B (5) A (B C) = (A B ) (A C) 证明: A (B C) = A ((B-C) (C-B)) = (A B C) (A C B) = (A B C) (A B A) (A C B) (A C A) = (A B A C) (A C A B ) = (A B -A C) (A C - A B ) = (A B ) (A C)
习题三 集
16. 求A={, a, {b}}的幂
解: A={, a, {b}} 2A = {, {} , {a} , {{b}} , {,a} , {,b} , {a, {b}} , {, a, {b}}}

离散数学第3章习题答案离散数学是计算机科学和数学领域中的一门重要课程，它涉及到了许多有趣的概念和方法。

在离散数学的学习过程中，习题是非常重要的一部分，通过解答习题可以巩固所学的知识，并提升自己的思维能力和解决问题的能力。

本文将对离散数学第3章的一些习题进行解答，帮助读者更好地理解和掌握相关的知识。

1. 习题3.1题目：证明或给出反例：若A、B、C是集合，且A∪B=A∪C，则B=C。

解答：要证明这个命题，我们可以采用反证法。

假设存在集合A、B、C，满足A∪B=A∪C，但是B≠C。

由于A∪B=A∪C，所以对于任意的元素x，如果x属于B，那么x也属于A∪C，反之亦然。

由于B≠C，所以存在一个元素y，y属于B但不属于C，或者y属于C但不属于B。

不失一般性，我们假设y属于B但不属于C。

由于y属于A∪B，所以y属于A∪C。

但是由于y不属于C，所以y必须属于A。

这就意味着y属于A∩B。

但是由于y属于B，所以y属于B∩A。

由于A∩B=A∩C，所以y属于C∩A。

但是由于y不属于C，所以y属于C∩A必然不成立。

因此，假设B≠C是错误的，即B=C。

2. 习题3.2题目：证明或给出反例：若A、B、C是集合，且A∩B=A∩C，则B=C。

解答：要证明这个命题，我们同样可以采用反证法。

假设存在集合A、B、C，满足A∩B=A∩C，但是B≠C。

由于A∩B=A∩C，所以对于任意的元素x，如果x属于B，那么x也属于A∩C，反之亦然。

由于B≠C，所以存在一个元素y，y属于B但不属于C，或者y属于C但不属于B。

不失一般性，我们假设y属于B但不属于C。

由于y属于A∩B，所以y属于A∩C。

但是由于y不属于C，所以y不属于C∩A。

这就意味着y不属于A∩C。

但是由于y属于A∩B，所以y 属于A∩C必然成立。

因此，假设B≠C是错误的，即B=C。

3. 习题3.3题目：证明或给出反例：若A、B、C是集合，且A∪B=A∩C，则B=C。

解答：要证明这个命题，我们同样可以采用反证法。

离散数学第三章第一篇：离散数学第三章第三章部分课后习题参考答案14.在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r 结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r 结论：p∧q 证明：（2）①⌝(q∧r)前提引入②⌝q∨⌝r ①置换③q→⌝r ②蕴含等值式④r 前提引入⑤⌝q ③④拒取式⑥p→q 前提引入⑦￢p ⑤⑥拒取式证明（4）：①t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q)⑤ 置换⑦（q→t）⑥化简⑧q ②⑥ 假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理(11)p∧q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q 结论：s→r 证明①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r)前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s 结论：⌝p 证明：①p 结论的否定引入②p→﹁q 前提引入③﹁q ①②假言推理④￢r∨q 前提引入⑤￢r ④化简律⑥r∧￢s 前提引入⑦r ⑥化简律⑧r∧﹁r ⑤⑦ 合取由于最后一步r∧﹁r 是矛盾式,所以推理正确.第二篇：离散数学离散数学课件作业第一部分集合论第一章集合的基本概念和运算1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是[ B ]A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} ⊆ A。

1-2 A,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 设集合 A ={3，4}，B = {4，3} ∩ Ø，C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，Ø，3，3}，试问哪两个集合之间可用等号表示？答：A = E；B = C；D = F1-5 用列元法表示下列集合（1）A = { x│x ∈N 且x2 ≤ 9 }（2）A = { x│x ∈N 且 3－x 〈 3 }答：（1）A = { 0，1，2，3 }；（2）A = { 1，2，3，4，……} = Z+；第二章二元关系2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：R = {〈x，y〉x，y ∈X 且x≤ y }求：(1)domR =?;(2)ranR =?;(3)R 的性质。

自考2324离散数学课后答案3.1 习题参考答案1、写出下列集合的的表示式。

a)所有一元一次方程的解组成的集合。

A={x|x是所有一元一次方程的解组成的集合}晓津答案：A={x| ax+b=0∧a∈R∧b∈R}b) x2-1 在实数域中的因式集。

B={1,(x-1),(x+1)|x∈R}c)直角坐标系中，单位圆内（不包括单位圆周）的点集。

C={x,y| x2+y2<1 }晓津答案：C={a(x,y)|a为直角坐标系中一点且 x2+y2<1 }d)极坐标中，单位圆外（不包括单位圆周）的点集。

D={r,θ| r>1,0<=θ<=360}晓津答案：D={a(r,θ)|a为极坐标系中一点且 r>1,0<=θ<=2π } e)能被5整除的整数集E={ x| x mod 5=0}2、判定下列各题的正确与错误。

a) {x}{x};正确b) {x}∈{x};正确晓津观点:本命题错误。

理由：{x}作为一个元素是一个集合，而右边集合中的元素并不是集合。

c) {x}∈{x,{x}};正确d) {x}{x,{x}};正确----------------------------------------------------------------3、设 A={1,2,4},B={1,3,{2}},指出下列各式是否成立。

a) {2}∈A; b) {2}∈B c) {2}Ad) {2}B; e) ∈A f) A解：jhju、晓津和wwbnb 的答案经过综合补充，本题的正确答案是：b、c、d、f成立，a，d、e不成立。

理由：a式中，{2}是一个集合，而在A中并无这样的元素。

因此不能说{2}属于A，当然如果说2∈A则是正确的。

对于e式也应作如此理解，空集是一个集合，在A中并无这个集合元素,如f 式则是正确的。

空集包含于任何集合中，但空集不一定属于任一集合。

----------------------------------------------------------------4、设A= {} ， B=(A),问下列各题是否正确。

30表示在晚上每隔半小时的九个时刻的集合设b3121517表示本地四个电视频道的集合设r的两个二元关系对于二无关系r表示在晚上九个时刻和四个电视频道所组成的电视节目表
证明：设A上定义的二元关系R为：
＜＜x,y＞,＜u,v＞＞∈R=
1对任意＜x,y＞∈A，因为=，所以
＜＜x,y＞,＜x,y＞＞∈R
即R是自反的。
证明：若Π细分Π。由假设aRb，则在Π中有某个块S，使得a,b∈S，因Π细分Π，故在Π中，必有某个块S，使SS，即a,b∈S，于是有aRb,即RR。
反之，若RR，令S为H的一个分块，且a∈S，则S=[a]R={x|xRa}
但对每一个x，若xRa，因RR，故xRa，因此{x|xRa}{x|xRa}即[a]R[a]R
所以R在A上是自反的，即R是A上的等价关系。
3-10.7设R1和R2是非空集合A上的等价关系，试确定下述各式，哪些是A上的等价关系，对不是的式子，提供反例证明。
a）（A×A）-R1；
b）R1-R2；
c）R12；
d) r（R1-R2）（即R1-R2的自反闭包）。
解a）（A×A）-R1不是A上等价关系。例如：
<x,y>∈Rkx-y=dk (对某个d∈I)
a)假设I/Rk细分I/Rj，则RkRj
因此<k,0>∈Rk<k,0>∈Rj
故k-0=1k=cj (对某个c∈I)
于是k是j的整数倍。
b)若对于某个r∈I，有k=rj则：
<x,y>∈Rkx-y=ck (对某个c∈I)
x-y=crj (对某个c,r∈I)
<x,y>∈Rj
A={a,b}，R1={＜a,a＞，＜b,b＞}
A×A={＜a,a＞，＜a,b＞，＜b,a＞，＜b,b＞}

6．Let be an undirected graph， ，then is a（）．
(A)．complete graph；(B)．null graph；(C)．Simple graph；(D)．multigraph．
7．Which of the following graphs is not aEuleriangraph(欧拉图)?（）
2．Let be aBoolean algebra，then there aredeferentfunctions from ；the identity for with respect to the operation “ ” is，the zero element for with respect to the operation “ ” is，the identity for with respect to the operation “ ” is，the zero element for with respect to the operation “ ” is．
(A)． ；(B)． ／ ，where “／” is the relation of exact division；
(C)． ；(D)． ；where ， is the power set of ．
6．Which of the following Hasse diagrams is not a distributive lattice?（）．
5．Which of the following algebraic systems is not a group（）．
(A)． ＝{1,10}， is defined by m n=mn (mod 11)；(B)． ={1,3,4,5,9}, is the same as A；