《离散数学复习指导1》由会员分享，可在线阅读，更多相关《离散数学复习指导1（6页珍藏版）》请在金锄头文库上搜索。
1、离散数学复习指导命题逻辑部分一 学习要求1理解命题、联结词的含义，掌握命题的符号化；2理解命题公式的赋值，能求出公式的真值表，判断公式的类型；3. 理解公式等值的定义,记住一些基本等值式,能进行等值演算;4. 体会公式的主范式与公式赋值之间的关系,能利用等值演算求出范式;5. 理解公式的蕴涵及推理的含义及联系,记住一些基本的推理规则,能用演绎推理方法进给出推理证明;二 范例例 1 将下列命题符号化小王聪明但不用功； 说数理逻辑枯燥无味或毫无价值，那是不对的； 你不及格就要补考。 不经一事，不长一智；解： 设 p：小王聪明，q：小王用功，则该命题可符号化为： 。qp p：数理逻辑枯燥无味，q：数
2、理逻辑毫无价值，则： 。)( p：你及格了；q：你要参加补考，则： 。qp p：经一事；Q：长一智，则： 。 这是简单命题，则 p：李卫与李星是兄弟。例 2 求命题公式 的主析取范式和主合取范式，指出公式的成真赋值和成假赋值，rq)(并判断公式的类型。解： p)( rpp)()()qr（主合取范式）42M765310mm(主析取范式) )7,(公式的成真赋值为：000，001，011，101，110，111 成假赋值为：010，100公式为非重言式的可满足式 。 例 3 构造下面推理的证明：前提： 结论：sqrp, rs证：(1) P;(2) T(1)化简规则;(3) T(1)化简规则 q(4
3、) P;rp(5) r T(3)(4)假言推理;(6) P;s(7) s T(3)(6)析取三段论; (8) T(5)(7)合取式. rs例 4. 先将下列相关命题符号化,给出推理证明如果 4是偶数,则 2不能整除 5. 或者 7不是素数或者 2整除 5. 7是素数.因此 4不是偶数.解: 设 p: 4是偶数; q: 2 能整除 5; r: 7是素数; s: 2 整除 5,则前提： 结论：,rqp.p证明: (1) 结论之否定;)(2) T(1)等值式;(3) P; (4) T(2)(3)假言推理;q(5) P; r(6) T(4)(5)析取三段论;(7) P;(8) T(6)(7)合取式.
4、r谓词逻辑部分一 学习要求1理解谓词逻辑的三要素，掌握命题的符号化；2理解谓词公式中量词的辖域、约束关系,及公式的解释，能求出在一个解释下公式的真值，能判断公式的类型；3. 理解公式等值的定义,记住谓词公式的特殊的基本等值式,能进行等值演算;4. 理解前束范式的定义,能利用等值演算求出公式的前束范式;5. 理解公式的蕴涵及推理的含义及联系,特别记住谓词中的一些推理规则,能用演绎推理方法进给出推理证明;二 范例例 1 将下列命题符号化 不是所以的人都要补考,但就有人要补考. 天下乌鸦一般黑。 不是所有火车都比汽车快，但有的火车比所有汽车快。解： ： 是人； ： 要补考，则：)(xP)(xQ（注意
5、特性谓词的用法）)(xP 设 D=乌鸦， ： 是黑的，则： （本题使用了论域）)( ： 是火车； ： 是汽车； ： 比 快，则：)(xx),(yR),()(), yxFQxyPy 或： 。(PQ例 2 设解释 I如下:D=2,3, , , , , , .3)2(f2)f1)F0)32(1)2(0)3(试求出下列公式在解释 I下的真值. yxF yxFxf解: 在解释 I下: )(,)(,)(, yyff )3(,)2(,3)(,2)(, fFffFf ,3101 ),()(,yxxfF),3(),2(32yFyf,3F)0()0(1例 3 求公式 的前束范式.)()(yQxF解: yx )()
6、()(xFyQxxy)()()()(xxF)( zFyzQ(前束范式)(zy例 4 构造推理证明，前题: ，HxGx结论: )(Gx证明:(1) 附加前题; )(xF(2) T(1) EI规则;a(3) P; )(4) T(3) UI规则;)(5) T(2)(4)假言推理规则; H(6) P;)(xGx(7) T(6) UI规则; )(a(8) T(5)(7)析取三段论.(9) T(8) EG规则.y集合论部分一 学习要求1领会集合的各种运算，掌握各种集合式的谓词演算的证明方法；2领会序偶及笛卡积的定义,理解二元关系的定义,掌握及关系的运算(定义域、值域、逆、复合、闭包)；掌握关系的三种表示方
7、法(集合、关系图、关系矩阵).3. 领会关系的性质,能判断或证明一个关系所具有的性质,4. 理解等价关系及划分的定义，掌握等价类及集合商集的求法，理解等价关系与划分的关系。5. 理解偏序关系的定义，特别注意偏序集中元素的可比性（“大小”的含义） ，能画出哈斯图，并能求出集合中的特殊元及集合的界； 理解函数的定义，掌握函数的复合及逆运算，领会特殊函数（单射，满射，双射）的概念。二 范例例 1 已知 ， ， ，求：12,0765,432E10xA15xB ； ； ； ； ABB ； ； ；（解： ， ； ； ；12076（10765432（； 543105432A ； ；6AB例 2 已知 , ,
8、dcba,dbcaR, 求:AIcS ; , , 1R2S2 )()(rstsr解: = ; =,bdab2,dacb= ,c=S2 , =)(RrAIc, bdcbaas, adt AIadcbr ,)(例 3 已知 X=a,b,c,给出 X上的所有等价关系。解:X 的划分其有五种:S1=a,b,c, S2=a,b,c,S3=a,c,b,S4=a,b,c,S5=a,b,c,因为 X上划分与等价关系一一对应,故 x上共有五个等价关系，它们是：R1, XIR2, , R3XIR4, , R5 XI例 4 已知偏序集X,R,其中 X=a,b,c,d,e, Y=d,e,R的关系矩阵为求：(1).用集
9、合的列举法写出 R(2).画出 R的哈斯图；(3).找出 X的极大元、极小元、最大 元、最小元；(4).找出 Y的上界、下界、最小上界、最大下界。10101RM解:(1). AIaedabcR,(2).略(3)X 的极大元:a; 极小元:c，d ; 最大元:a ; 最小元: 无.(4). Y的上界 e,a; 下界 d ; 最小上界 e; 最大下界 d。例 5 实数集 R上的函数 , ,3)(xf 5)(xg , 上函数 ,cbaA acbaf ,acbg判断 f是否单射、满射、双射,并求 , , .1)(f1f解: 为双射, 为双射3)(x53)(xg,8)(fffg, , 14 34)(1x
10、gf, .3)(1xf 253()()(11 xgfxfg 均为双射g, ,bca, f ,)(1cbaf, .,1b g代数结构部分一 学习要求1理解二元运算的含义及代数系统中的运算的性质及特殊元（单位元、零无、逆元）的定义；2了解代数系统的同态与同构的定义；知道满同态下的保持性;3. 记住半群的定义,掌握特殊半群（独异点、循环半群、可交换半群等）的证明方法。4. 记住群的定义,了解群的性质，掌握群的证明方法（从定义出发） 。;二 范例例 1. Z为整数集，S=x| ,在 S 上定义二元运算*: )105(xZxx*y=minx,y,证明是单元可交换半群。证： 对任意 x,y , x*y=m
11、inx,y ,S*是二元运算，是代数系统； 对任意 x,y,z(x*y)*z=(minx,y)*z=minx,y,zx*(y*z)= z * (minx,y) =minx,y,z*运算满足结合律，是半群； 对任意 x ，Sx*10=10*x=x10 是单位元，是单元半群； x*y=minx,y= miny,x=y*x, *运算满足交换律；故是单元可交换半群。例 2 （10 分） Z n=0,1,2,n-1 ,在 Zn上定义二元运算:xy=(x+y) mod n, 其中+、-是普通加法、减法，证明是循环群。 证(1)对任意 x,yZ n, 因xy=(x+y) mod nZ n所以是二元运算, 是代数系统;（2 分）(2) 对任意 x,y,zZ n,因(xy) z=(x+y) mod n) z=(x+y+z) mod nx(yz)=x(y+z) mod n)=(x+y+z) mod n有(xy) z= x(yz)所以满足结合律, 是半群; （2 分）(3) 对任意 x, 因 0x=x0=x所以,0 是单位元; （2 分）(4) ,1对任意 xZ n且 时,0x(n-x)=(n-x) x=0所以 1由(1)(2(3)(4)知是群; （2 分）（5）对任意 xZ n 都有 x=1x1是生成元，所以是循环群。 （2 分）
