资源描述：
《离散数学期末复习材料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第一部分：数理逻辑（25%）例1p→q的逻辑关系表示q是p的必要条件。只要p，就q因为p，所以qp仅当q只有q才p除非q才p除非q，否则非p如：除非a能被2整除，否则a不能被4整除令r：a能被4整除 s：a能被2整除符号化为r→s例2合取式的命题符号化：既……又……”、“不但……而且……”、“一面……一面……”、“虽然……但是……”如：吴颖虽然聪明，但不用功。令p:吴颖用功。q:吴颖聪明。符号化q∧┐p例3求真值表(1)(┐p∧q)→┐r(2)(p∧┐p)«(q∧┐q)(3)┐(p→q)∧q∧r例4用等值演
2、算法证明等值式(p→q)∧(p→r)(p→(q∧r))解：(p→q)∧(p→r)(┐p∨q)∧(┐p∨r)┐p∨(q∧r)p→(q∧r)例5求公式(┐p→q)→(┐q∨p)的主析取范式和主合取范式解：(┐p→q)→(┐q∨p)┐(p∨q)∨(┐q∨p)(┐p∧┐q)∨(┐q∨p)(┐p∧┐q)∨(┐q∧p)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)(┐p∧┐q)∨(p∧┐q)∨(p∧q)6例6前提：(p∧q)→r,┐s∨p,q结论：s→r证明：用附加前提证明法 ①s 附加前提引入②┐s∨p
3、 前提引入 ③p ①②析取三段论④(p∧q)→r前提引入⑤q 前提引入 ⑥p∧q ③⑤合取 ⑦r ④⑥假言推理例7构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果颐和园游人太多，就不去颐和园。今天是周六，并且颐和园游人太多。所以我们去圆明园或动物园玩。构造证明：（1）设p：今天是周六。q：到颐和园玩。r：到圆明园玩。s：颐和园游人太多。t：到动物园玩。（2）前提：p®(qÚr),s®┐q,p,s结论：rÚt证明：例8设F＝{<3,3>,<6,
4、2>},G={<2,3>}，则F-1＝{<3,3>,<2,6>}F°G＝{<2,3>}G°F＝{<6,3>}F-G=例9o画出偏序集<{1,2,3,4,5,6,7,8,9}，R整除>6oB={2,3}第二部分：代数系统（55%）例1：在整数集上定义运算，"x,y∈Z，x。y=x+y-2,证明是一个群解：(1)因为"x,y∈Z，x。y=x+y-2∈Z所以。是Z上的一个二元运算(2)"x,y∈Z，则(x。y)。z=(x+y-2)。z=x+y-2+z-2=x+y+z-4x。(y。z)=x。(y+z-2)=
5、x+y+z-2-2=x+y+z-4即。满足结合律(3)x。e=e。x=xÞe+x-2=xÞe=2"x∈Z有x。z=x+z-2=x=z。x则这个运算的单位元是2(4)x。x-1=eÞx+x-1-2=e=2Þx-1=4-x"x∈Z,有4-x∈Z且x+4-x-2=2=x。(4-x)=(4-x)。x则x的逆元是4-x则是一个群6例2求元素5,6的阶及逆元解：关于“+”运算的幺元（单位元）=0所以5的阶是8，逆元是-5=36的阶是4，逆元是-6=2例3的零元，单位元，有无零因子，“
6、.”是否满足消去律解：(1)零元：0，单位元：1(2)2-4=0所以2与4为零因子，无零因子环(3)由2-4=2,0=0，但4≠0，所以不满足消去律例4设A是一个非空集合，x∈P（A），求的单位元及x的逆元解：单位元为，x-1=x(xÅx=)例5：偏序集→上、下界→∧，∨，格是一个有补格解：(1)是一个格，"x,y∈P（A），x∧y=x∩y，x∨y=x∪y(2)全下界为，全上界为A6(3)"x,∈P（A），x的补元为A-x（x∧（A-x）=，x∨（A-x）=A）
7、第三部分：图论（20%）例1求最短路径6例2求关键路径关键路径：v1->v3->v7->v86
