[离散数学答案]离散数学答案版(全) 2

《[离散数学答案]离散数学答案版(全) 2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、[离散数学答案]离散数学答案版(全)25篇一:离散数学答案版25第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法等证明方法。教学目的：1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。2．熟练掌握常用的基本等价式及其应用。3．熟练掌握析/合取范式的求法及其应用。4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。5．熟练掌握形式演绎的方法。教学重点：1．命题的概念及判断2．联结词，命题的翻译3．主析取范式的求法4

2、．逻辑推理教学难点：1．主析取范式的求法2．逻辑推理1.1命题及其表示法1.1.1命题的概念数理逻辑将能够判断真假的陈述句称作命题。1.1.2命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。1.2命题联结词P↑P?﹁?﹁P；↑?﹁?P∧Q；↑?﹁P↑﹁Q?P∨Q。P↓P?﹁?﹁P；↓?﹁?P∨Q；↓?﹁P↓﹁Q?﹁?P∧Q。1.3命题公式、翻译与解释1.3.1命题公式定义命

3、题公式，简称公式，定义为：单个命题变元是公式；如果P是公式，则﹁P是公式；如果P、Q是公式，则P∧Q、P∨Q、P?Q、P?Q都是公式；当且仅当能够有限次的应用、、所得到的包括命题变元、联结词和括号的符号串是公式。例如，下面的符号串都是公式：∧Q）?R）∨S）?）∧R以下符号串都不是公式：?）1.3.2命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。命题翻译时应注意下列事项：确定所给句子是否为命题。句子中联结词是否为命题联结词。要正确的选择原子命题和合适的命题联结词。例：假如上午不下

4、雨，我去看电影，否则就在家里读书或看报。解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本例可表示为：∧）。1.3.3命题公式的解释定义设P1，P2，…，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，…，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI。例如，是G的一个解释，在这个解释下G的真值为1，即TI=1。1.4真值表与等价公式1.4.1真值表定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。构造真值表的方法如下：找出公式G中

5、的全部命题变元，并按一定的顺序排列成P1，P2，…，Pn。列出G的2n个解释，赋值从00…0开始，按二进制递加顺序依次写出各赋值，直到11…1为止，然后从低到高的顺序列出G的层次。根据赋值依次计算各层次的真值并最终计算出G的真值。定义设G为公式：如果G在所有解释下取值均为真，则称G是永真式或重言式；如果G在所有解释下取值均为假，则称G是永假式或矛盾式；如果至少存在一种解释使公式G取值为真，则称G是可满足式。1.4.3等价公式定义设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式

6、。记为A?B。性质定理设A、B、C是公式，则A?A若A?B则B?A若A?B且B?C则A?C定理设A、B、C是公式，则下述等价公式成立：双重否定律??A?A等幂律A∧A?A；A∨A?A交换律A∧B?B∧A；A∨B?B∨A结合律∧C?A∧∨C?A∨分配律∨C?∧∧C?∨德·摩根律???A∧?B???A∨?B吸收律A∨?A；A∧?A零一律A∨1?1；A∧0?0同一律A∨0?A；A∧1?A排中律A∨?A?1矛盾律A∧?A?0蕴涵等值式A→B??A∨B假言易位A→B??B→?A等价等值式A?B?∧等价否定等值式A?B??A?

7、?B??B??A归缪式∧??A1.4.4置换规则定理设?是一个含有子公式A的命题公式，?是用公式B置换了?中的子公式A后得到的公式，如果A?B，那么???。1.5对偶与范式1.5.1对偶定义在仅含有联结词?、∧、∨的命题公式A中，将联结词∧换成∨，将∨换成∧，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。例：公式∧的对偶式为：∨定理设A和A*互为对偶式，P1，P2，…，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则?A?A*A??A*定理设A、B是两个

8、命题公式，若A?B，则A*?B*，其中A*、B*分别为A、B的对偶式。1.5.2范式定义仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。定义仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。定理任何命题公式都存在着与之等价的析取范式和合取范式。1.5.3主范