文献综述 信息与计算科学 集合代数与粗糙集之间的关系研究 粗糙集理论是波兰数学家Pawlak于1982年提出的用于数据分析的理论. 由于该理论能够处理模糊和不确定性信息, 因此作为一种有效的知识获取工具受到了人工智能研究者的关注. 目前粗糙集理论已被成功应用在机器学习与知识发现、过程控制、数据挖掘、决策分析、模式识别等领域, 成为信息科学的研究热点之一. 1965年, 美国加利福尼亚大学控制论专家扎德(L. A. Zadeh)教授在《信息与控制》杂志上发表了一篇开创性论文<模糊集合>, 这标志着模糊数学的诞生. L. A. Zadeh教授多年来致力于“计算机”与“大系统”的矛盾研究, 集中思考了计算机为什么不能象人脑那样进行灵活的思维与判断问题. 计算机为什么不能象人脑思维那样处理模糊信息呢? 其原因在于传统的数学. 例如精确数学, 是建立在经典集合论的基础之上, 一个研究的对象对于某个给定的经典集合的关系要么是属于, 要么是不属于, 二者必居其一. [2]19世纪, 由于英国数学家布尔(Bool)等人的研究, 这种基于二值逻辑的绝对思维方法抽象后成为布尔代数, 它的出现促使数理逻辑成为一门很有适用价值的学科, 同时也成为计算机科学的基础. 但是, 1923年, 大哲学家罗素(Russell)就在其著名论文<论模糊性>中提出“整个语言或多或少是模糊的”及“所有二值逻辑都习惯上假定使用精确符号. 因此它仅适用于虚幻的存在. 而不适用于现实生活. 逻辑比其他学科使我们更接近天堂”[1]时认识到二值逻辑的不足. 二值逻辑无法解决一些逻辑悖论, 如著名的罗素(Russell)“理发师悖论”、“秃头悖论”、“克利特岛人说谎悖论”等等悖论问题. 这就是目前计算机不能象人脑思维那样灵活、敏捷地处理模糊信息的重要原因. 为克服这一障碍, L. A. Zadeh教授提出了“模糊集合论”. 在此基础上, 现在已形成一个模糊数学体系. 1960年柏克莱加州大学电子工程系扎德(L. A. Zadeh)教授, 提出“模糊”的概念. 1965年发表关于模糊集合理论的论文. 1966年马里诺斯(P. N. Marinos)发表关于模糊逻辑的研究报告. 以后, 扎德(L. A. Zadeh)又提出关于模糊语言变量的概念. 1974年扎德(L. A. Zadeh)进行有关模糊逻辑推理的研究. 1978年, 国际上第一本以模糊数学为主题的学术刊物《Fuzzy Sets
第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b};
或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。）
第一章，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. 设
《离散数学》代数结构部分练习题参考答案 2018年6月 一、填空题 1.在代数系统（N ，+）中，其单位元是0，仅有单位元0有逆元. 2.设A 是非空集合，集合代数),),(( A P 中，)(A P 对运算 的单位元是?，零元是 A.)(A P 对运算 的单位元是A . 3.设Z 为整数集，若1,,-+=∈?b a b a Z b a ，则Z a ∈?，a 的逆元=-1a 2－a . 4.设}3,2,1,0{4=Z ，?为模4乘法，即4mod )(xy y x =?，4,Z y x ∈?.则4Z 上运算?的运算表为.（略） 二、选择题 1.设集合{}10,...,3,2,1=A ,在集合A 上定义运算,不是封闭的为(A ) (A){}b a lcm b a A b a ,,,=?∈?(最小公倍数)(B){}b a ged b a A b a ,,,=?∈?(最大公约数) (C){}b a b a A b a ,max ,,=?∈?(D){} b a b a A b a ,min ,,=?∈?2.在自然数集N 上定义的二元运算?,满足结合律的是 (C )(A)b a b a -=?(B)b a b a 2+=?(C){}b a b a ,max =?(D)b a b a -=?三、解答题 1.通常数的乘法运算是否可以看成是下列集合上的二元运算，说明理由. （1）{}2,1=A （2）{}是质数x x B =（3）{}是偶数x x C =（4）{}N n D n ∈=2解：（1）数的乘法运算不是集合A 上的二元运算.因为A ?=?422（2）数的乘法运算不是集合B 上的二元运算.因为质数与质数的乘积不是质数. （3）数的乘法运算是集合C 上的二元运算.因为偶数乘偶数是偶数. （4）数的乘法运算是集合D 上的二元运算.因为D n m m n ∈=?+222. 2.实数集R 上的下列二元运算是否满足结合律与交换律？
一、填空 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. 设
《离散数学》代数系统 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=
第六章集合代数 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的元素无关，所以没有列出它们的元素。鉴于集合的元素都是集合这一规定，隶属关系可以看作是处在不同层次上的集合之间的关系。
《离散数学》第三部分----代数结构 一、选择或填空 1、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点
答：单位元，1 8、素数阶群一定是( )群, 它的生成元是( )。 答：循环群，任一非单位元 9、设〈G,*〉是一个群，a,b,c∈G，则 (1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。 答：（1）b1- *a(2) b 10、
集合代数 对事物进行分类是科学研究的一项基本工作。在数学上通常把分类的结果称为集合。因此，“集合”是数学中最常用的概念。事实上，现代数学中所有对象都可以视为集合，所有数学概念都可以用集合进行定义。数理逻辑学家们正努力用集合及其若干公理重新构造整个数学体系。我们学习集合论的意义有两点：（1）集合论是数学的基础，学习集合论有助于理解现代数学的公理化方法。（2）集合论为应用领域提供建模和分析工具。本讲学习集合论的基础知识，包括如下4个部分： 1.集合代数：若干基本概念和集合运算及其运算定律。 2.二元关系：用集合定义二元关系，二元关系的分类和性质。 3.函数：用二元关系定义函数，函数的分类和性质。 4.ZFC公理系统：学习由Zermelo和Frankel等人所设计的10组集合论公 理，并用以证明某些对象的分类是集合。 1.集合的概念和表达式 我们所能感知的客观事物和思想中产生的观念，是我们的认知对象（object，entity）。我们根据对象的各种共同性质把对象划分为不同的类（class）。在数学中，我们通常把一个类称为集合（set），其中的对象称为该集合的成员（member）或者元素（element）。通常用大写字母表示某集合，小写字母表示该集合中的元 表示x是A的成员，读作“x属于A”。这个素。对于任何集合A，我们用x A 成员隶属关系是集合论中的一个基本关系，可以定义其它的关系，包括两个集合相等、包含，等等。 在现代数学中，“集合”被选作为一个基础性概念，用以定义其它数学概念。作为整个数学体系的第一概念，它自身是没有定义的，也是不可能被定义的。尽管集合概念没有通用的定义，每个集合实例都是有严格定义的。我们有两种定义集合实例的方法，即枚举法和概括法。ZFC公理系统严格地描述了这两种定义集合的方法。这里我们先对两种定义方法做直观的描述。 枚举法：也称列举法，明确地将一个集合的所有元素（的名字）排列在花括号内，元素之间用逗号分隔。这种定义集合的表达式称为枚举式。例如，用枚举法可定义集合A为 A={a,b,c} 这个定义指出集合A含有三个元素a,b,c。对于一些元素有规律排列的集合，我们可以用省略号略去其中某些元素。例如，下面都是枚举法所定义的集合： B={a,b, …,z} N={0,1,2, …} Z={0,±1, ±2,…} 1
第六章作业 评分要求： 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)).
集合的交并差补与代数的加减乘除 wsy August13,2015 我们都知道，集合的运算和代数的运算是独立的，一般没有太大的关联。集合的基本的运算法则有： ?交集：A B; ?并集：A B; ?补集：A; ?差集：A?B. 但是，我们通过如下的定义，可以建立一个集合的代数运算关系：令全集?表示为1,空集?表示为0 ?交集：A∩B=ab; ?并集：A∪B=a+b?ab; ?补集：A=1?a; ?差集：A?B=A?A∩B=a?ab=a(1?b). 其中，集合A,B在代数运算中，用相应的小写字母a,b表示。注意到，因为A∩A=A,所以根据定义可以推导出，我们的定义满足幂等律 a·a=a2=a. 除了，这一点有差异之外，其它运算与代数运算都相同。 接下来，我们可以看到，集合的对偶律和结合律，使用上述定义之后，也是吻合的。下列代数式子在化简后是显然成立的，我们减去了化简的步骤。 1.对偶律: 1
?对于 A∩B=A∪B, 代入上述定义，有 1?ab=(1?a)+(1?b)?(1?a)(1?b). ?对于 A∪B=A∩B, 代入上述定义，有 1?(a+b?ab)=(1?a)(1?b). 2.结合律： ?对于 (A∩B)∪C=(A∪C)∩(B∪C), 代入上述定义，有 ab+c?abc=(a+c?ac)(b+c?bc). ?对于 (A∪B)∩C=(A∩C)∪(B∩C), 代入上述定义，有 (a+b?ab)c=ac+bc?ac·bc. 综上可知，我们的定义是满足集合运算的要求的。之所以要把集合的运算，转化为代数的运算，是因为一般的人，对于代数运算的熟悉程度远远高于集合运算。这为我们验证，求解，推断复杂的集合运算的式子提供了另外的一种新的更加简便快速的方式。 2
离散数学习题解 代数系统 习题四 第四章代数系统 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 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】