资源描述：
《离散数学--总复习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第一部分：集合论知识点：集合关系（Î，Í,Ì,Ï,=）集合运算（并、交、差、对称差、补集、幂集），特殊集合（Æ，E，P(A)）集合恒等式（幂等律、交换律、结合律、分配律、吸收律、德摩根律、补交转换律(A-B=AÇ~B)、德·摩根律~(BÈC)=~B~ÇC，A-(BÈC)=(A-B)Ç(A-C)）证明集合包含或相等（根据定义,通过逻辑等值演算证明、利用已知集合等式或包含式,通过集合演算证明）1.证:AÈ(BÇC)=(AÈB)Ç(AÈC)证"xxÎAÈ(BÇC)ÛxÎAÚ(xÎBÙxÎC)(并,交的定义)Û
2、(xÎAÚxÎB)Ù(xÎAÚxÎC)(逻辑演算的分配律)ÛxÎ(AÈB)Ç(AÈC)2.证明(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第二部分：逻辑学命题的定义（凡具有确定真假意义
3、的陈述句均称为命题。）联结词（Ø、∧、∨、®、«、、¯（公式转化为只含、¯的表达形式））例：将p®q化为只含的公式p®qÛØpÚqÛØ(p∧Øq)ÛpØqÛpØ(q∧q)Ûpqq命题符号化(1、王晓虽然聪明，但不用功.2、张辉与王丽都是三好生.3、张辉与王丽是同学.4、除非天冷，小王才穿羽绒服.5、除非小王穿羽绒服，否则天不冷.)等值演算（幂等律、交换律、结合律、分配律、吸收律、蕴涵等值式A®BÛØAÚB等价等值式A«BÛ(A®B)Ù(B®A)假言易位等值式A®BÛØB®ØA等价否定等值式A«BÛØA«
4、ØB）证明p®(q®r)Û(pÙq)®r证p®(q®r)ÛØpÚ(ØqÚr)（蕴涵等值式）Û(ØpØÚq)Úr（结合律）ÛØ(pÙq)Úr（德摩根律）Û(pÙq)®r（蕴涵等值式）判断下列公式的类型qØÙ(p®q)解qØÙ(p®q)ÛqØÙ(ØpÚq)（蕴涵等值式）ÛqÙ(pØÙq)（德摩根律）ÛpÙ(qØÙq)（交换律，结合律）ÛpÙ0（矛盾律）Û0（零律）该式为矛盾式.命题公式（重言式、矛盾式、可满足式），利用真值表判断，等值演算，范式。范式（析取范式、合取范式）求ØpÙ(pÚqÚØr)的主合取范式
5、和主析取范式解ØpÛ(ØpÚqÚr)Ù(ØpÚqÚØr)Ù(ØpÚØqÚr)Ù(ØpÚØqÚØr)ÛM4ÙM5ÙM6ÙM7pÚqÚØrÛM1得ØpÙ(pÚqØÚr)ÛM1ÙM4ÙM5ÙM6ÙM7ÛP(1,4,5,6,7)ÛS(0,2,3)主析取范式的用途:(1)求公式的成真赋值和成假赋值例如Ø(p®q)ØÚrÛm0Úm2Úm4Úm5Úm6成真赋值:000,010,100,101,110;成假赋值:001,011,111(2)判断公式的类型BÛØpÚ(pÚq)Û1Ûm0Úm1Úm2Úm3重言式(3)判断两
6、个公式是否等值p与(ØpÚq)®(pÙq)解pÛpÙ(ØqÚq)Û(pØÙq)Ú(pÙq)Ûm2Úm3(ØpÚq)®(pÙq)ÛØ(ØpÚq)Ú(pÙq)Û(pØÙq)Ú(pÙq)Ûm2Úm3故pÛ(ØpÚq)®(pÙq)(4)选派人员某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解记p:派A去,q:派B去,r:派C去(1)p®r,(2)qØ®r,(3)(pØÙq)Ú(ØpÙq
7、)求下式的成真赋值A=(p®r)Ù(qØ®r)Ù((pØÙq)Ú(ØpÙq))求A的主析取范式A=(p®r)Ù(qØ®r)Ù((pØÙq)Ú(ØpÙq))Û(ØpÚr)Ù(ØqØÚr)Ù((pØÙq)Ú(ØpÙq))Û((ØpØÙq)Ú(ØpØÙr)Ú(rØÙq)Ú(rØÙr))Ù((pØÙq)Ú(ØpÙq))Û((ØpØÙq)Ù(pØÙq))Ú((ØpØÙr)Ù(pØÙq))Ú((rØÙq)Ù(pØÙq))Ú((ØpØÙq)Ù(ØpÙq))Ú((ØpØÙr)Ù(ØpÙq))Ú((rØÙq)Ù(ØpÙq
8、))Û(pÙØqÙr)Ú(ØpÙqÙØr)成真赋值:101,010结论:方案1派A与C去,方案2派B去推理规则（附加律AÞ(AÚB)化简律(AÙB)ÞA假言推理(A®B)ÙAÞB拒取式(A®B)ÙØBÞØA析取三段论(AÚB)ÙØBÞA假言三段论(A®B)Ù(B®C)Þ(A®C)）(1)直接证明法在自然推理系统P中构造下面推理的证明:前提:pÚq,q®r,p®s,Øs结论:rÙ(pÚq)证明①p®s前提引入②Øs前提引入③Øp①②拒取式④p
