离散数学精编.docx

离散数学

第一篇：离散数学第一章数学语言与证明方法例1设E={x|x是北京某大学学生},A,B,C,D是E的子集,A={x|x是北京人}，B={x|x是走读生},C={x|x是数学系学生}，D={x|x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:(AD)~C={x|x是北京人或喜欢听音乐,但不是数学系学生}~AB={x|x是外地走读生}(A-B)D={x|x是北京住校生,并且喜欢听音乐}~D~B={x|x是不喜欢听音乐的住校生}例3证明:(1)AB=BA(交换律)证xxABxAxB(并的定义)xBxA(逻辑演算的交换律)xBA(并的定义)(2)A(BC)=(AB)(AC)(分配律)证xxA(BC)xA(xBxC)(并,交的定义)(xAxB)(xAxC)(逻辑演算的分配律)x(AB)(AC)(并,交的定义)(3)AE=E(零律)证xxAExAxE(并的定义)xA1(全集E的定义)1(逻辑演算的零律)xE(全集E的定义)(4)AE=A(同一律)证xxAExAxE(交的定义)xA1(全集E的定义)xA(逻辑演算的同一律)例4证明A(AB)=A（吸收律）证利用例3证明的4条等式证明A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=A(BE)(交换律)=AE(零律)=A(同一律)例5证明(A-B)-C=(A-C)-(B-C)证(A-C)-(B-C)=(A~C)~(B~C)(补交转换律)=(A~C)(~B~~C)(德摩根律)=(A~C)(~BC)(双重否定律)=(A~C~B)(A~CC)(分配律)=(A~C~B)(A)(矛盾律)=A~C~B(零律,同一律)=(A~B)~C(交换律,结合律)=(A–B)–C(补交转换律)例6证明(AB)(AC)=(BC)(AC))((AC)A例7设A,B为任意集合,证明:(1)AAB证xxAxAxB(附加律)xAB(2)ABA证xxABxAxBxA(化简律)(3)A-BA证xxA-BxAxBxA(化简律)(4)若AB,则P(A)P(B)证xxP(A)xAxB(已知AB)xP(B)例8证明AB=AB-AB.证AB=(A~B)(~AB)=(A~A)(AB)(~B~A)(~BB)=(AB)(~B~A)=(AB)~(AB)=AB-AB例3若A-B=A,则AB=证用归谬法,假设AB,则存在x,使得xABxAxBxA-BxB(A-B=A)xAxBxBxBxB，矛盾例4证明是无理数证假设是有理数,存在正整数n,m,使得=m/n,不妨设m/n为既约分数.于是m=n,m2=2n2,m2是偶数,从而m是偶数.设m=2k,得(2k)2=2n2,n2=2k2,这又得到n也是偶数,与m/n为既约分数矛盾.例6对于每个正整数n,存在n个连续的正合数.证令x=(n+1)!则x+2,x+3,…,x+n+1是n个连续的正合数:i|x+i，i=2,3,…,n+1例7判断下述命题是真是假:若AB=AC,则B=C.解反例:取A={a,b},B={a,b,c},C={a,b,d},有AB=AC={a,b}但BC,故命题为假.例8证明:对所有n1,1+2+…+n=n(n+1)/2证归纳基础.当n=1时,1=1(1+1)/2,结论成立.归纳步骤.假设对n1结论成立,则有1+2+…+n+(n+1)=n(n+1)/2+(n+1)(归纳假设)=(n+1)(n+2)/2得证当n+1时结论也成立.例9任何大于等于2的整数均可表成素数的乘积证归纳基础.对于2,结论显然成立.归纳步骤.假设对所有的k(2kn)结论成立,要证结论对n+1也成立.若n+1是素数,则结论成立;否则n+1=ab,2a,b命题逻辑例1下列句子中那些是命题？(1)北京是中华人民共和国的首都.(2)2+5＝8.(3)x+5＞3.(4)你会开车吗？(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题例2将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解(1)p∧q(2)p∧q(3)p∧q(4)记r:张辉是三好生,s:王丽是三好生，r∧