《离散数学.PPT》由会员分享，可在线阅读，更多相关《离散数学.PPT（58页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学离离 散散 数数 学学Discrete Mathematics 陈明陈明Email:mingchen_信息科学与工程学院信息科学与工程学院二零一三年九月二零一三年九月1离散数学离散数学课程回顾第第1次课：次课：命题；命题；5个联结词个联结词第第2次课：次课：命题的翻译命题的翻译命题公式等价的两种证明方法命题公式等价的两种证明方法真值表真值表利用命题定律推导利用命题定律推导2离散数学离散数学合式公式合式公式：命题演算的合式公式：命题演算的合式公式(wff) 规定为：规定为： (1)单个命题变元本身是一个合式公式。单个命题变元本身是一个合式公式。 (2)如果如果A是合式公式，那么是
2、合式公式，那么A是合式公式。是合式公式。 (3)如果如果A和和B是合式公式，那么是合式公式，那么(AB)，(AB)，(AB）和和(A B)都是合式公式。都是合式公式。 (4)当且仅当能够有限次地应用当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命所得到的包含命题变元，联结词和括号的符号串是合式公式。题变元，联结词和括号的符号串是合式公式。 翻译翻译 把自然语言中的有些语句，翻译成数理逻辑中的把自然语言中的有些语句，翻译成数理逻辑中的符号形式。符号形式。 优先次序优先次序 规定联结词运算的优先次序为：规定联结词运算的优先次序为：、3离散数学离散数学 真值表真值表 在命题公式中，对于分
3、量指派真值的各种可能组合，就确定在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。 逻辑相等逻辑相等 给定两个命题公式给定两个命题公式A和和B，设，设P1，P2，Pn为所有出现为所有出现于于A和和B中的原子变元，若给中的原子变元，若给P1，P2，Pn任一组真值指派，任一组真值指派，A和和B的真的真值都相同，则称值都相同，则称A和和B是等价的或逻辑相等。记作是等价的或逻辑相等。记作A B。 子公式子公式如果如果X是合式公式是合式公式A的一部分，且的一部分，且X本身
4、也是一个合式公式，则本身也是一个合式公式，则称称X为公式为公式A的子公式。的子公式。 定理定理1-4.1 设设X是合式公式是合式公式A的子公式，若的子公式，若X Y，如果将，如果将A中的中的X用用Y来置换，所得到公式来置换，所得到公式B与公式与公式A等价，即等价，即A B。 10个命题定律。个命题定律。4离散数学离散数学对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7同一律PF P，PT
5、 P8零律PT T，PF F9否定律PP T，PP F10PQ PQ表表1-4.85离散数学离散数学化简如下语句：化简如下语句：“情况并非如此：若他不来，则我不去情况并非如此：若他不来，则我不去”。 6离散数学离散数学解：首先符号化上述语句。解：首先符号化上述语句。 设设P：他来。：他来。Q：我去：我去 则原句：则原句：（PQ） 然后化简上述命题公式然后化简上述命题公式 （PQ） （ P Q ） P Q即：我去了，但他未来。即：我去了，但他未来。 7离散数学离散数学 P：上午下雨，：上午下雨，Q：我去看电影，：我去看电影，R：我在家看书；：我在家看书；S：我在家看报：我在家看报。（P Q） （
6、P （R S ）P12：（：（7）a）8离散数学离散数学 1-5 重言式与蕴含式重言式与蕴含式 1-6 其他联结词其他联结词9离散数学离散数学一、重言式和矛盾式一、重言式和矛盾式 从上节真值表和命题的等价公式推证中可以看到，有从上节真值表和命题的等价公式推证中可以看到，有些命题公式，无论对分量作何种指派，其对应的真值些命题公式，无论对分量作何种指派，其对应的真值都为都为T （见（见14页表页表1-4.4）或都为）或都为F（见（见13页表页表1-4.2）。）。PQP Q(P Q)PQP Q(P Q） P QTT T F F F F TTF F T F TT TFT F T T FT TFF F
7、T T TT T表表1-4.410离散数学离散数学 表表 1-4.2 P Q PQ P(PQ）PT T T F FT F F F FF T F T FF F F T F11离散数学离散数学 重言式和矛盾式这两类特殊的命题公式在今后重言式和矛盾式这两类特殊的命题公式在今后的命题演算中极为有用。的命题演算中极为有用。 定义定义1-5.1 给定一命题公式，若无论对分量作怎样给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为的指派，其对应的真值永为T，则称该命题公式为，则称该命题公式为重言式或永真公式重言式或永真公式。定义定义1-5.2 给定一命题公式，若无论对分量作怎样给定一命题公式，若无论
8、对分量作怎样的指派，其对应的真值永为的指派，其对应的真值永为F，则称该命题公式为，则称该命题公式为矛盾式或永假公式矛盾式或永假公式。12离散数学离散数学证明证明 由于重言式的真值与分量的指派无关，故对同一分由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为量以任何合式公式置换后，重言式的真值仍永为T。 定理定理1-5.2 一个重言式，对同一分量都用一个重言式，对同一分量都用任何合式公式置任何合式公式置换换，其结果仍为一重言式。，其结果仍为一重言式。 证明证明 设设A和和B为两个重言式，则不论为两个重言式，则不论A和和B的分量指派任的分量指派任何真值，总有何真
9、值，总有A为为T，B为为T，故，故ABT，ABT。 定理定理1-5.1 任何两个重言式的合取或析取，仍然是一个重任何两个重言式的合取或析取，仍然是一个重言式。言式。对于矛盾式也有类似于定理对于矛盾式也有类似于定理1-5.1和定理和定理1-5.2的结果。的结果。13离散数学离散数学例题例题1 证明证明(PS)R)V(PS)R)为重言式。为重言式。证明证明 因为因为PVPT， 如以如以(PS)R)置换置换P即得即得 (PS)R)V(PS)R) T14离散数学离散数学 重点将研究重言式重点将研究重言式，因为重言式的否定是矛盾式，因为重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。
10、矛盾式的否定是重言式，这样只研究其一就可以了。 重言式最有用，它有以下特点：重言式最有用，它有以下特点：两重言式的合取式、析取式、条件式和双条件式等两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。杂的重言式。 由重言式使用公认的规则可以产生许多有用由重言式使用公认的规则可以产生许多有用等价式等价式和和蕴涵式蕴涵式。15离散数学离散数学给定一命题公式，至少存在一个指派，公式相应确定给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为真值为真，称为可满足式可满足式。重言式必是可满足式，反之一般不
11、真。重言式必是可满足式，反之一般不真。判定给定公式是否为永真式、永假式或可满足式的问判定给定公式是否为永真式、永假式或可满足式的问题，称为题，称为给定公式的判定问题给定公式的判定问题。在命题逻辑中，由于任何一个命题公式的指派数目总在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判是有限的，所以命题逻辑的判定问题是可解的。其判定方法有定方法有真值表法真值表法和和公式推演法公式推演法。证明重言式的方法证明重言式的方法16离散数学离散数学 定理定理1-5.3 设设A、B为两个命题公式，为两个命题公式，A B当且仅当且仅当当A B为一个重言式。为一个重言式。
12、证明证明 若若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为重言式，则为重言式，则A B永为永
13、为T，故，故A、B的真的真值相同，即值相同，即AB。 17离散数学离散数学例题例题2 证明证明(PQ）（PQ）证明：据定理证明：据定理1-5.3 ，只需证：，只需证：(PQ） （PQ）为重言式。）为重言式。PQPQ(PQ)PQPQ(PQ） （PQ）TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T18离散数学离散数学联结词联结词 可用可用来表达。由第来表达。由第4节例题节例题5可知：可知：A B (AB)(BA) 下面讨论下面讨论AB的重言式。的重言式。1.定义定义定义定义1-5.3 当且仅当当且仅当PQ是一个重言式时，我们称是一个
14、重言式时，我们称“P蕴含蕴含Q”，并记作，并记作P Q。二、蕴含式二、蕴含式19离散数学离散数学2. 蕴含式的证明方法：蕴含式的证明方法：(1)列真值表法：列真值表法：根据定义，根据定义， 只需证只需证PQ是重言式是重言式(2)逻辑推论逻辑推论前真看后真前真看后真后假看前假后假看前假(3)等价置换等价置换20离散数学离散数学 例题例题3 证明证明P PQ 证明证明 列出真值表：列出真值表： 从表中看出从表中看出PPQ是一是一个重言式，故个重言式，故P PQ成立。成立。P Q PQPPQT T T TT F T TF T T TF F F T21离散数学离散数学 证明证明 列出真值表：列出真值表
15、： 从表中看出从表中看出PQP 不是一个重言式，故不是一个重言式，故 PQ P不成立。不成立。 P Q PQPQPT T T TT F T TF T T FF F F T例题例题4 考察考察PQ P是否成立。是否成立。22离散数学离散数学由例题由例题3和例题和例题4可知，可知，PQ和和QP不等价。不等价。对对PQ来说，来说，vQP称作它的逆换式；称作它的逆换式；vPQ称为它的反换式；称为它的反换式；vQP称为它的逆反式。称为它的逆反式。23离散数学离散数学P Q PQPQ原式原式Q P 逆反式逆反式QP逆换式逆换式PQ 反换式反换式T T F F T T T TT F F T F F T TF
16、 T T F T T F FF F T T T T T T它们之间的关系如表所示。它们之间的关系如表所示。表表1-5.124离散数学离散数学从表从表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
17、，指定真值为，指定真值为T，若由此推，若由此推出出Q的真值也为的真值也为T，则，则PQ是重言式，即是重言式，即P Q成立成立(前真看后前真看后前真看后前真看后真真真真)；（2）同理，如条件命题）同理，如条件命题PQ中，假定后件中，假定后件Q的真值取的真值取F，若由，若由此推出此推出P的真值为的真值为F，即推证了，即推证了Q P 故故P Q成立成立(后假看后假看后假看后假看前假前假前假前假)。25离散数学离散数学 P21页例题页例题1 推证推证Q(PQ） P 证法证法2 (后假看前假后假看前假) 假定假定P为为F，则，则P为为T。 (a）：若）：若Q为为F，则，则PQ为为F，Q(PQ）为）为F。
18、 (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。26离散数学离散数学 表 1-5.2 常用的蕴含式 PQ P（化简律）1 PQ Q2 P PQ（附加律）3 P PQ4 Q PQ5 (PQ） P6 (PQ） Q7 P(PQ） Q（假言律）8 Q(PQ） P9 P(PQ） Q10 (PQ）(QR） PR（传递律）11 (PQ）(PR）(QR） R12 (PQ）(RS） (PR)(QS)13
19、(P Q)(Q R) (P R)1427离散数学离散数学就象联结词就象联结词 和和的关系一样，等价式与蕴含式之的关系一样，等价式与蕴含式之间也有紧密的联系。间也有紧密的联系。 定理定理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。 这个这个定理也可作为
20、两个公式等价的定义。定理也可作为两个公式等价的定义。三、等价式和蕴含式的关系三、等价式和蕴含式的关系28离散数学离散数学蕴含有下面几个常用的性质：蕴含有下面几个常用的性质： (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
21、)式，式，(AB)(BC) AC，故，故由性质由性质(1)，AC为重言式，即为重言式，即A C。29离散数学离散数学 (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
22、30离散数学离散数学重点掌握重点掌握1、重言式、蕴含式定义、重言式、蕴含式定义2、蕴含式的证明、蕴含式的证明3、常用的蕴含式、常用的蕴含式31离散数学离散数学 前面已经定义了前面已经定义了5种联结词：种联结词：，和和 ，但这些联结词还不能，但这些联结词还不能广泛地直接广泛地直接表达命题间的联表达命题间的联系，下面再定义系，下面再定义4种命题联结词：种命题联结词：1-6 其他联结词其他联结词32离散数学离散数学 P QTT FTF TFT TFF F一、不可兼析取（异析取）一、不可兼析取（异析取） 表表1-6.1从真值表看与双条件的关系从真值表看与双条件的关系33离散数学离散数学(5)(P Q)
23、 (P Q) 34离散数学离散数学4. 定理定理证明则 如果PQ R R35离散数学离散数学1.定义定义2.定义定义1-6.2 设设P和和Q是两个命题公式，复合命题是两个命题公式，复合命题P Q称作命题称作命题P和和Q的条件否定，的条件否定，P Q的真值为的真值为T，当且仅当，当且仅当P的真值为的真值为T，Q的真值为的真值为F，否则的，否则的P Q的真值为的真值为F。 PQP Q TT FTF TFT FFF F表表1-6.22. 真值表真值表联结词联结词 的定义如表的定义如表1-6.2所示。所示。从定义可知从定义可知二、条件否定二、条件否定36离散数学离散数学1.定义定义 PQTT FTF
24、TFT TFF T表表1-6.32. 真值表从表1-6.3 可以看出2、真值表、真值表三、与非三、与非37离散数学离散数学3. 性质联结词“”有如下几个性质：(a) PQQP(b) PP P(c) (PQ)(PQ)PQ(d) (PP)(QQ)PQ 38离散数学离散数学 PQTT FTF FFT FFF T表表1-6.4从表1-6.4可以看出2. 真值表真值表1. 定义定义四、或非四、或非39离散数学离散数学3. 性质性质联结词“”有如下几个性质：(a) PQQP(b) PP P(c)(PQ)(PQ)PQ(d) (PP)(QQ)PQ40离散数学离散数学41离散数学离散数学五、联结词完备集五、联结
25、词完备集定义定义 设设S S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n1)n(n1)元元真值函数都可以由仅含真值函数都可以由仅含S S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S S是是联结词完备集联结词完备集。 42离散数学离散数学定理：定理： ，都是联结词完备集。都是联结词完备集。证证 已知已知,为联结词完备集为联结词完备集，因而只需证明其中的每，因而只需证明其中的每个联结词都可以由个联结词都可以由定义即可。定义即可。 而而 p pq p pq (pp) (pp) ( pq) ( pq) pp (1) pp (1) (pq) (2) (pq) (2) pq
26、 pq （定义）（定义） (pp)(qq) (pp)(qq)由由(1) (1) pq pq ( pq) ( pq) ( pq) ( pq) （定义）（定义） (3) (3) (pq)(pq) (pq)(pq) 由由(1) (1) 由（由（1）(3)可知可知是联结词完备集，类似可证是联结词完备集，类似可证是联结词完备集。是联结词完备集。 43离散数学离散数学六、最小联结词组六、最小联结词组 我们一共给出了九个联结词的定义，是否还需要定我们一共给出了九个联结词的定义，是否还需要定义其他联结词呢？下面列出两个命题变元可构成的所义其他联结词呢？下面列出两个命题变元可构成的所有不等价的命题公式（共有有不
27、等价的命题公式（共有16个）。个）。44离散数学离散数学PQ12345678910 1112 13 14 15 16TTTFTTFFTFTFTFTFTFTFTFTFFTFTTFFTFTTFFTTFFTTFFTTFTFFTFTFFTFFFTTFTFTTFTFTFPQ永真永假PQ非P非Q合取与非析取或非若P则Q逆条件双条件不可兼析取若Q则P逆条件由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了。由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了。45离散数学离散数学实际上这九个联结词并非都是必要的。因为包含某实际上这九个联结词并非都是必要的。因为包含某些联结词的公式可以用
28、另外一些联结词的公式等价些联结词的公式可以用另外一些联结词的公式等价代换。代换。下面考虑最小联结词组，对于任何一个命题公式，下面考虑最小联结词组，对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。都能由仅含这些联结词的命题公式等价代换。 46离散数学离散数学47离散数学离散数学所以常用联结词组常用联结词组，48离散数学离散数学作业作业P23：2.a), b)(3种方法：真值表法，前真看后真，种方法：真值表法，前真看后真，后假看前假后假看前假)P29：549离散数学离散数学回顾回顾 重言式重言式 给定一命题公式，若无论对分量作怎样的指派，给定一命题公式，若无论对分量作怎样的指派，其对
29、应的真值永为其对应的真值永为T，则称该命题公式为重言式或永真公式。，则称该命题公式为重言式或永真公式。 矛盾式矛盾式 给定一命题公式，若无论对分量作怎样的指派，给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为其对应的真值永为F，则称该命题公式为矛盾式或永假公式。，则称该命题公式为矛盾式或永假公式。 蕴含式蕴含式 当且仅当当且仅当PQ是一个重言式时，称是一个重言式时，称P蕴含蕴含Q，并，并记作记作P Q。 逆换式逆换式 对对PQ来说，来说，QP称作它的逆换式。称作它的逆换式。 反换式反换式 对对PQ来说，来说， PQ称为它的反换式。称为它的反换式。 逆反式逆反式 对对PQ来说，来说，
30、QP称为它的逆反式。称为它的逆反式。50离散数学离散数学 不可兼析取不可兼析取 设设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是两个命题公式
31、，复合命题是两个命题公式，复合命题 称作命称作命题题P和和Q的的“与非与非”，当且仅当，当且仅当P和和Q真值都是真值都是T时，时， 为为F，否则，否则 的真值都为的真值都为T。 或非或非 设设P和和Q是两个命题公式，复合命题是两个命题公式，复合命题 称作命题称作命题P和和Q的的“或非或非”，当且仅当，当且仅当P和和Q的真值都为的真值都为F时，时， 的真值为的真值为T，否则，否则 的真值都为的真值都为F。回顾回顾51离散数学离散数学 表表 1-5.2 常用的蕴含式常用的蕴含式 PQ P（化简律）1 PQ Q2 P PQ（附加律）3 P PQ4 Q PQ5 (PQ） P6 (PQ） Q7 P(PQ
32、） Q（假言律）8 Q(PQ） P9 P(PQ） Q10 (PQ）(QR） PR（传递律）11 (PQ）(PR）(QR） R12 (PQ）(RS） (PR)(QS)13 (P Q)(Q R) (P R)1452离散数学离散数学PQ12345678910 1112 13 14 15 16TTTFTTFFTFTFTFTFTFTFTFTFFTFTTFFTFTTFFTTFFTTFFTTFTFFTFTFFTFFFTTFTFTTFTFTFPQ永真永假PQ非P非Q合取与非析取或非若P则Q逆条件双条件不可兼析取若Q则P逆条件由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了。由上述分析，除常量及命
33、题变元本身外，命题联结词一共有九个就够了。53离散数学离散数学回顾回顾 重言式重言式 给定一命题公式，若无论对分量作怎样的指派，给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为其对应的真值永为T，则称该命题公式为重言式或永真公式。，则称该命题公式为重言式或永真公式。 矛盾式矛盾式 给定一命题公式，若无论对分量作怎样的指派，给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为其对应的真值永为F，则称该命题公式为矛盾式或永假公式。，则称该命题公式为矛盾式或永假公式。 蕴含式蕴含式 当且仅当当且仅当PQ是一个重言式时，称是一个重言式时，称P蕴含蕴含Q，并，并记作记作P Q。 逆换式逆
34、换式 对对PQ来说，来说，QP称作它的逆换式。称作它的逆换式。 反换式反换式 对对PQ来说，来说， PQ称为它的反换式。称为它的反换式。 逆反式逆反式 对对PQ来说，来说， QP称为它的逆反式。称为它的逆反式。54离散数学离散数学 不可兼析取不可兼析取 设设P和和Q是两个命题公式，复合命题是两个命题公式，复合命题 称作称作P和和Q的不可兼析取。的不可兼析取。 的真值为的真值为T，当且仅当，当且仅当P与与Q的真值不同时为的真值不同时为T，否则，否则 的真值为的真值为F。 条件否定条件否定 设设P和和Q是两个命题公式，复合命题是两个命题公式，复合命题P Q 称作命题称作命题P和和Q的条件否定，的条
35、件否定，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。回顾回顾55离散数学
36、离散数学 表表 1-5.2 常用的蕴含式常用的蕴含式 PQ P（化简律）1 PQ Q2 P PQ（附加律）3 P PQ4 Q PQ5 (PQ） P6 (PQ） Q7 P(PQ） Q（假言律）8 Q(PQ） P9 P(PQ） Q10 (PQ）(QR） PR（传递律）11 (PQ）(PR）(QR） R12 (PQ）(RS） (PR)(QS)13 (P Q)(Q R) (P R)1456离散数学离散数学9个联结词：个联结词：否定否定 、合取、合取 、析取、析取 、条件、条件 、双、双条件条件 ；不可兼或不可兼或 、条件否定、条件否定 、与非、与非、或、或非非。57离散数学离散数学符号符号和和的区别与联系类似于的区别与联系类似于 和和的关系。的关系。区别：区别：是逻辑联结词，属于对象语言中的符号，是是逻辑联结词，属于对象语言中的符号，是公式中的符号；公式中的符号；不是联结词，属于元语言中的符号，表示两不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。个公式之间的关系，不是两公式中符号。58
