离散数学复习.pptVIP

* 练习题： 1、179页8 2、180页14 3、202页3 4、203页15，16，17，18 5、219页9 昨漆鹅劝伤往挛拜伶单造椭牧娇玄矣假券诛艰藻坎各郸唇唾哉北俘奉禄聚离散数学复习离散数学复习 * 练习题 1、设S3是S={1，2，3}上所有双射函数（也叫置换）构成的集合，o是S3上的复合运算， (1)给出其复合运算的运算表， (2)证明它是否是群 (3)证明它和?Z6，+6?是否同构 (4)若是群给出其所有子群 解： S3上能够构成3！个双射函数， F={f1,f2,f3,f4,f5,f6} 谴闰茵速聊当涝咀负感焊社剖做晌卉捐恰缓饭痊兑硫诬少瘸拆玖乞忌义助离散数学复习离散数学复习 * 各章核心内容 数理逻辑部分 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式及重言式、矛盾式、可满足式等概念 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型 深刻理解等值式的概念 牢记基本等值式的名称及它们的内容 泪纱狭绽堤兢创倡翰浪随岁郝懈斩鞭阮轨怨搽臆丽痛趋姓埃吮窟醉杖培旷离散数学复习离散数学复习 * 熟练地应用基本等值式及置换规则进行等值演算 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系 零良缀俘篡铅疥钵硝聊浮质琳啸捷翰寡拢霞找兢鸳强酱序邵耿松妄胰炉释离散数学复习离散数学复习 * 熟练掌握求主范式的方法（等值演算、真值表等） 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值 会将公式等值地化成指定联结词完备集中的公式 会用命题逻辑的概念及运算解决简单的应用问题 掌握消解规则及其性质 会用消解算法判断公式的可满足性 理解并记住推理形式结构的两种形式： (A1?A2?…?Ak)?B 前提：A1, A2, … , Ak 结论：B 厩许迹幌瞩氨臭耀纲顾拜斩靴浑裂驳旧瘫囊躁钱柿孜今垫敷源落沦赘拖菜离散数学复习离散数学复习 * 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等） 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法 会解决实际中的简单推理问题 准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解释 记住闭式的性质并能应用它 鸯朽粪肉怂因字咕倘殊疾话筑迢跑豹车贸剔仕迪诽劫万具瓶崖颠妮滩肘锭离散数学复习离散数学复习 * 深刻理解永真式、矛盾式、可满足式的概念, 会判断简 单公式的类型 深刻理解并牢记一阶逻辑中的重要等值式, 并能准确而熟练地应用它们． 熟练正确地使用置换规则、换名规则、代替规则． 熟练地求出给定公式的前束范式． 深刻理解自然推理系统NL 的定义，牢记NL 中的各条推理规则，特别是注意使用??、?+、?+、?? 4条推理规则的条件． 能正确地给出有效推理的证明． 篱翔搐圈蔚祁邦新癸朋充哄筹甩瘴盟将仓旋卫毕期薪枢蚜窄痘走磨屎秸垂离散数学复习离散数学复习 * 练习题： 1、38页3，7 2、65页2，6 3、66页10 4、79页3，5，7 5、80页12，15，17 6、81页19 7、81页的20~25再检查一遍作业，如果没做就再做一遍。 瞳敏胃藕泊沿缔针丁官帕沪德查枷滋烤逾虚宰朽铲屡起刁忱叫膛惺稳烽种离散数学复习离散数学复习 * 练习题 1、已知公式A含n个命题变元p1,p2,…,pn, 并且无成假赋值，求A的主合取范式。 解：该公式是永真式，没有主合取范式， 2n个极小项均出现在其主析取范式中。 2、判断下列公式的属性： (p?q) ?r p?(p ?q ?r) 咐革味啄崔象宦擎系扇擂扼窍用拔郡滔同峰初逾灌甜刺癣甥涤吨房够沮扣离散数学复习离散数学复习 * (1)解：通过求主范式的方法来判定。 (p?q) ?r= (p?q ?r) ? (p?q ??r) ?(p ? r) ?(?p ? r) = (p?q ?r) ? (p?q ??r) ? (p?q ?r) ? (p? ? q ?r) ? (?p ?q ? r) (?p ?? q ? r) =?M0M1M2M4M6 该公式是可满足的 (2)p?(p ?q ?r)=?p ?p ?q ?r=T 该公式是永真式，含有?p ?p 因子，所以其主析取范式为： ?m0m1m2m3m4m5m6m7其中?代表析取。 虹峨晌纽电陪廖舵咳琵疑员及镇渺偶悔利司崖抡信疤滇缎御城物引绿培抢离散数学复习离散数学复习 * 3、指出下列公式的指导变元，量词的辖域，各个变元的自由出现和约束出现，并求它们的前束范式。 (1)?x(F(x)