离散数学15,16资料

《离散数学15,16资料》由会员分享，可在线阅读，更多相关《离散数学15,16资料（58页珍藏版）》请在金锄头文库上搜索。

1、离 散 数 学 Discrete Mathematics,陈明 Email:mingchen_gang,信息科学与工程学院,二零一三年九月,课程回顾,第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

3、。 10个命题定律。,PQ PQ,表1-4.8,化简如下语句： “情况并非如此：若他不来，则我不去”。,解：首先符号化上述语句。 设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、4,表 1-4.2,重言式和矛盾式这两类特殊的命题公式在今后的命题演算中极为有用。 定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。,定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。,证明 由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为T。,定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。,证明 设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故ABT，ABT。,定理1-

5、5.1 任何两个重言式的合取或析取，仍然是一个重言式。,对于矛盾式也有类似于定理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当

7、且仅当A B为一个重言式。 证明 若AB，则A、B有相同真值，即A B永为T。 若A B为重言式，则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 证明 列出真

8、值表： 从表中看出PPQ是一个重言式，故P PQ成立。,证明 列出真值表： 从表中看出PQP 不是一个重言式，故 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）只要对

9、条件命题PQ的前件P，指定真值为T，若由此推出Q的真值也为T，则PQ是重言式，即P Q成立(前真看后真)； （2）同理，如条件命题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 常用的蕴含式,就象联结词 和的关系一样，等价

10、式与蕴含式之间也有紧密的联系。 定理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。 这个定理也可作为两个公式等价的定义。,三、等价式和蕴含式的关系,蕴含有下面几个常用的性质： (1)设A、B、C为合式公式，若A B且A是重言式，则B必是重言式。 证明 因为AB永为T，所以，当A为T时，B必永为T。 (2)若A B，且B C则A C，即蕴含关系是传递的。 证明 由A B，

11、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 B，则AC B。 证明 因为AB为T，CB为T，故(AB)(CB)为T。 即(AC)B)为T或ACB为T。 所以 AC B,重点掌握 1、重言式、蕴含式定义 2、蕴含式的证明 3、常用的蕴含式,前面已经定义了5种

12、联结词：，和 ，但这些联结词还不能广泛地直接表达命题间的联系，下面再定义4种命题联结词：,1-6 其他联结词,一、不可兼析取（异析取）,表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)

13、 PP P (c) (PQ)(PQ)PQ (d) (PP)(QQ)PQ,表1-6.4,从表1-6.4可以看出,2. 真值表,1. 定义,四、或非,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 （定

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