




如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
《离散数学》期末复习大纲(完整版)(含例题和考试说明) 一、命题逻辑 [复习知识点] 1、命题与联结词(否定¬、析取∨、合取∧、蕴涵→、等价↔),复合命题 2、命题公式与赋值(成真、成假),真值表,公式类型(重言、矛盾、可满足),公式的基本等值式 3、范式:析取范式、合取范式,极大(小)项,主析取范式、主合取范式 4、公式类型的判别方法(真值表法、等值演算法、主析取/合取范式法) 5、命题逻辑的推理理论 本章重点内容:命题与联结词、公式与解释、(主)析取范式与(主)合取范式、公式类型的判定、命题逻辑的推理 [复习要求] 1、理解命题的概念;了解命题联结词的概念;理解用联结词产生复合命题的方法。 2、理解公式与赋值的概念;掌握求给定公式真值表的方法,用基本等值式化简其它公式,公式在解释下的真值。 3、了解析取(合取)范式的概念;理解极大(小)项的概念和主析取(合取)范式的概念;掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法。 4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。 5、掌握命题逻辑的推理理论。 [疑难解析] 1、公式类型的判定 判定公式的类型,包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种,一是真值表法,二是等值演算法。 2、范式 求范式,包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点:一是准确理解掌握定义;另一是巧妙使用基本等值式中的分配律、同一律和互补律(排中律、矛盾律),结果的前一步适当使用幂等律,使相同的短语(或子句)只保留一个。 3、逻辑推理 掌握逻辑推理时,要理解并掌握12个(除第10,11)推理规则和3种证明法(直接证明法、附加前提证明法和归谬法)。 例1.试求下列公式的主析取范式: (1);(2) ( ) 2.用真值表判断下列公式是恒真?恒假?可满足? (1)(PP)Q (2)(PQ)Q (3)((PQ)(QR))(PR) 解: 真值表 PQPPP(PP)Q00101011001000111000因此公式(1)为可满足。 真值表 PQPQ(PQ)(PQ)Q00100011001001011100因此公式(2)为恒假。 真值表 PQRPQQRPR((PQ)(QR))(PR)00011110011111010101101111111000101101011111010011111111因此公式(3)为恒真。 3.┐Q(P→Q)蕴涵┐P (an:法1:真值表 法2:若┐Q(P→Q)为真,则┐Q,P→Q为真, 所以Q为假,P为假,所以┐P为真。 法3:若┐P为假,则P为真,再分二种情况: ①若Q为真,则┐QÙ(P→Q)为假 ②若Q为假,则P→Q为假,则┐Q(P→Q)为假 根据①②,所以┐Q(P→Q)蕴涵┐P。) 4.利用基本等价式证明下列命题公式为恒真公式。 ((PQ)(QR))(PR) ((PQ)(P(QR)))(PQ)(PR) (1、证明: ((PQ)(QR))(PR) =((PQ)(QR))(PR) =((PQ)(QR))(PR) =(PQ)(QR)PR =((PQ)P)((QR)R) =(1(QP))((QR)1) =QPQR =(QQ)PR =1PR =1 ((PQ)(P(QR)))(PQ)(PR) =((PQ)(P(QR)))(P(QR)) =(P(QQR))(P(QR)) =(P(QR))(P(QR)) =1) 5.用形式演绎法证明:{}蕴涵 证明: (1)规则P (2)规则Q(1) (3)规则P (4)规则Q(3) (5)规则Q(2)(4) (6)RS规则P (7)PS规则Q(5)(6)) 6.用形式演绎法证明:(蕴涵A 证明:(改() (1)A规则D (2)A∨B规则Q(1) (3)规则P (4)规则Q(2)(3) (5)D规则Q(4) (6)规则Q(5) (7)规则P (8)E规则Q(6)(7) (9)规则Q(1)(8)) 7.┐(P∧┐Q),┐Q∨R,┐R蕴涵┐P (1)┐Q∨R (2)┐R (3)┐Q (4)┐(P∧┐Q) (5)┐P∨Q (6)┐P) 8.某案涉及甲、乙、丙、丁四个,根据已有线索,已知: 若甲、乙均未作案,则丙、丁也均未作案; 若丙、丁均未作案,则甲、乙也均未作案; 若甲与乙同时作案,则丙与丁有一人且只有一人作案; 若乙与丙同时作案,则

ys****39
实名认证
内容提供者


最近下载