离散数学第1章重言式与蕴含式和其它连接词

1、1,离 散 数 学 discrete mathematics,2,为什么要学习离散数学？,李开复：给中国学生的第四封信大学四年应该这么度过 数学是理工科学生必备的基础。很多学生在高中时认为数学是最难学的，到了大学里，一旦发现本专业对数学的要求不高，就会彻底放松对数学知识的学习，而且他们看不出数学知识有什么现实的应用或就业前景。但大家不要忘记，绝大多数理工科专业的知识体系都建立在数学的基石之上。例如，要想学好计算机工程专业，那至少要把离散数学（包括集合论、图论、数理逻辑等）、线性代数、概率统计和数学分析学好；要想进一步攻读计算机科学专业的硕士或博士学位，可能还需要更高的数学素养。,3,课程回顾,

2、第1次课： 命题；5个联结词 第2次课： 合式公式 命题的翻译 命题公式等价的两种证明方法 真值表 利用命题定律推导,第一章 命题逻辑 第3讲15 重言式与蕴含式 16 其他连结词,重点：重言式、蕴含式 难点：用推理方法证明蕴含式。,5,回顾,表1-4.4,6,回顾,表 1-4.2,7,一、重言式和矛盾式 定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为t，则称该命题公式为重言式或永真公式。,定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为f，则称该命题公式为矛盾式或永假公式。,对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果。,证明

3、 由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为t。 口,定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。,证明 设a和b为两个重言式，则不论a和b的分量指派任何真值，总有a为t，b为t，故abt，abt。 口,定理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式。,因为重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了，后面将重点研究重言式。重言式最有用，因为它有以下特点： 两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。 由重言式使用公认的规则

4、可以产生许多有用等价式和蕴涵式。,10,证明重言式的方法,给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为可满足式。 重言式必是可满足式，反之一般不真。 判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。 在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。,例题1 证明(ps)r)v(ps)r)为重言式。,证明 因为pvpt， 如以(ps)r)置换p即得 (ps)r)v(ps)r) t,定理1-5.3 设a、b为两个命题公式，a b当且仅当a b为一个重言式。 证明 若ab，则a、b有相

5、同真值，即a b永为t。 若a b为重言式，则a b永为t，故a、b的真值相同，即ab。,定理1-5.3的作用：为a b又提供了一种方法。 其他方法： （1）真值表法 （2）利用命题定律推导证明,13,例题2 证明(pq）（pq）,证明：据定理1-5.3 ，只需证：(pq） （pq）为重言式。,二、蕴含式 联结词 可用来表达。由第4节例题5可知： a b (ab)(ba) 下面讨论ab的重言式。 1.定义 定义1-5.3 当且仅当pq是一个重言式时，我们称“p蕴含q”，并记作p q。,符号和的区别与联系类似于和的关系。区别： 是逻辑联结词，属于对象语言中的符号，是公式中的符号； 不是联结词，属

6、于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。,2. 蕴含式的证明方法： (1)列真值表法： 根据定义， 只需证pq是重言式 (2)逻辑推论 前真看后真 后假看前假 (3)等价置换,例题3 证明p pq 证明 列出真值表： 从表中看出ppq是一个重言式，故p pq成立。,证明 列出真值表： 从表中看出pqp 不是一个重言式，故 pq p不成立。,例题4 考察pq p是否成立。,由例题3和例题4可知，pq和qp不等价。 对pq来说， qp称作它的逆换式； pq称为它的反换式； qp称为它的逆反式。 它们之间的关系如表所示。,从表1-5.1中看出：(pq）（qp） (qp）（pq）

7、因此要证明p q，只需证明q p，反之亦然。 要证明p q，即证pq是重言式。 对于pq来说，除p的真值取t，q的真值取f这样一种指派时，pq的真值为f外，其余情况，pq的真值为t。 要证pq是重言式： （1）只要对条件命题pq的前件p，指定真值为t，若由此推出q的真值也为t，则pq是重言式，即p q成立(前真看后真)； （2）同理，如条件命题pq中，假定后件q的真值取f，若由此推出p的真值为f，即推证了q p 故p q成立(后假看前假)。,例题1 推证q(pq） p,证法2 (后假看前假) 假定p为f，则p为t。 (a）：若q为f，则pq为f，q(pq）为f。 (b）：若q为t，则q为f，q

8、(pq）为f。 所以q(pq) p成立。,证法1 (前真看后真) 假定q(pq）为t，则q为t，且(pq）为t。由q为f，则必须p为f，故p为t。,表 1-5.2 常用的蕴含重言式,三、等价式和蕴含式的关系 就象联结词 和的关系一样，等价式与蕴含式之间也有紧密的联系。 定理1-5.4 设p、q为任意两个命题公式，pq的充分必要条件是p q且q p。,证明 若pq，则p q为重言式，因为 p q (pq)(qp)，故pq为t且qp为t，即p q，q p成立。反之，若p q且q p，则，pq为t且qp为t，因此p q为t，p q是重言式，即pq。 这个定理也可作为两个公式等价的定义。,蕴含有下面几

9、个常用的性质： (1)设a、b、c为合式公式，若a b且a是重言式，则b必是重言式。 证明 因为ab永为t，所以，当a为t时，b必永为t。 (2)若a b，且b c则a c，即蕴含关系是传递的。 证明 由a b，b c，即ab，bc为重言式。所以(ab)(bc)为重言式。 由表l-5.2的(11)式，(ab)(bc) ac，故由性质(1)，ac为重言式，即a c。,(3)若a b，且a c，则a (bc)。 证明 由假设ab，ac为重言式。设a为t，则b、c为t，故bc为t。因此，a(bc)为t。 若a为f，则bc不论有怎样的真值，a(bc)为t。 所以， a (bc) (4)若a b，且c

10、b，则ac b。 证明 因为ab为t，cb为t，故(ab)(cb)为t。 即(ac)b)为t或acb为t。 所以 ac b,四、小结 本节主要内容 1. 深刻理解以下概念 重言式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为t，则称该命题公式为重言式或永真公式。 矛盾式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为f，则称该命题公式为矛盾式或永假公式。 蕴含式 当且仅当pq是一个重言式时，称p蕴含q，并记作p q。 逆换式 对pq来说，qp称作它的逆换式。 反换式 对pq来说， pq称为它的反换式。 逆反式 对pq来说， qp称为它的逆反式。,2. 掌握以下定理 定

11、理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式。 定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。 定理1-5.3 设a、b为两个命题公式，a b当且仅当a b为一个重言式。 定理1-5.4 设p、q为任意两个命题公式，p q的充分必要条件是p q且q p。 3. 会证明重言式、蕴含式,28,前面已经定义了5种联结词：，和 ，但这些联结词还不能广泛地直接表达命题间的联系，下面再定义4种命题联结词：,16 其他连结词,29,一、不可兼析取（异析取）,表1-6.1,30,31,4. 定理,证明,则,32,二、条件否定 定义 定义1-6.2 设p和q是两个

12、命题公式，复合命题p q称作命题p和q的条件否定，p q的真值为t，当且仅当p的真值为t，q的真值为f，否则的p q的真值为f。,表1-6.2,2. 真值表 联结词 的定义如表1-6.2所示。,从定义可知,33,三、与非 定义,表1-6.3,2. 真值表,从表1-6.3 可以看出,2、真值表,34,3. 性质,联结词“”有如下几个性质： (a) pqqp (b) pp p (c) (pq)(pq)pq (d) (pp)(qq)pq,35,表1-6.4,从表1-6.4可以看出,2. 真值表,1. 定义,四、或非,36,3. 性质,联结词“”有如下几个性质： (a) pqqp (b) ppp (c

13、) (pq)(pq)pq (d) (pp)(qq)pq,37,38,五、联结词完备集 定义 设s是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含s中的联结词构成的公式表示，则称s是联结词完备集。 根据需要，人们还可构造形式上更为简单的联结词完备集。例如，在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。,39,定理： ，都是联结词完备集。,证 已知,为联结词完备集，因而只需证明其中的每个联结词都可以由定义即可。,而 p pq (pp) ( pq) pp (1) (pq) pq （定义） (pp)(qq)由(1) (3) pq ( pq) ( pq) （

14、定义） (pq)(pq) 由(1)(2),由（1）(3)可知是联结词完备集，类似可证是联结词完备集。,40,五、最小联结词组 我们一共给出了九个联结词的定义，是否还需要定义其他联结词呢？下面列出两个命题变元可构成的所有不等价的命题公式（共有16个）。,41,由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了。,42,实际上这九个联结词并非都是必要的。因为包含某些联结词的公式可以用另外一些联结词的公式等价代换。 下面考虑最小联结词组，对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。,43,所以,44,六、小结 本节所讲内容如下： 不可兼析取 设p和q是两个命题公式，复合

15、命题 称作p和q的不可兼析取。 的真值为t，当且仅当p与q的真值不同时为t，否则 的真值为f。 逆条件 设p和q是两个命题公式，复合命题p q 称作命题p和q的条件否定，p q的真值为t，当且仅当p的真值为t，q的真值为f，否则的p q的真值为f。 与非 设p和q是两个命题公式，复合命题 称作命题p和q的“与非”，当且仅当p和q真值都是t时， 为f，否则 的真值都为t。 或非 设p和q是两个命题公式，复合命题 称作命题p和q的“或非”，当且仅当p和q的真值都为f时， 的真值为t，否则 的真值都为f。,45,作业,p23：2.a)(3种方法)，8 p29：3,46,离 散 数 学 discret

16、e mathematics,山东科技大学 信息科学与工程学院,第一章 命题逻辑第4讲17 对偶与范式,要求：掌握对偶与范式，会求命题公式的主析取范式和主合取范式。 重点和难点：求命题公式的主析取范式和主合取范式。,一、对偶式 1. 复习命题定律。见15页表1-4.8,我们从表1-4.8可以看到命题定律除对合律外都是成对出现的，其不同的只是和互换。我们把这样的公式称作具有对偶规律。 定义1-7.1 在给定的命题公式中，将联结词换成，将换成 ，若有特殊变元f和t亦相互取代，所得公式a*称作a的对偶式。 显然a也是a*的对偶式。,2. 对偶式的定义,例题1 写出下列表达式的对偶式。,(p q) r

17、(p q) f (p q) (p (q s),（a）(pq) r （b）(pq) t （c）(p q) (p (q s),a,a*,定理1-7.1 设a和a*是对偶式，p1， p2 ，pn是出现在a和a*中的原子变元，则 a（ p1， p2 ，pn ） a*（ p1， p2 ，pn ） a（ p1， p2 ，pn ） a*（ p1， p2 ，pn ）,证明 由德摩根定律 (pq) (p q)， p q (p q) 故 a（ p1， p2 ，pn ） a*（ p1， p2 ，pn ） 同理 a*（ p1， p2 ，pn ） a（ p1， p2 ，pn ）,例题3 设a*（s，w，r）是 s (w r) ，证明 a*（s， w， r） a（s，w，r）,.所以 a*（s， w， r） a（s，w，r）,证明 由于a*（s，w，r）是 s (w r) ，,则 a*（s， w， r）是 s (w