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

离散数学DiscreteMathematics,1,课程回顾,第1次课：命题；5个联结词第2次课：命题的翻译命题公式等价的两种证明方法真值表利用命题定律推导,2,合式公式：命题演算的合式公式(wff)规定为：(1)单个命题变元本身是一个合式公式。(2)如果A是合式公式，那么A是合式公式。(3)如果A和B是合式公式，那么(AB)，(AB)，(AB）和(AB)都是合式公式。(4)当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元，联结词和括号的符号串是合式公式。翻译把自然语言中的有些语句，翻译成数理逻辑中的符号形式。优先次序规定联结词运算的优先次序为：、,真值表在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。逻辑相等给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作AB。子公式如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。定理1-4.1设X是合式公式A的子公式，若XY，如果将A中的X用Y来置换，所得到公式B与公式A等价，即AB。10个命题定律。,PQPQ,表1-4.8,化简如下语句：“情况并非如此：若他不来，则我不去”。,解：首先符号化上述语句。设P：他来。Q：我去则原句：（PQ）然后化简上述命题公式（PQ）（PQ）PQ即：我去了，但他未来。,P：上午下雨，Q：我去看电影，R：我在家看书；S：我在家看报。（PQ）（P（RS）,P12：（7）a）,1-5重言式与蕴含式1-6其他联结词,一、重言式和矛盾式从上节真值表和命题的等价公式推证中可以看到，有些命题公式，无论对分量作何种指派，其对应的真值都为T（见14页表1-4.4）或都为F（见13页表1-4.2）。,表1-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.1任何两个重言式的合取或析取，仍然是一个重言式。,对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果。,例题1证明(PS)R)V(PS)R)为重言式。,证明因为PVPT，如以(PS)R)置换P即得(PS)R)V(PS)R)T,重点将研究重言式，因为重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。重言式最有用，它有以下特点：两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。,给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为可满足式。重言式必是可满足式，反之一般不真。判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。,证明重言式的方法,定理1-5.3设A、B为两个命题公式，AB当且仅当AB为一个重言式。证明若AB，则A、B有相同真值，即AB永为T。若AB为重言式，则AB永为T，故A、B的真值相同，即AB。,定理1-5.3的作用：为AB又提供了一种方法。其他方法：（1）真值表法（2）利用命题定律推导证明,定理1-5.3设A、B为两个命题公式，AB当且仅当AB为一个重言式。证明若AB，则A、B有相同真值，即AB永为T。若AB为重言式，则AB永为T，故A、B的真值相同，即AB。,例题2证明(PQ）（PQ）,证明：据定理1-5.3，只需证：(PQ）（PQ）为重言式。,联结词可用来表达。由第4节例题5可知：AB(AB)(BA)下面讨论AB的重言式。1.定义定义1-5.3当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作PQ。,二、蕴含式,2.蕴含式的证明方法：(1)列真值表法：根据定义，只需证PQ是重言式(2)逻辑推论前真看后真后假看前假(3)等价置换,例题3证明PPQ证明列出真值表：从表中看出PPQ是一个重言式，故PPQ成立。,证明列出真值表：从表中看出PQP不是一个重言式，故PQP不成立。,例题4考察PQP是否成立。,由例题3和例题4可知，PQ和QP不等价。对PQ来说，QP称作它的逆换式；PQ称为它的反换式；QP称为它的逆反式。,它们之间的关系如表所示。,表1-5.1,从表1-5.1中看出：(PQ）（QP）(QP）（PQ）因此要证明PQ，只需证明QP，反之亦然。要证明PQ，即证PQ是重言式。对于PQ来说，除P的真值取T，Q的真值取F这样一种指派时，PQ的真值为F外，其余情况，PQ的真值为T。要证PQ是重言式：（1）只要对条件命题PQ的前件P，指定真值为T，若由此推出Q的真值也为T，则PQ是重言式，即PQ成立(前真看后真)；（2）同理，如条件命题PQ中，假定后件Q的真值取F，若由此推出P的真值为F，即推证了QP故PQ成立(后假看前假)。,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的充分必要条件是PQ且QP。,证明若PQ，则PQ为重言式，因为PQ(PQ)(QP)，故PQ为T且QP为T，即PQ，QP成立。反之，若PQ且QP，则PQ为T且QP为T，因此PQ为T，PQ是重言式，即PQ。这个定理也可作为两个公式等价的定义。,三、等价式和蕴含式的关系,蕴含有下面几个常用的性质：(1)设A、B、C为合式公式，若AB且A是重言式，则B必是重言式。证明因为AB永为T，所以，当A为T时，B必永为T。(2)若AB，且BC则AC，即蕴含关系是传递的。证明由AB，BC，即AB，BC为重言式。所以(AB)(BC)为重言式。由表l-5.2的(11)式，(AB)(BC)AC，故由性质(1)，AC为重言式，即AC。,(3)若AB，且AC，则A(BC)。证明由假设AB，AC为重言式。设A为T，则B、C为T，故BC为T。因此，A(BC)为T。若A为F，则BC不论有怎样的真值，A(BC)为T。所以，A(BC)(4)若AB，且CB，则ACB。证明因为AB为T，CB为T，故(AB)(CB)为T。即(AC)B)为T或ACB为T。所以ACB,重点掌握1、重言式、蕴含式定义2、蕴含式的证明3、常用的蕴含式,前面已经定义了5种联结词：，和，但这些联结词还不能广泛地直接表达命题间的联系，下面再定义4种命题联结词：,1-6其他联结词,一、不可兼析取（异析取）,表1-6.1,从真值表看与双条件的关系,4.定理,证明,则,定义定义1-6.2设P和Q是两个命题公式，复合命题PQ称作命题P和Q的条件否定，PQ的真值为T，当且仅当P的真值为T，Q的真值为F，否则的PQ的真值为F。,表1-6.2,2.真值表联结词的定义如表1-6.2所示。,从定义可知,二、条件否定,定义,表1-6.3,2.真值表,从表1-6.3可以看出,2、真值表,三、与非,3.性质,联结词“”有如下几个性质：(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ,表1-6.4,从表1-6.4可以看出,2.真值表,1.定义,四、或非,3.性质,联结词“”有如下几个性质：(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ,五、联结词完备集定义设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。,定理：，都是联结词完备集。,证已知,为联结词完备集，因而只需证明其中的每个联结词都可以由定义即可。,而ppq(pp)(pq)pp(1)(pq)(2)pq（定义）(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，并记作PQ。逆换式对PQ来说，QP称作它的逆换式。反换式对PQ来说，PQ称为它的反换式。逆反式对PQ来说，QP称为它的逆反式。,不可兼析取设P和Q是两个命题公式，复合命题称作P和Q的不可兼析取。的真值为T，当且仅当P与Q的真值不同时为T，否则的真值为F。条件否定设P和Q是两个命题公式，复合命题PQ称作命题P和Q的条件否定，PQ的真值为T，当且仅当P的真值为T，Q的真值为F，否则的PQ的真值为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，并记作PQ。逆换式对PQ来说，QP称作它的逆换式。反换式对PQ来说，PQ称为它的反换式。逆反式对PQ来说，QP称为它的逆反式。,不可兼析取设P和Q是两个命题公式，复合命题称作P和Q的不可兼析取。的真值为T，当且仅当P与Q的真值不同时为T，否则的真值为F。条件否定设P和Q是两个命题公式，复合命题PQ称作命题P和Q的条件否定，PQ的真值为T，当且仅当P的真值为T，Q的真值为F，否则的PQ的真值为F。与非设P和Q是两