离散数学第九章代数系统
离散数学第10章
第十章 3. 在R 中定义二元运算，使得,a b R ?∈有 *a b a b ab =++ 证明
(2) a) 由运算表可得：运算封闭，且F 不是空集，所以,F <> 为一个代数系统。 b) 函数复合运算满足结合律。 c) 单位元为f1 d) f1-1=f1, f2-1=f2, f3-1=f3, f4-1=f5, f5-1=f4, f6-1 =f6, 所以,F <> 为群
离散数学--第九章--作业答案
习题9 1-7 1、 答、运算表如下表所示： 2、 答、（1），；，；，；，（2）、运算标如下表： 3、 答、（1）可以， （2）不可以 4、 答、（1）封闭 （2）不封闭
（3）加法、乘法都封闭 （4）加法不封闭，乘法封闭 （5）不封闭 （6）加法、乘法都封闭 （7）封闭 （8）加法不封闭，乘法封闭 （9）加法不封闭，乘法封闭 （10）加法不封闭，乘法封闭 5、 答、（1）没有交换律、结合律，对于一个运算不能考虑分配率 （3）加法满足交换律、结合律，乘法满足结合律，乘法对加法满足分配率 （4）乘法满足结合律 （6）加法和乘法都满足交换律、结合律，乘法对加法满足分配率 （7）满足结合律 （8）乘法满足交换律、结合律 （9）乘法满足交换律、结合律 （10）乘法满足交换律、结合律 6、 答、（1）没有单位元、零元，没有可逆元素 （3）n阶全0矩阵是加法单位元，也是乘法的零元；n阶单位矩阵是乘法单位元；加法没有零元。任意n阶矩阵M对于加法都是可逆元素，其逆元为-M；只有n阶可你矩阵（行列式不为0）对乘法是可逆元素，其逆元为
（4）乘法单位元为n阶单位矩阵，没有零元。每个矩阵M都是逆元 （6）加法单位元0，没有零元，每个元素x都可逆，其逆元是它的相反数-x，当n=1时，乘法有单位元1，只有两个可逆元素：，。当＞时乘法没有单位元和可逆元素。 （7）没有单位元和零元，也没有可逆元素 （8）乘法单位元为1，只有1是可逆元素， （9）乘法单位元为1，只有1是可逆元素，，乘法零元是0 （10）乘法没有单位元、零元以及可逆元素 7、 答、（1）4*6=4,7*3=3 （2）满足交换律、结合律、幂等律 （3）没有单位元，1是零元，没有可逆元素
离散数学重点笔记
第一章，0命题逻辑 素数 = 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。 若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A （2）等幂律 A∧A?A ； A∨A?A （3）交换律 A∧B?B∧A ； A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C）（6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A （8）零一律 A∨1?1 ； A∧0?0 （9）同一律 A∨0?A ； A∧1?A （10）排中律 A∨?A?1 （11）矛盾律 A∧?A?0
（12）蕴涵等值式 A→B??A∨B （13）假言易位 A→B??B→?A （14）等价等值式 A?B?（A→B）∧（B→A） （15）等价否定等值式 A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A (p∧┐q)∨(┐q∧┐r)∨p (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】 ∧成真小写 【例】 (p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q)
离散数学 代数系统
第三部分：代数系统 1.在代数系统,S *中，若一个元素的逆元是唯一的，其运算*必定可结合。( ) 2.每一个有限整环一定是域，反之也对。( ) 3.任何循环群必定是阿贝尔群，反之亦真。( ) 4.设(),A ∧∨是布尔代数，则(),A ∧∨一定为有补分配格。( ) 5.设Q 为有理数集，Q 上运算*定义为max(,)a b a b *=，则 ,Q * 是半群。( ) 6.阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。( ) 7.群中可以有零元（对阶数大于一的群）。( ) 8.循环群一定是阿贝尔群。( ) 9.每一个链都是分配格。( ) 1. 对自然数集合N ，哪种运算不是可结合的，运算定义为任,a b N ∈ ( ) A. min(,)a b a b *= B. 2a b a b *=+ C. 3a b a b *=+- D. a b a b *=+ (mod 3) 2. 任意具有多个等幂元的半群，它 ( ) A. 不能构成群 B. 不一定能构成群 C. 不能构成交换群 D. 能构成交换群 3. 循环群33,Z +的生成元为[][]1,2，它们的周期为 ( ) A. 5 B. 6 C. 3 D. 9 4. 设
离散数学代数系统练习
一、填空 1.下列集合中， 对普通加法和普通乘法都封闭。 （ ） （A ）{}1,0 （B ）{}2,1 （C ）{}N n n ∈2 （D ）{} N n n ∈2 2、在自然数集N 上，下面哪种运算是可结合的？ （ ） （A ）b a - （B ）),max(b a （C ）b a 2+ （D ）b a - 3、有理数集Q 关于下列哪个运算能构成代数系统？ （ ） （A ）b a b a =* （B ）()1ln 22++=*b a b a （C ）()b a b a +=*sin （D ）ab b a b a -+=* 4、下列运算中，哪种运算关于整数集I 不能构成半群？ （ ） （A ）()b a b a ,max =* （B ）b b a =* （C ）ab b a 2=* （D ）b a b a -=* 5．设代数系统?A ，·?，则（ ）成立. A ．如果?A ，·?是群，则?A ，·?是阿贝尔群 B ．如果?A ，·?是阿贝尔群，则?A ，·?是循环群 C ．如果?A ，·?是循环群，则?A ，·?是阿贝尔群 D ．如果?A ，·?是阿贝尔群，则?A ，·?必不是循环群 6．设?L ,∧∨,?是格，?L ，≤?是由这个格诱导的偏序集，则（ ）不成立. A ．对任意a L b a ,,∈≤b b a b =∨? B ．∧∨对是可分配 C ．∧∨,都满足幂等律 D ．?L,≤?的每对元素都有最小上界与最大下界 7．在下列四个哈斯图表示的偏序集中（ ）是格.
8. 已知偏序集的哈斯图，如图所示，是格的为( ) 9. 6阶有限群的任何子群一定不是（）。 (A) 2阶(B) 3 阶(C) 4 阶(D) 6 阶 10. 下列哪个偏序集构成有界格（） (1) （N,≤）(2) （Z,≥） (3) （{2,3,4,6,12},|（整除关系））(4) (P(A),?) 11. 下面代数系统中（G、＊）中（）不是群 A、G为整数集合＊为加法 B、G为偶数集合＊为加法 C、G为有理数集合＊为加法 D、G为有理数集合＊为乘法 12. 设
第九章环与域 91 环
第九章环与域 ?9.1 环：两个二元运算的代数结构 ?1.环的概念 ?定义9.1：
9.2 整环和域 ?定义9.5：R是环，令，若为阿 贝尔群，则称
内蒙古大学离散习题代数系统部分答案
《离散数学》代数系统 1.以下集合和运算是否构成代数系统？如果构成，说明该系统是否满足结合律、交换律？求出该运算的幺元、零元和所有 可逆元素的逆元. 1)P(B)关于对称差运算⊕，其中P(B)为幂集. 构成代数系统；满足结合律、交换律；幺元φ；无零元；逆元为自身。 2)A={a,b,c}，*运算如下表所示：构成代数系统；满足结合律、交换律；无幺元；无逆元；零元b. 2.设集合A={a,b}，那么（1）在A上可以定义多少不同的二元运算？（2）在A上可以定义多少不同的具有交换律的二元 运算？24个不同的二元运算；23个不同的具有交换律的二元运算 3.设A={1,2},B是A上的等价关系的集合. 1)列出B的元素. 2元集合上只有2种划分，因此只有2个等价关系，即B={I A，E A} 2)给出代数系统V=
离散数学第10章习题答案
第10章习题答案 1.解 (1)设G 有m 条边，由握手定理得2m ＝∑∈V v v d )(＝2＋2＋3＋3＋4＝14，所以G 的边数7条。 (2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得∑∈V v v d )(＝2m ＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有， 其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G 中至多有9个结点。 2.证明 设1v 、2v 、…、n v 表示任给的n 个人，以1v 、2v 、…、n v 为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G 。由握手定理知 ∑=n k k v d 1 )(＝3n 必为偶数，从而n 必为偶数。 3. 解 由于非负整数列d ＝(d 1，d 2，…，d n )是可图化的当且仅当∑=n i i d 1 ≡0(mod 2)，所以(1)、(2)、 (3)、(5)能构成无向图的度数列。 (1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。 (5)是不可简单图化的。若不然，存在无向图G 以为1，3，3，3度数列，不妨设G 中结点为1v 、2v 、 3v 、4v ，且d(1v )＝1，d(2v )＝d(3v )＝d(4v )＝3。而1v 只能与2v 、3v 、4v 之一相邻，设1v 与2v 相邻，于 是d(3v )＝d(4v )＝3不成立，矛盾。 4.证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。 5. 解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)~(16)为其生成子图。 6. 解 (1)G 的所有子图如图所示。 (1)(3)(5) (6) (9)(10) (13) (14)
离散数学答案 第八章 代数系统
第八章 代数系统 习题8.1 1．解 ⑴是，⑵不是，⑶是，⑷不是。 2．解 若﹡对 是可分配的，则有任意a,b,c ∈* I ,均有 a ﹡( b 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 ≠a b+c 故﹡对 是不可分配的。 3．解 ⑴对于任意A ∈P(S), 因为A ?S ，所以，A ?S =S ，因此，S 是关于?运算的零元； ⑵对于任意A ∈P(S), 因为A ?S ，所以，A ?S = A ，因此，S 是关于?运算的零元单。 4．解 ⑴①因为x*y=xy-2x-2y+6，则y*x=yx-2y-2x+6= x*y ，满足交换律； ②任意x,y,z ∈R 有 x*(y*z)=x*(yz-2y-2 z +6)=x(yz-2y-2 z +6)-2x-2(yz-2y-2z+6)+6 =xyz-2xy-2xz+6x-2x -2yz+4y+4z-12+6= xyz-2xy-2xz-2yz+4x+4y+4z-6. (x*y)*z=(xy-2x-2y+6) *z =(xy-2x-2y+6)z-2(xy-2x-2y+6)-2z+6 =xyz-2xz-2yz+6z-2xy+4x+4y-2z-6=x*(y*z). 故满足结合律。 (2) ①设任意a ∈R,存在e ∈R,要e*a= ea-2e-2a+6=a ，由于a 的任意性则e=3。 因此e=3是其单位元; ②设任意b ∈R, z ∈R ，要有z*b= zb-2 z-2b+6= z ，由于b 的任意性则z=2，因此 z=2是其零元。 （3）因为*是满足交换律，对于x ∈R ，要存在1 -x ∈R ，须有x*1 -x = x 1 -x -2x-21 -x +6= e=3, 当x ≠2 时，2 321 --= -x x x 。即对于任意的x ，当x ≠2时x 都是可逆的，且2 321 --= -x x x 。 5．解 f 1,f 2,f 3都满足交换律，f 4满足等幂率，f 2有单位元a ，f 1有零元a ，f 3有零元b 。 习题8.2 1．解 构成代数系统的运算有（2），（3），（4）。 2．解 >⊕<>⊕<>⊕<444},3,2,1,0{,},2,0{,},0{ 1f b a a a a a b a 2f b a b a a b b a 3f b a a b a a b a 4f b a b a b a b a 表8-2
华东师范大学离散数学章炯民课后习题第10章答案
P179 1. 给出下列序列的一个递推关系： （4）{n 2+3n} （6）{1+(-1)n } 解： (4) a n =a n-1+2n+2(n>0)，a 0=0 (6) a n =a n-1+2(-1)n (n>0)，a 0=2 或110 220n n n a a a --=?=?=?，a 0=2 3. 设含连续三个0的n 位二进制串的数目是s n ，请给出{s n }的递推关系和初始条件。 解：a n = a n-1 +a n-2 +a n-3+2n-3 (n≥3)，a 0=0，a 1=0，a 2=0 4. 设{1,2,…,n}的错排列数是D n ，请给出{D n }的递推关系和初始条件。 解：D n =(n-1)(D n-1+D n-2)，D 1=0，D 2=1 10（2）求初值问题的通项公式：a n =10a n-1-25a n-2；a 0=-7，a 1=15。 解： 特征方程：r 2-10r+25=0，特征根：r 2=r 1=5 通解：a n =(α+βn)5n 由a 0=α50=α=-7和a 1= (-7+β)51 =15解得：α=-7，β=10 初值问题的解：a n =(-7+10n)2n *12（2）. 求递推关系的一个特解： a n ＝8a n-2-16a n-4+n 24n 。 解： 特征方程：x 4=8x 2-16，特征根：x 1=-2，x 2=2 一个特解：T n =n 0(a+bn+cn 2) 4n = (a+bn+cn 2)4n 代入递推关系：(a+bn+cn 2)4n =8(a+b(n-2)+c(n-2)2)4n-2-16(a+b(n-4)+c(n-4)2)4n-4 即9cn 2+(9b+8c)n+(8a+4b-16+c)=0 9c=0 9b+8c=0 8a+4b-16+c=0 解得：c=0,b=0,a=2 特解：2n 24n 13（2）. 写出序列{1,0,1,0,1,0,…}的生成函数。 解：1+x 2+x 4+x 6+…=2i 2i 01x 1x ∞ ==-∑
离散数学结构 第6章 集合代数
第六章集合代数 1. 集合，相等，（真）包含，子集，空集，全集，幂集 2. 交，并，（相对和绝对）补，对称差，广义交，广义并 3. 文氏图，有穷集计数问题 4. 集合恒等式（等幂律，交换律，结合律，分配律，德·摩根律，吸收律，零律，同一 律，排中律，矛盾律，余补律，双重否定律，补交转换律等） 学习要求 1. 熟练掌握集合的子集、相等、空集、全集、幂集等概念及其符号化表示 2. 熟练掌握集合的交、并、（相对和绝对）补、对称差、广义交、广义并的定义及其性 质 3. 掌握集合的文氏图的画法及利用文氏图解决有限集的计数问题的方法 4. 牢记基本的集合恒等式（等幂律、交换律、结合律、分配律、德·摩根律、收律、零 律、同一律、排中律、矛盾律、余补律、双重否定律、补交转换律） 5. 准确地用逻辑演算或利用已知的集合恒等式或包含式证明新的等式或包含式
6.1 集合的基本概念 一．集合的表示 集合是不能精确定义的基本概念。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如： 方程x2－1＝0的实数解集合； 26个英文字母的集合； 坐标平面上所有点的集合； …… 集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。 表示一个集合的方法有两种：列元素法和谓词表示法，前一种方法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。例如 A={a，b，c，…，z} Z={0，±1，±2，…} 都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性，例如集合 B＝{x|x∈R∧x2－1＝0} 表示方程x2－1＝0的实数解集。许多集合可以用两种方法来表示，如B也可以写成{-1，1}。但是有些集合不可以用列元素法表示，如实数集合。 集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如{1，1，2，2，3}＝{1，2，3} 集合的元素是无序的，如 {1，2，3}＝{3，1，2} 在本书所采用的体系中规定集合的元素都是集合。 元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作，例如 A＝{a，{b，c}，d，{{d}}} 这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但b A，{d} A. b和{d}是A的元素的元素。可以用一种树形图来表示这种隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素。上述集合A的树形图如图6.1所示。图中的a，b，c，d也是集合，由于所讨论的问题与a，b，c，d的元素无关，所以没有列出它们的元素。鉴于集合的元素都是集合这一规定，隶属关系可以看作是处在不同层次上的集合之间的关系。
离散数学答案 第十章 格和布尔代数
第十章 格和布尔代数 习题10.1 1．解 ⑴不是，因为L 中的元素对{2,3}没有最小上界； ⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a ,b ，都有最小上界和最大下界； ⑶是，与⑵同理； ⑷不是，因为L 中的元素对{6,7}没有最小上界不存在最小上界。 2．证明 ⑴因为，a ≤b,所以，a ∨b=b ；又因为，b ≤c,所以，b ∧c=b 。故a ∨b=b ∧c ； ⑵因为，a ≤b ≤c,所以，a ∧b=a,b ∧c=b,而a ∨b=b ，因此，(a ∧b )∨(b ∧c )=b ； 又a ∨b=b,b ∨c=c,而b ∧c=b, 因此，(a ∨b )∧(b ∨c )=b 。即 (a ∧b)∨(b ∧c)=(a ∨b)∧(b ∨c)。 习题10.2 1．解 由图1知：＜S 1,≤＞不是＜L,≤＞的子格，这是因为，e ∨f=g ?S 1; ＜S 2,≤＞不是＜L,≤＞的子格， ∵e ∧f=c ?S 2; ＜S 3,≤＞是＜L,≤＞的子格. 2．解 S 24的包含5个元素的子格有如下的8个： S 1={1,3,6,12,24}, S 2={1,2,6,12,24}, S 3={1,2,4,12,24}, S 4={1,2,4,8,24}, S 5={1,2,3,6,12}, S 6={1,2,4,6,12}, S 7={2,4,6,12,24}, S 7={2,4,8,12,24}. 3．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是
第九章 代数系统
第九章代数系统 9.1 二元运算及其性质 一、二元运算与一元运算的定义 1．二元运算的定义与实例 定义9.1 设S为集合,函数f：S×S→S称为S上的二元运算,简称为二元运算。 验证一个运算是否为集合S上的二元运算主要考虑两点： (1)S中任何两个元素都可以进行这种运算,且运算的结果是唯一的。 (2)S中任何两个元素的运算结果都属于S,即S对该运算是封闭的。 例9.1 (1) 自然数集合N上的加法和乘法是N上的二元运算,但减法和除法不是。 (2) 整数集合Z上的加法、减法和乘法都是Z上的二元运算,而除法不是。 (3) 非零实数集R*上的乘法和除法都是R*上的二元运算,而加法和减法不是,因为两个非零实数相加或相减可能得0. (4) 设M n(R)表示所有n阶(n≥2)实矩阵的集合,即 则矩阵加法和乘法都是M n(R)上的二元运算。 (5) S为任意集合,则∪、∩、－、为S的幂集P(S)上的二元运算,这里∪和∩是初级并和初级交。 (6) S为集合,S S为S上的所有函数的集合,则函数的集合运算为S S上的二元运算。 2．一元运算的定义与实例 定义9.2设S为集合,函数f：S→S称为S上的一个一元运算,简称为一元运算。例9.2 (1) 求一个数的相反数是整数集合Z,有理数集合Q和实数集合R上的一元运算。 (2) 求一个数的倒数是非零有理数集合Q*,非零实数集合R*上的一元运算。 (3) 求一个复数的共轭复数是复数集合C上的一元运算。
S 可以用x x. x,y 3*4=3,(-5)*0.2=-5,0* a a a a i a 1
潍坊学院计算机系（院）讲稿专用纸 例9.4设S={1,2},给出P(S)上的运算~和的运算表,其中全集为S. 解：所求的运算表如表9.3和表9.4. 表9.3 表9.4 三．二元运算的性质 1．主要算律 定义9.3 设为S上的二元运算, (1)如果对于任意的x,y∈S,有x y=y x,则称运算在S上满足交换律。 (2)如果对于任意的x,y,z∈S有(x y)z=x(y z),则称运算在S上满足结合律。 (3)如果对于任意的x∈S有x x=x,则称运算在S上满足幂等律。 定义9.4设和*为S上两个不同的二元运算, (1)如果对于任意的x,y,z∈S有(x*y)z=(x z)*(y z)和z(x*y)=(z x)*(z y),则称运算对*运算满足分配律。 (2)如果和*都可交换,并且对于任意的x,y∈S有x(x*y)=x和x*(x y)=x,则称和*运算满足吸收律。 例9.5 表9.5和9.6给出了某些常见代数运算的性质,其中Z、Q、R分别代表整数集、有理数集、实数集,M n(R)表示n(n≥2)阶实矩阵的集合,A A是所有从A到A的函数的集合。 表9.5
离散数学-第六章集合代数课后练习习题及答案
第六章作业 评分要求： 1. 合计57分 2. 给出每小题得分(注意: 写出扣分理由). 3. 总得分在采分点1处正确设置. 一有限集合计数问题 (合计20分: 每小题10分, 正确定义集合得4分, 方法与过程4分, 结果2分) 要求: 掌握集合的定义方法以及处理有限集合计数问题的基本方法 1 对60个人的调查表明, 有25人阅读《每周新闻》杂志, 26人阅读《时代》杂志, 26人阅读《财富》杂志, 9人阅读《每周新闻》和《财富》杂志, 11人阅读《每周新闻》和《时代》杂志, 8人阅读《时代》和《财富》杂志, 还有8人什么杂志也不读. (1) 求阅读全部3种杂志的人数; (2) 分别求只阅读《每周新闻》、《时代》和《财富》杂志的人数. 解定义集合: 设E={x|x是调查对象}, A={x|x阅读《每周新闻》}, B={x|x阅读《时代》}, C={x|x阅读《财富》} 由条件得|E|=60, |A|=25, |B|=26, |C|=26, |A∩C|=9, |A∩B|=11, |B∩C|=8, |E-A∪B∪C|=8 (1) 阅读全部3种杂志的人数=|A∩B∩C| =|A∪B∪C|－(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|) =(60-8)－(25+26+26)+(11+9+8)=3 (2) 只阅读《每周新闻》的人数=|A－B∪C|=|A－A∩(B∪C)|=|A－(A∩B)∪(A∩C)| =|A|－(|A∩B|+|A∩C|－|A∩B∩C|)=25－(11+9-3)=8 同理可得只阅读《时代》的人数为10, 只阅读《财富》的人数为12. 2 使用容斥原理求不超过120的素数个数. 分析:本题有一定难度, 难在如何定义集合. 考虑到素数只有1和其自身两个素因子, 而不超过120的合数的最小素因子一定是2,3,5或7(比120开方小的素数), 也就是说, 不超过120的合数一定是2,3,5或7的倍数. 因此, 可定义4条性质分别为2,3,5或7的倍数, 先求出不超过120的所有的合数, 再得出素数的个数. 解定义集合: 设全集E={x|x∈Z∧1≤x∧x≤120} A={2k|k∈Z∧k≥1∧2k≤120}, B={3k|k∈Z∧k≥1∧3k≤120}, C={5k|k∈Z∧k≥1∧5k≤120}, D={7k|k∈Z∧k≥1∧7k≤120}. 则不超过120的合数的个数=|A∪B∪C∪D|－4 (因为2,3,5,7不是合数) =(|A|+|B|+|C|+|D|)－(|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|)+ (|A∩B∩C|+|A∩B∩D|+|A∩C∩D|+|B∩C∩D|)－|A∩B∩C∩D|－4 =(60+40+24+17)－(20+12+8+8+5+3)+(4+2+1+1)－0－4 (理由见说明部分) =89 因此不超过120的素数个数=120－1－89=30 (因为1不是素数) 说明: |A|=int(120/2); |A?B|=int(120/lcd(2,3)); |A?B?C|=int(120/lcd(2,3,5)); |A?B?C?D|=int(120/lcd(2,3,5,7)).
离散数学习题解+代数系统
离散数学习题解 代数系统 习题四 第四章代数系统 1．设I 为整数集合。判断下面的二元关系是否是I 上的二元运算 a ）+={（x ，y ），z|x ，y ，zI 且z=x+y} b ）－={（（x ，y ），z ）|x ，y ，zI 且z=x －y} c ）3={（（x ，y ），z ）|x ，y ，zI 且z=x 3y} d ）/={（（x ，y ），z ）|x ，y ，zI 且z=x/y} e ）R={（（x ，y ），z ）|x ，y ，zI 且z=x y } f ） ={（（x ，y ），z ）|x ，y ，zI 且z=y x } g ）min = {（（x ，y ），z ）|x ，y ，zI 且z=max （x ，y ）} h ）min = {（（x ，y ），z ）|x ，y ，zI 且z=min （x ，y ）} i ）GCD = {（（x ，y ），z ）|x ，y ，zI 且z= GCD （x ，y ）} j ）LCM={（（x ，y ），z ）|x ，y ，z ∈I 且z= LCM （x ，y ）} [解] a ）是。由于两个整数之和仍为整数，且结果唯一，故知+：I 2→I 是I 上的一个二元运算。 b ）是。由于两个整数之差仍为整数，且结果唯一，故知一：I 2→I 是I 上的一个二元运算。 c ）是。由于两个整数这积仍为整数，且结果唯一，故知x ：I 2→I 是I 上的一个二元运算。 d ）不是：例如若x=5，y=6，则z=x/y=5/6?I ；当y=0时z=x|y=x/0无定义。 e ）不是。例如若x=2，y= -2，则z=x y =2 –2= 2 2 1=I 41 ?；若x=y=0，则z=x y =0，则z=I 2x ?= χ； g ）是。由于两个整数中最大者仍为整数，且结果唯一。故知max ：I 2→I 是I 上的一个二 元运算。 h ）是。由于两个整数中最小者仍为整数，且结果唯一。故知min ：I 2→I 是I 上的一个二 元运算。 i ）是。由于两个整数的最大公约数仍为整数，且结果唯一。故知GCD ：I 2→I 是I 上的一 个二元运算。 j ）是。由于两个整数的最小公倍数仍为整数，且结果唯一。故知LCD ：I 2→I 是I 上的一 个二元运算。 注：两个整数a 和b 的最大公约数GCD （a ，b ）定义为同时除尽a 和b 的正整数中最大
离散数学重点笔记(注释)
第一章，0命题逻辑 素数= 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。(┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A
（2）等幂律A∧A?A ；A∨A?A （3）交换律A∧B?B∧A ；A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C）（6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律A∨（A∧B）?A；A∧（A∨B）?A （8）零一律A∨1?1 ；A∧0?0 （9）同一律A∨0?A ；A∧1?A （10）排中律A∨?A?1 （11）矛盾律A∧?A?0 （12）蕴涵等值式A→B??A∨B （13）假言易位A→B??B→?A （14）等价等值式A?B?（A→B）∧（B→A） （15）等价否定等值式A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A A i(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨A s为析取范式(p∧┐q)∨(┐q∧┐r)∨p A=A1∧A2∧…∧A s为合取范式(p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】
- 离散数学王元元习题解答 (10)
- 离散数学课件 第9章 半群和群
- 离散数学第8,9章课后习题答案
- (完整word版)离散数学重点笔记
- 离散数学第9章习题答案
- 离散数学习题答案1-2-6-7-8-9章-2009-12-17
- 离散数学知识点
- 离散数学答案 第九章 特殊代数系统
- 离散数学第9章习题解答
- 1、《离散数学》左孝凌等编著读后感
- 离散数学(双语) - 第九章答案(高辉)
- 离散数学 第九章：树
- 离散数学_第9章_树与平面图
- 离散数学第五版第九章(耿素云、屈婉玲、张立昂编著)
- 离散数学章节总结
- 离散数学第九章
- (优选)离散数学第五版第九章.Ppt
- 离散数学--第九章--作业答案
- 离散数学第二版屈婉玲第九章第十章答案培训资料
- 离散数学第五版第九章(耿素云、屈婉玲、张立昂编著)