离散数学1-5,1-6.ppt

1、离 散 数 学 Discrete Mathematics,信息科学与工程学院,二零一三年九月,课程回顾,第1次课： 命题；5个联结词 第2次课： 命题的翻译 命题公式等价的两种证明方法 真值表 利用命题定律推导,合式公式：命题演算的合式公式(wff) 规定为： (1)单个命题变元本身是一个合式公式。 (2)如果A是合式公式，那么A是合式公式。 (3)如果A和B是合式公式，那么(AB)，(AB)，(AB）和(A B)都是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元，联结词和括号的符号串是合式公式。 翻译 把自然语言中的有些语句，翻译成数理逻辑中的符号形式。

2、 优先次序 规定联结词运算的优先次序为：,真值表 在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。 逻辑相等 给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作A B。 子公式如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。 定理1-4.1 设X是合式公式A的子公式，若X Y，如果将A中的X用Y来置换，所得到公式B与公式A等价，即A B。 10个命题定律,PQ PQ,表1-4.8,化

3、简如下语句： “情况并非如此：若他不来，则我不去,解：首先符号化上述语句。 设P：他来。Q：我去 则原句：（PQ） 然后化简上述命题公式 （PQ） （ P Q ） P Q 即：我去了，但他未来,P：上午下雨，Q：我去看电影，R：我在家看书；S：我在家看报。 （P Q） （P （R S,P12：（7）a,1-5 重言式与蕴含式 1-6 其他联结词,一、重言式和矛盾式 从上节真值表和命题的等价公式推证中可以看到，有些命题公式，无论对分量作何种指派，其对应的真值都为T （见14页表1-4.4）或都为F（见13页表1-4.2,表1-4.4,表 1-4.2,重言式和矛盾式这两类特殊的命题公式在今后的命题

4、演算中极为有用。 定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式,定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式,证明 由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为T,定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式,证明 设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故ABT，ABT,定理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式,对于矛盾式也有类似于定

5、理1-5.1和定理1-5.2的结果,例题1 证明(PS)R)V(PS)R)为重言式,证明 因为PVPT， 如以(PS)R)置换P即得 (PS)R)V(PS)R) T,重点将研究重言式，因为重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。 重言式最有用，它有以下特点： 两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。 由重言式使用公认的规则可以产生许多有用等价式和蕴涵式,给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为可满足式。重言式必是可满足式，反之一般不真。判定给定公式是否为永真式、永假式或可满足式的问题，称

6、为给定公式的判定问题。在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法,证明重言式的方法,定理1-5.3 设A、B为两个命题公式，A B当且仅当A B为一个重言式。 证明 若AB，则A、B有相同真值，即A B永为T。 若A B为重言式，则A B永为T，故A、B的真值相同，即AB,定理1-5.3的作用：为A B又提供了一种方法。 其他方法： （1）真值表法 （2）利用命题定律推导证明,定理1-5.3 设A、B为两个命题公式，A B当且仅当A B为一个重言式。 证明 若AB，则A、B有相同真值，即A B永为T。 若A B为重言

7、式，则A B永为T，故A、B的真值相同，即AB,例题2 证明(PQ）（PQ,证明：据定理1-5.3 ，只需证：(PQ） （PQ）为重言式,联结词 可用来表达。由第4节例题5可知： A B (AB)(BA) 下面讨论AB的重言式。 1.定义 定义1-5.3 当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作P Q,二、蕴含式,2. 蕴含式的证明方法： (1)列真值表法： 根据定义， 只需证PQ是重言式 (2)逻辑推论 前真看后真 后假看前假 (3)等价置换,例题3 证明P PQ 证明 列出真值表： 从表中看出PPQ是一个重言式，故P PQ成立,证明 列出真值表： 从表中看出PQP 不是一个重

8、言式，故 PQ P不成立,例题4 考察PQ P是否成立,由例题3和例题4可知，PQ和QP不等价。 对PQ来说， QP称作它的逆换式； PQ称为它的反换式； QP称为它的逆反式,它们之间的关系如表所示,表1-5.1,从表1-5.1中看出：(PQ）（QP） (QP）（PQ） 因此要证明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

9、）同理，如条件命题PQ中，假定后件Q的真值取F，若由此推出P的真值为F，即推证了Q P 故P Q成立(后假看前假,P21页例题1 推证Q(PQ） P,证法2 (后假看前假) 假定P为F，则P为T。 (a）：若Q为F，则PQ为F，Q(PQ）为F。 (b）：若Q为T，则Q为F，Q(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,证明 若

10、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。 这个定理也可作为两个公式等价的定义,三、等价式和蕴含式的关系,蕴含有下面几个常用的性质： (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，故由性质(

11、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 B，则AC B。 证明 因为AB为T，CB为T，故(AB)(CB)为T。 即(AC)B)为T或ACB为T。 所以 AC B,重点掌握 1、重言式、蕴含式定义 2、蕴含式的证明 3、常用的蕴含式,前面已经定义了5种联结词：，和 ，但这些联结词还不能广泛地直接表达命题间的联系，下面再定义4种命题联结词,1-6 其他联结词,一、不可兼析取（异析

12、取,表1-6.1,从真值表看与双条件的关系,4. 定理,证明,则,定义 定义1-6.2 设P和Q是两个命题公式，复合命题P Q称作命题P和Q的条件否定，P Q的真值为T，当且仅当P的真值为T，Q的真值为F，否则的P Q的真值为F,表1-6.2,2. 真值表 联结词 的定义如表1-6.2所示,从定义可知,二、条件否定,定义,表1-6.3,2. 真值表,从表1-6.3 可以看出,2、真值表,三、与非,3. 性质,联结词“”有如下几个性质： (a) PQQP (b) PP P (c) (PQ)(PQ)PQ (d) (PP)(QQ)PQ,表1-6.4,从表1-6.4可以看出,2. 真值表,1. 定义,

13、四、或非,3. 性质,联结词“”有如下几个性质： (a) PQQP (b) PP P (c)(PQ)(PQ)PQ (d) (PP)(QQ)PQ,五、联结词完备集 定义 设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集,定理： ，都是联结词完备集,证 已知,为联结词完备集，因而只需证明其中的每个联结词都可以由定义即可,而 p pq (pp) ( pq) pp (1) (pq) (2) pq （定义） (pp)(qq)由(1) pq ( pq) ( pq) （定义） (3) (pq)(pq) 由(1,由（1）(3)可知是联结词完备集，类

14、似可证是联结词完备集,六、最小联结词组 我们一共给出了九个联结词的定义，是否还需要定义其他联结词呢？下面列出两个命题变元可构成的所有不等价的命题公式（共有16个,由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了,实际上这九个联结词并非都是必要的。因为包含某些联结词的公式可以用另外一些联结词的公式等价代换。 下面考虑最小联结词组，对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换,所以,常用联结词组,作业,P23：2.a), b)(3种方法：真值表法，前真看后真，后假看前假) P29：5,回顾 重言式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命

15、题公式为重言式或永真公式。 矛盾式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。 蕴含式 当且仅当PQ是一个重言式时，称P蕴含Q，并记作P Q。 逆换式 对PQ来说，QP称作它的逆换式。 反换式 对PQ来说， PQ称为它的反换式。 逆反式 对PQ来说， QP称为它的逆反式,不可兼析取 设P和Q是两个命题公式，复合命题 称作P和Q的不可兼析取。 的真值为T，当且仅当P与Q的真值不同时为T，否则 的真值为F。 条件否定 设P和Q是两个命题公式，复合命题P Q 称作命题P和Q的条件否定，P Q的真值为T，当且仅当P的真值为T，Q的真值为F，否则的P

16、 Q的真值为F。 与非 设P和Q是两个命题公式，复合命题 称作命题P和Q的“与非”，当且仅当P和Q真值都是T时， 为F，否则 的真值都为T。 或非 设P和Q是两个命题公式，复合命题 称作命题P和Q的“或非”，当且仅当P和Q的真值都为F时， 的真值为T，否则 的真值都为F,回顾,表 1-5.2 常用的蕴含式,由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了,回顾 重言式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。 矛盾式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。 蕴含式 当且仅当PQ是一个重言式时，称P蕴含Q，并记作P Q。 逆换式 对PQ来说，QP称作它的逆换式。 反换式 对PQ来说， PQ称为它的反换式。 逆反式 对PQ来说， QP称为它的逆反式,不可兼析取 设P和Q是两个命题公式，复合命题 称作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是两个命题