离散数学笔记

《离散数学笔记》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、范式的求法2．逻辑推理1.1命题及其表示法1.1.1命题的概念数理逻辑将能够判断真假的陈述句称作命题。1.1.2命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。1.2命题联结词1.2.1否定联结词﹁P01101.2.2合取联结词∧00001010011146离散数学教案1.2.3析取联结词∨0000111011111.2.4条件联结词→0010111001111.2.

3、5双条件联结词0010101001111.2.6与非联结词↑001011101110性质：（1）P↑P﹁（P∧P）﹁P；（2）（2）（P↑Q）↑（P↑Q）﹁（P↑Q）P∧Q；（3）（P↑P）↑（Q↑Q）﹁P↑﹁QP∨Q。1.2.7或非联结词↓001010100110性质：（1）P↓P﹁（P∨Q）﹁P；（2）（P↓Q）↓（P↓Q）﹁（P↓Q）P∨Q；（3）（P↓P）↓（Q↓Q）﹁P↓﹁Q﹁（﹁P∨﹁Q）P∧Q。46离散数学教案1.3命题公式、翻译与解释1.3.1命题公式定义命题公式，简称公式，定义为：（1）单个

4、命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、PQ、PQ都是公式；（4）当且仅当能够有限次的应用(1)、(2)、(3)所得到的包括命题变元、联结词和括号的符号串是公式。例如，下面的符号串都是公式：（（（（﹁P）∧Q）R）∨S）（（P﹁Q）（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）（∧Q））（∧Q）1.3.2命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。命题翻译时应注意下列事项：（1）确定所给句子是否为命题。

5、（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。例：假如上午不下雨，我去看电影，否则就在家里读书或看报。解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本例可表示为：（PQ）∧（P（R∨S））。1.3.3命题公式的解释定义设P1，P2，…，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，…，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。例如，G=（P∧Q）R，则I：110是G的一个解释，在这个解释下G

6、的真值为1，即TI（G）=1。1.4真值表与等价公式1.4.1真值表定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。构造真值表的方法如下：（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，Pn。（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…046离散数学教案为止），然后从低到高的顺序列出G的层次。（3）根据赋值依次计算各层次的真值并最终计算出G的真值。例：G=

7、（P→Q）∧Q001000110010010111001.4.2命题公式的分类定义设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。1.4.3等价公式定义设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为AB。性质定理设A、B、C是公式，则（1）AA（2）若AB则BA（3）若AB且BC则AC定理设A、B、C是公式，则下述等价

8、公式成立：（1）双重否定律AA（2）等幂律A∧AA；A∨AA（3）交换律A∧BB∧A；A∨BB∨A（4）结合律（A∧B）∧CA∧（B∧C）（A∨B）∨CA∨（B∨C）（5）分配律（A∧B）∨C（A∨C）∧（B∨C）（A∨B）∧C（A∧C）∨（B∧C）（6）德·摩根律（A∨B）A∧B（A∧B）A∨B（7）吸收律A∨（A∧B）A；A∧（A∨B）A（8）零一律A∨11；A∧00（9）同一律A∨0A；A∧1