离散数学(贾振华主编) 第一章

《离散数学(贾振华主编) 第一章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学21世纪高职高专新概念教材中国水利水电出版社贾振华主编1第1章命题逻辑1.1命题及其表示法1.2命题联结词1.3命题公式、翻译与解释1.4真值表与等价公式1.5对偶与范式1.6公式的蕴涵1.7其它联结词与最小联结词组1.8命题逻辑推理理论21.1命题及其表示法1.1.1命题的概念数理逻辑将能够判断真假的陈述句称作命题。1.1.2命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大

2、学生。R：我是一名大学生。31.2命题联结词1.2.1否定联结词1.2.2合取联结词1.2.3析取联结词1.2.4条件联结词1.2.5双条件联结词1.2.6与非联结词1.2.7或非联结词41.2联结词1.2.1否定联结词﹁PP﹁P0110PQP∧Q0000101001111.2.3析取联结词∨PQP∨Q0000111011111.2.2合取联结词∧51.2联结词PQP→Q0010111001111.2.4条件联结词→1.2.5双条件联结词PQPQ00101010011161.2联结词1.2.6与

3、非联结词↑PQP↑Q001011101110性质：（1）P↑P﹁（P∧P）﹁P；（2）（P↑Q）↑（P↑Q）﹁（P↑Q）P∧Q；（3）（P↑P）↑（Q↑Q）﹁P↑﹁QP∨Q。71.2联结词1.2.7或非联结词↓PQP↓Q001010100110性质：（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。81.3命题公式、翻译与解释1.3.1命题公式1.3.2命题的翻译1.3.3命题公式的解

4、释91.3命题公式、翻译与解释1.3.1命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、PQ、PQ都是公式；（4）当且仅当能够有限次的应用(1)、(2)、(3)所得到的包括命题变元、联结词和括号的符号串是公式。101.3命题公式、翻译与解释1.3.1命题公式例如，下面的符号串都是公式：（（（（﹁P）∧Q）R）∨S）（（P﹁Q）（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）（∧Q

5、））（∧Q）111.3命题公式、翻译与解释1.3.2命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。命题翻译时应注意下列事项：（1）确定所给句子是否为命题。（2）句子中联结词是否为命题联结词。（3）要正确的选择原子命题和合适的命题联结词。121.3命题公式、翻译与解释1.3.2命题的翻译解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本例可表示为：（PQ）∧（P（R∨S））。例：假如上午不下雨，我去看电影，否则就在家里读书或看报。131

6、.3命题公式、翻译与解释1.3.3命题公式的解释定义设P1，P2，…，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，…，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。例如，G=（P∧Q）R，则I：PQR110是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。141.4真值表与等价公式1.4.1真值表1.4.2命题公式的分类1.4.3等价公式1.4.4置换规则151.4真值表与等价公式1.4.1真值表定义将公式G在其所有解释下所取得的

7、真值列成一个表，称为G的真值表。构造真值表的方法如下：（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，Pn。（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…0为止），然后从低到高的顺序列出G的层次。（3）根据赋值依次计算各层次的真值并最终计算出G的真值。161.4真值表与等价公式1.4.1真值表例：G=（P→Q）∧QpQP→Q（P→Q）（P→Q）∧Q001000

8、11001001011100171.4真值表与等价公式1.4.2命题公式的分类定义设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。181.4真值表与等价公式1.4.3等价公式定义设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为AB。性质：定理设A、B、C是公式，则（1）AA（